2.3. Relations 25 Exercise 2.3.10. Properly speaking, transitivity just gives the graph- ical interpretation “for any vertices x, y, z, if there is an edge from x to y and an edge from y to z, there is an edge from x to z.” Prove that this statement is equivalent to the (a priori more general) one given for transitivity above. We will consider two subsets of these properties that define classes of relations which are of particular importance. Definition 2.3.11. An equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The quintessential equivalence relation is equality, which is the relation consisting of only the reflexive pairs. What is special about an equivalence relation? We can take a quotient structure whose elements are equivalence classes. Definition 2.3.12. Let R be an equivalence relation on A. The equivalence class of some x A is the set [x] = {y A : R(x, y)}. Exercise 2.3.13. Let R be an equivalence relation on A and let x, y be elements of A. Prove that either [x] = [y] or [x] [y] = ∅. In short, an equivalence relation puts all the elements of the set into boxes so that each element is unambiguously assigned to a single box. All possible pairings from within each box are in the relation, and no pairings that draw from different boxes are in the relation. We can consider the boxes themselves as elements, getting a quotient structure. Definition 2.3.14. Given a set A and an equivalence relation R on A, the quotient of A by R, A/R, is the set whose elements are the equivalence classes of A under R. Now we can define cardinality more correctly. The cardinality of a set is the equivalence class it belongs to under the equivalence relation of bijectivity, so cardinalities are elements of the quotient of the collection of all sets under that relation. Exercise 2.3.15. Let A be the set {1, 2, 3, 4, 5}, and let R be the binary relation on A that consists of the reflexive pairs together with (1, 2), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), (5, 4).
Previous Page Next Page