Joseph Muscat 2014 1 Sets [email protected] October 2013 1 Classes Logic deals with statements and their deductions, and the simplest statements are usually of the type “x is A”, where x is an object and A a property. In practice, apropertymayitselfbeanobjectwithpropertiese.g.“rosesarered”, “red is a color”, so that there ought to be no distinction in notation between the two; the two are amalgamated into one concept of “class”: The class {x:x is A} corresponds to the property A, and can be thought of as a “collection” of objects x, called its elements. For convenience, we will call the class also by the name A to avoid duplicating symbols unnecessarily, because it contains the same information as the “property” A. The statement x is A (as a property) is rewritten as x∈A (as a class). The basic construct in logic is ⇒ ; the corresponding structure in classes is the subset, and equality. Definition: Equality of classes A=B when ∀x, x is A ⇔ x is B Subset A⊆B when ∀x, x is A ⇒ x is B. Logic already defines equality of objects and of properties by x=y ⇔ ∀C,(x∈C ⇔ y ∈C) A=B ⇔ ∀x,(x∈A ⇔ x∈B) (Informally, the “entity” {A : x is A} ought to characterize x, just as {x : x is A} characterizes A.) For consistency, if we are to amalgamate the two concepts, we are forced to make the assumption: Axiom1ofExtensionality: Equalityaspropertiesandasobjectsareequiv- alent, x=y ⇔ ∀z,(z ∈x ⇔ z ∈y) However, we are immediately faced with a contradiction if we allow every property to act as an object with properties: let x is A := not (x is x) then A is A ⇔ not (A is A). This is Russel’s “barber’s paradox” (the barber who shaves everyone who does not shave himself: who shaves the barber?); the self- referential x is x is similar to references like an “omnipotent who creates an indestructible”. The way out of this is to distinguish between two types of classes: Joseph Muscat 2014 2 • Properclasses arethosethatcannothaveanyproperties,i.e.,substituting a proper class instead of x in “x is A” may lead to a contradiction; for example, the class {x:x(cid:54)∈x} is a proper class. • Sets are classes which have properties; i.e., those x such that x ∈ A for some A (those classes that we can say something about)1. Since there is no guarantee that they exist, we need Axiom 2 of Existence: There is a set. The informal correspondence between classes and properties, A={x:x is A}, x∈A ⇔ x is A, is extended to cover the composite properties: Empty set False ∅={ }:={x:False} Universal class True Υ:={x:True} Complement not (x is A) Ac :={x:x(cid:54)∈A} Intersection (x is A) and (x is B) A∩B :={x:(x∈A) and (x∈B)} ∀y, (x,y) is A (cid:84)A=(cid:84) A :={x:∀y, (x,y)∈A} y y Union (x is A) or (x is B) A∪B :={x:(x∈A) or (x∈B)} ∃y, (x,y) is A (cid:83)A=(cid:83) A :={x:∃y, (x,y)∈A} y y Singleton x=a {a}:={x:x=a}. Other definitions: A(cid:114)B :={x:(x is A) butnot (x is B)}={x∈A:x(cid:54)∈B}, A(cid:52)B :=(A(cid:114)B)∪(B(cid:114)A)={x:(x is A) xor (x is B)}, {a,b}:={a}∪{b}={x:x=a or x=b}, {a,b,c}:={a,b}∪{c}={x:x=a or x=b or x=c},etc. (cid:83) (cid:83) (cid:83) We often write B or A instead of A, where I is an indexing B∈A i∈I i (cid:84) (cid:84) set of A; similarly for B or A . B∈A i∈I i The logical tautologies can then be written as theorems of classes: 1. A⊆B and B ⊆C ⇒ A⊆C 2. A=A, A=B ⇒ B =A, A=B and B =C ⇒ A=C 3. Acc =A, ∅c =Υ, ∅⊆A⊆Υ, Υc =∅ 1Theremayalsobeobjectsthatarenotproperties,called“ur-elements”. Joseph Muscat 2014 3 4. A∪B =B∪A, A∪∅=A, A∪A=A, A∪(B∪C)=(A∪B)∪C, A∪Υ=Υ. 5. A∩B =B∩A, A∩∅=∅, A∩A=A, A∩(B∩C)=(A∩B)∩C, A∩Υ=A. 6. A∩Ac =∅, (A∪B)c =Ac∩Bc, A∪Ac =Υ, (A∩B)c =Ac∪Bc. 7. A∩(B∪C)=(A∩B)∪(A∩C), A∪(B∩C)=(A∪B)∩(A∪C) 8. A⊆B ⇔ A=A∩B ⇔ B =A∪B ⇔ Bc ⊆Ac 9. A∩B ⊆A⊆A∪B 10. A(cid:114)B =A∩Bc =A(cid:114)(A∩B)=(A∪B)(cid:114)B; A(cid:114)A=∅; A(cid:114)∅=A; A⊆B ⇔ A(cid:114)B =∅; (cid:114) (cid:114) (cid:114) A (B C)=(A B)∪(A∩C); (cid:114) (cid:114) A (A B)=A∩B; (cid:114) (cid:114) (cid:114) (A B) C =A (B∪C); (cid:114) (cid:114) A∩(B C)=(A∩B) (A∩C); (cid:114) A=(A∩B)∪(A B) 11. A(cid:52)B =B(cid:52)A, A(cid:52)∅=A, A(cid:52)A=∅ (A(cid:52)B)(cid:52)C =A(cid:52)(B(cid:52)C), A(cid:52)Υ=Ac, (cid:114) A(cid:52)B =(A∪B) (A∩B), A∩(B(cid:52)C)=(A∩B)(cid:52)(A∩C). 12. ∀x,x(cid:54)∈∅; A(cid:54)=∅ ⇔ ∃x∈A (since x ∈ ∅ ⇔ False; conversely, x (cid:54)∈ A ⇔ (x ∈ A ⇒ False), so ∅⊆A⊆∅.) 13. For sets, {a}={b} ⇔ a=b, {a}={b,c} ⇔ a=b=c. 14. (cid:83)∅=∅, (cid:84)∅=Υ, (cid:83){a}=a=(cid:84){a} (cid:83) (cid:84) 15. A∪B = {A,B},A∩B = {A,B}. ‘(Proof: x ∈ A∪B ⇔ x ∈ A or x ∈ B ⇔ ∃y ∈ {A,B},x ∈ y ⇔ x ∈ (cid:83) {A,B}.) (cid:83) (cid:83) (cid:84) (cid:84) 16. A∩ B = (A∩B ) A∪ B = (A∪B ) i i i i i i i i ((cid:84) A )c =(cid:83) Ac ((cid:83) A )c =(cid:84) Ac i i i i i i i i (cid:83) (cid:84) (cid:84) (cid:83) A ⊆ A i j i,j j i i,j Thereverseinclusionmaybefalse: (A∩B)∪(C∩D)⊆(A∪C)∩(B∪D), e.g. A=D ={a}, B =C =∅. 17. {x:(x is A) ⇒ (x is B)}=Ac∪B. Joseph Muscat 2014 4 1.1 Pairs Ordered pairs of sets are defined2 as (a,b):={{a,0},{b,1}} (Here, 0 and 1 are any two distinct markers). It follows that (a,b)=(c,d) ⇔ a=c and b=d, and so a (cid:54)= b ⇒ (b,a) (cid:54)= (a,b). Of course, the definition can be extended to (a,b,c) as (a,(b,c)) or as {{a,0},{b,1},{c,2}} The class of ordered pairs is denoted A×B :={(a,b):a∈A and b∈B} (we also write A2 :=A×A). (A∪B)×C =(A×C)∪(B×C), (A∩B)×(C∩D)=(A×C)∩(B×D), ∅×A=A×∅=∅, A⊆C and B ⊆D ⇒ A×B ⊆C×D. Axiom 3 of Replacement: If the elements of a set A are replaced by other sets, the result is a set {f(x):x is A}. It contains as a special case the removal of elements, because this is equiv- alent to replacing them with an already existing element of A (unless A = ∅). Thus it implies (when A(cid:54)=∅) the following: Axiom 3’ of Specification: A subset of a set is itself a set. It follows that when A is a set, then so is A∩B for any class B. This is often written as {x ∈ A : x is B}, and is the usual way of creating sets from predicates. In particular ∅ is a set, since sets exist (∅=A∩Ac)3, and A(cid:114)B is (cid:84) a set when A is; more generally A is a set when any A is a set. y y x Conversely, if A⊆B and A is a proper class, then so is B. In particular, Υ is a proper class, since there are proper classes. How is Russel’s paradox avoided? For any set A, let B :={x∈A:x(cid:54)∈x}; then B ∈ B ⇔ B ∈ A and B ∈/ B, hence B (cid:54)∈ B and B (cid:54)∈ A, without contradiction. Incidentally, this shows that for every set A there is a set B not in A; hence the class {x:x is a set } cannot be a set, but is a proper class. Note that Axiom 3 is not really one axiom but a schema of axioms, one for each f. 2A common alternative definition is {{a},{a,b}}; but its disadvantage is that it does notscaleup: (a,b,c):={{a},{a,b},{a,b,c}}gives(a,a,b)=(a,b,b). 3Well, Axiom 3 does not imply, by itself, that ∅ is a set; so usually Axiom 3’ is dropped andAxiom2isreplacedby“∅isaset”. Joseph Muscat 2014 5 There is still the possibility that a set be defined in terms of itself, A ∈ A, or that there is an unending chain ...∈C ∈B ∈A. These cases of circular or improper definitions are disallowed by requiring: Axiom 4 of Regularity/Foundation/Well-definition: For any nonempty class A, it cannot be the case that all its ele- ments have elements of A, i.e., not ∃A(cid:54)=∅,∀x∈A,∃y ∈A,y ∈x In particular for any set A, it cannot be the case that A∈A or A∈B ∈A etc. (otherwise{A,B}consistsofelementsthatcontainA,B). So{x:x(cid:54)∈x}=Υ. Therenowfollowtwoaxiomsabouthowlargersetscanbeconstructedfrom given ones. Axiom 5 of Powers: When A is a set, so is the set of subsets 2A :={x:x⊆A} Consequences: 2∅ = {∅} is a set; so applying the axiom of replacement, {a} is a set when a is a set. 2{∅} ={∅,{∅}} is a set; so again, {a,b} is a set when a and b are. A=B ⇔ 2A =2B. (cid:83) Axiom 6 of Unions: When A is a set, so is A. (cid:83) It follows that A∪B = {A,B} is a set when A, B are sets. In particular A(cid:52)B is a set when A and B are. But Ac and B(cid:114)A (with B proper) need not be sets. A×B is a set when A and B are, since A×B ⊆22A∪B∪{0,1}. 2 Functions Theclassequivalentofarelationisρ:={(x,y):ρ }. Thusxρy ⇔ (x,y)∈ x,y ρ. Can generalize to relations with n variables. ArelationontwosetsX andY isasubsetofX×Y,denotedbyρ:X →Y. The identity relation is ι, defined as equality x=y. The inverse relation is ρ−1 :={(y,x):x ρ y}:Y →X; then (ρ−1)−1 =ρ. The image of a subset A⊆X is the set ρA:={y ∈Y :∃x∈A,x ρ y}; the image of ρ is imρ := ρX (when X is understood); while its domain is ρ−1Y; the image of an element a is the set ρ{a}={y ∈Y :a ρ y}. A⊆B ⇒ ρA⊆ρB, ρ∅=∅, (cid:83) (cid:83) ρ(A∪B)=ρA∪ρB, ρ A = ρA , i i i i (cid:84) (cid:84) ρ(A∩B)⊆ρA∩ρB, ρ A ⊆ ρA . i i i i Joseph Muscat 2014 6 (Theinverseρ−1 ismoreproperlydenotedρ∗ becauseitisnotatrueinverse: ρ◦ρ−1 need not be ι.) A relation ρ can be restricted ρ| := ρ∩(C ×D); relations ρ : A → B C×D and σ :C →D can be composed to give σ◦ρ:={(a,c):∃b∈B∩C,a ρ b σ c} satisfying τ ◦(σ◦ρ)=(τ ◦σ)◦ρ, ρ◦ι=ρ=ι◦ρ, (σ◦ρ)−1 =ρ−1◦σ−1. The union of two relations ρ,σ :X →Y, ρ∪σ is also a relation; more generally (cid:83) ρ is a relation. i i A relation ρ:X →X is called an equivalence relation when it is • transitive x ρ y and y ρ z ⇒ x ρ z (i.e., ρ◦ρ⊆ρ); • reflexive x ρ x (i.e., ι| ⊆ρ); and X2 • symmetric x ρ y ⇒ y ρ x (i.e., ρ−1 =ρ). Equivalence relations are in correspondence with partitions: A partition of A is a class of subsets B ⊆A such that A=(cid:83) B and i(cid:54)=j ⇒ B ∩B =∅. i i i i j Proposition 1 Everyequivalencerelationinducesapartitionon its domain and vice versa. Proof. Suppose ρ is an equivalence relation. Let [x] := ρ{x}, called the equivalence class of x, and let P := {[x] : x ∈ X} be the class of equivalence classes. Then A=(cid:83) [x] since y ∈A ⇒ y ∈[y]∈P; and [x]∩[y](cid:54)=∅ ⇒ [x]∈P ∃z,zρx and zρy ⇒ xρy, and for any z,z ∈ [x] ⇔ zρx ⇔ zρy ⇔ z ∈ [y] so [x]=[y]. Conversely,ifP isapartitionofA,letxρybedefinedby∃i,x,y ∈A ∈P. It i is transitive since x,y ∈A and y,z ∈A implies A ∩A (cid:54)=∅ and so A =A , i j i j i j so x,z ∈ A . It is reflexive since x,x ∈ A for some i. And it is obviously i i symmetric. (cid:3) AfunctionisarelationforwhichtheimageonanyelementofthedomainX consists of exactly one element, ∀x∈X,∃y ∈Y,f{x}={y}, i.e., the function preserves equality If (x,y)∈f and (x(cid:48),y(cid:48))∈f, then x=x(cid:48) ⇒ y =y(cid:48), Joseph Muscat 2014 7 equivalently ∀x∈X,∃!y ∈Y,(x,y)∈f. We can therefore write f(x) instead of the object y whenever (x,y)∈f. The axiom of replacement, written rigorously, states that if A is a set and f a function (with domain and codomain being classes), then fA={f(x):A } x is a set. If two functions are equal f = g then they have the same domain X and image Y, and ∀x∈X,f(x)=g(x). Note that the identity relation, restrictions with the same codomain, and composition of functions X → Y ⊆ C → D are functions. fA⊆B ⇔ A⊆f−1B f(cid:83) A =(cid:83) fA f−1(cid:84) A =(cid:84) f−1A i i i i i i i i f−1Ac =(f−1A)c A⊆f−1fA, ff−1A⊆A A function is 1-1 (injective) when f(x)=f(y) ⇒ x=y (⇔ f−1◦f =ι ⇔ fAc ⊆(fA)c), it is onto (surjective) when fX =Y, i.e., ∀y ∈Y, ∃x∈X, f(x)=y (⇔ f ◦f−1 =ι ⇔ (fA)c ⊆fAc). If f ◦g =ι then f must be onto and g 1-1. The inverse f−1 is itself a function when f is both 1-1 and onto (called bijective), equivalently f−1◦f =ι , f ◦f−1 =ι . X Y When f is 1-1, f(A∩B) = fA∩fB; when f and g are 1-1 (resp. onto), then f ◦g is also 1-1 (resp. onto); so the composition of bijective functions is againbijective; sothesetofbijectivefunctionswithdomainandcodomain Ais closed under composition, called the permutation group A!. The kernel of a function f : A → B is the partition on A induced by the equivalence relation f(x)=f(y). f is 1-1 ⇔ kerf =kerι ⇔ kerf ◦g =kerg, A f is onto ⇔ imf =imι ⇔ img◦f =img. B The set of all functions f: A→B is denoted BA (it is a set when A and B are, since BA ⊆2A×B); more generally the set (cid:89) (cid:91) A :={f :I → A and ∀i∈I,f(i)∈A } i i i i∈I i 2.1 Axiom of Choice Axiom 7 of Choice: For any sets A (cid:54)=∅ and I, (cid:81) A (cid:54)=∅ i i∈I i Equivalently, Joseph Muscat 2014 8 For every set A, there is a function (cid:15) : 2A → A such that ∅ (cid:54)= B ⊆ A ⇒ (cid:15)(B)∈B; For every onto function f: X → Y there is a function g: Y → X such that f ◦g =ι. Proof: For A (cid:54)= ∅, A2A ⊇ (cid:81) B (cid:54)= ∅, i.e., ∃(cid:15) : 2A → A, such that ∅(cid:54)=B⊆A (cid:15)(B) ∈ B. Given f : X → Y, let g(y) := (cid:15)(f−1y), so f ◦g(y) ∈ ff−1y = {y}. Given A (cid:54)= ∅ (wolog disjoint), let f : (cid:83) A → I be defined by f(x) := i if i i i x∈A ; then f ◦g(i)=i, i.e., g(i)∈A . i i This axiom seems sensible because it disallows sets that have elements that cannot be sampled; without it there may be non-empty sets that do not have “witness”elements. Nonethelessitiscontroversialbecauseitintroducesafunc- tion that cannot be constructed, and because it has some unexpected conse- quences (e.g. Banach-Tarski “paradox”); yet these theorems cannot become false when this axiom is not included, they may simply become undecidable. Moreover, there are also paradoxes when the axiom of choice is false, e.g. infi- nite sets that do not contains countable subsets. A stronger global form of the axiom of choice is: ∃(cid:15):Υ→Υ,(cid:15)(A)∈A for A(cid:54)=∅. 3 Numbers Two sets A and B are said to have the same number of elements (or are cardinally equivalent) when there is a bijective function f: A → B. This is an equivalence relation, here denoted by A≡B. A set A is said to have less elements than B when A is embedded in B, denoted A ⊂ B, i.e., there is a subset C ⊆ B such that A ≡ C ⊆ B; this is ∼ equivalent to saying that there is a 1-1 function f: A → B (take C := fA), or that there is an onto function g: B → A (Proof: If f : A → B is 1-1, then (cid:40) a if f(a)=b, g(b):= ; if g :B →A is onto, let f be a (1-1) choice function a if b∈/ imf 0 f(a) ∈ g−1(a)). In this case A is numerically equivalent to fA. Of course, if A⊆B, then A has at most as many elements as B. Clearly, A⊂A and A⊂B ⊂C ⇒ A⊂C. ∼ ∼ ∼ ∼ Proposition 2 Either A has less elements than B or vice-versa. Proof. Assuming A,B (cid:54)= ∅, and the Hausdorff Maximality Principle (a consequenceoftheAxiomofChoice), thenthesetof1-1functionswithdomain inAandimageinB hasamaximalelementf,whenorderedbyinclusion. Were boththedomainandimageoff strictlylessthanA,B,thenitcanbeextended Joseph Muscat 2014 9 by some (a,b) and remain 1-1. Thus either f : A → B is 1-1, or f−1 : B → A is 1-1. (cid:3) The following states that if A has at most as many elements as B, and B as many as A, then they have the same number of elements: Proposition 3 If A⊂B ⊂A then A≡B. ∼ ∼ That is, if f: A → B and g: B → A are both 1-1, then A, B are numerically equivalent. Proof. Let F: 2A →2A be defined by F(C):=g(f(C)c)c. It is increasing (C ⊆C ⇒ F(C )⊆F(C )), hence has a fixed point (see Complete lattices), 1 2 1 2 i.e., a set D such that g(f(D)c)c = D. Therefore g(f(D)c) = Dc, so one can define a new map h:A→B by (cid:40) f(x) x∈D, h(x):= g−1(x) x∈Dc. It is 1-1 and onto since g−1Dc =f(D)c. (cid:3) Corollary: If A⊂B ⊂C ⊂A, then A≡B. ∼ ∼ ∼ Thuswecanformequivalenceclassesofcardinallyequivalentsets,andthese are precisely the (cardinal) numbers n. (Note that the class of numbers is not a set; neither need be each equivalence class.) Moreover for disjoint sets A with cardinal numbers n , we define (these are i i well-defined) (cid:88) (cid:91) (cid:89) (cid:89) n :=[ A ], n :=[ A ], nm :=[AB]. i i i i i i i i We also write n(cid:54)m when A⊂B. ∼ Proposition 4 A function f: A→2A on sets cannot be onto, nor f: 2A →A be 1-1: n<2n Joseph Muscat 2014 10 Proof. Suppose f: A → 2A is onto. Then B := {x ∈ A : x (cid:54)∈ f(x)} is a subset of A. So there must be an element y ∈ A such that f(y) = B, but y ∈B ⇔ y (cid:54)∈f(y) ⇔ y (cid:54)∈B. (cid:3) ThiswasthefirstindicationtoCantorthattherewassomethingwrongwith sets as he defined them, since 2Υ =Υ. One can form a sequence of cardinally inequivalent numbers as follows: for any set A, let A+ :=A∪{A}: 0 := ∅ ={ } ={} 1 :=0+ ={0} ={{}} 2 :=1+ ={0,1} ={{},{{}}} 3 :=2+ ={0,1,2} ={{},{{}},{{},{{}}}} 4 :=3+ ={0,1,2,3} ={{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}} ... Itwillbeshownshortlythatthesesetsareinequivalent,soitisclearthatwe would need more and more symbols to denote all these numbers. We normally adopt a number system to extend these numerals and denote larger numbers: in the decimal system, after 9, we write 10, then 11, etc.; in the binary system, we write 10 after 1, then 11, 100, 101, etc. The numbers constructed this way are called the natural numbers. Any set that is numerically equivalent to one of them is called finite. To say this better, we need to form the set of natural numbers, but how do we characterize them? A class is said to be inductive when n ∈ A ⇒ n+ ∈ A. The intersection of inductive classes is itself inductive, so one can generate an inductive class (cid:84) starting from any set, as Ind(A) := {B : inductive,A ⊆ B}. Then the class of natural numbers is the inductive class generated by 0, (cid:92) N:=Ind(0)= {A:A inductive,0∈A} The numbers defined above, namely 0, 1 = 0+, 2, etc.are in N, since it is inductive; and there are no other since N is the least such class. The next axiom is controversial in that it accepts that “actual” infinity is logically consistent. Axiom 2’ of Infinity: N is a set (Equivalently, there exists an inductive set; this can replace the axiom that there exists a set.) The sets numerically equivalent to N are called countably infinite, with their number sometimes denoted by ω. Every set is either finite, countably infinite, or uncountable, according to whether it has less, equal, or more elements than N.