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.