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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.