Equivalence relations The preimage determines a function f"1: V(B) — » P(A). This splendid abuse of notation, however, don't confuse the preimage an inverse function. Inverse functions only exist when / is one- and onto. Furthermore, the domain of the preimage is the se subsets of B. We list some properties of the image and preim functions. The proofs are left to the reader. Proposition 1.2. Let f: A — B be a function and U, V subset B. Then 1) IfUcV, thenf-\U)cf-l{V). 2) f-1(UuV) = f-1(U)Uf-1(V). 3) r1(unv) = f-1(U)nf-1(v). 4) f{f-\U))cU. 5) ForXcA,Xcf-l{f{X)). 6) //, for any U C B, f{f~l{U)) = £7, then f is onto. 7) If, for any X C A, f~1(f(X)) — X, then f is one-one. Equivalence relations A significant notion in set theory is the equivalence relation. relation, R, is formally a subset of the set of pairs A x A, of a set We write x ~ y whenever (x, y) G R. Definition 1.3. A relation ~ is an equivalence relation if 1) For all x in A, x ~ x. (Reflexive) 2) If x ~ y, then y ~ x. (Symmetric) 3) If x ~ y and y ~ z, then x ~ z. (Transitive) Examples. (1) For any set A, the relation of equality = is an equ alence relation: No element is related to any other element exc itself. (2) Let A = Z, the set of integers with the usual sense of div ibility. Given a nonzero integer m, write k = / whenever m divi / — /c, denoted m \ I — k. Notice that m \ 0 = k — k so k = any k and = is reflexive. If m | I — h, then m \ — (I — k) — so that k = I implies / = k and = is symmetric. Finally, supp

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2006 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.