12 CHAPTER 1. BASIC CONCEPTS AND EXAMPLES The set f 0 ; 1 ; 2 ; 3 ;::: g is infinite. In general, we have x 6 = f x g because the set f x g has only one element, whereas the set x could have more than one element. Note that if x = f x g , then x 2 x , i.e. x is an element of itself, a quite strange and unexpected phenomena, which will be forbidden by an axiom that will be introduced in the next part, in other words such an object will not be a set (it may be something else!) The sets f x;x;y g , f x;y g and f y;x g are equal because they contain the same elements, namely x and y . This set has either one or two elements: It has one element if x = y , otherwise it has two elements. On the other hand the set f 3 ; 5 g has exactly two elements because 3 6 = 5 (as we will prove in the second part of our book once we know what these objects are). It would be interesting to know what the reader things about the equality 2 = f 0 ; 1 g . Does it hold or not? It all depends on the definition of 2. As we will see in the next part, the integer 2 will be defined as the set f 0 ; 1 g , so that the equality 2 = f 0 ; 1 g does indeed hold. But we will not go into these fine points of set theory in this part. The number of elements of a set X is denoted by j X j . Thus jf 0 ; 1 ; 2 gj = 3, jf 0 ; 1 ; 2 ; 3 ;::: gj = 1 and 1 ∑ jf x;y gj ∑ 2. The set f x;y g has always at least one element. Here is another set: ff 0 ; 1 ; 2 g ; f 2 ; 3 ; 6 gg . This set has just two elements, namely f 0 ; 1 ; 2 g and f 2 ; 3 ; 6 g . The two elements f 0 ; 1 ; 2 g and f 2 ; 3 ; 6 g of this set are sets themselves and each have three elements. A set x is called a subset of another set y if every element of x is also an element of y . We then write x μ y . In this case, one sometimes says that y is a superset of x . For example, the set f 0 ; 2 ; 3 g is a subset of the set f 0 ; 1 ; 2 ; 3 ; 4 g because each one of the elements of the first one appears in the second one. But the set f 0 ; 2 ; 3 g is not an element of the set f 0 ; 1 ; 2 ; 3 ; 4 g unless f 0 ; 2 ; 3 g is equal to one of 0, 1, 2, 3, 4 (which is not the case as we will see in the next part). Another example: The set of even integers is a subset of the set of integers divisible by 6. We will refrain from giving non mathematical examples such as “the set of pupils in your class is a subset of the set of pupils of your school”. Another (mathematical) example: The set f 0 ; 1 g is a subset of f 0 ; 1 ; 2 g . This is clear. Is it an element? No if the set f 0 ; 1 g is not equal to one of 0, 1 and 2. Unfortunately, the way we will define numbers in the second part of the book, 2 is equal to the set f 0 ; 1 g ; therefore f 0 ; 1 g is also an element of f 0 ; 1 ; 2 g . But the reader is not supposed to know these fine points at this stage and may as well suppose that f 0 ; 1 g is not an element of f 0 ; 1 ; 2 g . Anyway, we will try to convince the reader in the second part that the definition of 2 as the set f 0 ; 1 g is in some sense arbitrary. Clearly every set is a subset of itself. Thus for all sets x , we have x μ x . We also note the following fact which is used very often in mathematics: Two sets x and y are equal 3 if and only if x μ y and y μ x . This means that 3 Here we act as if we know what the equality means, because we are doing intuitive set 1.1. SETS, SUBSETS AND EMPTYSET 13 two sets are equal if they have the same elements, i.e. if an element of one of them is an element of the other and vice versa. If x μ y and x 6 = y , then we write x Ω y . For example, f 0 ; 3 gΩf 0 ; 2 ; 3 ; º g . If the set x is not a subset of the set y , we write x 6μ y . For example, f º g6μf 3 : 14 ; 3 : 14159 ; 22 = 7 g . The statement of our first theorem must be well known by the reader, but its proof may not be so well known. In fact the proof is very interesting and we urge the reader to digest it well. Theorem 1.1.1 A set with no elements is a subset of every set. Proof: Let ; be a set with no elements 4 . Let x be any set. Assume ; is not a subset of x . We will obtain a contradiction, proving that ; is a subset of x . Since ; is not a subset of x , by the very definition of the concept of “subset”, there is an element in ; which is not in x . But ; has no elements. Thus ; cannot have an element which is not in x . Hence ;μ x . § Corollary 1.1.2 There is at most one set without elements. Proof: Let ; 1 and ; 2 be two sets with no elements. By the theorem above, ; 1 μ; 2 and ; 2 μ; 1 . Hence ; 1 = ; 2 . § A set that has no elements at all is called emptyset and is denoted by ; . As we have seen in the Corollary above there is only one set with no elements 5 . Here we list all the subsets of the set f 0 ; 1 ; 2 g : ; f 0 g f 1 g f 2 g f 0 ; 1 g f 0 ; 2 g f 1 ; 2 g f 0 ; 1 ; 2 g The set of subsets of a set X is denoted by } ( X ). Thus the set } ( f 0 ; 1 ; 2 g ) has the eight elements listed above. Theorem 1.1.3 If j X j = n is finite then j } ( X ) j = 2 n . theory. In the second part, in some sense, the equality will be defined so as to satisfy this property. 4 We do not know yet that there is only one set with no elements. We will prove it right after this theorem. 5 In fact, all we have shown in the Corollary is that a set with no elements is unique in case there is such a set . In the next part one of our axioms will state that there is a set with no elements. This fact cannot be proven, so either the existence of such a set or a statement implying its existence must be accepted as an axiom. 14 CHAPTER 1. BASIC CONCEPTS AND EXAMPLES Proof: Assume j X j = n . To form a subset of X , we must decide which elements are in the subset, i.e. for each element of X we must give a decision “yes” or “no”. Since there are n elements in X and since for each element there are two possible decisions “yes” or “no”, there are 2 n possible subsets of X . § Exercises. i. Let X = f 0 ; 1 g . List the elements of f } ( A ) : A 2 } ( X ) g : ii. Let X = ; . List the elements of f } ( A ) : A 2 } ( X ) g : iii. Show that ;6 = f;g . iv. Write the 16 elements of } ( } ( f 0 ; 1 g )). v. Show that } ( ; ) = f;g . vi. Show that } ( } ( ; )) = f; ; f;gg . vii. Find } ( } ( } ( ; ))). viii. Find a set X with an element x such that x 2 X and x μ X . ix. Can we have x μ f x g ? Answer: According to the definition, x μ f x g if and only if any element of x is an element of f x g , and this means that any element of x (if any) is x . This implies that either x = ; or x = f x g . This last possibility is quite curious, and, mush later in the book will be forbidden with the help of an axiom. We do not want a set to have itself as an element, because we feel that to define and to know a set we need to know its elements, so that if x 2 x then to know x we need to know its element x ! x. Suppose x = f x g . Find } ( x ). Is x μ } ( x )? Find } ( } ( x )). Is x μ } ( } ( x ))? xi. Show that X = ; satisfies the following formula: “for every x 2 X , x is a subset of X ”. xii. Can you find a set X 6 = ; such that for every x 2 X , x is a subset of X ? xiii. Show that X μ Y if and only if } ( X ) μ } ( Y ). xiv. Show that if X μ Y then } ( X ) 2 } ( } ( Y )). xv. Show that for any set X , f;g2 } ( X ) if and only if ;2 X . xvi. Show that for any set X , f;g2 } ( } ( X )). xvii. Show that for any set X , f;g2 } ( } ( } ( } ( } ( X ))))). xviii. Show that for any set X , f X g2 } ( } ( X )). xix. Show that for any set X , ff;g ; ff X ggg2 } ( } ( } ( } ( X )))). 1.2. NOTES ON FORMALISM 15 xx. Show that f } ( A ) : A μ X g2 } ( } ( } ( X ))). xxi. Show that ff x g ; f x;y gg = ff z g ; f z;t gg if and only if x = z and y = t . xxii. § Show that any element of ; is ; . (Hint: See Theorem 1.1.1 and its proof). xxiii. § Have a philosophical discussion among your friends about whether we should allow the existence of a set x such that x = f x g . xxiv. § Have a philosophical discussion among your friends about whether we should allow the existence of two sets x and y such that x 2 y and y 2 x . 1.2 Notes on Formalism Let us look at the definition of “subset” once again: x μ y if and only if every element of x is an element of y . Here, “if and only if” means that if x μ y then every element of x is an element of y , and if every element of x is an element of y then x μ y . Some abbreviate the phrase “if and only if” by the symbol , and write the sentence above in the following abbreviated form: x μ y , every element of x is an element of y , although it is a bad taste to use such symbols in print, or even in classroom or exams. Let us continue to abbreviate sentences in this way. Now consider the phrase every element of x is an element of y . We can rephrase this as for all z , if z is an element of x then z is an element of y and then as follows: for all z , if z 2 x then z 2 y . Very often, mathematicians use the symbol Rightarrow for “if ::: then ::: ”, i.e. instead of “if p then q ” they write p ) q . With this formalism, we can write the above phrase as for all z , z 2 x ) z 2 y . That is not enough: “for all z ” is abbreviated as 8 z . Now the phrase every element of x is an element of y 16 CHAPTER 1. BASIC CONCEPTS AND EXAMPLES becomes 8 z ( z 2 x ) z 2 y ) : Finally, the definition of “subset” can be written as x μ y ,8 z ( z 2 x ) z 2 y ) : What we have above is really a short cut for the English sentence “ x is a subset of y if and only if every element of x is an element of y ”, it is some kind of steno, a shorthand, as useful as “TGIF”. Although it is convenient, we will refrain from using such abbreviations without any apparent reason, and we advice the young reader not to use such symbolism in their papers, unless they are asked to do so. Since the above definition is for all sets x and y , we can write, 8 x 8 y ( x μ y ,8 z ( z 2 x ) z 2 y )) : The fact that every set is a subset of itself is formalized by 8 xx μ x . Let us formalize the equality of two sets. As we know, two sets x and y are equal if and only if x μ y and y μ x . Thus x = y , ( x μ y and y μ x ) : (The reader should note the need of parentheses). Instead of the word “and” we will write ^ , thus we now have x = y , ( x μ y ^ y μ x ) : We can continue and replace x μ y with 8 z ( z 2 x ) z 2 y ) and y μ x with 8 z ( z 2 y ) z 2 x ). Thus x = y , (( 8 z ( z 2 x ) z 2 y ) ^ ( 8 z ( z 2 y ) z 2 x ))) : A moment of thought will convince the reader that ( 8 z ( z 2 x ) z 2 y ) ^ ( 8 z ( z 2 y ) z 2 x )) is equivalent to 8 z (( z 2 x ) z 2 y ) ^ ( z 2 y ) z 2 x )) ; and that this one is equivalent to 8 z ( z 2 x , z 2 y ) : Thus x = y ,8 z ( z 2 x , z 2 y ) : Since this is true for all sets x and y , we have 8 x 8 y ( x = y ,8 z ( z 2 x , z 2 y )) : Let us look at the meaning of x 6 = y . By definition, x 6 = y if it is not true that x = y , i.e. if there is an element in one of the sets which is not in the other. Thus, x 6 = y if and only if 1.3. NUMBER SETS 17 either there is an element in x which is not in y or there is an element in y which is not in z . The first one, namely “there is an element in x which is not in y ” means there is a z 2 x such that z 62 y , i.e., there is a z such that z 2 x ^ z 62 y . We abbreviate “there is a z ” by the symbols 9 z . Thus the phrase “there is an element in x which is not in y ” is formalized by 9 z ( z 2 x ^ z 62 y ) : Now x 6 = y is formalized by either 9 z ( z 2 x ^ z 62 y ) or 9 z ( z 2 y ^ z 62 x ). Finally, the ”either ... or ...” part is shortened by ::: _ ::: , so that x 6 = y becomes equivalent to ( 9 z ( z 2 x ^ z 62 y )) _ ( 9 z ( z 2 y ^ z 62 x )) : A moment of reflection will show that this is equivalent to 9 z (( z 2 x ^ z 62 y ) _ ( 9 z ( z 2 y ^ z 62 x )) : What about the proposition that x Ω y , how is it formalized? By definition, x Ω y if and only if x μ y and x 6 = y . We know how to formalize x Ω y . What about x 6 = y ? By definition, x 6 = y if there is an element in one of them To be completed... This subsection may have to go somewhere else
Posted on: Thu, 11 Jul 2013 09:20:17 +0000
Trending Topics
Recently Viewed Topics
© 2015