Order theory

Introduction

Order theory is the branch of mathematics that formalizes the concept of order using binary relations. This page introduces its basic definitions.

Definitions

Binary relations

For example, on $\mathbf{N}_+$, divisibility $\mid$ and less-than-or-equal-to $\leq$ are both binary relations.

When studying binary relations, we are often interested in whether they have certain special properties. For a set $S$ and a binary relation $R$ on it, define the following properties:

1. Reflexive: $(\forall~a \in S)~~aRa$,
2. Irreflexive (anti-reflexive): $(\forall~a \in S)~~\lnot(aRa)$,
3. Symmetric: $(\forall~a,b \in S)~~aRb \iff bRa$,
4. Antisymmetric: $(\forall~a,b \in S)~~(aRb \land bRa) \implies a=b$,
5. Asymmetric: $(\forall~a,b \in S)~~aRb \implies \lnot(bRa)$,
6. Transitive: $(\forall~a,b,c \in S)~~(aRb \land bRc) \implies aRc$,
7. Connected: $(\forall~a,b \in S)~~a \neq b \implies (aRb \lor bRa)$,
8. Well-founded: $(\exists~m \in S \neq \varnothing)~~(\forall~a \in S\setminus\{m\})~~\lnot(aRm)$ (that is, a nonempty set $S$ contains a minimal element $m$),
9. Transitive of incomparability: $(\forall~a,b,c \in S)~~(\lnot(aRb \lor bRa) \land \lnot(bRc \lor cRb)) \implies \lnot(aRc \lor cRa)$ (if $\lnot(aRb \lor bRa)$, then $a$ and $b$ are called incomparable).

We also define several special binary relations:

Operations on relations

For sets $X$ and $Y$, and binary relations $R$ and $S$ on them, we can define the following operations:

1. The union of $R$ and $S$, $R\cup S$, satisfies $G(R\cup S):=\{(x,y):xRy \lor xSy\}$ (for example, $\leq$ is the union of $<$ and $=$),
2. The intersection of $R$ and $S$, $R\cap S$, satisfies $G(R\cap S):=\{(x,y):xRy \land xSy\}$,
3. The complement of $R$, $\bar{R}$, satisfies $G(\bar{R}):=\{(x,y):\lnot(xRy)\}$,
4. The dual of $R$, $R^T$, satisfies $G(R^T):=\{(y,x):xRy\}$.

For sets $X$ and $Y$ with a binary relation $R$, and sets $Y$ and $Z$ with a binary relation $S$, we can define their composition $S\circ R$ by $G(S\circ R):=\{(x,z):(\exists~y\in Y)~~xRy\land ySz\}$.

Partially ordered sets

It is easy to see that $\mathbf{N}$, $\mathbf{Z}$, $\mathbf{Q}$, and $\mathbf{R}$ are all totally ordered sets under $\leq$.

Visual representation of a poset: Hasse diagrams

For a finite poset, we can use a Hasse diagram to visualize its partial order.

For example, for the power set $\{0,1,2\}$, denoted $S$, with the subset relation $\subseteq$, the corresponding Hasse diagram is:

Because a partial order is antisymmetric, a Hasse diagram is necessarily a directed acyclic graph. We can therefore construct a total order for any finite poset using topological sorting.

Chains and antichains

For example, for the power set $\{0,1,2\}$, denoted $S$, with the subset relation $\subseteq$, $\{\varnothing,\{1\},\{1,2\}\}$ is a chain, $\{\{1\},\{0,2\}\}$ is an antichain, and the width of $S$ is $3$.

Special elements in preordered sets

In a preordered set, we can define concepts such as maximal and minimal elements, upper and lower bounds, and suprema and infima. These concepts extend to other order relations.

For example, $1$ is a minimal element and a lower bound of $\mathbf{N}_+$.

It can be proved that:

• In a preordered set, maximal and minimal elements, upper and lower bounds, and suprema and infima need not exist; even when they exist, they need not be unique.

• If a poset $S$ has a subset $T$ with a supremum or infimum, it is unique.

  We denote the supremum and infimum of $T$ by $\sup T$ and $\inf T$, respectively. If a poset $S$ has both an upper bound and a lower bound, then $S$ is called bounded.

In an infinite poset, a maximal element need not exist. Zorn's Lemma can be used to determine whether an infinite poset has a maximal element.

Zorn's Lemma is equivalent to the axiom of choice and the well-ordering theorem.

Directed sets and lattices

We know that if a subset of a poset has a supremum or infimum, it is unique. This does not hold for maximal and minimal elements. For example, consider the poset $S=\{\{0\},\{1\},\{2\},\{0,1\},\{0,2\},\{1,2\}\}$ under the partial order $\subseteq$. It is easy to see that it has $3$ maximal elements and $3$ minimal elements.

We would like to add conditions to a poset so that whenever a maximal or minimal element exists, it is unique; this would let us define greatest and least elements.

Directed sets can also be defined as follows:

It is easy to see that:

• If an upward directed set has a maximal element, it is unique. We call the maximal element of an upward directed set its greatest element.
• If a downward directed set has a minimal element, it is unique. We call the minimal element of a downward directed set its least element.

In a directed poset, for any elements $a,b$, the set $\{a,b\}$ has an upper bound. Replacing “upper bound” with “supremum” gives the definition of a join-semilattice.

For a poset $S$ with partial order $\preceq$:

For example, the set of positive divisors of $60$, $S=\{1,2,3,4,5,6,10,12,15,20,30,60\}$, forms a poset under divisibility. For any positive integers $a,b$ in it, $\operatorname{lcm}(a,b)$ is the join of $a$ and $b$, while $\gcd(a,b)$ is the meet of $a$ and $b$, so $S$ is a lattice.

Duality

Duality is a common concept in order theory. Examples mentioned above include the duality between maximal and minimal elements, between upper and lower bounds, and between suprema and infima.

For a poset $P$ with partial order $\preceq$, define its dual (opposite) poset $P^d$ by: $x \preceq y$ holds in $P$ if and only if $y \preceq x$ holds in $P^d$. Reversing the edges of the Hasse diagram of $P$ gives the Hasse diagram of $P^d$.

Dilworth's theorem and Mirsky's theorem

For a finite poset $S$ with partial order $\preceq$, we have the following pair of dual theorems:

Dilworth's theorem is equivalent to Hall's marriage theorem.

We can use Dilworth's theorem to prove the following theorem:

Examples

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> a;
  int x;
  while (cin >> x) a.push_back(x);
  vector<int> f, g;
  for (int i : a) {
    if (f.empty() || -i >= f.back())
      f.push_back(-i);
    else
      *upper_bound(f.begin(), f.end(), -i) = -i;
    if (g.empty() || i > g.back())
      g.push_back(i);
    else
      *lower_bound(g.begin(), g.end(), i) = i;
  }
  cout << f.size() << '\n' << g.size() << '\n';
  return 0;
}

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int t = 0;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<vector<int64_t>> a(n, vector<int64_t>(m));
    for (auto &i : a)
      for (auto &j : i) cin >> j;
    vector<vector<int64_t>> f(n, vector<int64_t>(m));
    for (int i = 0; i < n; ++i)
      for (int j = m - 1; j >= 0; --j)
        f[i][j] =
            max({(i == 0 ? 0 : f[i - 1][j]), (j == m - 1 ? 0 : f[i][j + 1]),
                 (i == 0 || j == m - 1 ? 0 : f[i - 1][j + 1]) + a[i][j]});
    cout << f[n - 1][0] << '\n';
  }
  return 0;
}

Exercises

• [CTSC2008] Sacrifice
• CodeForces 590E Birthday

Applications in C++

See also: STL related to sorting — Basic algorithms.

The C++ STL algorithms and data structures requiring comparisons apply order theory. We often need to define custom comparators in C++; the STL requires them to be a strict weak order. Let $<$ be a custom comparator; then we can define:

• $x>y$ as $y<x$;
• $x \leq y$ as $y \nless x$;
• $x \geq y$ as $x \nless y$;
• $x=y$ as $x \nless y\land y \nless x$.

References and further reading

1. Order theory - From Academic Kids
2. Binary Relation - Wikipedia
3. Order Theory - Wikipedia
4. Hasse diagram - Wikipedia
5. Directed set - Wikipedia
6. Order Theory, Lecture Notes by Mark Dean for Decision Theory
7. Kaicheng Lu, Huaming Lu, Combinatorics (3rd ed.), 2006
8. List of Order Theory Topics - Wikipedia
9. A discussion of applications of adjacent-swap sorting and points to note by ouuan
10. One thing you should know about comparators—Strict Weak Ordering
11. Dilworth's theorem - Wikipedia
12. Dilworth's Theorem | Brilliant Math & Science Wiki
13. Hall's marriage theorem - Wikipedia
14. Hall's Marriage Theorem | Brilliant Math & Science Wiki
15. Dilworth study notes - Selfish