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