1.2.SETS AND EQUIVALENCE RELATIONS 5 Example 1.1.Let R be the universal set and suppose that A={x∈R:0<x≤3}andB={x∈R:2≤x<4}. Then AnB={x∈R:2≤x≤3} AUB={x∈R:0<x<4} A\B={x∈R:0<x<2} A'={x∈R:x≤0orx>3}. Proposition 1.2.Let A,B,and C be sets.Then 1.AUA=A,AnA=A,and A\A=0; 2.AU0=A and An0=0; 3.AU(BUC)=(AUB)UC and An(BnC)=(AnB)nC; 4.AUB=BUA and AnB=BnA; 5.AU(B∩C)=(AUB)∩(AUC): 6.A∩(BUC)=(A∩B)U(A∩C) PROOF.We will prove (1)and (3)and leave the remaining results to be proven in the exercises. (1)Observe that AUA={x:x∈Aorx∈A} ={x:x∈A} =A and AnA={x:x∈A and x∈A} ={x:x∈A} =A. Also,A\A=AnA'=0. (3)For sets A,B,and C, AU(BUC)=AU{x:x∈Borx∈C} ={x:x∈Aorx∈B,orx∈C} ={x:x∈Aorx∈B}UC =(AUB)UC. A similar argument proves that An(BnC)=(A0 B)nC. O Theorem 1.3 De Morgan's Laws.Let A and B be sets.Then 1.(AUB)'=A'∩B; 2.(A∩B)'=A'UB
1.2. SETS AND EQUIVALENCE RELATIONS 5 Example 1.1. Let R be the universal set and suppose that A = {x ∈ R : 0 < x ≤ 3} and B = {x ∈ R : 2 ≤ x < 4}. Then A ∩ B = {x ∈ R : 2 ≤ x ≤ 3} A ∪ B = {x ∈ R : 0 < x < 4} A \ B = {x ∈ R : 0 < x < 2} A ′ = {x ∈ R : x ≤ 0 or x > 3}. Proposition 1.2. Let A, B, and C be sets. Then 1. A ∪ A = A, A ∩ A = A, and A \ A = ∅; 2. A ∪ ∅ = A and A ∩ ∅ = ∅; 3. A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C; 4. A ∪ B = B ∪ A and A ∩ B = B ∩ A; 5. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C); 6. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Proof. We will prove (1) and (3) and leave the remaining results to be proven in the exercises. (1) Observe that A ∪ A = {x : x ∈ A or x ∈ A} = {x : x ∈ A} = A and A ∩ A = {x : x ∈ A and x ∈ A} = {x : x ∈ A} = A. Also, A \ A = A ∩ A′ = ∅. (3) For sets A, B, and C, A ∪ (B ∪ C) = A ∪ {x : x ∈ B or x ∈ C} = {x : x ∈ A or x ∈ B, or x ∈ C} = {x : x ∈ A or x ∈ B} ∪ C = (A ∪ B) ∪ C. A similar argument proves that A ∩ (B ∩ C) = (A ∩ B) ∩ C. Theorem 1.3 De Morgan’s Laws. Let A and B be sets. Then 1. (A ∪ B) ′ = A′ ∩ B′ ; 2. (A ∩ B) ′ = A′ ∪ B′
6 CHAPTER 1.PRELIMINARIES PROOF.(1)If AU B=0,then the theorem follows immediately since both A and B are the empty set.Otherwise,we must show that (AU B)'C A'n B'and (AUB)A'n B'. Let z(AU B).Then x AUB.So x is neither in A nor in B,by the definition of the union of sets.By the definition of the complement,x A'and x B'.Therefore, xE A'n B'and we have (AUB)'C A'n B'. To show the reverse inclusion,suppose that x∈A'∩B'.Then x∈A'andx∈B',and so x A and x丰B.Thus z年AUB and so x∈(AUB)'.Hence.,(AUB)'pA'nB'and s0(AUB)'=A'∩B. The proof of(2)is left as an exercise. 口 Example 1.4.Other relations between sets often hold true.For example, (A\B)n(B\A)=0. To see that this is true,observe that (A\B)0(BA)=(A0B)0(BOA) =A∩A'nBnB =0. Cartesian Products and Mappings Given sets A and B,we can define a new set A x B,called the Cartesian product of A and B,as a set of ordered pairs.That is, A×B={(a,b):a∈A and b∈B}. Example 1.5.If A={,y),B={1,2,3},and C=0,then A x B is the set {(x,1),(,2),(x,3),(y,1),(y,2),(y,3)} and A×C=0. We define the Cartesian product of n sets to be A1×…×An={(a1,.,an):a∈Ai for i=1,.,n} IfA=A=A2=·=An,we often write Am for A×·×A(where A would be written n times).For example,the set R3 consists of all of 3-tuples of real numbers. Subsets of Ax B are called relations.We will define a mapping or function f C Ax B from a set A to a set B to be the special type of relation where (a,b)E f if for every element a E A there exists a unique element bB.Another way of saying this is that for every element in A,f assigns a unique element in B.We usually write f:AB or A B. Instead of writing down ordered pairs (a,b)EA x B,we write f(a)=b or f:ab.The set A is called the domain of f and f(A)={f(a):a∈A}CB is called the range or image of f.We can think of the elements in the function's domain as input values and the elements in the function's range as output values
6 CHAPTER 1. PRELIMINARIES Proof. (1) If A ∪ B = ∅, then the theorem follows immediately since both A and B are the empty set. Otherwise, we must show that (A ∪ B) ′ ⊂ A′ ∩ B′ and (A ∪ B) ′ ⊃ A′ ∩ B′ . Let x ∈ (A ∪ B) ′ . Then x ∈/ A ∪ B. So x is neither in A nor in B, by the definition of the union of sets. By the definition of the complement, x ∈ A′ and x ∈ B′ . Therefore, x ∈ A′ ∩ B′ and we have (A ∪ B) ′ ⊂ A′ ∩ B′ . To show the reverse inclusion, suppose that x ∈ A′ ∩ B′ . Then x ∈ A′ and x ∈ B′ , and so x ∈/ A and x ∈/ B. Thus x ∈/ A ∪ B and so x ∈ (A ∪ B) ′ . Hence, (A ∪ B) ′ ⊃ A′ ∩ B′ and so (A ∪ B) ′ = A′ ∩ B′ . The proof of (2) is left as an exercise. Example 1.4. Other relations between sets often hold true. For example, (A \ B) ∩ (B \ A) = ∅. To see that this is true, observe that (A \ B) ∩ (B \ A) = (A ∩ B ′ ) ∩ (B ∩ A ′ ) = A ∩ A ′ ∩ B ∩ B ′ = ∅. Cartesian Products and Mappings Given sets A and B, we can define a new set A × B, called the Cartesian product of A and B, as a set of ordered pairs. That is, A × B = {(a, b) : a ∈ A and b ∈ B}. Example 1.5. If A = {x, y}, B = {1, 2, 3}, and C = ∅, then A × B is the set {(x, 1),(x, 2),(x, 3),(y, 1),(y, 2),(y, 3)} and A × C = ∅. We define the Cartesian product of n sets to be A1 × · · · × An = {(a1, . . . , an) : ai ∈ Ai for i = 1, . . . , n}. If A = A1 = A2 = · · · = An, we often write An for A × · · · × A (where A would be written n times). For example, the set R 3 consists of all of 3-tuples of real numbers. Subsets of A×B are called relations. We will define a mapping or function f ⊂ A×B from a set A to a set B to be the special type of relation where (a, b) ∈ f if for every element a ∈ A there exists a unique element b ∈ B. Another way of saying this is that for every element in A, f assigns a unique element in B. We usually write f : A → B or A f→ B. Instead of writing down ordered pairs (a, b) ∈ A × B, we write f(a) = b or f : a 7→ b. The set A is called the domain of f and f(A) = {f(a) : a ∈ A} ⊂ B is called the range or image of f. We can think of the elements in the function’s domain as input values and the elements in the function’s range as output values
1.2.SETS AND EQUIVALENCE RELATIONS 7 A 心 2 b Figure 1.6:Mappings and relations Example 1.7.Suppose A={1,2,3}and B=fa,b,ch.In Figure 1.6 we define relations f and g from A to B.The relation f is a mapping,but g is not because 1E A is not assigned to a unique element in B;that is,g(1)=a and g(1)=b. Given a function f:A-B,it is often possible to write a list describing what the function does to each specific element in the domain.However,not all functions can be described in this manner.For example,the function f:R-R that sends each real number to its cube is a mapping that must be described by writing f(x)=z3 or f:x3. Consider the relation f:QZ given by f(p/g)=p.We know that 1/2 =2/4,but is f(1/2)=1 or 2?This relation cannot be a mapping because it is not well-defined.A relation is well-defined if each element in the domain is assigned to a unique element in the range. If f A->B is a map and the image of f is B,i.e.,f(A)=B,then f is said to be onto or surjective.In other words,if there exists an aA for each bB such that f(a)=b, then f is onto.A map is one-to-one or injective if a a2 implies f(a1)f(a2). Equivalently,a function is one-to-one if f(a1)=f(a2)implies a1 a2.A map that is both one-to-one and onto is called bijective. Example 1.8.Let f:Z-Q be defined by f(n)=n/1.Then f is one-to-one but not onto.Define g:Q-Z by g(p/q)=p where p/g is a rational number expressed in its lowest terms with a positive denominator.The function g is onto but not one-to-one. Given two functions,we can construct a new function by using the range of the first function as the domain of the second function.Let f:A-B and g:BC be mappings. Define a new map,the composition of f and g from A to C,by (go f)(x)=g(f(x))
1.2. SETS AND EQUIVALENCE RELATIONS 7 1 2 3 a b c 1 2 3 a b c A B A g B f Figure 1.6: Mappings and relations Example 1.7. Suppose A = {1, 2, 3} and B = {a, b, c}. In Figure 1.6 we define relations f and g from A to B. The relation f is a mapping, but g is not because 1 ∈ A is not assigned to a unique element in B; that is, g(1) = a and g(1) = b. Given a function f : A → B, it is often possible to write a list describing what the function does to each specific element in the domain. However, not all functions can be described in this manner. For example, the function f : R → R that sends each real number to its cube is a mapping that must be described by writing f(x) = x 3 or f : x 7→ x 3 . Consider the relation f : Q → Z given by f(p/q) = p. We know that 1/2 = 2/4, but is f(1/2) = 1 or 2? This relation cannot be a mapping because it is not well-defined. A relation is well-defined if each element in the domain is assigned to a unique element in the range. If f : A → B is a map and the image of f is B, i.e., f(A) = B, then f is said to be onto or surjective. In other words, if there exists an a ∈ A for each b ∈ B such that f(a) = b, then f is onto. A map is one-to-one or injective if a1 ̸= a2 implies f(a1) ̸= f(a2). Equivalently, a function is one-to-one if f(a1) = f(a2) implies a1 = a2. A map that is both one-to-one and onto is called bijective. Example 1.8. Let f : Z → Q be defined by f(n) = n/1. Then f is one-to-one but not onto. Define g : Q → Z by g(p/q) = p where p/q is a rational number expressed in its lowest terms with a positive denominator. The function g is onto but not one-to-one. Given two functions, we can construct a new function by using the range of the first function as the domain of the second function. Let f : A → B and g : B → C be mappings. Define a new map, the composition of f and g from A to C, by (g ◦ f)(x) = g(f(x))
8 CHAPTER 1.PRELIMINARIES A B 0 7 A Figure 1.9:Composition of maps Example 1.10.Consider the functions f:A-B and g:BC that are defined in Figure 1.9 (top).The composition of these functions,gof:A-C,is defined in Figure 1.9 (bottom). Example 1.11.Let f(x)=x2 and g(z)=2x+5.Then (fog)(x)=f(g(x)=(2x+5)2=4x2+20x+25 and (gof)(x)=g(f(x)=2x2+5. In general,order makes a difference;that is,in most cases foggof. Example 1.12.Sometimes it is the case that fog=go f.Let f(x)=x3 and g(x)=. Then (fog)(z)=f(g(z))=f()=()3=x and (gof)(x)=g(f(x)=9(x3)=3=x. Example 1.13.Given a 2 x 2 matrix we can define a map T R2-R2 by TA(x,y)=(ax+by,ca+dy) for(x,y)in R2.This is actually matrix multiplication;that is, a 2 e d u ax+by cx dy Maps from Rn to Rm given by matrices are called linear maps or linear transforma- tions
8 CHAPTER 1. PRELIMINARIES A B C 1 2 3 a b c X Y Z f g A C 1 2 3 X Y Z g ◦ f Figure 1.9: Composition of maps Example 1.10. Consider the functions f : A → B and g : B → C that are defined in Figure 1.9 (top). The composition of these functions, g ◦ f : A → C, is defined in Figure 1.9 (bottom). Example 1.11. Let f(x) = x 2 and g(x) = 2x + 5. Then (f ◦ g)(x) = f(g(x)) = (2x + 5)2 = 4x 2 + 20x + 25 and (g ◦ f)(x) = g(f(x)) = 2x 2 + 5. In general, order makes a difference; that is, in most cases f ◦ g ̸= g ◦ f. Example 1.12. Sometimes it is the case that f ◦ g = g ◦ f. Let f(x) = x 3 and g(x) = √3 x. Then (f ◦ g)(x) = f(g(x)) = f( √3 x ) = (√3 x ) 3 = x and (g ◦ f)(x) = g(f(x)) = g(x 3 ) = √3 x 3 = x. Example 1.13. Given a 2 × 2 matrix A = ( a b c d) , we can define a map TA : R 2 → R 2 by TA(x, y) = (ax + by, cx + dy) for (x, y) in R 2 . This is actually matrix multiplication; that is, ( a b c d) (x y ) = ( ax + by cx + dy) . Maps from R n to R m given by matrices are called linear maps or linear transformations
1.2.SETS AND EQUIVALENCE RELATIONS 9 Example1.l4.Suppose that S={1,2,3}.Define a mapπ：S→Sby π(1)=2， π(2)=1， π(3)=3. This is a bijective map.An alternative way to write r is 2 For any set S,a one-to-one and onto mapping S-S is called a permutation of S. Theorem1.l5.Letf:A→B,g:B→C,andh:C→D.Then 1.The composition of mappings is associative;that is,(hog)of=ho(gof); 2.If f and g are both one-to-one,then the mapping go f is one-to-one; 3.If f and g are both onto,then the mapping gof is onto; 4.If f and g are bijective,then so is go f. PROOF.We will prove (1)and(3).Part(2)is left as an exercise.Part(4)follows directly from (2)and (3). (1)We must show that ho(gof)=(hog)of. Fora∈A we have (ho(gof))(a)=h((gof)(a)) =h(g(f(a))) =(hog)(f(a)) =((hog)of)(a). (3)Assume that f and g are both onto functions.Given cC,we must show that there exists an a E A such that (go f)(a)=g(f(a))=c.However,since g is onto,there is an element b E B such that g(b)=c.Similarly,there is an a E A such that f(a)=b. Accordingly, (go f)(a)=g(f(a))=g(b)=c. ▣ If S is any set,we will use ids or id to denote the identity mapping from S to itself. Define this map by id(s)=s for all s∈S.A map g：B→A is an inverse mapping of f:A-B if go f idA and fog =idB;in other words,the inverse function of a function simply "undoes"the function.A map is said to be invertible if it has an inverse. We usually write f-1 for the inverse of f. Example 1.16.The function f(r)=23 has inverse f-1(x)=by Example 1.12. Example 1.17.The natural logarithm and the exponential functions,f(z)=Inx and f-1(x)=e",are inverses of each other provided that we are careful about choosing domains. Observe that f(f-(x))=f(ex)=Inex=x and f-1(f(z))=f-1(Inz)=elmz=x whenever composition makes sense
1.2. SETS AND EQUIVALENCE RELATIONS 9 Example 1.14. Suppose that S = {1, 2, 3}. Define a map π : S → S by π(1) = 2, π(2) = 1, π(3) = 3. This is a bijective map. An alternative way to write π is ( 1 2 3 π(1) π(2) π(3)) = ( 1 2 3 2 1 3) . For any set S, a one-to-one and onto mapping π : S → S is called a permutation of S. Theorem 1.15. Let f : A → B, g : B → C, and h : C → D. Then 1. The composition of mappings is associative; that is, (h ◦ g) ◦ f = h ◦ (g ◦ f); 2. If f and g are both one-to-one, then the mapping g ◦ f is one-to-one; 3. If f and g are both onto, then the mapping g ◦ f is onto; 4. If f and g are bijective, then so is g ◦ f. Proof. We will prove (1) and (3). Part (2) is left as an exercise. Part (4) follows directly from (2) and (3). (1) We must show that h ◦ (g ◦ f) = (h ◦ g) ◦ f. For a ∈ A we have (h ◦ (g ◦ f))(a) = h((g ◦ f)(a)) = h(g(f(a))) = (h ◦ g)(f(a)) = ((h ◦ g) ◦ f)(a). (3) Assume that f and g are both onto functions. Given c ∈ C, we must show that there exists an a ∈ A such that (g ◦ f)(a) = g(f(a)) = c. However, since g is onto, there is an element b ∈ B such that g(b) = c. Similarly, there is an a ∈ A such that f(a) = b. Accordingly, (g ◦ f)(a) = g(f(a)) = g(b) = c. If S is any set, we will use idS or id to denote the identity mapping from S to itself. Define this map by id(s) = s for all s ∈ S. A map g : B → A is an inverse mapping of f : A → B if g ◦ f = idA and f ◦ g = idB; in other words, the inverse function of a function simply “undoes” the function. A map is said to be invertible if it has an inverse. We usually write f −1 for the inverse of f. Example 1.16. The function f(x) = x 3 has inverse f −1 (x) = √3 x by Example 1.12. Example 1.17. The natural logarithm and the exponential functions, f(x) = ln x and f −1 (x) = e x , are inverses of each other provided that we are careful about choosing domains. Observe that f(f −1 (x)) = f(e x ) = ln e x = x and f −1 (f(x)) = f −1 (ln x) = e ln x = x whenever composition makes sense