2.3. Relations 27

(ii) Describe the equivalence relation on Z that gives rise to arith-

metic mod 12.

(iii) Let m, n, and p be integers. Prove that

n = m (mod 12) =⇒ n + p = m + p (mod 12).

This shows that addition of equivalence classes via representa-

tives is well-defined.

Our second important class of relations is partial orders.

Definition 2.3.20. A partial order ≤ on a set A is a binary relation

that is reflexive, antisymmetric, and transitive. A with ≤ is called a

partially ordered set, or poset.

In a poset, given two nonequal elements of A, either one is strictly

greater than the other or they are incomparable. If all pairs of ele-

ments are comparable, the relation is called a total order or linear

order on A.

Example 2.3.21. Let A = {a, b, c, d, e} and define ≤ on A as follows:

• (∀x ∈ A)(x ≤ x)

• a ≤ c, a ≤ d

• b ≤ d, b ≤ e

We could graph this as follows:

c

❂❂❂❂❂❂❂❂

d

❂❂❂❂❂❂❂❂

e

✁✁✁✁✁✁✁✁

a b

Technically, there are arrowheads pointing up and each element

has a loop, but for partial orders we often assume that.

In Example 2.3.21, the elements c and d have no upper bound:

no single element that is greater than or equal to both of them. We

might add elements f and g, augmenting the relation to include c ≤ f,

d ≤ f, d ≤ g, and e ≤ g (making the diagram vertically symmetric),

plus the necessary pairs to obtain transitivity (e.g., a ≤ f; this is

called taking the transitive closure). Then f is an upper bound for c