Set Theory/Naive Set Theory

In the late 19th century, when Cantor proved his theorem and mathematicians' understanding of infinity developed, set theory was not the rigorously axiomatised subject it is today. It relied upon woolly intuitions about what sets were and their relationship with their members. This lack of rigour led to several paradoxes.

In Naive Set Theory, something is a set if and only if it is a well-defined collection of objects. Sets count as objects. A member is anything contained in a set. Any two sets containing precisely the same members are the same set (Principle of Extensionality).

Russell's Paradox

One of the most celebrated paradoxes is Russell's. Bertrand Russell, the English philosopher and logician, discovered this paradox in 1901. It centres on the set containing all and only those sets that do not contain themselves. It is impossible to answer the question 'does this set contain itself?' without running into a contradiction. If it contains itself, it is by definition a set that does not contain itself - contradiction. If it does not contain itself, it is a set that does not contain itself and so should contain itself - contradiction. A parallel semantic paradox is the Barber's paradox. The Barber shaves everyone in town who does not shave himself and only those people. Does the Barber shave himself? If so, he is not someone who does not shave himself. If he does not, he should. In this case, the Barber's contract is inconsistent and so, by analogy, is the Naive Set Theory upon which Russell's paradox is constructed.

Cantor's Paradox

The explanation of this paradox is somewhat technical but brief and some readers may therefore prefer to return to it later.

A set A is a subset of another set B iff all the members of the A are members of the B. Hence, all sets are subsets of themselves. Also, the empty set, Ø or {}, the set containing no members, is a subset of any set, since all of its members are also members of any other set (since it has no members). A proper subset of a set is a subset that is not the set itself. The Powerset of a set is the set of all the subsets of that set. For example, the Powerset of the empty set is the set containing the empty set, {Ø}. Note that this set is different from the empty set: {Ø} has a member (Ø); Ø has none.

In 1873, Cantor proved that the Powerset of any set is larger than that set (Cantor's Theorem). This may seem obvious for finite sets, but the matter is less perspicuous when infinite sets are considered. For the time being, an infinite set will be said to be a set that has the same size as one of its proper subsets, and two sets are said to be the same size or equinumerous if and only if there exists a bijection between them (there is a unique member of the first for every member of the second and a unique member of the second for every member of the first). The set of natural numbers {1,2,3,...}, for example, is infinite. It has a proper subset {2,4,6,...}, the even numbers, but for every member of the set of natural numbers (i.e. for every natural number) there is a member of the set of even numbers and vice versa. This is because every natural number can be doubled, resulting in an even number (i.e. every natural number can be assigned some unique member of the set of even numbers) and every even number can be halved, assigning to it a unique member of the set of natural numbers. If two sets are equinumerous, there is a means of pairing each member of the first with the second such that every member of the first set appears in the first position of precisely one pair and every member of the second set appears in the second position of precisely one pair (ordered pairs are not subject to the principle of extensionality: <a,b> does not equal <c,d> if a does not equal c). So, for {1,2,3...} and {2,4,6...} there are the pairs <1,2>, <2,4>, <3,6>, etc. The set of all such pairs is a function (and a bijection).

Proof of Cantor's Theorem rests upon the notions thus described. The proof described here is reductio ad absurdum, i.e. the negation of what is to be proved is assumed true; the proof shows that such an assumption is inconsistent.

Suppose that a set A is equinumerous with its Powerset PA. Hence there is a bijection g from A to PA. Let g(x) be the member of PA (i.e. a subset of A) associated with a member x of A. Since A is assumed to be equinumerous with PA, for every member y of PA there is a member x of A such that y = g(x). Let B be the subset of A such that any member x of B is not a member of g(x) (remember g(x) will be some subset of A). Hence there is no x that is a member of A and g(x) = B. If there was, either it would be a member of B or not. If x was a member of B, it would be a member of g(x) and so would not be a member of B - contradiction. If it was not, it would not be a member of g(x) and so would be a member of B - contradiction (note the similarity with Russell's paradox used to show this contradiction). However, B is a member of PA (since B is a subset of A) and so there should be some x such that g(x) = B. This contradiction completes the proof. For any set, there is always some subset that cannot be assigned uniquely one of the members of that set.

The paradox follows as an extension of the theorem. Consider the set containing everything, all sets, trees, people, planets, stalagmites, numbers, calculators and so on. According to the theorem, the Powerset of this set is larger than it. However, if this is so, the set of everything must have missed something out, since there is a set which is larger than it and so contains something else besides.

Richard's and Berry's Paradoxes

Consider the set containing all natural numbers that are definable in English in fewer than twenty syllables. It will contain twenty-six (only three syllables), the two-millionth prime number (only seven syllables) and ten raised to the ten raised to the ten raised to the ten raised to the ten plus fourteen (nineteen syllables). Since there are only a finite number of syllables and a definition must be finite in length, this set must be finite in size. It will be a proper subset of the set containing all arrangements of nineteen or fewer syllables; in particular, it is the set containing those arrangements that define a natural number. Since this set has only a finite number of members, it must have a largest member (but observe that infinite sets need not, e.g. the set of natural numbers).

Consider the number defined by: the least number not definable in English in twenty syllables. This number is the smallest number not in the set; yet it is definable in fewer than twenty syllables, for it has just been defined in eighteen! This is Berry's paradox, proposed by Berry in 1906 as a simplified version of Richard's paradox, which is as below.

Consider all the numbers between 0 and 1 that can be designated in a finite number of words. For example, 0.33333333... is designated by 'a third'. 'The ratio between the lengths of the side and the diagonal of a square', is another example. Arranging all such numbers lexicographically shows that it comprises a denumerable set. Listing all such numbers in some order is hence possible. However, there is a number p that differs in its kth place to every kth number in the listing. Hence it appears nowhere in the listing, yet it should, for it has just been described in a finite number of words.

Richard's and Berry's paradoxes arise through sloppy use of terms such as definability and designatability and the inclusion of self-reference. No such carelessness is possible in Axiomatic Set Theory.