Lectures on Constructive Set Theory

(Padua, Spring 1998)

Lecture 4: 13th May (16.30 - 18.00)

See Lecture 3

The notion of set: preliminary ideas

Here are some possible requirements on any notion of set.
1.
Each set is an object (of some type).
2.
Each set s determines, firstly a type, and secondly a class on that type, the class of its elements. We write that s is a set over A if A is the type it determines and if c:A then we write c:s if the object c is in the class determined by s.
3.
Sets, determining the same type, are equal if they have the same elements; i.e. if their classes of elements are extensionally equal.
We shall take these as necessary requirements on any notion of set.

Set Theories with a universal type of sets

Naive Set Theory

This theory adopts the following additional principles.
Universal Type Principle
All sets are objects of a type V. Moreover all sets are over the same type V.
Frege's Principle
Every class on V is extensionally equal to the class of elements of some set.
We will call the set of elements of a class, given in Frege's Principle, the extension of the class. It is natural to identify classes on V with their extensions.

Naive Set Theory was implicitly adopted by Frege as part of the basis for his scheme to reduce mathematics to logic. But Russell found his famous paradox.

Russell's Paradox
Let R={x:V | x is a set and not x:x}. This is a class on V that we identify with its extension. So we take R to be a set in V and ask the question: Is R:R ?

If R:R then R satisfies the predicate `x is a set and not x:x'. In particular not R:R. So the assumption that R:R leads to a contradiction. It follows that not R:R so that [R is a set and not R:R]; i.e. R does satisfy the predicate `x is a set and not x:x'. So R:R and now we have a contradiction.

Cantor's set Theory

Cantor never considered any typing principle. But if we try to capture his conception of set in the framework we wish to adopt, which does assume the typing principle, then we can do it with the following principles.
Universal Type Principle
All sets are objects of a type V. Moreover all sets are over the same type V.
Cantor's Principle
All mathematical objects can be represented as objects of type V, provided it is consistent to do so. In particular, for any collection into a whole of objects of type V there is a set of those objects.
It seems that Cantor was well aware of the potential for paradox in his set theory, well before Russell found his Paradox. The evidence for this can be found in a letter to Dedekind dated 1896(?), where Cantor writes about inconsistent sets. A paradox that he was probably aware of involves the theory of cardinal numbers and has come to be called Cantor's Paradox. This is an application of Cantor's Theorem; i.e. his result that card(Pow(A)) > card(A) for any set A, where Pow(A) is the set of all subsets of A, called the powerset of A. Now if we suppose that there is a set, having all the objects of V as elements, which we may as well call the set V, then its powerset Pow(V) will have to be a subset of V and hence card(Pow(V)) is less than or equal to card(V), contradicting Cantor's theorem. There is some evidence to suggest that Cantor was probably aware of this kind of argument already in the 1880s, but this opinion is not generally accepted. Cantor was probably also aware of the so-called Burali-Forti paradox concerning ordinal numbers. The idea for this paradox was presented in Burali-Forti(1887), although Burali-Forti does not seem to have considered it a paradox about sets. If we assume that the ordinal numbers form a set then it is a well-ordered set, whose order type will itself be an ordinal number which would have to be strictly larger than all ordinal numbers, including itself. But this is impossible.

The Axiom of Choice

Versions of this axiom were implicitly used before the axiom was first mentioned by Peano, Bettazzi and Levi at the turn of the century and explicitly formulated by Zermelo, in Zermelo(1904). In particular Cantor implicitly used it in his proof of the well-ordering theorem, that every set can be well-ordered.

One version of the axiom, used by Zermelo in Zermelo(1908), states that if X is a set of non-empty pairwise disjoint sets then there is a set C that intersects each element of X in exactly one element.

The axiom of choice has been criticised for its non-constructivity. In the above version it postulates the existence of the set C but gives no indication how the set C may be defined.


Last part: Cantor's invention of ordinal numbers.

.
.
.

See Lecture 5

Draft. Last Revised: 18th May, 1998.