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