10 CHAPTER 1.PRELIMINARIES Example 1.18.Suppose that A =52) Then A defines a map from R2 to R2 by TA(x,）=(3x+,5x+2y): We can find an inverse map of TA by simply inverting the matrix A;that is,T=TA-1. In this example, A =（-53 hence,the inverse map is given by T(z,)=(2x-,-5x+3. It is easy to check that TAoTA(,y)=TAoTAl(,y)=(,y). Not every map has an inverse.If we consider the map TB(x,y）=(3x,0) given by the matrix 730 B=00) then an inverse map would have to be of the form TB(x,y)=(ax+by,cx+dy) and (e,)=ToTB(c,)=(3ax+3by,0) for all x and y.Clearly this is impossible because y might not be 0. Example 1.19.Given the permutation 3 231/ on S={1,2,3},it is easy to see that the permutation defined by 123 312 is the inverse of r.In fact,any bijective mapping possesses an inverse,as we will see in the next theorem. Theorem 1.20.A mapping is invertible if and only if it is both one-to-one and onto. PROOF.Suppose first that f:A-B is invertible with inverse g:B-A.Then gof idA is the identity map;that is,g(f(a))=a.If a1,a2 A with f(a1)=f(a2),then a1 =g(f(a1))=g(f(a2))=a2.Consequently,f is one-to-one.Now suppose that bE B. To show that f is onto,it is necessary to find an a E A such that f(a)=b,but f(g(b))=b with g(b)EA.Let a=g(b). Conversely,let f be bijective and let bE B.Since f is onto,there exists an aA such that f(a)=b.Because f is one-to-one,a must be unique.Define g by letting g(b)=a.We have now constructed the inverse of f. ▣
10 CHAPTER 1. PRELIMINARIES Example 1.18. Suppose that A = ( 3 1 5 2) . Then A defines a map from R 2 to R 2 by TA(x, y) = (3x + y, 5x + 2y). We can find an inverse map of TA by simply inverting the matrix A; that is, T −1 A = TA−1 . In this example, A −1 = ( 2 −1 −5 3 ) ; hence, the inverse map is given by T −1 A (x, y) = (2x − y, −5x + 3y). It is easy to check that T −1 A ◦ TA(x, y) = TA ◦ T −1 A (x, y) = (x, y). Not every map has an inverse. If we consider the map TB(x, y) = (3x, 0) given by the matrix B = ( 3 0 0 0) , then an inverse map would have to be of the form T −1 B (x, y) = (ax + by, cx + dy) and (x, y) = T ◦ T −1 B (x, y) = (3ax + 3by, 0) for all x and y. Clearly this is impossible because y might not be 0. Example 1.19. Given the permutation π = ( 1 2 3 2 3 1) on S = {1, 2, 3}, it is easy to see that the permutation defined by π −1 = ( 1 2 3 3 1 2) is the inverse of π. In fact, any bijective mapping possesses an inverse, as we will see in the next theorem. Theorem 1.20. A mapping is invertible if and only if it is both one-to-one and onto. Proof. Suppose first that f : A → B is invertible with inverse g : B → A. Then g ◦ f = idA is the identity map; that is, g(f(a)) = a. If a1, a2 ∈ A with f(a1) = f(a2), then a1 = g(f(a1)) = g(f(a2)) = a2. Consequently, f is one-to-one. Now suppose that b ∈ B. To show that f is onto, it is necessary to find an a ∈ A such that f(a) = b, but f(g(b)) = b with g(b) ∈ A. Let a = g(b). Conversely, let f be bijective and let b ∈ B. Since f is onto, there exists an a ∈ A such that f(a) = b. Because f is one-to-one, a must be unique. Define g by letting g(b) = a. We have now constructed the inverse of f
1.2.SETS AND EQUIVALENCE RELATIONS 11 Equivalence Relations and Partitions A fundamental notion in mathematics is that of equality.We can generalize equality with equivalence relations and equivalence classes.An equivalence relation on a set X is a relation RC XxX such that ·(x,x)∈R for all x∈X(reflexive property: ·(x,y）∈R implies(y,x)∈R(symmetric property): ·(r,y)and(y,z)∈R imply(x,z)∈R(transitive property). Given an equivalence relation R on a set X,we usually write ~y instead of (y)ER. If the equivalence relation already has an associated notation such as ==or we will use that notation. Example 1.21.Let p,q,r,and s be integers,where q and s are nonzero.Define p/q~r/s if ps gr.Clearly is reflexive and symmetric.To show that it is also transitive,suppose that p/g~r/s and r/s ~t/u,with q,s,and u all nonzero.Then ps gr and ru st. Therefore, psu gru qst. Since s≠0，pu=qt.Consequently,p/q~t/u. Example 1.22.Suppose that f and g are differentiable functions on R.We can define an equivalence relation on such functions by letting f(x)~g(z)if f(x)=g'(x).It is clear that is both reflexive and symmetric.To demonstrate transitivity,suppose that f(r)~g(z) and g(x)~h(x).From calculus we know that f(x)-g(x)=c1 and g(x)-h(x)=c2,where ci and c2 are both constants.Hence, f(x)-h(x)=(f(x)-g(x)+(g(x)-h(x)=c1-c2 and f'(x)-h'(x)=0.Therefore,f(x)~h(x). Example 1.23.For (z1,y1)and (x2,y2)in R2,define (x1,)(22,y2)if+=. Then is an equivalence relation on R2. Example 1.24.Let A and B be 2 x 2 matrices with entries in the real numbers.We can define an equivalence relation on the set of 2 x 2 matrices,by saying A~B if there exists an invertible matrix P such that PAP-1=B.For example,if then A~B since PAP-1 =B for Let I be the 2 x 2 identity matrix;that is, 1=0 0 Then IAI=IAI=A;therefore,the relation is reflexive.To show symmetry,suppose that A~B.Then there exists an invertible matrix P such that PAP-1=B.So A=P-BP=P-1B(P-1)-1
1.2. SETS AND EQUIVALENCE RELATIONS 11 Equivalence Relations and Partitions A fundamental notion in mathematics is that of equality. We can generalize equality with equivalence relations and equivalence classes. An equivalence relation on a set X is a relation R ⊂ X × X such that • (x, x) ∈ R for all x ∈ X (reflexive property); • (x, y) ∈ R implies (y, x) ∈ R (symmetric property); • (x, y) and (y, z) ∈ R imply (x, z) ∈ R (transitive property). Given an equivalence relation R on a set X, we usually write x ∼ y instead of (x, y) ∈ R. If the equivalence relation already has an associated notation such as =, ≡, or =∼, we will use that notation. Example 1.21. Let p, q, r, and s be integers, where q and s are nonzero. Define p/q ∼ r/s if ps = qr. Clearly ∼ is reflexive and symmetric. To show that it is also transitive, suppose that p/q ∼ r/s and r/s ∼ t/u, with q, s, and u all nonzero. Then ps = qr and ru = st. Therefore, psu = qru = qst. Since s ̸= 0, pu = qt. Consequently, p/q ∼ t/u. Example 1.22. Suppose that f and g are differentiable functions on R. We can define an equivalence relation on such functions by letting f(x) ∼ g(x) if f ′ (x) = g ′ (x). It is clear that ∼ is both reflexive and symmetric. To demonstrate transitivity, suppose that f(x) ∼ g(x) and g(x) ∼ h(x). From calculus we know that f(x)−g(x) = c1 and g(x)−h(x) = c2, where c1 and c2 are both constants. Hence, f(x) − h(x) = (f(x) − g(x)) + (g(x) − h(x)) = c1 − c2 and f ′ (x) − h ′ (x) = 0. Therefore, f(x) ∼ h(x). Example 1.23. For (x1, y1) and (x2, y2) in R 2 , define (x1, y1) ∼ (x2, y2) if x 2 1+y 2 1 = x 2 2+y 2 2 . Then ∼ is an equivalence relation on R 2 . Example 1.24. Let A and B be 2 × 2 matrices with entries in the real numbers. We can define an equivalence relation on the set of 2 × 2 matrices, by saying A ∼ B if there exists an invertible matrix P such that P AP −1 = B. For example, if A = ( 1 2 −1 1) and B = ( −18 33 −11 20) , then A ∼ B since P AP −1 = B for P = ( 2 5 1 3) . Let I be the 2 × 2 identity matrix; that is, I = ( 1 0 0 1) . Then IAI−1 = IAI = A; therefore, the relation is reflexive. To show symmetry, suppose that A ∼ B. Then there exists an invertible matrix P such that P AP −1 = B. So A = P −1BP = P −1B(P −1 ) −1
12 CHAPTER 1.PRELIMINARIES Finally,suppose that A~B and B~C.Then there exist invertible matrices P and Q such that PAP-1=B and QBQ-1 =C.Since C=QBQ-1=QPAP-IQ-1=(QP)A(QP)-1, the relation is transitive.Two matrices that are equivalent in this manner are said to be similar. A partition P of a set X is a collection of nonempty sets X1,X2,...such that XinXi= 0 for ij and UX=X.Let be an equivalence relation on a set X and let z E X. Then [x=y e X:y ~x}is called the equivalence class of x.We will see that an equivalence relation gives rise to a partition via equivalence classes.Also,whenever a partition of a set exists,there is some natural underlying equivalence relation,as the following theorem demonstrates. Theorem 1.25.Given an equivalence relation on a set X,the equivalence classes of X form a partition of X.Conversely,if P={Xih is a partition of a set X,then there is an equivalence relation on X with equivalence classes Xi. PROOF.Suppose there exists an equivalence relation on the set X.For any xX, the reflexive property shows that e [and so [is nonempty.Clearly X=Urex[]. Now let z,y X.We need to show that either [z]=[y]or []n ly]=0.Suppose that the intersection of [z]and ly]is not empty and that z []ny].Then z~z and ~y. By symmetry and transitivity ~y;hence,[x]C[y].Similarly,[y]C [and so []=ly]. Therefore,any two equivalence classes are either disjoint or exactly the same. Conversely,suppose that P ={Xi}is a partition of a set X.Let two elements be equivalent if they are in the same partition.Clearly,the relation is reflexive.If x is in the same partition as y,then y is in the same partition as r,so r~y implies y~x.Finally, if x is in the same partition as y and y is in the same partition as z,then x must be in the same partition as z,and transitivity holds. ▣ Corollary 1.26.Two equivalence classes of an equivalence relation are either disjoint or equal. Let us examine some of the partitions given by the equivalence classes in the last set of examples. Example 1.27.In the equivalence relation in Example 1.21,two pairs of integers,(p,q) and (r,s),are in the same equivalence class when they reduce to the same fraction in its lowest terms. Example 1.28.In the equivalence relation in Example 1.22,two functions f(x)and g(x) are in the same partition when they differ by a constant. Example 1.29.We defined an equivalence class on R2 by (1,y1)~(x2,y2)ify= x2+y.Two pairs of real numbers are in the same partition when they lie on the same circle about the origin. Example 1.30.Let r and s be two integers and suppose that n E N.We say that r is congruent to s modulo n,or r is congruent to s mod n,if r-s is evenly divisible by n; that is,r-s =nk for some k Z.In this case we write r =s (mod n).For example, 41 17 (mod 8)since 41-17 =24 is divisible by 8.We claim that congruence modulo n forms an equivalence relation of Z.Certainly any integer r is equivalent to itself since r-r =0 is divisible by n.We will now show that the relation is symmetric.If r=s
12 CHAPTER 1. PRELIMINARIES Finally, suppose that A ∼ B and B ∼ C. Then there exist invertible matrices P and Q such that P AP −1 = B and QBQ−1 = C. Since C = QBQ−1 = QP AP −1Q −1 = (QP)A(QP) −1 , the relation is transitive. Two matrices that are equivalent in this manner are said to be similar. A partition P of a set X is a collection of nonempty sets X1, X2, . . . such that Xi∩Xj = ∅ for i ̸= j and ∪ k Xk = X. Let ∼ be an equivalence relation on a set X and let x ∈ X. Then [x] = {y ∈ X : y ∼ x} is called the equivalence class of x. We will see that an equivalence relation gives rise to a partition via equivalence classes. Also, whenever a partition of a set exists, there is some natural underlying equivalence relation, as the following theorem demonstrates. Theorem 1.25. Given an equivalence relation ∼ on a set X, the equivalence classes of X form a partition of X. Conversely, if P = {Xi} is a partition of a set X, then there is an equivalence relation on X with equivalence classes Xi. Proof. Suppose there exists an equivalence relation ∼ on the set X. For any x ∈ X, the reflexive property shows that x ∈ [x] and so [x] is nonempty. Clearly X = ∪ x∈X[x]. Now let x, y ∈ X. We need to show that either [x] = [y] or [x] ∩ [y] = ∅. Suppose that the intersection of [x] and [y] is not empty and that z ∈ [x] ∩ [y]. Then z ∼ x and z ∼ y. By symmetry and transitivity x ∼ y; hence, [x] ⊂ [y]. Similarly, [y] ⊂ [x] and so [x] = [y]. Therefore, any two equivalence classes are either disjoint or exactly the same. Conversely, suppose that P = {Xi} is a partition of a set X. Let two elements be equivalent if they are in the same partition. Clearly, the relation is reflexive. If x is in the same partition as y, then y is in the same partition as x, so x ∼ y implies y ∼ x. Finally, if x is in the same partition as y and y is in the same partition as z, then x must be in the same partition as z, and transitivity holds. Corollary 1.26. Two equivalence classes of an equivalence relation are either disjoint or equal. Let us examine some of the partitions given by the equivalence classes in the last set of examples. Example 1.27. In the equivalence relation in Example 1.21, two pairs of integers, (p, q) and (r, s), are in the same equivalence class when they reduce to the same fraction in its lowest terms. Example 1.28. In the equivalence relation in Example 1.22, two functions f(x) and g(x) are in the same partition when they differ by a constant. Example 1.29. We defined an equivalence class on R 2 by (x1, y1) ∼ (x2, y2) if x 2 1 + y 2 1 = x 2 2 + y 2 2 . Two pairs of real numbers are in the same partition when they lie on the same circle about the origin. Example 1.30. Let r and s be two integers and suppose that n ∈ N. We say that r is congruent to s modulo n, or r is congruent to s mod n, if r − s is evenly divisible by n; that is, r − s = nk for some k ∈ Z. In this case we write r ≡ s (mod n). For example, 41 ≡ 17 (mod 8) since 41 − 17 = 24 is divisible by 8. We claim that congruence modulo n forms an equivalence relation of Z. Certainly any integer r is equivalent to itself since r − r = 0 is divisible by n. We will now show that the relation is symmetric. If r ≡ s
1.3.EXERCISES 13 (mod n),then r-s =-(s-r)is divisible by n.So s-r is divisible by n and s =r (mod n).Now suppose that r =s (mod n)and s=t (mod n).Then there exist integers k and I such that r-s=kn and s-t =In.To show transitivity,it is necessary to prove that r-t is divisible by n.However, r-t=r-s+s-t=kn+ln=(k+l)n, and so r-t is divisible by n. If we consider the equivalence relation established by the integers modulo 3,then [0={,-3,0,3,6,…}, [1={,-2,1,4,7,…}, [2={.,-1,2,5,8,.…} Notice that [O]U [1]U[2]=Z and also that the sets are disjoint.The sets [0],[1],and [2] form a partition of the integers. The integers modulo n are a very important example in the study of abstract algebra and will become quite useful in our investigation of various algebraic structures such as groups and rings.In our discussion of the integers modulo n we have actually assumed a result known as the division algorithm,which will be stated and proved in Chapter 2. 1.3 Exercises 1.Suppose that A={x:x∈N and x is even} B=fx:xE N and x is prime}, C=fx xE N and x is a multiple of 5h. Describe each of the following sets. (a)AnB (c)AUB (b)BnC (d)An(BUC) 2.If A=fa,b,c,B={1,2,3,C=fx},and D=0,list all of the elements in each of the following sets. (a)A×B (c)A×B×C (b)B×A (d)A×D 3.Find an example of two nonempty sets A and B for which A x B=B x A is true. 4.Prove AU0=A and An0=0. 5.Prove AUB=BUA and AnB=BnA. 6.Prove AU(BnC)=(AUB)n(AUC). 7.Prove A∩(BUC)=(A∩B)U(A∩C): 8.Prove A C B if and only if AnB=A. 9.Prove (AnB)'=A'UB'. 10.Prove AUB=(AnB)U(A\B)U(B\A)
1.3. EXERCISES 13 (mod n), then r − s = −(s − r) is divisible by n. So s − r is divisible by n and s ≡ r (mod n). Now suppose that r ≡ s (mod n) and s ≡ t (mod n). Then there exist integers k and l such that r − s = kn and s − t = ln. To show transitivity, it is necessary to prove that r − t is divisible by n. However, r − t = r − s + s − t = kn + ln = (k + l)n, and so r − t is divisible by n. If we consider the equivalence relation established by the integers modulo 3, then [0] = {. . . , −3, 0, 3, 6, . . .}, [1] = {. . . , −2, 1, 4, 7, . . .}, [2] = {. . . , −1, 2, 5, 8, . . .}. Notice that [0] ∪ [1] ∪ [2] = Z and also that the sets are disjoint. The sets [0], [1], and [2] form a partition of the integers. The integers modulo n are a very important example in the study of abstract algebra and will become quite useful in our investigation of various algebraic structures such as groups and rings. In our discussion of the integers modulo n we have actually assumed a result known as the division algorithm, which will be stated and proved in Chapter 2. 1.3 Exercises 1. Suppose that A = {x : x ∈ N and x is even}, B = {x : x ∈ N and x is prime}, C = {x : x ∈ N and x is a multiple of 5}. Describe each of the following sets. (a) A ∩ B (b) B ∩ C (c) A ∪ B (d) A ∩ (B ∪ C) 2. If A = {a, b, c}, B = {1, 2, 3}, C = {x}, and D = ∅, list all of the elements in each of the following sets. (a) A × B (b) B × A (c) A × B × C (d) A × D 3. Find an example of two nonempty sets A and B for which A × B = B × A is true. 4. Prove A ∪ ∅ = A and A ∩ ∅ = ∅. 5. Prove A ∪ B = B ∪ A and A ∩ B = B ∩ A. 6. Prove A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). 7. Prove A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). 8. Prove A ⊂ B if and only if A ∩ B = A. 9. Prove (A ∩ B) ′ = A′ ∪ B′ . 10. Prove A ∪ B = (A ∩ B) ∪ (A \ B) ∪ (B \ A)
14 CHAPTER 1.PRELIMINARIES 11.Prove(AUB)×C=(A×C)U(B×C). 12.Prove (AnB)\B=0. 13.Prove (AUB)\B=A\B. 14.Prove A\(BUC)=(A\B)n(A\C). 15.Prove An(B\C)=(AnB)\(AnC). 16. Prove (A\B)U(B\A)=(AUB)(AnB) 17.Which of the following relations f:QQ define a mapping?In each case,supply a reason why f is or is not a mapping. (a)f/g)=p+1 p-2 (c)f(p/q)=P+g 93 (b)fp/g)=3 p (d)f(p/q)= 3p2 P 7g2-q 18.Determine which of the following functions are one-to-one and which are onto.If the function is not onto,determine its range. (a)f R-R defined by f(x)=ez (b)f ZZ defined by f(n)=n2 +3 (c)f:R-R defined by f(x)=sinx (d)f:ZZ defined by f()=22 19.Let f:A->B and g:BC be invertible mappings;that is,mappings such that f-1 and g-1 exist.Show that (go f)-1=f-log-1. 20. (a)Define a function f:N-N that is one-to-one but not onto. (b)Define a function f:N->N that is onto but not one-to-one. 21.Prove the relation defined on R2 by (1,y)(x2,y2)if=is an equivalence relation. 22.Letf:A→B and g:B→C be maps.. (a)If f and g are both one-to-one functions,show that go f is one-to-one. (b)If go f is onto,show that g is onto. (c)If go f is one-to-one,show that f is one-to-one. (d)If go f is one-to-one and f is onto,show that g is one-to-one. (e)If go f is onto and g is one-to-one,show that f is onto. 23.Define a function on the real numbers by = What are the domain and range of f?What is the inverse of f?Compute f o f-l and f-lof. 24.Let f X-Y be a map with A1,A2 C X and B1,B2 CY
14 CHAPTER 1. PRELIMINARIES 11. Prove (A ∪ B) × C = (A × C) ∪ (B × C). 12. Prove (A ∩ B) \ B = ∅. 13. Prove (A ∪ B) \ B = A \ B. 14. Prove A \ (B ∪ C) = (A \ B) ∩ (A \ C). 15. Prove A ∩ (B \ C) = (A ∩ B) \ (A ∩ C). 16. Prove (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B). 17. Which of the following relations f : Q → Q define a mapping? In each case, supply a reason why f is or is not a mapping. (a) f(p/q) = p + 1 p − 2 (b) f(p/q) = 3p 3q (c) f(p/q) = p + q q 2 (d) f(p/q) = 3p 2 7q 2 − p q 18. Determine which of the following functions are one-to-one and which are onto. If the function is not onto, determine its range. (a) f : R → R defined by f(x) = e x (b) f : Z → Z defined by f(n) = n 2 + 3 (c) f : R → R defined by f(x) = sin x (d) f : Z → Z defined by f(x) = x 2 19. Let f : A → B and g : B → C be invertible mappings; that is, mappings such that f −1 and g −1 exist. Show that (g ◦ f) −1 = f −1 ◦ g −1 . 20. (a) Define a function f : N → N that is one-to-one but not onto. (b) Define a function f : N → N that is onto but not one-to-one. 21. Prove the relation defined on R 2 by (x1, y1) ∼ (x2, y2) if x 2 1 + y 2 1 = x 2 2 + y 2 2 is an equivalence relation. 22. Let f : A → B and g : B → C be maps. (a) If f and g are both one-to-one functions, show that g ◦ f is one-to-one. (b) If g ◦ f is onto, show that g is onto. (c) If g ◦ f is one-to-one, show that f is one-to-one. (d) If g ◦ f is one-to-one and f is onto, show that g is one-to-one. (e) If g ◦ f is onto and g is one-to-one, show that f is onto. 23. Define a function on the real numbers by f(x) = x + 1 x − 1 . What are the domain and range of f? What is the inverse of f? Compute f ◦ f −1 and f −1 ◦ f. 24. Let f : X → Y be a map with A1, A2 ⊂ X and B1, B2 ⊂ Y