Concept
What are partial orders and partially ordered sets?
Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1
"An endorelation that is (1) reflexive, (2) antisymmetric, and (3) transitive is called a partial order. A set together with a partial order is called a partially ordered set, or “poset” for short. The name “partial order” makes sense because it establishes a partial, but incomplete, hierarchy. Suppose D is the set of all dogs, with a relation “isAtLeastAsToughAs” between them. The relation starts with every reflexive pair, such as (Rex, Rex) and (Fido, Fido), because every dog is at least as tough as itself. Whenever two dogs x and y encounter each other, one of the ordered pairs is added to the relation: either (x, y) or (y, x), but never both. In this toy example, “isAtLeastAsToughAs” is reflexive because every dog was added with itself, antisymmetric because both directions are never added, and transitive because if Rex is tougher than Fido and Fido is tougher than Cuddles, then Rex would establish dominance over Cuddles. A partial order gives us some semblance of structure: the relation establishes directionality, and we are guaranteed not to get wrapped up in contradictions, but it does not completely order all the elements. There may be a lack of information. If Rex has never met Killer, and nobody Rex has met has ever met anyone Killer has met, there is no chain between them, so there is no way to know which is toughest. Likewise, if Rex established dominance over Cuddles and Killer also established dominance over Cuddles, those pairs alone do not tell us whether Rex or Killer is tougher. If a partial order completely orders all the elements, it is called a total order."
Related Ideas
- What do reflexivity, symmetry, and antisymmetry mean for endorelations?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What properties does the outranks relation have?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What is an endorelation?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What is a relation between two sets?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How are asymmetric, symmetric, and antisymmetric relations different?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How is membership in a relation written?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What is an infinite relation and how can it be specified?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- How are graphs related to sets?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1