Order Theory

Introduction

Order theory is a branch of mathematics that formalizes the concept of "order" using binary relations. The following sections introduce the basic definitions of this field.

Definitions

Binary Relations

Definition

A binary relation \(R\) on sets \(X\) and \(Y\) is defined as a tuple \((X,Y,G(R))\), where \(X\) is called the domain, \(Y\) is called the codomain, and \(G(R)\subseteq X\times Y=\{(x,y):x\in X,y\in Y\}\) is called the graph of the binary relation \(R\). The notation \(xRy\) holds if and only if \((x,y)\in G(R)\).

If \(X=Y\), the binary relation is called a homogeneous relation or endorelation.

Unless otherwise specified, the binary relations discussed below are homogeneous relations.

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

When studying binary relations, we often focus on whether they possess certain special properties. For a binary relation \(R\) on a set \(S\), we define the following special properties:

Reflexive: \((\forall~a \in S)~~aRa\),
Irreflexive (or anti-reflexive): \((\forall~a \in S)~~\lnot(aRa)\),
Symmetric: \((\forall~a,b \in S)~~aRb \iff bRa\),
Antisymmetric: \((\forall~a,b \in S)~~(aRb \land bRa) \implies a=b\),
Asymmetric: \((\forall~a,b \in S)~~aRb \implies \lnot(bRa)\),
Transitive: \((\forall~a,b,c \in S)~~(aRb \land bRc) \implies aRc\),
Connected: \((\forall~a,b \in S)~~a \neq b \implies (aRb \lor bRa)\),
Well-founded: \((\exists~m \in S \neq \varnothing)~~(\forall~a \in S\setminus\{m\})~~\lnot(aRm)\) (i.e., there exists a minimal element \(m\) in the non-empty set \(S\)),
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 said to be incomparable).

We also define some special binary relations:

Binary Relation	Reflexive	Irreflexive	Symmetric	Antisymmetric	Asymmetric	Transitive	Connected	Well-founded	Transitive of Incomparability
Equivalence relation	Yes		Yes			Yes
Preorder (quasiorder)	Yes					Yes
Partial order	Yes			Yes		Yes
Total order	Yes			Yes		Yes	Yes
Well-order	Yes			Yes		Yes	Yes	Yes
Strict preorder		Yes				Yes
Strict partial order		Yes			Yes	Yes
Strict weak order		Yes			Yes	Yes			Yes
Strict total order		Yes			Yes	Yes	Yes

Operations on Relations

For binary relations \(R\) and \(S\) on sets \(X\) and \(Y\), we can define the following operations:

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

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

Partially Ordered Sets

Definition

If a binary relation \(\preceq\) on a set \(S\) is reflexive, antisymmetric, and transitive, then \(S\) is called a partially ordered set (poset), and \(\preceq\) is a partial order on it.

If the partial order \(\preceq\) is also connected, it is called a total order, and the corresponding set is called a totally ordered set, linearly ordered set (loset), or simply ordered set.

It is easy to see that \(\mathbf{N}\), \(\mathbf{Z}\), \(\mathbf{Q}\), and \(\mathbf{R}\) are all totally ordered sets with respect to \(\leq\).

Visual Representation of Posets: Hasse Diagrams

For finite partially ordered sets, we can use Hasse diagrams to visually represent the partial order.

Definition

For a finite poset \(S\) with partial order \(\preceq\), define \(x\prec y\iff (x\preceq y\land x\neq y)\). The corresponding Hasse diagram is a graph \(G=\langle V,E\rangle\) satisfying:

\(V=S\),
\(E=\{(x,y)\in S\times S: x\prec y \land ((\nexists~z\in S)~~x\prec z\prec y)\}\)

For example, for the power set \(S\) of \(\{0,1,2\}\) and the set inclusion relation \(\subseteq\), the corresponding Hasse diagram is:

Since partial orders are antisymmetric, Hasse diagrams are necessarily directed acyclic graphs. Consequently, we can construct a total order for any finite poset via topological sorting.

Chains and Antichains

Definition

For a poset \(S\) with partial order \(\preceq\), a totally ordered subset of \(S\) is called a chain. If any two distinct elements in a subset \(T\) of \(S\) are incomparable (i.e., \((\forall~a,b \in T)~~a \neq b \implies (a \npreceq b \land b \npreceq a)\)), then \(T\) is called an antichain.

For a poset \(S\) with partial order \(\preceq\), the length of the longest antichain in \(S\) is called the width (or partial order width).

For example, for the power set \(S\) of \(\{0,1,2\}\) and the set inclusion 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 preordered sets, we can define concepts such as maximal (minimal) elements, upper (lower) bounds, and suprema (infima). These concepts can be generalized to other order relations.

Definition

For a preordered set \(S\) with preorder \(\preceq\), take an element \(m\) in \(S\):

If \((\forall~a \in S\setminus\{m\})~~\lnot(m\preceq a)\), then \(m\) is called a maximal element.
If for \(T \subseteq S\), \((\forall~t\in T)~~t\preceq m\), then \(m\) is called an upper bound of \(T\).
If \(m\) is an upper bound of \(T \subseteq S\) and for any upper bound \(n\) of \(T\), \(m \preceq n\) holds, then \(m\) is called the supremum of \(T\).

Similarly, we can define minimal element, lower bound, and infimum.

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

It can be shown that:

In a preordered set, maximal (minimal) elements, upper (lower) bounds, and suprema (infima) do not necessarily exist, and even if they exist, they may not be unique.
If a subset \(T\) of a poset \(S\) has a supremum (infimum), it is necessarily unique.

We denote the supremum and infimum of \(T\) as \(\sup T\) and \(\inf T\), respectively. If a poset \(S\) has both an upper bound and a lower bound, it is said to be bounded.

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

Zorn's Lemma

Zorn's Lemma, also known as the Kuratowski–Zorn Lemma, states: If every chain in a non-empty poset has an upper bound, then the 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 (infimum), it is unique. However, this does not necessarily apply to maximal (minimal) elements. For example, consider the poset \(S=\{\{0\},\{1\},\{2\},\{0,1\},\{0,2\},\{1,2\}\}\) with partial order \(\subseteq\). It has \(3\) maximal elements and \(3\) minimal elements.

We aim to impose additional conditions on posets to ensure that if maximal (minimal) elements exist, they are unique, thus allowing us to define the concepts of greatest (least) elements.

Directed Set

For a preordered set \(S\) with preorder \(\preceq\), if \((\forall~a,b\in S)~~(\exists~c\in S)~~a\preceq c\land b\preceq c\), then \(\preceq\) is called a direction on \(S\), and \(S\) is called a directed set or filtered set.

Sometimes a set \(S\) satisfying the above definition is called an upward directed set; similarly, we can define a downward directed set.

Directed sets can also be defined equivalently as follows:

Equivalent Definition of Directed Set

For a preordered set \(S\) with preorder \(\preceq\), if every finite subset \(T\) of \(S\) has an upper bound, then \(\preceq\) is called a direction on \(S\), and \(S\) is called a directed set.

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 the greatest element.
If a downward directed set has a minimal element, it is unique. We call the minimal element of a downward directed set the least element.

In a directed poset, for any elements \(a,b\), the set \(\{a,b\}\) has an upper bound. If we replace "upper bound" with "supremum", we obtain the definition of a join-semilattice.

For a poset \(S\) with partial order \(\preceq\):

Join-Semilattice

If for any elements \(a,b\) in \(S\), the set \(\{a,b\}\) has a supremum \(c\), then \(S\) is called a join-semilattice (or upper semilattice), and we call \(c\) the join of \(a\) and \(b\), denoted \(a\lor b\).

Meet-Semilattice

If for any elements \(a,b\) in \(S\), the set \(\{a,b\}\) has an infimum \(c\), then \(S\) is called a meet-semilattice (or lower semilattice), and we call \(c\) the meet of \(a\) and \(b\), denoted \(a\land b\).

Lattice

If \(S\) is both a join-semilattice and a meet-semilattice, then \(S\) is called a lattice.

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

Duality

In order theory, duality is a very common concept, such as the duality between maximal and minimal elements, upper and lower bounds, and suprema and infima.

For a poset \(P\) with partial order \(\preceq\), define its dual (or opposite) poset \(P^d\) such that \(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\) yields 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 dual theorems:

Dilworth's Theorem

The width of \(S\) (the length of the longest antichain) equals the minimum number of chains needed to cover \(S\).

Proof

Consider mathematical induction. When \(|S|\leq 3\), the proposition obviously holds.

Assume the proposition holds for all posets with fewer elements than \(|S|\). Let the width of \(S\) be \(d\). If all elements in \(|S|\) are incomparable, the proposition obviously holds. Otherwise, take a chain in \(S\) of length greater than \(1\), and denote its minimal element as \(m\) and maximal element as \(M\).

Let \(T=S\setminus\{m,M\}\). If the width of \(T\) is at most \(d-1\), then by the induction hypothesis, \(T\) can be covered by at most \(d-1\) chains. Consequently, \(S\) can be covered by these chains plus the chain \(\{m,M\}\), and the proposition holds. Otherwise, the width of \(T\) is also \(d\). Let \(A\) be a longest antichain in \(T\).

Consider the following two sets:

\[ S^+:=\{x\in S:(\exists~a\in A)~~a\preceq x\} \]

\[ S^-:=\{x\in S:(\exists~a\in A)~~x\preceq a\} \]

We can observe the following properties:

\(S^+\cup S^-=S\),
\(S^+\cap S^-=A\),
\(|S^+|<|S|\), \(|S^-|<|S|\) (since \(m\notin S^+\) and \(M\notin S^-\)).

Applying the induction hypothesis to both \(S^+\) and \(S^-\), the minimum chain cover number for each is \(d\), and these chains each contain exactly one element \(a\) from \(A\). Denote these chains as \(C_a^+\) and \(C_a^-\), respectively. Then \(\{C_a^-\cup\{a\}\cup C_a^+\}_{a\in A}\) is a minimum chain cover of \(S\), proving the proposition.

Mirsky's Theorem

The length of the longest chain in \(S\) equals the minimum number of antichains needed to cover \(S\).

Proof

Let the length of the longest chain in \(S\) be \(d\). By definition, the minimum antichain cover number is at least \(d\).

Let \(f(s)\) be the length of the longest chain with \(s\) as its minimal element. Note that if \(f(s)=f(t)\), then \(s\) and \(t\) are incomparable. Consequently, \((\forall~n\in\mathbf{N})~~f^{-1}(\{n\})\) are all antichains, where \(f^{-1}(\{n\}):=\{a\in S:f(a)=n\}\) is called a level set.

Therefore, it follows that \(\{f^{-1}(\{i\}):1\leq i\leq d\}\) is an antichain cover, so the minimum antichain cover number is at most \(d\).

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

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

Erdős–Szekeres Theorem

A real sequence \(\{a_i\}\) with at least \(rs+1\) elements either has a non-decreasing subsequence of length \(r+1\) or a non-increasing subsequence of length \(s+1\).

Proof

Let the sequence length be \(n\geq rs+1\). Define the poset \(\{(i,a_i)\}_{i=1}^{n}\) with partial order \(\preceq\) defined as:

\[ (i,a_i)\preceq (j,a_j)\iff (i\leq j\land a_i\leq a_j) \]

Assume the width of this poset is at most \(s\). By Dilworth's Theorem, the poset can be covered by at most \(s\) chains. If the length of each chain is at most \(r\), then the number of elements in the sequence is at most \(rs\), contradicting the condition.

Example Problems

Luogu P1020 [NOIP1999 Improvement Group] Missile Interception

A certain country has developed a missile interception system to defend against enemy missile attacks. However, this system has a flaw: while its first shell can reach any height, each subsequent shell cannot exceed the height of the previous one. One day, radar detects incoming enemy missiles. Since the system is still in the trial phase, only one set is available, so it might not intercept all missiles.

Given the heights of the incoming missiles in order, calculate the maximum number of missiles this system can intercept and the minimum number of such systems required to intercept all missiles.

For all data, the missile heights are positive integers not exceeding \(5\times 10^4\).

Solution

Let there be \(n\) missiles, with the height of the \(i\)-th missile being \(h_i\). Then the set \(\{(i,h_i)\}_{i=1}^{n}\) is a poset with partial order \(\preceq\) defined as:

\[ (i,h_i)\preceq(j,h_j) \iff (i\leq j \land h_i\geq h_j) \]

By Dilworth's Theorem, we have: The minimum number of non-increasing subsequences needed to cover the sequence equals the length of the longest increasing subsequence. Thus, the problem can be solved using the \(O(n\log n)\) approach for the longest non-decreasing subsequence.

Reference Code

#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;
}

[TJOI2015] Combinatorial Mathematics

Given an \(n \times m\) grid, each cell contains a certain number of treasures. Starting from the top-left corner, you can only move right or down. Each time you pass through a cell, you can pick up at most one treasure. Determine the minimum number of trips required to collect all treasures.

\(1\le n \le 1000\), \(1\le m \le 1000\), and each cell contains at most \(10^6\) treasures.

Solution

Ignoring the vertex weights of the grid, it is not hard to see that moving according to the given rules on the grid is equivalent to moving on a DAG. Thus, we can treat it as a Hasse diagram to construct a poset. By Dilworth's Theorem, we have: The minimum chain cover number of a DAG equals the size of the maximum independent set.

Therefore, the problem reduces to finding the maximum weighted independent set in the given grid.

Let \(a_{ij}\) be the weight of the grid at point \((i,j)\), and let \(f(i,j)\) be the answer for the subgrid from \((i,j)\) to \((1,m)\). Note that each point is non-adjacent to its upper-right neighbor. The state transition equation is:

\[ f(i,j)=\max\{f(i-1,j),f(i,j+1),f(i-1,j+1)+a_{ij}\} \]

The answer is \(f(n,1)\).

Reference Code

#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

Applications in C++

Also refer to: Sorting-related STL - Basic Algorithms.

Order theory is applied in C++ STL algorithms and data structures that require comparisons. We often need to define custom comparators in C++. The STL requires that comparators must define 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

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用