Sets PDF

UNIT 2 SETS STUDY GOALS On completion of this unit, you will have learned... – what is meant by a set, subset, and superset. – how to form the union, intersection, and difference of sets. – which calculation rules apply for unions, intersections, and differences. – what is meant by th...

UNIT 2 SETS STUDY GOALS On completion of this unit, you will have learned... – what is meant by a set, subset, and superset. – how to form the union, intersection, and difference of sets. – which calculation rules apply for unions, intersections, and differences. – what is meant by the cardinality of a set. – how the power set of a set is formed. – what it means when one number splits another number. – how equivalence relations and equivalence classes are defined and what properties they have.  2. SETS Introduction In this lesson you will learn about sets. Sets are basic mathematical concepts on which many other things are based. They are of extraordinarily central importance for all mathe- matics. In the following sub-units we will clarify the concept of the set of the natural num- bers ℕ, the integers ℤ, the rational numbers ℚ, and the real numbers ℝ, and we will high- light important properties of sets. Then we will go into sets with very special properties, called equivalence classes. Please work through this learning cycle particularly thoroughly. 2.1 Properties of and Calculation Rules for Sets First of all, we want to specify what we mean by a set. For this we use the definition of Georg Cantor (1845—1918). Cantor was a famous German mathematician and the founder of set theory. Definition: Set Set By a set we mean every gathering M of certain well-differentiated objects m of our view or In plain English, a set is a our thinking (which are called the elements of M) into a whole. grouping or collection of distinct objects. A set thus comprises objects that are clearly distinguishable from each other. We call these objects the elements of the set. At first, no statement is made about what kind of elements a set must contain. They can be real-world objects, such as a group of people, but also mathematical constructs, such as the set of natural numbers ℕ. Sets are often written in capital letters, e.g., M, while lowercase letters are usually used for objects, e.g., m. To express that an object m is element of a set M, we write m ∈ M. To expre ss that an obje ct m is not element of a set M, we write m ∉ M. The empty set, i.e., the set that has no single element, is given the symbol ∅. The elements of a set are noted within curly brackets, also known as braces. For example, M := {a, b, c} denotes a set M containing the three elements a, b, and c. It is therefore a ∈ M, b ∈ M, and c ∈ M. Often one wants to express additionally that the elements of a set have a certain property e. This fact can be noted as M = {m|m has the property e}. In this case M would be the set of all elements having the property e. The specification of such a property is optional. 26 Example: Sets 1. ℕ is the set of natural numbers. We can write this as ℕ := {1, 2, 3, 4,...} 2. ℤ is the set of integers. We can write this as ℤ := {..., −3, −2, −1, 0, 1, 2, 3,...} 3. Let M be the set of numbers 1, 2, 3, 4. We can write this as M := {1, 2, 3, 4}. 4. Let P be the set of all people with blond hair. Then we can write this as P := {p|p has blond hair}. 5. Let U be the set of all odd numbers. Then we can write this as U := {u|u is an odd number}. Often, however, this notation is too general. For example, if you look at the set of people with blonde hair, the question inevitably arises: from which greater set or larger group of people are they selected? Do you look at all the people in a particular city? Or all the stu- dents in a course? Or the entire world population? The same applies, for example, to the set U defined above. From which basic set do you choose the odd numbers as elements for U? Only from the natural numbers ℕ? Or from the whole numbers ℤ? To make this more precise, we introduce the terms subset and superset. Definition: Subset and Superset A set N is called a subset of a set M, if every element of N is also in M. For this we write N ⊆ M. The set M is then called superset of N. Examples: Partial sets and supersets 1. Let A := {1, 2, 3, 4} and let B := {2, 4}. Then A is a superset of B and B is a subset of A. So it applies that B ⊆ A. The following figure illustrates this relationship. 2. Let P be the set of all persons who live in Berlin. Then we can define the set of all per- sons with blond hair in this group as P' := {p ∈ P|p has blond hair}. P is then a superset of P' and P' is a subset of P. So it applies that P' ⊆ P. 3. We define the set of all odd natural numbers as N':= {n ∈ ℕ|n is odd}. Then ℕ is a superset of N' and N' is a subset of ℕ. It therefore applies N' ⊆ ℕ. 4. Every natural number is also an integer and every integer is also a real number. It therefore applies ℕ ⊆ ℤ ⊆ ℝ. To express clearly that a set N is not a subset of a set M, use the symbol of a subset in crossed-out form and write N ⊈ M. 27  Figure 1: The set A: = {1,2,3,4} } is a superset of B: : = {2,4}, B is a subset of A. This is written as B C A. Source: Brückmann, 2013. Definition: Equality of Sets Two sets M and N are equal if N ⊆ M and M ⊆ N are valid, i.e., if all elements of N are also in M and vice versa. Example: Equality of sets Let M: = {1, 2, 3} and N: = {1, 2, 3}. Obviously M ⊆N, because all elements of M, i.e., 1, 2, and 3, are also in N. Likewise N ⊆ M, because all elements of N, i.e., 1, 2, and 3, are also in M. Thus the sets M and N are equal, meaning M = N. This e xample shows the manne r by which we always proce e d if we want to show that two se ts M and N are equal. First, one shows that M is a subset of N. Then we show that N is also a subset of M. From this follows equality. Next, we will introduce various operations (also called combinations) that can be per- formed on sets. Definition: Union of Sets Let M and N be sets. Then we define the union of M and N as M ∪ N := {x|x ∈ M ∨ x ∈ N}. This is read “M union N.” The set M ∪ N thus consists of all e le me nts that occur in M or in N (or both sets). It should be noted that sets generally never contain duplicate elements. This means that even an element that occurs in both sets M and N is only contained once in M ∪ N. Definition: Intersection of Sets Let M and N be sets. Then we define the intersection of M and N as M ∩ N := {x|x ∈ M ∧ x ∈ N}. This is read “M intersect N.” 28 The set M ∩ N therefore contains only those elements that occur in both sets, i.e., in M and N. Definition: Difference of Sets Let M and N be sets. Then we define the difference of M and N as M\N := {x|x ∈ M ∧ x ∉ N}. This is read “M difference N.” Thus, the set M\N contains exactly those elements that occur only in M but not in N. Example: Union, intersection, and difference of sets Let M := {1, 2, 3, 4} and N := {3, 4, 5, 6}. Then M ∪ N= 1, 2, 3, 4, 5, 6 M ∩ N= 3, 4 M\N= 1, 2 The operations on sets can be illustrated very well by using Venn diagrams. These set dia- grams were named after the English mathematician John Venn (1834—1923). The figure below illustrates the various operations using such a graphic representation of two sets A and B. The shaded area indicates the result of the operation. In the case of a union, this extends over both circles, because the union contains all the elements contained in A or in B or in both. In the intersection, the shaded area is only the middle part where the two circles intersect, because the intersection contains only those elements that occur in both A and B. In the difference, the whole circle of A is shaded except the area covered by B, because the difference contains the elements that are only in A but not in B. Figure 2: Union (left), intersection (middle), and difference (right) of quantities. Source: Brückmann, 2013. Definition: Disjoint Two sets M and N are called disjoint if M ∩ N = ∅ applies, i.e., the intersection is empty. Disjoint Two sets are said to be disjoint if they have no Two disjoint sets have no single common element that occurs in both sets. elements in common. 29  Theorem: Associative Laws for Sets Let L, M, and N be sets. Then the following two rules apply: L∪ M∪N = L∪M ∪N L∩ M∩N = L∩M ∩N Proof: First, we prove that L ∪ (M ∪ N) = (L ∪ M ) ∪ N. For this purpose we follow the defini- tion of equality of sets: If we can show that the set on the left side is a subset of the set on the right side and vice versa, then it follows that the two sets are equal. This is exactly how we want to proceed: We first show that L ∪ (M ∪ N) is ⊆ (L ∪ M) ∪ N. For this we must show that each element from L ∪ (M ∪ N) is also located in (L ∪ M) ∪ N. So let x be any element of this set, so x ∈ L ∪ (M ∪ N). Since x lies in the union of L and M ∪ N, x must lie in at least one of these sets. We can therefore make a case distinction. If x ∈ is L, then x ∈ L ∪ M, and therefore x ∈ (L ∪ M) ∪ N. If x ∈ M ∪ N, then x is in M or in N or in both. If x ∈ M, then x ∈ (L ∪ M) is also x ∈ (L ∪ M), and thus x ∈ (L ∪ M) ∪ N. If x ∈ N, then x ∈ (L ∪ M) ∪ N. Thus L ∪ (M ∪ N) ⊆ (L ∪ M) ∪ N. Analogously, one can show that L ∪ (M ∪ N) ⊇ (L ∪ M) ∪ N (this is left to you for practice). This leads to the first part of the claim, namely L ∪ (M ∪ N) = (L ∪ M) ∪ N. The second part of the assertion is shown in a similar way: Let x ∈ L ∩ (M ∩ N). Then x is in both L and M ∩ N. From x ∈ M ∩ N further follows that x is in both M and N. It follows further that x is also located in L ∩ M and thus in (L ∩ M) ∩ N. Thus it follows that L ∩ (M ∩ N) ⊆ (L ∩ M) ∩ N. Analogously, one can show that L ∩ (M ∩ N) ⊇ (L ∩ M) ∩ N (this is left to you for practice). This leads to the second part of the claim, namely L ∩ (M ∩ N) = (L ∩ M) ∩ N. □ Example: associative laws for sets Let L := {1, 2, 3}, M := {3, 4} and N := {3, 5}. Then L∪ M∪N = 1, 2, 3 ∪ 3, 4 ∪ 3, 5 = 1, 2, 3 ∪ 3, 4, 5 = 1, 2, 3, 4, 5 = 1, 2, 3, 4 ∪ 3, 5 = 1, 2, 3 ∪ 3, 4 ∪ 3, 5 = L∪M ∪N and 30  L∩ M∩N = 1, 2, 3 ∩ 3, 4 ∩ 3, 5 = 1, 2, 3 ∩ 3 = 3 = 3 ∩ 3, 5 = 1, 2, 3 ∩ 3, 4 ∩ 3, 5 = L∩M ∩N Theorem: Distribution Laws for Sets Let L, M and N be sets. Then the following two rules apply: L∪ M∩N = L∪M ∩ L∪N L∩ M∪N = L∩M ∪ L∩N The proof of this statement is left to you for practice. The procedure is very similar to the previous proof. The following important rules were written by the British mathematician Augustus de Mor- gan (1806—1871) and were also named after him. Theorem: Rules of de Morgan Let L, M and N be sets. Then the following two rules apply: L\ M ∩ N = L\M ∪ L\N L\ M ∪ N = L\M ∩ L\N Proof: We first prove the first rule of de Morgan and proceed analogously to the previous proofs. Let x ∈ L\(M ∩ N). The n x is ∈ L and x ∉ M ∩ N. The latte r me ans that x is either contained in only one of the two sets M, N or in none of them. If x ∈ M∧ x ∉ N, then because of x ∈ L, x ∈ is L\N and therefore x ∈ (L\M) is ∪ (L\N). If x ∉ M∧ x ∈ N, then x ∈ L\M and therefore x ∈ (L\M) ∪ (L\N) applies accordingly. If x ∉ M is ∧ x ∉ N, then even x ∈ L\M and x ∈ L\N and thus in particular x ∈ (L\M) ∪ (L\N) applies. Thus L\(M ∩ N)⊆ (L\M) ∪ (L\N) follows. Let x ∈ (L\M) ∪ (L\N). Then x ∈ is L\M or x ∈ L\N or x is in both sets. If x ∈ is L\M, then x ∈ is L and x ∉ is M. It follows that x ∉ is M ∩ N, and thus x ∈ is L\(M ∩ N). If x ∈ is L\N, then x ∈ is L and x ∉ is N. It follows accordingly that x ∉ is M ∩ N, and hence x ∈ L\(M ∩ N). Thus L\(M ∩ N)⊇ (L\M) ∪ (L\N) follows and thus the first rule of de Mor- gan applies. The second rule of de Morgan is proved in an analogous way (we leave this to you for prac- tice). The overall conclusion is therefore that the allegation is correct. □ 31  The following theorem shows some more interesting properties of subsets with respect to union and intersection. Theorem: Properties of Subsets with Regard to Union and Intersection Let M and N be sets. Then the following statements are equivalent: N⊆M M∩N=N M∪N=M Proof: (i) ⇒ (ii) N ⊆ M applies. For all x ∈ N therefore x ∈ M also applies. After defining the intersection, M ∩ N := {x|x ∈ M ∧ x ∈ N}. For all x ∈ N is therefore x ∈ M ∩ N and therefore N ⊆ M ∩ N. For all x ∈ M ∩ N is by de finition x ∈ M and in particular also x ∈ N. Thus M ∩ N follows ⊆ N. This means that in total M ∩N = N follows. (ii) ⇒ (iii) M ∩ N = N. According to the definition of the union, M ∪ N := {x|x ∈ M ∨ x ∈ N}. For all x ∈ M is therefore x ∈ M ∪ N and therefore M ⊆ M ∪ N. For all x ∈ M ∪ N applies that x ∈ M or x ∈ N. For all x ∈ N is because of M ∩ N = N also x ∈ M ∩ N and thus x ∈ M. Thus M ∪ N it follows ⊆ M. This means that in general it follows that M ∪ N = M. (iii) ⇒ (i) M ∪ N = M. Assuming that N ⊈ M. Then there is x ∈ N with x ∉ M. It follows that there is x ∈ M ∪ N with x ∉ M. This leads to a contradiction, because then M ∪ N = M can- not apply. Thus, the assumption N ⊈ M is wrong. It therefore follows that N ⊆ M. □ Definition: Cardinality Let M be a set. We define the cardinality of a set as n, ifn ∈ ℕ ∪ 0 is the number of elements in M is M:= ∞, if M has infinitely many elements. 32 ∞ is the mathematical symbol for infinity. Example: Cardinality 1. Let M1 := {a, b, c, d}. Then |M1| = 4. 2. Let M2 := {1, 2, 3, 4, 5, 6, 7, 8} and let M'2⊆ M 2 with M'2 := {m ∈ M2|m is even} = {2, 4, 6, 8}. Then |M2| = 8 and |M'2| = 4. 3. Let M3 := N. Then |M3| = ∞. Definition: Power Set Let M be a set. Then we define the power set of M as the set of all possible subsets of M and we call it P(M). Please note that the empty set ∅ is always a possible subset of any other set! Thus ∅ is always included in every power set. 1. Let M1 := {a,b,c,d}. Then P M1 = ∅, a , b , c , d , a, b , a, c , a, d , b, c , b, d , c, d , a, b, c , a, b, d , a, c, d , b, c, d , a, b, c, d 2. Let M2 := {1,2,3}. Then P M2 = ∅, 1 , 2 , 3 , 1, 2 , 1, 3 , 2, 3 , 1, 2, 3 Please note that the empty set is always an element of the power set of a set! The power set of a finite set is always finite, the power set of an infinite set is infinite. Theorem: Cardinality of the Power Set Let M be a finite set with |M| = n ∈ ℕ0. Then |P(M)| = 2n. Proof: We prove the statement of this theorem with induction: Base case: If n = 0, then M is the empty set. The power set of the empty set has only one element, namely the empty set itself. So it follows that |P(M)| = 1= 20 and thus the induction base case is valid. Induction step: Now let n ≥ 0. Let |P(M)| = 2n be valid for each finite set M with n ele- ments. We must show that from this it follows that |P(M')| = 2n+1 for every finite set M' with n + 1 elements. 33  Let M' be a set with n + 1 elements, thus M' := {a1,..., a(n+1)}. We investigate how many different subsets M' has. Let L' be any subset of M', i.e., L' ⊆ M'. Then there are exactly two possibilities: 1. Possibility: an+1 ∈ L' 2. Possibility: an+1 ∉ L' 1: If an+1 ∈ is L', then L' is of the form L' = L ∪ {an+1} with L ⊆ M := {a1,..., an}. We know that there are 2n different subsets of M, because since |M| = n it follows that |P(M)| = 2n. Since L is a subset of M, there are therefore 2n possibilities for how L can exist. Thus there are 2n possibilities of how L' can exist, and consequently there are 2n subsets of M' containing an+1. 2: If an+1 ∉ is L', then L' is a subset of M := {a1,..., an}. We know that there are 2ndiffer- ent subsets of M, because |P(M)| = 2n. Consequently, there are 2n different possibilities for L' and thus 2n subsets of M', which do not contain an+1. Since there are no other possibilities, there are exactly 2n subsets of M' that contain an+1 and 2n subsets of M' that do not contain an+1. M' thus has a total of 2n + 2n = 2 ⋅ 2n = 2n+1 subsets and it follows |P(M')| = 2n+1. □ Definition: Cartesian Product Cartesian product Let M and N be non-empty sets. Then the Cartesianproduct of M and N is defined as M This aspect of set theory × N := {(m, n)|m ∈ M, n ∈ N}. M × N is read “M cross N.” The set defined by M × N was developed by the 17th-century French phi- is also known as the product set. losopher and mathemeti- cian René Descartes. The (m, n) ∈ M × N are called ordered pairs. Two ordered pairs (m1, n1) and (m2, n2) are exactly the same when m1 = m2 and n1 = n2. Example: Cartesian product Let A := {x, y, z} and B := {1, 2, 3}. A × B := {(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2), (z, 3)}. HINT Notice the order of the elements in the pairs is important! (unless A=B) 34 Figure 3: Cartesian Product 2.2 Equivalence Relations Definition: Divide Let n ∈ ℕ and a ∈ ℤ. We say “n divides a” and write n|a for it if there is an x ∈ ℤ so that x ⋅ n = a. Examples: Divide 1. It is true that 2|6, because 3 ⋅ 2 = 6. 2. It is true that 5|35, because 7 ⋅ 5 = 35. 3. It is true that 8|24, because 3 ⋅ 8 = 24. 4. It is true that 4|−12, because (−3) ⋅ 4 = −12. 5. It is true that 3|−15, because (−5) ⋅ 3 = −15. Theorem: Divisor of Sums and Differences Let n ∈ ℕ and a, b ∈ ℤ. It applies that n|a and n|b. It follows that n|(a + b) and n|(a − b) also applies. Proof: 35  It applies that n|a. Then there is a x1 ∈ ℤ with x1n = a. Furthe rmore , n|b still applies. Then there is an x2 ∈ ℤ with x2n = b. From this it follows that a + b = x1n + x2n = (x1 + x2) ⋅ n, thus n|a + b. Furthermore it follows that a − b = x1⋅ n − x2 ⋅ n = (x1 − x2) ⋅ n, thus n|a − b. □ Example: Divisor of sums and differences 1. It applies that 2|6, because 3 ⋅ 2 = 6, and 2|8, because 4 ⋅ 2 = 8, so obviously 3 ⋅ 2+ 4 ⋅ 2 = 7 ⋅ 2 = 14 = 6 + 8 and thus 2|(6 + 8). 2. It applies that 3|9, because 3 ⋅ 3 = 9, and 3|15, because 5 ⋅ 3 = 15, so obviously 3 ⋅ 3 + 5 ⋅ 3 = 8 ⋅ 3 = 24 = 9 + 15 and therefore 3|(9 + 15). 3. It applies that 5|20, because 4 ⋅ 5 = 20, and 5|35, because 7 ⋅ 5 = 35. Obviously then 4 ⋅ 5 − 7 ⋅ 5 = (−3) ⋅ 5 = −15 = 20 − 35 and therefore 5|(20 − 35). Definition: Congruent Modulo Let a, b ∈ ℤ and let m ∈ ℕ. We write a ≡ b mod m, if m divides the number b − a, i.e., if m|(b − a) applies. a ≡ b mod m is read “a is congruent to b modulo m.” Example: Congruent modulo 1. It applies that 21 ≡ 0 mod 7, because 7|(0 − 21) because of −3 ⋅ 7 = −21. 2. It applies that 2 ≡ 12 mod 5, because 5|(12 − 2) because 2 ⋅ 5 = 10. 3. It applies that −8 ≡ 4 mod 2, because 2|(4 − (−8)) because 6 ⋅ 2 = 12. 4. It applies that 5 ≡ −19 mod 4, because 4|(−19 − 5) because of (−6) ⋅ 4 = −24. Definition: Equivalence Relation Let M be a set. A subset R ⊆ M × M is called an equivalence relation to M if the three following properties apply to all x, y, z ∈ M: 1. Reflexivity: (x, x) ∈ R 2. Symmetry: If (x, y) ∈ R, then (y, x) ∈ R also applies 3. Transitivity: If (x, y) ∈ R and (y, z) ∈ R, then (x, z) ∈ R also applies An equivalence relation is therefore a set whose elements must fulfill certain properties. If R is an equivalence relation on M and (x, y) ∈ R, the n we write x ∼R y for it. One re ads this “x is equivalent to y.” Often, instead of x ∼R y, one simply writes x ∼ y in abbreviated form, if the context indi- cates to which quantity the equivalence relation refers. Example: Equivalence relations a ∼n b is an equivalence relation to ℤ: 36 a) ∼n is reflexive, because for a ∈ ℤ it applies that because of 0 ⋅ n = 0 = a − a, then n| (a − a). b) ∼n is symmetrical, because for a, b ∈ ℤ it applies that, if n|(a − b), then n|−(a − b) and thus n|(b − a). c) ∼n is transitive, because if n|(a − b) and n|(b − c) for a, b, c ∈ ℤ then n|(a − b) + (b − c) is also valid, and because of (a − b) + (b − c) = a − c then n|(a − c) is also valid □ If a ∼n b, then n|(a − b) applie s. This is e quivale nt to a ≡ b mod n. The e quivale nce re lation ∼n is therefore also called congruent modulo equivalence relation. Definition: Equivalence Class Let M be a set and R be an equivalence relation to M. A non-empty subset L ⊆ M is called equivalence class with respect to R if the following two properties apply: 1. From x, y ∈ L it follows that x ∼ y. 2. If x ∈ L and y ∈ M, and if x ∼ y, then y ∈ L. An equivalence class thus denotes a non-empty subset L of a set M, with respect to which we have formed an equivalence relation. Property 1 states that all elements of such an equivalence class L must be equivalent to each other in pairs. Property 2 states that every element of M which is equivalent to an element of equivalence class L must also be an element of this equivalence class. Example: Equivalence classes 1. Let’s look at the amount M of students enrolled in the subjects medicine, computer science, and history. We have seen that the property of whether two students are in the same course of study forms an equivalence relation on M. We assume that each course has at least one student (otherwise the university would not offer it). Each of the students is therefore enrolled in exactly one of these courses. Then we can define three sets: SM : = x ∈ Mx studies medicine ⊆ M SI : = x ∈ Mx studies computer science ⊆ M SG : = x ∈ Mx studies history ⊆ M First, we note that SM ≠∅, SI ≠ ∅ and SG ≠ ∅. This is important according to the previ- ous definition, because equivalence classes are always non-empty subsets. If x, y ∈ is SM, then x and y are both studying medicine, i.e., they are enrolled in the same course. Thus x ∼ y. The same applies to x, y ∈ S I and x, y ∈ S G. Thus the first property for equivalence classes is fulfilled for all three sets. 37  If x ∈ SM is equivalent to y ∈ M, i.e., if x ∼ y applies, then x and y are in the same course of study and in particular are both studying medicine. But that also means y ∈ SM, because SM is just the quantity of all medical students. The same applies to the sets SI and SG. Thus the second property for equivalence classes is also fulfilled for all three sets. It follows that SM, SIand SG are equivalence classes with respect to ∼. □ 2. Let us consider the equivalence relation ∼n on ℤ. Let a ∈ ℤ and [a] := {a + kn|k ∈ ℤ}. The set [a] is an equivalence class with respect to ∼n, which is explained as fol- lows: Because a = a + 0n, then a is ∈ [a]. Thus [a] ≠ is ∅. Let x, y ∈ [a]. Then there is k, k' ∈ ℤ with x = a + kn and y = a + k'n. It applies that x − y = a + kn − a − k'n = n(k − k'). Because of n|n(k − k') it applies that n|(x − y) and therefore x ∼n y. Let x ∈ [a], i.e., there is a k ∈ ℤ with x = a + kn. Furthermore, let y ∈ ℤ and x ∼n y, i.e., n|(x − y). Then it follows that n|((a + kn) − y). Thus there is an m ∈ ℤ with mn = a + kn − y. We reformulate the equation and obtain y = a + kn − mn = a + (k − m)n. From this it follows that y ∈ [a]. Altogether it follows that [a] is an equivalence class with respect to ∼n. □ One can now ask the question whether an element could also be contained in more than one equivalence class. The following theorem states that this is not possible. Theorem: Uniqueness of equivalence classes If M is a set and R is an equivalence relation to M, then every x ∈ M is in e xactly one e quivale nce class of M with respect to R. Proof: Let x ∈ M and be Lx := {y ∈ M |y ∼ x}. First, we show that Lx is an equivalence class containing x. Then we will prove that Lx is unique. It applies that Lx ≠ ∅, because due to the reflexivity of ∼, x ∼ is x and therefore x ∈ Lx. Let y, y' ∈ Lx. Then y ∼ x and y' ∼ x. Because ∼ is symmetrical, it follows that x ∼ y'. Because ∼ is also transitive, y ∼ x and x ∼ y' continues to follow y ∼ y'. Let y ∈ Lx and y' ∈ M. It applie s that y ∼ y'. Be cause y ∈ Lx it applies that x ∼ y. Because ∼ is transitive, it follows that x ∼ y' and thus y' ∈ Lx. Consequently, Lx is an equivalence class containing x. It remains to be shown that Lx is unique, i.e., that x is not in any other equivalence class. Let L'x be another equivalence class of M with respect to R, which contains x. 38 Let y ∈ Lx. Then it applies that y ∼ x and also y ∈ M. Because L'x is an equivalence class and because x ∈ L'x, it follows with the second property of equivalence classes that y ∈ L'x. Thus Lx ⊆ L'x. Let y' ∈ L'x. Then it applies that y' ∼ x and also y' ∈ M. Because Lx is an equivalence class and because x ∈ Lx, it follows that with the second property of equivalence classes that y' ∈ is Lx. Therefore, L'x ⊆ Lx and therefore Lx = L'x altogether. □ With this we have answered the question asked above: Each element of the set lies exactly in one equivalence class. Finally, let us briefly consider how equivalence classes can be related to each other. Theorem: Relationships of Equivalence Classes Let M be a non-empty set and let R be an equivalence relation on M. Let L and L' be equivalence classes with respect to R. Then L and L' are either equal or disjoint. Proof: The assertion follows directly from the uniqueness of the equivalence classes which we have previously proved. If two equivalence classes contain a common element, they are identical due to their uniqueness. If they do not contain a common element, they are dis- joint. A third possibility does not exist. □ Each equivalence relation on a non-empty set thus provides a decomposition of this set into disjoint equivalence classes. The practical thing about equivalence classes is that the choice of an element from them is often arbitrary, as long as one is only interested in the property by which the equivalence relation is defined. Because all elements of a class are equivalent to each other and thus have the same value in the considered property, the selection of a representative is arbitrary. For example, it is completely irrelevant which stu- dent we look at in the above example from the group of medical students, if we are only interested in the field of study, because all the people in this group are studying the same thing, namely medicine. This is reflected in the following definition. Definition: Representative of an Equivalence Class Let M be a non-empty set and let R be an equivalence relation to M. Let L be an equiva- lence class with respect to R. Any element x ∈ L is called a representative of the equiva- lence class. Example: Relationships and representatives of equivalence classes 1. Let us look at our example with the students enrolled in the subjects of medicine, computer science and history. We have seen that the equivalence classes for this are given by SM, SI and SG. Obviously M = SM ∪ SI ∪ SG is a decomposition of the set M 39  and SM ∩ SI = ∅, SM ∩ SG = ∅ and SI ∩ SG = ∅. Each medical student is a represen- tative of the equivalence class SM, each computer science student is a representative of SI and each history student is a representative of SG. 2. Let us consider the equivalence relation ∼n. The equivalence classes regarding ∼n were given for a ∈ ℤ by [a] := {a + kn|k ∈ ℤ}. So we have equivalence classes = {0+ kn|k ∈ ℤ}, = {1+ kn|k ∈ ℤ}, = {2+ kn|k ∈ ℤ} etc. First of all, we con- sider that these classes actually provide a decomposition of ℤ: is the equivalence class that contains 0. Since all equivalence classes containing 0 are equal, we can choose 0 as a representative of this class and call the equivalence class containing 0. Accordingly, we choose 1 as the representative of equivalence class and call the equivalence class containing 1. is then the equivalence class containing 2, and so on. It is clear that n ∈ and n ∈ [n]. Thus and [n] are not disjunctive and are there- fore equal, i.e., = [n]. Likewise, n ∈ [2n], n ∈ [3n], etc., i.e., generally n ∈ [kn] for k ∈ ℤ. Thus = [kn] for k ∈ ℤ. Accordingly, n + 1 is ∈ and n + 1 is ∈ [n + 1], i.e., = [n + 1]. Furthermore, n +1 ∈ [2n + 1], n +1 ∈ [3n + 1] etc., i.e., generally n +1 ∈ [kn + 1] for k ∈ ℤ. Thus = [kn + 1] applies to k ∈ ℤ. Analogue is = [kn + 2], = [kn + 3], etc. We thus obtain a decomposition of ℤ by ℤ = ∪ ∪... ∪ [n − 1]. Let us examine whether these sets are disjoint: Let a, b ∈ ℤ with 0 ≤ a, b < n and let x ∈ [a] ∩ [b]. Then there is k, k' ∈ ℤ with x = a + nk and x = b + nk'. By subtracting the equations from each other, we get 0 = a + nk − b − nk' = a − b + n(k − k'). We change the equation and get b − a = n(k − k'). Thus n|(b − a) follows, i.e., n is a divisor of b − a. Because of 0 ≤ a, b < n is −n < b − a < n and therefore it applies that b−a −1 < n