next up previous
Next: April 4, 2000 Up: Lecture Notes Previous: Solution to (part of)

April 3, 2000

Set Theory

We are going to develop enough set theory to provide us with basic
machinery for mathematics.  We will start with an unusual set of axioms
which I chose because of their elegance; we will prove from these a set
of theorems (which I will formally list) which could be taken as axioms
in a more usual development.

Informal Discussion of Set Theory

It is important to realize that a set is not simply a ``whole'' of which
its elements are ``parts''.  This is best seen by considering the difference
between 1 and {1} (the number 1 and the set with one element) or even
better the difference between {{1,2}} and its element {1,2}  (here the
difference between the two objects is clear:  one of them has one element
and one of them has two!)

Notation (Membership Relation and Restricted Quantifiers)

We write x E y for ``x is an element of y''.  This is now an ordinary
predicate of our language (which it was not when we introduced set notation
above).

We write (Ax E a)(Px) to mean (Ax.(x E a -> Px)) and (Ex E a)(Px) to
mean (Ex.(x E a & Px)).  We'll talk more about this notation later.

An Axiom

We adopt the following axiom

Axiom of Extensionality:  (Aab.(a=b <-> (Ax.(x E a <-> x E b))))

This says that two objects are equal iff they have the same elements.
If one's universe includes some objects which are not sets, one would
need to qualify this:

Let {} be the empty set.

Define Class(x) as (x = {} | (Ey.y E x)); something is a class (for
now a synonym of ``set'') if it is the empty set or has elements.

The axiom can be restated as (Aab.(Class(a) & Class(b))->(a=b <-> (Ax.(x E
a <-> x E b))))

Two objects which are not classes can be unequal while having the same
elements (none!)

Another Axiom?

In our informal encounters with sets before this, we have seen sets introduced
in three ways.

1.  By listing elements: {1,2,3} This works only for finite sets of
manageable size.

2.  By properties of their elements:  {x : x is an even natural number}
or {x : x was listed in the 1900 US Census}.  Sets listed in this way
are usually infinite (the first example) or unmanageably large (the
second example).  The first case falls under this case as well:
{1,2,3} = {x : x=1 | x=2 | x = 3}

3.  By cheating:  N = {0,1,2,...}

We will avoid alternative 3 when speaking formally.  As we have seen,
alternative 1 falls under alternative 2.

It seems natural to propose this axiom to say what sets there are:

Axiom of Comprehension: For every property P, there is a set {x : Px}
such that for all y, y E {x : Px} iff Py.

Russell's Paradox

Unfortunately, this axiom cannot be true.

Suppose the Axiom of Comprehension were true.  Then there would be a
set R = {x : ~(x E x)} such that for all y, y E R iff ~(y E y).  But
then R E R iff ~(R E R).  This is impossible!

Our Official Axioms

So we must axiomatize set theory more carefully.

1.  Axiom of Extensionality (from above)

We distinguish between two kinds of collections, classes and sets.  We
use the same notation x E y for membership in sets or classes, and we
use Set(x) to abbreviate ``x is a set''.  Sets are a special kind of
class.

2.  Axiom of Class Existence

For any property P, the class {x : Set(x) & Px} exists (and may or may
not be a set).

For example the class {x : Set(x) & ~(x E x)} exists.  Call it R.  We
have R E R iff Set(R) & ~(R E R).  This is clearly impossible.  But
there is no contradiction: we can have ~(R E R) as long as we
stipulate ~Set(R).  The class of all sets which are not members of
themselves is a class, but not a set.

Classes allow us to talk in a fairly free-wheeling way about arbitrary
collections of sets proper without risk of paradox.

3.  Axiom of Elements

(Axy. (Set(x) & y E x) -> Set(y)

Elements of sets are sets.

4.  Axiom of Subsets

We define x c= y (x is a subclass of y) as (Az. z E x -> x E y).  If set
have ``parts'' they are their subsets rather than their elements!  We use
``subset'' when y is a set.

The axiom is 

(Axy. (Set(x) & y c= x) -> Set(y)

Subclasses of sets are sets.

5.  Axiom of Set Existence

This is a rather tricky axiom.  For now I will content myself with
stating it; we may later talk about motivation.

If Px is a sentence in which the predicate Set is not mentioned and in
which all free variables or constants other than x represent sets (I
did not make this essential stipulation in class!) and if the
statement (Ax.Px -> Set(x)) is true (all objects with property P are
sets) then {x : Px} exists.

The axiom is best understood to begin with by seeing it in action.

Theorem 1:  {} is a set.

The class {} = {x : x=/=x} exists by class existence.  We can see further
that it is a set because ``x=/=x'' does not mention Set, contains no free
variable other than x, and all elements of the empty class are sets...

Theorem 2:  For any set a, {a} is a set.

The predicate ``x = a'' does not mention Set, the free variable a is a
set, and the only object with the property is a, which is a set.

Theorem 3:  For any sets a and b, the union a U b = {x : x=a | x=b} is
a set.

The predicate ``x=a | x=b'' does not mention Set, has free variables a
and b which stand for sets, and is true of objects x which are either
elements of the set a or elements of the set b, and in either case are
sets by axiom 3.

Theorems 1-3 allow us to build all finite sets of sets by listing:
{a,b,c} = {a} U {b} U {c}, for example (this only works if a, b, c are
sets!)

Theorem 4:  For any sets a and b, the intersection a ^ b = {x : x=a & x=b} is
a set.

The proof is basically the same as the proof of theorem 3.

This is where we stopped on April 3.



Randall Holmes
2000-05-05