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.