Sets and relations · Definition

Partial order relation

discrete mathematicsrelations

It formalizes the idea of «coming before» when not every two elements need to be comparable.

Definition

A relation \(\preceq\) on a set \(S\) that is reflexive, antisymmetric and transitive, and therefore orders some pairs of elements of \(S\).

\[a\preceq a;\quad (a\preceq b\ \wedge\ b\preceq a)\Rightarrow a=b;\quad (a\preceq b\ \wedge\ b\preceq c)\Rightarrow a\preceq c\]

Typical examples are \(\le\) on numbers, \(\subseteq\) between sets and divisibility \(\mid\) among positive integers. With \(\mid\) we have \(2\mid4\) and \(4\mid12\), hence \(2\mid12\); but neither \(2\mid3\) nor \(3\mid2\): two elements may be incomparable. Hence the word «partial».

When every pair of elements is also comparable, the order is called total and the elements line up in a single row, like the real numbers under \(\le\). The strict inequality \(<\) is not a partial order in this sense because it is not reflexive; it is obtained from \(\le\) by removing the pairs \((a,a)\).

An equivalence relation and an order relation share reflexivity and transitivity; they differ in that the first is symmetric and the second antisymmetric. A common mistake is to confuse antisymmetric with «not symmetric»: the equality relation is both symmetric and antisymmetric.

A set with a partial order is called a partially ordered set. To draw it without clutter one uses the Hasse diagram, and on it one defines maximal and minimum elements and bounds.

Think about it

Is equality \(=\) a partial order on a set \(S\)?

Yes: it is reflexive, antisymmetric and transitive. It is the order in which no two distinct elements are comparable.

Exercises 10

  1. Which of these relations on \(\mathbb{Z}\) is a partial order?
  2. Which partial-order property fails for \(R=\{(1,1),(2,2),(1,2),(2,1)\}\) on \(\{1,2\}\)?
  3. In \(\{1,2,3,4,6,12\}\) under divisibility, which pair of elements is incomparable?
  4. If \(\preceq\) is a partial order with \(a\preceq b\) and \(b\preceq a\), what follows?
  5. Why is \(<\) on \(\mathbb{Z}\) not a partial order?
  6. How many pairs \((a,b)\) with \(a,b\in\{1,\dots,6\}\) satisfy \(a\mid b\)?
  7. In \(\mathcal{P}(\{a,b\})\) under \(\subseteq\), how many pairs \((A,B)\) satisfy \(A\subsetneq B\)?
  8. \(R=\{(1,1),(2,2),(3,3),(1,2),(2,3)\}\) on \(\{1,2,3\}\) is not a partial order. Which pair suffices to add to make it one?
  9. How many different partial orders are there on the set \(\{1,2\}\)?
  10. How many partial orders on \(\{1,2,3\}\) compare every pair of elements?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §9.6
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §8.5
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §7.3