Orders
Orders and posets
Definition: a relation \(\sqsubseteq\) on a set \(P\) is called an order if it is reflexive, antisymmetric and transitive.
- The pair \((P, \sqsubseteq)\) is called a partially ordered set or for short poset.
- Two elements \(x\) and \(y\) in a poset \((P, \sqsubseteq)\) are called comparable if \(x \sqsubseteq y\) or \(y \sqsubseteq x\). The elements are incomparable if \(x \not\sqsubseteq y\) and \(y \not\sqsubseteq x\).
- If any two elements are comparable then the relation is called a linear order.
For example on the set of real numbers \(\mathbb{R}\) the relation \(\leq\) is an order relation. For any two numbers \(x,y \in \mathbb{R}\) we have \(x \leq y\) or \(y \leq x\). This makes \(\leq\) into a linear order.
Definition - Hasse diagram: let \((P, \sqsubseteq)\) be a poset. The graph with vertex set \(P\) and two vertices \(x,y \in P\) adjacent if and only if \(x \sqsubseteq y\) and there is no \(z \in P\) different from \(x\) and \(y\) with \(x \sqsubseteq z\) and \(z \sqsubseteq y\).
Maximal and minimal elements
Definition: let \((P, \sqsubseteq)\) be a partially ordered set and \(A \subseteq P\). An element \(a \in A\) is called the maximum (\(\top\)) of \(A\), if for all \(a' \in A\) we have \(a' \sqsubseteq a\). An element \(a \in A\) is called maximal if for all \(a' \in A\) we have that either \(a' \sqsubseteq a\) or \(a\) and \(a'\) are incomparable.
Similarly we can define the notion of minimum (\(\bot\)) and minimal element.
If we consider the poset of all subsets of a set \(S\) then the empty set \(\varnothing\) is the minimum of the poset, whereas the whole set \(S\) is the maximum. The atoms are the subsets of \(S\) containing just a single element.
Definition: if a poset \((P, \sqsubseteq)\) has a minimum \(\bot\), then the minimal elements of \(P\backslash \{\bot\}\) are called the atoms of \(P\).
Lemma: let \((P, \sqsubseteq)\) be a partially ordered set. Then \(P\) contains at most one maximum and one minimum.
Proof:
Suppose \(p,q \in P\) are maxima. Then \(p \sqsubseteq q\) as \(q\) is a maximum. Similarly \(q \sqsubseteq p\) as \(p\) is a maximum. By antisymmetry of \(\sqsubseteq\) we have \(p = q\).
Lemma: let \((P, \sqsubseteq)\) be a finite poset then \(P\) contains a minimal and a maximal element.
Proof:
Consider the directed graph associated to \((P, \sqsubseteq)\) and pick a vertex in this graph. If the vertex is not maximal, then there is an edge leaving it. Move along this edge to the neighbour. Repeat this as long as no maximal element is found. Since the graph contains no cycles, a vertex will never be met twice. Hence, as \(P\) is finite, the procedure has to stop. Implying a maximal element has been found. A minimal element of \((P, \sqsubseteq)\) is a maximal element of \((P, \sqsupseteq)\) and thus also exists.
Definition: if \((P, \sqsubseteq)\) is a poset and \(A \subseteq P\) then an upperbound for \(A\) is an element \(u\) with \(a \sqsubseteq u\) for all \(a \in A\). A lowerbound for \(A\) is an element \(u\) with \(u \sqsubseteq a\) for all \(a \in A\).
If the set of all upperbounds of \(A\) has a minimal element then this element is called the least upperbound or supremum of \(A\). Such an element is denoted by \(\mathrm{sup} A\).
If the set of all lowerbounds of \(A\) has a maximal element then this element is called the largest lowerbound or infimum of \(A\). Such an element is denoted by \(\mathrm{inf} A\).
For example let \(S\) be a set. In \((\wp(S), \subseteq)\) any set \(A\) of subsets of \(S\) has a least upperbound and an largest lowerbound. Indeed
If \((P, \sqsubseteq)\) is a finite poset then the elements from \(P\) can be ordered as \(p_1, p_2, \dots, p_n\) such that \(p_i \sqsubseteq p_j\) implies \(i < j\). This implies that the adjacency matrix of \(\sqsubseteq\) is uppertriangular, which means that it has only nonzero entries on or above the main diagonal.
Definition: an ascending chain in a poset \((P, \sqsubseteq)\) is a sequence \(p_1 \sqsubseteq p_2 \sqsubseteq \dots\) of elements \(p_i \in P,i \in \mathbb{N}\). A descending chain in \((P, \sqsubseteq)\) is a sequence \(p_1 \sqsupseteq p_2 \sqsupseteq \dots\) of elements \(p_i \in P, i \in \mathbb{N}\).
The poset \((P, \sqsubseteq)\) is called well founded if any descending chain is finite.