Russell's Paradox in Frege's System

Russel had told Frege his paradox. In Frege's system, the paradox has a different formulation. Frege defined a concept as a function that has a truth-value. Frege used the notion of the extension of a concept. Frege did not define extensions, but used axioms to govern them. The extension of a concept can be understood as the mapping in mathematics, which is considered as the ordered pairs of arguments and value of the function. That is to say, it tells us the arguements for the function having the True as the value, and also the arguments for it having the False as the value. Let us designate the extension of a concept F as εF. One of the famous axioms in Frege's system is the Basic Law V:

εF = εG if and only if ∀x[F(x) = G(x)].

The equality in the left-hand side means the concepts F and G have the same extension (as an object), while the equality in the right-hand side means F(x) and G(x) have the same truth values for all arguments x. Let us consider a concept H(x) defined by

∃G[x = εG ∧ ¬G(x)]

(there exists G such that x = εG and not G(x)). Then H(εH) (is true) if and only if ∃G[εH = εG ∧ ¬G(εH)]. If ∃G[εH = εG ∧ ¬G(εH)], it follows from Basic Law V that ¬H(εH). On the other hand, it is clear that if ¬H(εH), then ∃G[εH = εG ∧ ¬G(εH)] (where G is taken to be H) so that H(εH). The latter implication (without Basic Law V) shows that the definition of H may be doubtful, so that the possibilities will be:

• ¬H(εH) is false, while (it follows from the former implication that) it is the problem of the Basic Law V;
• H(εH) is meaningless (either εH is not in the range of significance of H, or H(x) is meaningless for any x).

First of all, we may say two concepts to be extensionally equal if they have the same range of significance, and have the same values on the range. At least a concept is extensionally equal to itself. Then the next step will be the formulation of (the existence of) such an object called extension (before we can tell whether it is in the range of significance of some concept) such that the extensions of two concepts are the same if and only if the concepts are extensionally equal.

Although the existence of the extension of a concept (as an object) is taken for granted in an axiom in Frege's system, we don't know much about this object, e.g., how we can check if it is in the range of significance of another concept. Let us go back to the concept H above. How can we check if H(εH) is significant? First and foremost, we should have made sure what we mean by the range of significance of a concept. As a concept is a function that has a truth-value, the range of significance of a concept should be the set of all objects such that taking these objects as argumentsthe concept has values (either True or False). Can we say H(εH) is true or false? Can we check it against the definition of H? Can we check the case that G is taken to be H? We cannot, not only because we don't know what ¬G(εH) is when G is taken to be H, but also because we don't know if G can be taken to be H - does such an H exist anyway?

Russell's Paradox and Cantor's Theorem

Russell's paradox asks whether the "set" R defined by

R = {x: x is not an element of x}

is an element of itself. As it was mentioned in a previous article, Russell's solution to his paradox was his theory of types. He arranged all propositions into a hierarchy. The lowest level of the hierarchy consisted of propositions about individuals, not sets. The next lowest level consisted of propositions about sets of individuals. The next lowest level consisted of propositions about sets of sets of individuals, and so on. Thereby the definition (one of these "valid" propositions) of any set only referred to objects of the same "type" (at the same level).

It seems that Russell discovered the paradox as a result of his analysis on Cantor's theorem on the cardinality (i.e. the "number of elements") of the power set (i.e. the set of all subsets) of a set. In the following discussion, let P(A) denote the power set of a set A. Furthermore, some common axioms of the set theory are assumed.

Cantor considered if there was uncountable set. A infinte set is countable if it can be put into one-to-one correspondence with the set ℕ of all natural numbers. For example the set of all even numbers is countable (considering the mapping that maps a natural number n to 2n), so that the set of all even number has the same cardinality (the same "number of elements") as ℕ. A infinite set is said to be uncountable if it is not countable. Cantor considered the set of all infinite sequences of elements that were either 0 or 1. For instance (0, 0, 0, ...) is one of these sequences. Clearly, it is infinite. Cantor used his diagonal argument to prove that this set is uncountable. That is, any mapping from ℕ to this set cannot be a one-to-one correspondence. Let this set be denoted by S. Consider any mapping f: ℕ → S. Then for each natural number n, we have a sequence f(n), and we denote it by (f(n)₀, f(n)₁, f(n)₂, ...). Along the diagonal, we then have a sequence (f(0)₀, f(1)₁, f(2)₂, ...). Cantor obtained a sequence (a₀, a₁, a₂, ...) in S such that a_n ≠ f(n)_n for each natural number n (if f(n)_n is 0, then a_n is taken to be 1). Thereby this sequence is different from f(n) for every natural number n. Hence, S is uncountable.

With this argument, Cantor had actually proved that P(ℕ), the power set of ℕ, was uncountable. In fact the set S is in one-to-one correspondence with P(ℕ) - for a sequence (a₀, a₁, a₂, ...) in S, consider the subset A of ℕ such that A contains n if (and only if) a_n = 1. Thus we can "translate" the diagonal argument as follows. Consider any f: ℕ → P(ℕ). Then for each natural number n, we have a set f(n) of natural numbers, so that we can ask if f(n) contains a given natural number m. Thus we can define a set A such that A contains a natural number n if and only if f(n) does not contains n. That is,

A = {n ∈ ℕ: n ∉ f(n)}.

Then for any natural number n, A ≠ f(n). That is, f is not surjective. Hence, P(ℕ) is uncountable.

It is clear that in the above argument ℕ can be replaced by any non-empty set, and we can conclude that there is no surjection from a set to its power set.

It follows immediately that there does not exist a set of all sets. Otherwise, if U was a set of all sets, then P(U) would be a subset of U, and we would have a trivial surjection f: U → P(U) such that f(x) = x for all x belonging to P(U), and f(y) was any subset of U, such as the empty set, for all y not belonging to P(U). It then leads to a contradiction that for all x ∈ U, f(x) ≠ A, where

A = {x ∈ U: x ∉ x}.

It is in fact Russell's paradox.

The General Form in Tractatus

At 4.442 of Tractatus, Wittgenstein introduces a propositional sign to denote the truth table. For example, if p and q are propositions, then (TTFT)(p, q), or simply (TT-T)(p, q), denotes the proposition with truth table:

p	q	p→q
T	T	T
F	T	T
T	F	F
F	F	T

It is in fact the proposition p→q. Here the order or the truth-possibilities (of p and q) in a scheme is fixed once and for all by a combinatory rule (4.442). Wittgenstein does not state the order explicitly, while the sequences of the truth-possibilities of no more than three propositions (terms of the truth-functions) are shown at 4.31. The order is not stated explicitly because it is really not important in the discussion in Tractatus, except that the truth-possibilities are all F in the last row in the truth table. Thus, (---T)(p,q) is the same as p↓q, where ↓ is the Peirce arrow, and has the following truth table:

p	q	p↓q
T	T	F
F	T	F
T	F	F
F	F	T

For propositions p, q, r, ..., a variable ξ having them as its values (the terms of the truth-function) is used, and the sign becomes (-...-T)(ξ, ...) at 5.5. At 5.501 and 5.502, the sign is further simplified to (-...-T)(`ξ) and N(`ξ) respectively, while the order of the terms (the propositions) is indifferent. The sign is called (5.5) the negation of the propositions. Thus (5.51), if ξ has only one value p, then N(`ξ) is ¬p (not p); if ξ has two values p and q, then N(`ξ) is ¬p∧¬q (neither p nor q). Furthermore (5.52), if ξ has as its values all the values of a function f(x) for all values of x, then N(`ξ) is ¬∃xf(x).

The importance of the Peirce arrow in logic (and therefore the importance of the operation N in Tractatus) is that any logical operation can be expressed in terms of it (completeness). For example,

• ¬p is equivalent to p↓p;


• p∧q is equivalent to (p↓p)↓(q↓q);


• p∨q is equivalent to (p↓q)↓(p↓q);


• p→q is equivalent to ((p↓q)↓q)↓((p↓q)↓q).

A truth-function can therefore be obtained by successive negation of the propositions. In Wittgenstein's notation, for example, if ξ has values p and q, then N( `ξ) is p↓q. Furthermore, if ξ has value p↓q, then N(`ξ) is p∨q. Any truth-function and any proposition can be obtained by successive application of such operations. Thereby for a series of successive application of an operation O' on a variable a

a, O'a, O'O'a, ...,

Wittgenstein introduces the sign for the general form at 5.2522:

[a, x, O'x]

where the first term of the bracketed expression is the beginning of the series of forms, the second is the form of a term x arbitrarily selected from the series, and the third is the form of the term that immediately follows x in the series. For example if x is the third term O'O'a of the series, then O'x is the fourth term O'O'O'a. Nevertheless, while each of these variables a and x only has one values, the situation of truth-functions or operations on propositions is a bit more complicated, at least in the sense of mathematical rigorousness. Let us consider an expression

[`a, `x, O'`x]

where both a and x have more than one value, and O'`x is a family of operations of different numbers of variables (for a fixed number n, there is a well-defined operation of n variables in this family). The words in Russell's introduction to Tractatus can be used for the explanation of this expression. The symbol means whatever can be obtained by taking any selection of values of a, taking the result of the operation of O' `x on them, then taking any selection of the set of values now obtained, together with any of the originals - and so on indefinitely. Obviously, we cannot interpret it simply with a series as in 5.2522. We cannot regard Wittgenstein's bracket as a symbol in Mathematics or Mathematical Logic.

Hence in Wittgenstein's notation, the general form of truth-function and of proposition (6 of Tractatus) is given by:

[`p, `ξ, N(`ξ)]

where p has all elementary propositions (or just the elementary propositions that appear in the expression) as its values, and ξ has some selection of propositions obtained in the previous operations (together with any of the original elementary propositions) as its values, and N( `ξ) is the negation of all the propositional values of ξ.

"Plato loves Socrates" says that Plato loves Socrates

To analyse those forms of propositions in psychology such as 'A believes that p is the case' and 'A has the thought p', Wittgenstein says at 5.542 of Tractatus that:

It is clear, however, that 'A believes that p', 'A has the thought p', and 'A says p' are of the form '"p" says p': and this does not involve a correlation of a fact with an object, but rather the correlation of facts by means of the correlation of their objects.

Wittgenstein points exactly against the superficial thought of such forms of propositions - it looks as if the proposition p stood in some kind of relation to an object A (5.541).

First of all, how to understand / explain '"p" says p'? Let us consider a proposition of the form '"q" says p':

"Wittgenstein was taller than Russell" says that Socrates was fatter than Plato.

Everyone, as long as he / she understands this English sentence, can tell immediately without any thoughtful logical analysis that it is a false statement. Furthermore, he / she can also tell immediately that the following proposition is true (no matter whether it is the case that Wittgenstein was really taller than Russell):

"Wittgenstein was taller than Russell" says that Russell was shorter than Wittgenstein.

As Wittgenstein says at 3.14, propositional sign (such as "q") is a fact. Logically, to justify if such propositions of the form '"q" says p' is true, we can examine whether it is the case that q if and only if p, which is just a truth-operation of the p and q as Wittgenstein asserts at 5.54. Besides, to perceive a complex means to perceive that its constituents are related to one another in such and such a way (5.5423). Of course not all propositions of the form '"q" says p' can be understood in this way. Clearly, the following statement is not true:

"If it is raining, then it is raining" says that if it is hot, then it is hot.

Although it is of the form '"q" says p', where q if and only if p, both p and q are in fact tautologies. As Wittgenstein says at 4.461, tautologies say nothing. In the first place, "q" says nothing, so that we cannot even assert the following:

"If it is raining, then it is raining" says that if it is raining, then it is raining.

We cannot assert the following statement either:

"Wattginstein was taller than Sucrotis" says that Sucrotis was shorter than Wattginstein.

As long as the symbols "Wattginstein" and "Sucrotis" do not signify anything, "Wattginstein was taller than Sucrotis" is nonsensical. We cannot compare nonsensical propositions in the first place.

Then how to understand / explain / justify 'A says p'? We have to examine what A said on the objects of the fact p (if A has said something about them) to determine the correlation of this fact (what A said) and the fact p, as Wittgenstein asserts at 5.542. Logically, "p" should say something in the first place, and we compare the fact p with each of the facts represented by the finite set of sensical statements of A. A composite soul would no longer be a soul (5.5421). What about if A says nonsense? We can just tell that A says nonsense, but we cannot have a statement like:

A says that Sucrotis Wattginstein was tham shorter.

It is nothing but just another piece of nonsense! Hence, Wittgenstein says at 5.5422 that

The correct explanation of the form of the proposition, 'A makes the judgement p', must show that it is impossible for a judgement to be a piece of nonsense.

Thus, if I tell you, "I make the judgement that Sucrotis was shorter than Wattginstein," and if I do not tell you a piece of nonsense, it means that I really know two guys called Sucrotis and Wattginstein, and maybe Sucrotis was in fact taller than Wattginstein so that my judgement may be wrong, but at least my judgement is not a piece of nonsense. Besides, propositions occur in such propositions still as bases of truth-operations as Wittgenstein asserts at 5.54.

Nevertheless, Russell says in his introduction to Tractatus that

This problem is simply one of a relation of two facts, namely, the relation between the series of words used by the believer and the fact which makes these words true or false.

But on the other hand, he concludes that the proposition does not occur at all in the same sense in which it occurs in a truth-function. I think that is why Wittgenstein believed that Russell did not really understand the Tractatus.

Anyway, is the heading "proposition" a good example? Is "Plato loves Socrates" really a sensical proposition (it is an example in Russell's introduction to Tractatus)? Is "love" what we cannot speak about? Must we pass "love" over in silence (as the conclusion at the end of Tractatus)? Er... I have such a thought, but my wife doesn't think so!

Identity in Tractatus

In Tractatus, identity of object Wittgenstein expresses by identity of sign, and not by using a sign for identity (5.53). He speaks roughly that (5.5303):

To say of two things that they are identical is nonsense, and to say of one thing that it is identical with itself is to say nothing at all.

Then he also says at 5.535 that Russell's "Axiom of Infinity", which says that there are infinitely many objects (at 4.1272, Wittgenstein says one even cannot say so), would express itself in language through the existence of infinitely many names with different meanings. In fact, as Russell says in his introduction to Tractatus, the rejection of identity removes one method of speaking of the totality of things.

To Wittgenstein, tautologies also say nothing at all (4.461), although they are not nonsensical (4.46211). Of course, everyone absolutely agrees that tautologies like "if it is raining, then it is raining" really say nothing at all. However, the "problem" of human beings (or of the world) is that the world is so complicated that we cannot determine many tautologies at first sight.

Identity is a relation in Mathematics. There are occasions at which one object may have more than one name / sign - signs are used to refer to the descriptions of some objects, and eventually it is found (proved) that these descriptions have the same reference. In the real world, we might call the murderer of some case of murder X, and eventually we found that he was the man called A: A = X. The introduction of the identity-sign simplifies our deduction.

Wittgenstein's Tractatus Logico-Philosophicus & Russell's Paradox

"No proposition can make a statement about itself, because a propositional sign cannot be contained in itself," Wittgenstein says at 3.332 of Tractatus Logico-Philosophicus (the decimal figures hereafter refers to the numbers in the Tractatus). He also "disposes" Russell's paradox at 3.333.

Let us consider the following proposition p:

This statement is false.

Clearly, if p is true, then from the content of p, p is false. On the contrary, if p is false, then what p says is true, so that p is true. It is the liar paradox.

At first glance, the problem of the liar paradox is due to self-reference of the proposition. Let us consider a more general version of the paradox. Let P and Q denote the following proposition respectively:

Q is true; P is false.

We see that the paradoxes arise from the actually meaningless definitions of the objects (that is, the propositions) concerned. To define an object, we must use already well-defined terms. A self-referential proposition is meaningless because it is defined by itself. For the last version of the paradox, both P and Q are defined by what are being defined! Let us return to the self-referential liar paradox and rewrite p as

p is false.

Consider a function F(q):

q is false.

Then F(p) is the proposition:

p is false.

Besides, F(F(p)) is the proposition:

F(p) is false.

Here, as mentioned in 3.333, p, F(p) and F(F(p)) are in fact different propositions, and they should not be signified by the same sign such as p (as what liar paradox does), as states in 3.325:

In order to avoid such errors we must make use of a sign-language that excludes them by not using the same sign for different symbols and by not using in a superficially similar way signs that have different modes of signification: that is to say, a sign-language that is governed by logical grammar--by logical syntax. (The conceptual notation of Frege and Russell is such a language, though, it is true, it fails to exclude all mistakes.)

Wittgenstein does not mention the liar paradox but that of Russell. Russell's paradox is a set-theoretical paradox that asks whether the set R defined by

R = {x: x is not an element of x}

is an element of itself. If we use f(x) to denote the proposition

x is not an element of x,

then

R = {x: f(x)}.

However, is the definition of R meaningful? If it was, it had to be able to tell if any given object was an element of R. In particular, could it tell if the object R (if it could be defined) itself was an element? In other words, is f(R) true (or false)? Actually, if R was well-defined, f(R) could be rewritten as f({x: f(x)}), which was also a meaningless self-referential proposition (covered by the definition)!

Russell's solution to his paradox was his theory of types. He arranged all propositions into a hierarchy. The lowest level of the hierarchy consisted of propositions about individuals, not sets. The next lowest level consisted of propositions about sets of individuals. The next lowest level consisted of propositions about sets of sets of individuals, and so on. Thereby the definition (one of these "valid" propositions) of any set only referred to objects of the same "type" (at the same level).

It seems that Russell's theory of types is just an ad hoc solution to the problem of self-reference of his paradox (3.332). However, we see that the rules in his theory are not just syntactic, but semantic - he had to mention the meaning of signs when establishing the rules for them (3.331). On the other hand, Wittgenstein provided a syntactic solution to these paradoxes. More precisely, Wittgenstein did not provide any solution (because a solution is more or less ad hoc), but it is just that there is no such paradox in the system of his Tractatus.