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