Partial Order Relation

A partial order relation is a binary relation that is a transitive relation and an antisymmetric relation.

• AKA: Partial Ordering.
• Context:
  • It can range from being a Weak Partial Order (when also a reflexive relation) to being a Strict Partial Order (when also an irreflexive relation).
  • It can range from being a Total Partial Order Relation to being a Non-Total Partial Order.
  • It can be associated (express a linear order) to a Partially Ordered Set (a poset).
• Example(s):
  • Ord(1,3) ⇒ True.
  • Ord(3,1) ⇒ False.
  • The GreaterThan relation.
  • The GreaterThanOrEqualTo relation.
  • The relation between items in an ordered dataset.
  • …
• Counter-Example(s):
  • Ord(apple, orange) ⇒ True.
  • A Symmetric Relation.
  • A Reflexive Relation.
  • An Antitransitive Relation.
• See: Order Relation, Strict Order Relation, Hasse Diagram, Sorting Task.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Glossary_of_order_theory#P Retrieved:2015-6-14.
  • Partial order. A partial order is a binary relation that is reflexive, antisymmetric, and transitive. In a slight abuse of terminology, the term is sometimes also used to refer not to such a relation, but to its corresponding partially ordered set.
  • Partially ordered set. A partially ordered set (P, ≤), or poset for short, is a set P together with a partial order ≤ on P.
  • Poset. A partially ordered set.

2009

• http://en.wiktionary.org/wiki/partial_order
  • 1. (set theory) A relation that is reflexive, antisymmetric, and transitive.
  • Synonym: partial ordering relation
  • Related terms

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Partially_ordered_set
  • In mathematics, especially order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that describes, for certain pairs of elements in the set, the requirement that one of the elements must precede the other. However, a partially ordered set differs from a total order in that some pairs of elements may not be related to each other in this way. A finite poset can be visualized through its Hasse diagram, which depicts the ordering relation between certain pairs of elements and allows one to reconstruct the whole partial order structure.
  • A familiar real-life example of a partially ordered set is a collection of people ordered by genealogical descendancy. Some pairs of people bear the ancestor-descendant relationship, but other pairs bear no such relationship.
  • A partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., for all a, b, and c in P, we have that:
    • a ≤ a (reflexivity);
    • if a ≤ b and b ≤ a then a = b (antisymmetry);
    • if a ≤ b and b ≤ c then a ≤ c (transitivity).
  • In other words, a partial order is an antisymmetric preorder.
  • A set with a partial order is called a partially ordered set (also called a poset). The term ordered set is sometimes also used for posets, as long as it is clear from the context that no other kinds of orders are meant. In particular, totally ordered sets can also be referred to as "ordered sets", especially in areas where these structures are more common than posets.
  • Examples
    • The real numbers ordered by the standard less-than-or-equal relation ≤ (a totally ordered set as well).
    • The set of natural numbers equipped with the relation of divisibility.
    • The set of subsets of a given set (its power set) ordered by inclusion (see the figure on top-right).
    • The set of subspaces of a vector space ordered by inclusion.
    • For a partially ordered set P, the sequence space containing all sequences of elements from P, where sequence a precedes sequence b if every item in a precedes the corresponding item in b. Formally, (a_n)_{n\in\mathbf{N}} \le (b_n)_{n\in\mathbf{N}} if and only if a_n \le b_n for all n in N.
    • For a set X and a partially ordered set P, the function space containing all functions from X to P, where f ≤ g if and only if f(x) ≤ g(x) for all x in X.
    • The vertex set of a directed acyclic graph ordered by reachability.
    • A fence, a partially ordered set defined by an alternating sequence of order relations a < b > c < d ...
  • Extrema There are several notions of "greatest" and "least" element in a poset, notably:
    • Greatest element and least element
    • Maximal elements and minimal elements
    • Upper and lower bounds

• A Hasse Diagram.
  • http://upload.wikimedia.org/wikipedia/commons/e/ea/Hasse_diagram_of_powerset_of_3.svg

---