24 CHAPTER 2. SET THEORY 2.1.1 Algebraic properties of set operations The following commutative, associative, and distributive properties of sets are natural extensions of Theorem 1 and easily seen in Figure 2.1.2 Theorem 19 Let A, B, C be any sets. Then(i)(C)AnB= BnA, AUB= BUA; (ii)(A)(AnB)nc= An(BnC),(AUB)UC= AU(BUC); andm)(D)An(BUC)=(AnB)∪(AnC,AU(B∩C)=(AUB)n∩(AUC) Exercise 2.1.1 Prove Theorem 19. This amounts to applying the logical con nectives and above definitions. Besides using Venn Diagrams, we can just use the definition ofn and U. For example, to show AnB= BnA, it is sufficient to note x∈A∩B(x∈A)∧(x∈B)(x∈B)A(x∈A)台x∈B∩A The following properties are used extensively in probability theory and e easily seen in Figure 2.1.3 Theorem 20(DeMorgan's Laws)If A, B, C are any sets, then(a)A\(BU C)=(A\B)n(A\C), and(b)A(BnC)=(A\B)U(A\C) Proof.(a)2 parts (,→) Suppose T∈A\(B∪C). Then r∈ A and E(BUC).Thsr∈A and (a f B and a C). This implies a E A\B and a E A\C. But this is just .z∈(A\B)∩(AC (i) Suppose a∈(A\B)∩(4C). Then a∈(A\B)andr∈(AC) A and(a f B or a g f(BUC But this is just a∈A\(B∪C).■ Exercise 2.1.2 Finish the proof of Theorem 20 2.2 Cartesian Products There is another way to construct new sets out of given ones; it involves the tion of an"ordered pair"of objects. That is, in the set fa, b there preference given to a over b i.e. a, bf=(b, af so that it is an unordered pair. We can also consider ordered pairs(a, b)where we distinguish between the first and second elements 2 2Don't confuse this notation with the interval consisting of all real numbers such that
24 CHAPTER 2. SET THEORY 2.1.1 Algebraic properties of set operations The following commutative, associative, and distributive properties of sets are natural extensions of Theorem 1 and easily seen in Figure 2.1.2. Theorem 19 Let A, B, C be any sets. Then (i) (C) A ∩ B = B ∩ A, A∪B = B∪A;(ii) (A) (A∩B)∩C = A∩(B∩C), (A∪B)∪C = A∪(B∪C); and (iii) (D) A∩(B∪C)=(A∩B)∪(A∩C), A∪(B∩C)=(A∪B)∩(A∪C). Exercise 2.1.1 Prove Theorem 19.This amounts to applying the logical connectives and above definitions. Besides using Venn Diagrams, we can just use the definition of ∩ and ∪. For example,to show A∩B = B∩A, it is sufficient to note x ∈ A∩B ⇔ (x ∈ A) ∧ (x ∈ B) 1.1 ⇔ (x ∈ B) ∧ (x ∈ A) ⇔ x ∈ B ∩A. The following properties are used extensively in probability theory and are easily seen in Figure 2.1.3. Theorem 20 (DeMorganís Laws) If A, B, C are any sets, then (a) A\(B ∪ C)=(A\B) ∩ (A\C), and (b) A\(B ∩ C)=(A\B) ∪ (A\C). Proof. (a) 2 parts. (i,⇒) Suppose x ∈ A\(B ∪C). Then x ∈ A and x /∈ (B ∪C). Thus x ∈ A and (x /∈ B and x /∈ C). This implies x ∈ A\B and x ∈ A\C. But this is just x ∈ (A\B) ∩ (A\C). (ii,⇐) Suppose x ∈ (A\B) ∩ (A\C). Then x ∈ (A\B) and x ∈ (A\C). Thus x ∈ A and ( x /∈ B or x /∈ C). This implies x ∈ A and x /∈ (B ∪ C). But this is just x ∈ A\(B ∪ C). Exercise 2.1.2 Finish the proof of Theorem 20. 2.2 Cartesian Products There is another way to construct new sets out of given ones; it involves the notion of an ìordered pairî of objects. That is, in the set {a, b} there is no preference given to a over b;i.e. {a, b} = {b, a} so that it is an unordered pair. We can also consider ordered pairs (a, b) where we distinguish between the first and second elements.2 2Donít confuse this notation with the interval consisting of all real numbers such that a < x < b
2.3. RELATIONS 25 Definition 21 If A and B are nonempty sets, then the cartesian product ( denoted A x B) is just the set of all ordered pairs (a,b):aEA andbE Bl Example22A={1,2,3},B={4,5},A×B={(1,4),(1,5),(2,4),(2,5) (3,4),(3,5)} Example 23 A=[0, 1U2, 3,B=1, 2U 3, 4, A x B in Figure 2.2 This set operation also generalizes to finite and infinite index sets 2. 3 Relations To be able to compare elements of a set, we need to define how they are related. The general concept of a relation underlies all that will follow. For instance, just comparing the real numbers l and 2 requires such a definition Furthermore, a correspondence or function is just a special case of a relation In what follows, our definitions of relations, correspondences, and functions are meant to emphasize that they are simply special kinds of sets Definition 24 Given two sets A and B, a binary relation between mem bers of a and members of b is a subset R C Ax B. We use the notation (a, b)E R to denote the relation R on A xB and read it "a is in the relation R to b". If A=b we say that R is the relation on the set A Example 25 Let A=Austin, Des Moines, Harrisburg and B=Teras, Towa, Pennsylvania. Then the relation R=((Austin, Teras), (Des Moines, Iowa (Harrisburg, Pennsylvania) empresses "is the state capital of In general, we can consider n-nary relations between members of sets A1,A2,…, An which is just the subset R A1×A2×…×An A relation is characterized by a certain set of properties that it possesses We next consider important types of relations that differ in their symmetry roperties 2.3.1 Equivalence relations Definition 26 An equivalence relation on a set A is a relation n hav- ng the following three properties:(i) Reflexivity, a N T, VC E A;(ii) Sym metry, if n y, then y N a, V., y E A; and (iii) Transitivity, if r N y and y N 2, then Nz, V, y, 2 A
2.3. RELATIONS 25 Definition 21 If A and B are nonempty sets, then the cartesian product (denoted A×B) is just the set of all ordered pairs {(a, b) : a ∈ A and b ∈ B}. Example 22 A = {1, 2, 3}, B = {4, 5}, A × B = {(1, 4),(1, 5),(2, 4),(2, 5), (3, 4),(3, 5)}. Example 23 A = [0, 1] ∪ [2, 3], B = [1, 2] ∪ [3, 4], A × B in Figure 2.2.1 This set operation also generalizes to finite and infinite index sets. 2.3 Relations To be able to compare elements of a set, we need to define how they are related. The general concept of a relation underlies all that will follow. For instance, just comparing the real numbers 1 and 2 requires such a definition. Furthermore, a correspondence or function is just a special case of a relation. In what follows, our definitions of relations, correspondences, and functions are meant to emphasize that they are simply special kinds of sets. Definition 24 Given two sets A and B, a binary relation between members of A and members of B is a subset R ⊂ A × B. We use the notation (a, b) ∈ R to denote the relation R on A×B and read it ìa is in the relation R to bî. If A = B we say that R is the relation on the set A. Example 25 Let A = {Austin, Des Moines, Harrisburg} and B = {T exas, Iowa, P ennsylvania}. Then the relation R = {(Austin, T exas), (Des Moines, Iowa), (Harrisburg, P ennsylvania)} expresses ìis the state capital ofî. In general, we can consider n-nary relations between members of sets A1, A2, ..., An which is just the subset R ⊂ A1 × A2 × ... × An. A relation is characterized by a certain set of properties that it possesses. We next consider important types of relations that differ in their symmetry properties. 2.3.1 Equivalence relations Definition 26 An equivalence relation on a set A is a relation ë ∼0 having the following three properties: (i) Reflexivity, x ∼ x, ∀x ∈ A; (ii) Symmetry, if x ∼ y, then y ∼ x, ∀x, y ∈ A;and (iii) Transitivity, if x ∼ y and y ∼ z, then x ∼ z, ∀x, y, z ∈ A
CHAPTER 2. SET THEORY Example 27 Equality is an equivalence relation on R Example 28 Define the congruence modulo 4 relation Mon Z by V y E Z, My if remainders obtained by dividing and y by 4 are equal. For ex ample, 13M65 because dividing 13 and 65 by 4 give the same remainder of Exercise 2.3.1 Show that congruence modulo 4 is an equivalence relation. Definition 29 Given an equivalence relation N on a set A and an element E A, we define a certain subset e of a called the equivalence class de- termined by z by the equatione=yE A: y a. Note that the equivalence class determined by a contains since t3e Example 30 The equivalence classes of z for the relation congruence mod ulo4 are determined by a∈{0,1,2,3} ghere e={∈Z:z=4k+x,k∈Z (i. e. a is the remainder when z is divided by 4) Equivalence classes have the following property Theorem 31 Two equivalence classes e and E are either disjoint or equal. Proof.LetE={y∈A:y}andE={y∈A:yx}. Consider E∩E can be either empty (in which case E and E are disjoint )or nonempty. Let z∈E∩E. We show that e=E.Letw∈E. Then a^t. Since∈E∩E we know z r and z ' so that by transitivity z. also by transitivity wr' so that w EE. Thus E C E Symmetry allows us to conclude that ECE as well. Hence e=E".■ Given an equivalence relation on A, let us denote by 8 the collection of all equivalence classes. Theorem 31 shows that distinct elements of 8 are disjoint.On the other hand, the union of all the elements of 8 equals all of a because every element of A belongs to an equivalence class. In this case we say that E is a partition of A Definition 32 A partition of a set A is a collection of disjoint subsets of A whose union is all of a Example 33 It is clear that the equivalence classes of Z in Example(30)is a partition since, for instance, Eo=.,8,4,0,4,8,, E1=.,-5,-1, 1,5, E2={…,-6,-2,2,6,…},E3={…,-7,-3,3,7,…} are disjoint and their union is all of Z. Another simple example is a coin toss erperiment where the sample space S=Heads, Tails) has mutually exclusive events(i.eHeads Tail
26 CHAPTER 2. SET THEORY Example 27 Equality is an equivalence relation on R. Example 28 Define the congruence modulo 4 relation ëM0 on Z by ∀x, y ∈ Z, xMy if remainders obtained by dividing x and y by 4 are equal. For example, 13M65 because dividing 13 and 65 by 4 give the same remainder of 1. Exercise 2.3.1 Show that congruence modulo 4 is an equivalence relation. Definition 29 Given an equivalence relation ∼ on a set A and an element x ∈ A, we define a certain subset E of A called the equivalence class determined by x by the equation E = {y ∈ A : yòx}. Note that the equivalence class determined by x contains x since xòx. Example 30 The equivalence classes of Z for the relation congruence modulo 4 are determined by x ∈ {0, 1, 2, 3} where Ex = {z ∈ Z : z = 4k + x, k ∈ Z} (i.e. x is the remainder when z is divided by 4). Equivalence classes have the following property. Theorem 31 Two equivalence classes E and E0 are either disjoint or equal. Proof. Let E = {y ∈ A : yòx} and E0 = {y ∈ A : yòx0 }. Consider E ∩ E0 . It can be either empty (in which case E and E0 are disjoint) or nonempty. Let z ∈ E ∩ E0 . We show that E = E0 . Let w ∈ E. Then wòx. Since z ∈ E ∩ E0 , we know zòx and zòx0 so that by transitivity xòx0 . Also by transitivity wòx0 so that w ∈ E0 . Thus E ⊂ E. Symmetry allows us to conclude that E0 ⊂ E as well. Hence E = E0 . Given an equivalence relation on A, let us denote by E the collection of all equivalence classes. Theorem 31 shows that distinct elements of E are disjoint. On the other hand, the union of all the elements of E equals all of A because every element of A belongs to an equivalence class. In this case we say that E is a partition of A. Definition 32 A partition of a set A is a collection of disjoint subsets of A whose union is all of A. Example 33 It is clear that the equivalence classes of Z in Example (30) is a partition since, for instance, E0 = {..., −8, −4, 0, 4, 8, ...}, E1 = {..., −5, −1, 1, 5, ...}, E2 = {..., −6, −2, 2, 6, ...}, E3 = {..., −7, −3, 3, 7, ...} are disjoint and their union is all of Z. Another simple example is a coin toss experiment where the sample space S = {Heads, T ails} has mutually exclusive events (i.e.Heads∩ T ails = ∅)
2.3. RELATIONS 2.3.2 Order relations A relation that is reflexive and transitive but not symmetric is said to be an order relation. If we consider special types of non symmetry, we have special types of order relati Definition 34 A relation R' on A is said to be a partial ordering of a set A if it has the following properties:(i)Reflexivity, aRe, Vr E A;(ii) Antisymmetry, if r Ry and y Rr, then r=y, Va, y E A; and (iii) Transitivity, if Ry and y Rz, then aRx, V, y, t E A. We call(r, A)a partially ordered et PlA ple 35< is a partial ordering on R and c'is a partial ordering on P(A). It is clear that s is not symmetric on R; just take a =l and y=2 It is also clear that C is not symmetric on P(A); if A= a, b, then while La]c a it is not the case that A c a]. Finally, 'on R given by (r1, 12)3(91, y2)if x1 s y1 and c2 y2 is a partial ordering since it is clear that x is not symmetric on R x i because s is not symmetric even on R Definition 36 A partially ordered relation 'R' on a is said to be a total (or linear) ordering of A if (i) Completeness, for any two elements ,y E A we have either Ry or y Rc. We call(R, a)atotally ordered set. A chain in a partially ordered set is a subset on which the order is total Thus, a total ordering means that any two elements a and be compared, unlike a partial ordering where there are elements that are noncomparable Exercise 2.3.2 Show that if A b and b is totally ordered, then a is totally ordered. We write c <y if <y and x+y, and call''a strict partial or strict total ordering Example 37 "< is a strict total ordering on R while is a total ordering on R, both of which follow by the completeness ariom of real numbers. 'Cis not a total ordering on P(A)since if A=a, b, there is no inclusion relation between the sets a and b. < ' XR given in Example 35 is not a
2.3. RELATIONS 27 2.3.2 Order relations A relation that is reflexive and transitive but not symmetric is said to be an order relation. If we consider special types of non symmetry, we have special types of order relations. Definition 34 A relation ëRí on A is said to be a partial ordering of a set A if it has the following properties: (i) Reflexivity, xRx, ∀x ∈ A; (ii) Antisymmetry, if xRy and yRx, then x = y, ∀x, y ∈ A; and (iii) Transitivity, if xRy and yRz, then xRz, ∀x, y, z ∈ A. We call (R, A) a partially ordered set. Example 35 ë ≤í is a partial ordering on R and ë⊂í is a partial ordering on P(A). It is clear that ≤ is not symmetric on R; just take x = 1 and y = 2. It is also clear that ⊂ is not symmetric on P(A); if A = {a, b}, then while {a} ⊂ A it is not the case that A ⊂ {a}. Finally, ë-1í on R × R given by (x1, x2) -1 (y1, y2) if x1 ≤ y1 and x2 ≤ y2 is a partial ordering since it is clear that -1 is not symmetric on R × R because ≤ is not symmetric even on R. Definition 36 A partially ordered relation íRí on A is said to be a total (or linear) ordering of A if (i) Completeness, for any two elements x, y ∈ A we have either xRy or yRx.We call (R, A) a totally ordered set. A chain in a partially ordered set is a subset on which the order is total. Thus, a total ordering means that any two elements x and y in A can be compared, unlike a partial ordering where there are elements that are noncomparable. Exercise 2.3.2 Show that if A ⊂ B and B is totally ordered, then A is totally ordered. We write x ≺ y if x ¹ y and x 6= y, and call í≺í a strict partial or strict total ordering. Example 37 ì<í is a strict total ordering on R while í≤í is a total ordering on R, both of which follow by the completeness axiom of real numbers. ë⊂í is not a total ordering on P(A) since if A = {a, b}, there is no inclusion relation between the sets {a} and {b}. ë -1íon R × R given in Example 35 is not a
CHAPTER 2. SET THEORY total ordering because we can't compare elements where 1 yi and 2 23/2 However, a line passing through the origin having positive slope is a chain On the other hand, the relation 2' R given by(1, 2)32(91, 92) if 1<g or if 1=91 and 2 <92 is a total ordering. This is also known as a lexicographic ordering since the first element of the totally ordered set has the highest priority in determining the ordering just as the first letter of a word does in the ordering of a dictionary. We compare '<1'to 2' in Figure 2.3.1 for the following four elements a =(,1),y=(,2),2=(,)in IR XR. There are 3 pairwise comparisons for each relation. First consider 21,. We have a <y, a x z but y and z are not comparable under l', which is why we call it a partial ordering. Nert consider x where each pair is comparable(i.e. we have a <2a, a < y, and a < y) which is why we call it a total ordering. Notice that by transitivity they can be ranked (all can be placed in the dictionary There are other types of order relations Definition 38 A weak order relation assumes: (i) transitivity;(i)com pleteness; and(ii)non symmetry (just the negation of symmetry defined in 26.4 Weak order relations form the basis for consumer choice Example 39 Preference relations: We can represent consumer preferences by the binary relation defined on a non-empty, closed, conver consumptio set X. If(a, r2)Es or x z2 we say consumption bundle x' is at least as good as 2. We embody rationality or consistency by completeness and transitivity Exercise 2.3.3 Why aren't preference relations just total orderings Why are they weak orderings Show why indifference is an equivalence relation Because elements of a partially ordered set are not necessarily comparable it may be the case that a maximum and /or minimum of a two element set doesn t even exist, We turn to this next Dont be confused that we have left out a case (i.e. a1>y1) by considering only 1 yi or if a1 =91 and a2 y2. For instance, if the two elements we are considering are(2, 3)and(1, 7), simply take T=(1,7) (2, 3). The point is that any two real numbers can be compared using< Reflexivity is implied by completene nts show that transitivity is often violated
28 CHAPTER 2. SET THEORY total ordering because we canít compare elements where x1 ≤ y1 and x2 ≥ y2. However, a line passing through the origin having positive slope is a chain. On the other hand, the relation ë-2í on R × R given by (x1, x2) -2 (y1, y2) if x1 ≤ y1 or if x1 = y1 and x2 ≤ y2 is a total ordering.3 This is also known as a lexicographic ordering since the first element of the totally ordered set has the highest priority in determining the ordering just as the first letter of a word does in the ordering of a dictionary. We compare ë -1í to ë-2í in Figure 2.3.1 for the following four elements x = ° 1 4 , 1 4 ¢ , y = ° 1 2 , 1 2 ¢ , z = ° 1 4 , 3 4 ¢ in R × R. There are 3 pairwise comparisons for each relation. First consider ë -1í . We have x -1 y, x -1 z but y and z are not comparable under í-1í, which is why we call it a partial ordering. Next consider ë -2í where each pair is comparable (i.e. we have x -2 z, x -2 y, and z -2 y) which is why we call it a total ordering. Notice that by transitivity they can be ranked (all can be placed in the dictionary). There are other types of order relations. Definition 38 A weak order relation assumes: (i) transitivity; (ii) completeness; and (iii) non symmetry (just the negation of symmetry defined in 26. 4 Weak order relations form the basis for consumer choice. Example 39 Preference relations: We can represent consumer preferences by the binary relation % defined on a non-empty, closed, convex consumption set X. If (x1, x2) ∈% or x1 % x2 we say ìconsumption bundle x1 is at least as good as x2î. We embody rationality or consistency by completeness and transitivity.5 Exercise 2.3.3 Why arenít preference relations just total orderings? Why are they weak orderings? Show why indifference is an equivalence relation. Because elements of a partially ordered set are not necessarily comparable, it may be the case that a maximum and/or minimum of a two element set doesnít even exist. We turn to this next. 3Donít be confused that we have left out a case (i.e. x1 > y1) by considering only x1 ≤ y1 or if x1 = y1 and x2 ≤ y2. For instance, if the two elements we are considering are (2, 3) and (1, 7), simply take x = (1, 7) and y = (2, 3). The point is that any two real numbers can be compared using í≤í. 4Reflexivity is implied by completeness. 5Experiments show that transitivity is often violated