I'm going to start by recapitulating the formal content of yesterday's lecture (which included an intuitive and motivational component which may have been hard to sort out). I will also correct an omission in the statement of axiom 5. We introduce the notation x E y for ``x is an element of y''. We define (Ax E y.Px) as (Ax.(x E y -> Px)). We define (Ex E y.Px) as (Ex.(x E y & Px)). In both of these notations, y should not appear free in Px. We refer to general elements of our universe as ``classes'' (``sets'' will be reserved for a specific kind of class). We adopt the Axiom of Extensionality: (Axy.(x = y <-> (Az.z E x <-> z E y))) In words, ``Classes are equal iff they have the same elements''. A consequence of the way that we have phrased this axiom is that everything in our world is a class. We define {x : Px} as the class A such that (Ay.(y E A <-> Py)). If there is no such class, we say ``{x : Px} does not exist''. We proved the following theorem: Russell's Paradox: {x : ~(x E x)} does not exist. So it is necessary to restrict what properties can be used to define sets. We propose some axioms for this purpose. First, we introduce a new predicate Set(x), read ``x is a set''. Axiom 2 (Class Existence): For any property P, {x : Set(x) & Px} exists. Less technically, the collection of sets defined by any property exists (but is not necessarily a set). We considered the following Example: {x : Set(x) & ~(x E x)} exists by Axiom 2. This is the class of all sets which are not members of themselves. Call it R for short. We see that R E R <-> Set(R) & ~(R E R). This shows that Set(R) is impossible; this class is not a set. Axiom 3 (Elements): (Set(x) & y E x) -> Set(y) In words, any element of a set is a set. Definition: x c= y is defined as (Az.(z E x -> z E y)) We read x c= y as ``x is a subclass of y'' or as ``x is a subset of y'' when x is a set. Axiom 4 (Subsets): (Set(x) & y c= x) -> Set(y) In words, any subclass of a set is a set. Axiom 5 (Set Existence): {x : Px} exists and is a set if the following conditions hold: 1. Px does not mention the Set predicate, and 2. any free variable or constant other than x mentioned in Px represents a set (this was omitted yesterday) 3. (Ax.Px -> Set(x)); i.e., anything with property P is a set. Notice that this is not an iff: it is possible for {x : Px} to exist and be a set for some other conditions Px. Axiom 5 is rather tricky; the best way to see how it works is to use it. Positive Results (axioms of standard set theory): Theorem 1: {}, the empty class, is a set. The formula ``x =/= x'' satisfies conditions 1-3. The trickiest part here is that all elements of the empty class are sets -- this is true vacuously. Theorem 2: {A}, the singleton of A, is a set if A is a set. The formula ``x E A'' satisfies conditions 1-3 as long as the free variable A represents a set. Theorem 3: A U B, the union of A and B, is a set if A and B are sets. The formula ``x E A | x E B'' satisfies conditions 1-2 as long as A and B are sets. We see that ((x E A | x E B) -> Set(x)) by axiom 3 (elements of sets are sets). Corollary: sets defined by ``listing'' exist. For example, {A , B, C} = {A} U {B} U {C} is a set if A, B, and C are sets. Theorem 4: {x E A : Px}, the set of x in A such that Px, is a set for _any_ property P if A is a set. We define {x E A : Px} as {x : x E A & Px}. If x E A, we have Set(x) by axiom 3. Thus {x : x E A & Px} exists by axiom 2 (any class of sets exists). {x : x E A & Px} is a set by axiom 4 (any subclass of the set A is a set). Notice that this does not use axiom 5, and that P can be any property at all. Corollary: For any sets A and B, the intersection A ^ B and the relative complement A - B are sets. A ^ B = {x E A : x E B} = {x : x E A & x E B} A - B = {x E A : ~(x E B)} = {x : x E A & ~(x E B)} Theorem 5: P(A), the power set of A, is a set if A is a set. P(A) is the set of all subsets of A: {x : x c= A}. The formula x c= A does not mention Set (one can expand the definition of c= to see this, and so satisfies conditions 1-2 as long as A is a set. It satisfies condition 3 by axiom 4 (any subclass of the set A is a set) so is a set by axiom 5. Theorem 5 is a very strong assertion; think about infinite sets A. Theorem 6: U(A), the set union of A, is a set if A is a set. U(A) is the set of all elements of elements of A: U(A) = {x : (Ey.(x E y & y E A))}. The formula ``(Ey.(x E y & y E A))'' satsfies conditions 1-2 and satisfies condition 3 by two applications of axiom 3: an element of an element of a set A will be a set. U(A) is a device for taking the union of a possibly infinite collection of sets. Definition: we define 0 as {} and x' as x U {x} for any set. This means that we define 0 as {}, 1 as 0 U {0} = {0}, 2 as 1 U {1} = {0,1}, 3 as 2 U {2} = {0,1,2}, and so forth. No profound philosophical significance is claimed for this definition! Theorem 7: N, the set of ``natural numbers'', exists. The hardest part of this is coming up with the definition: N = {x : (Ac.(c E 0 & (Ay.y E c -> y' E c)) -> x E c)} The formula ``(Ac.(c E 0 & (Ay.y E c -> y' E c))->x E c)'' satisfies conditions 1 and 2, though it is odd that it contains a quantifier over all classes! To see that it satisfies condition 3, observe that the class of all sets contains 0 (by Theorem 1) and contains y' if it contains y (by Theorems 2 and 3), so any x that satisfies ``(Ac.(c E 0 & (Ay.y E c -> y' E c))->x E c)'' will belong to the class of all sets (as a particular choice for c) which establishes Theorem 7. The secret of the definition is in ``(c E 0 & (Ay.y E c -> y' E c)''; if this formula is true of a class c, we can (informally) prove that all natural numbers belong to it by mathematical induction: we call such classes c ``inductive classes''. All such classes c contain N (intuitively speaking) and N is itself such a class, so a natural number is an object which belongs to all inductive classes. Then the trick of the proof is to notice that the class V of all sets (which, as we will see, is not a set) is an inductive class, and so all elements of N are sets. Negative Results: Definition: We define V as {x : Set(x)}; V is the class of all sets. Theorem 8: V is not a set. If V were a set, we would be able to apply Theorem 4 to show that {x E V : ~(x E X)} = {x : Set(x) & ~(x E X)} is a set, and we already know that this is not a set. Theorem 9: The complement V - A = {x: Set(x) & ~(x E A)} of a set A is not a set. If the complement of A were a set, then its union with A would be a set by Theorem 3, and so V would be a set, which we know is not the case. Theorem 10: Not all elements of classes are sets. In some treatments with both sets and classes, the classes are exactly the arbitrary collections of sets (which we cannot safely assume are sets) which means that non-sets are not elements of classes (and so not elements of anything). We show that this cannot be true in this system. Suppose all elements of classes were sets. Then the class {x : (Ey.x E y)} would exist as a class by axiom 2 (everything satisfying the defining property would be a set), and as a set by axiom 5 ((Ey.yEx) certainly satisfies conditions 1 and 2 and would satisfy condition 3 by our hypothesis). By Theorem 2, every set x satisfies (Ey.x E y)} (every set belongs to its singleton) so the class {x : (Ey.x E y)} would be the class of all sets V, and we know this cannot be a set. The Story Behind This Here's a story to explain axioms 1-5. We build the world of sets by some process of construction in which we choose collections of things already constructed and declare them sets. For ``class'', read ``collection we might construct''; for ``set'' read ``collection we will actually construct''. Axiom 2 says that any collection of things we actually will construct is something we might have constructed (but not necessarily something we will construct); since we have the power to choose arbitrary collections of things we have already constructed, we believe this. Axiom 3 says that any collection we will construct has elements we will construct (would have constructed already!) Axiom 4 says that any subclass of a collection we will construct will also get constructed (this is a strong assertion!) Axiom 5, as always, is trickiest. It specifies conditions under which a property defines a set: 1. Any object mentioned in the definition of the property has already been constructed. (condition 2 in ax. 5) 2. The property of ``actually being constructed'' is not mentioned (because we aren't done with the construction process yet -- we don't actually know what sets will be constructed). (condition 1 in ax. 5) 3. The property is only true of objects we will actually construct. (condition 3 of ax. 5) Relation to Standard Set Theory It is known that the system with axioms 1-5 (plus Extensionality and two technical axioms of Foundation and Choice) is equivalent to the standard set theory ZFC in everything it says about sets (ZFC does not have classes). The theory with axiom 1-5 is called ``Ackermann set theory'' after the same German mathematician who gave his name to ``Ackermann's function''. Theorems 1-7 are an axiom set (again, with the exception of Extensionality, Foundation and Choice) for an important subset of ZFC called ``Zermelo set theory'', which is enough of a foundation for most of mathematics. After this, we will almost always rely on these statements as if they were axioms, and seldom appeal to our official axioms. On April 4, we covered all of this except the ``negative results''.