Partial Orders & Total Orders

Math for CS · Axiom Academy

Structuring sets with "less than or equal to" -- hierarchies, Hasse diagrams, and lattices Where equivalence relations capture "sameness," partial orders capture "hierarchy." A partial order formalizes the idea that some elements come before others -- but not every pair needs to be comparable. Antisymmetric: If a b and b a , then a = b Transitive: If a b and b c , then a c On the positive integers, define a b ("a divides b") as: there exists an integer k such that b = ak . Reflexive: a a because a = a 1 Antisymmetric: If a b and b a , then b = ak and a = bj , so a = akj , giving kj = 1 . For positive integers, k = j = 1 , so a = b . Transitive: If a b and b c , then b = ak and c = bj = akj , so a c . This is a partial order because not all pairs are comparable: 3 and 5 are incomparable since neither divides the other. For any set S , the power set (S) with forms a partial order. \ 1\ \ 1,2\ -- these are comparable \ 1\ and \ 2\ are incomparable -- neither is a subset of the other In CS, type hierarchies and class inheritance form partial orders under subtyping. A Hasse diagram is a compact visual representation of a partial order. You draw the elements as nodes, with edges going upward to represent the ordering -- but you omit edges that can be inferred by transitivity. If a b and there is no c with a c b (i.e., b "covers" a ), draw an edge from a up to b Omit self-loops (reflexive edges) Omit transitive edges (they can be recovered by following paths)

This is the written version of the interactive lesson above. See the full Math for CS course.