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
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