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.