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
Previous Page Next Page