Something interesting about partial orders to show to my students

Question

I'm looking for some interesting examples or theorems about partial orders to show to my students, can be also some fundamental theorem such as an analogue of this theorem on equivalence relations.

Any help is welcome

Thanks

Answer 1

I suppose this depends on what is the general setting (finite, infinite, with the axiom of choice or without it). Here is one which I particularly like.

If $(A,\leq)$ is a partial order then there is a embedding $f$ from $A$ into $\mathcal P(A)$ such that $f(a)\subseteq f(b)\iff a\leq b$.

The function you can use for this is $f(a)=\{b\mid b\leq a\}$.

• This function is injective since if $f(a)=f(b)$ then $b\leq a$ and $a\leq b$, and so $a=b$.

• If $a\leq b$ then clearly $f(a)\subseteq f(b)$. On the other hand if $f(a)\subseteq f(b)$ then $a\in f(b)$ and so $a\leq b$.

Answer 2

I know of a couple of interesting examples of posets.

• Let $\Bbb N$ be collection of all natural numbers (including $0$). We can order $\Bbb N$ by divisibility. This poset is actually a complete lattice, and it's interesting that the top of this poset is $0$ and that the supremum of any infinite collection of numbers is also $0$.
• Suppose $X$ is a set. Let $\mathcal R$ denote all of the partial orderings for $X$. Given two partial orderings $\leq$ and $\sqsubseteq$ for $X$, we say that the partial ordering $\sqsubseteq$ extends the partial ordering $\leq$ if $x\leq y$ implies $x\sqsubseteq y$ for all $x$ and $y\in X$. Now we can actually equip $\mathcal R$ with a partial ordering. Namely, we say that $\leq$ is less than $\sqsubseteq$ if $\sqsubseteq$ extends $\leq$. (It is an interesting exercise to prove that the maximal elements in this poset are the linear orderings of $X$)
• Let $X$ and $Y$ be two sets. Given two partial functions $f$ and $g$ from $X$ to $Y$, let's say $f\leq g$ if the domain of $f$ is a subset of the domain of $g$ and $f(x)=g(x)$ for all $x$ in the domain of $f$. You can verify that $\leq$ is a partial ordering on the set of all partial functions from $X$ to $Y$.
• The previous example is particularly interesting when $X$ is a collection of non-empty sets and $Y=\bigcup X$ and we restrict our attention to those partial functions $f$ such that $f(A)\in A$ for each $A$ in its domain. In this case, we are ordering the set of all partial choice functions of $X$ by restriction. (This gives an easy proof of the Axiom of Choice from the Hausdorff Maximal Principle since this poset is chain-complete).
• (This is kind of an alternative to the previous result) Let $X$ be a collection of non-empty sets. Let $\mathcal C$ be the collection of all sets $T$ such that $T\subseteq\bigcup X$ and for each $A\in X$, $A\cap T$ consists of at most one element (such a $T$ is called a partial transversal of $X$). We can order $\mathcal C$ be inclusion. (This is chain-complete, and we get an easy proof that every collection of non-empty sets has a traversal by the HMP)
• Let $V$ be a vector space. You can order the set of all linearly-independent collections of vectors by inclusion. (This poset is also chain-complete, and you can get an easy proof that every vector space has a basis by the HMP)
• Let $(X,\leq)$ be a poset. Let $\mathcal C$ denote the collection of all subchains of $X$. You can order this collection by inclusion. (This poset is chain complete, thus it is inductive. From this collection you get an easy proof that Zorn's lemma implies the HMP)
• Let $(X,\leq)$ be a poset. Let $\mathcal A$ denote the collection of all antichains of $X$. You can order this collection by inclusion also. (This is also chain-complete, and (surprise) you get an easy proof that every poset has a maximal antichain by the HMP)
• Let $X$ be a set. Let $\mathcal W$ be the set of all elements of the form $(S,\leq)$ where $S$ is a subset of $X$, and $\leq$ is a well-ordering of $S$. Given two elements $(S,\leq)$ and $(T,\preceq)$ from $\mathcal W$, let's say that $(S,\leq)\sqsubseteq (T,\preceq)$ if $S\subseteq T$ and for each $x$ and $y\in S$ we have that $x\leq y$ implies $x\preceq y$. Succinctly, we say $(S,\leq)$ is less than $(T,\preceq)$ if $(T,\preceq)$ continues $(S,\leq)$. You can verify that $\sqsubseteq$ is a partial ordering for $\mathcal W$. (And guess what! It's chain-complete. From this you get an easy proof of the Well-Ordering theorem from the HMP)
• Let $\Bbb R[x]$ be the set of all real polynomials. Given two polynomials $f$ and $g$, let's say $f\sqsubseteq g$ if there exists an $x\in\Bbb R$ such that for all $y\geq x$ we have that $f(y)\leq g(y)$. It's an interesting exercise to show that $\sqsubseteq$ is a linear order on $\Bbb R[x]$. Overmore, $\sqsubseteq$ is compatible with the operation $+$ on polynomials. So that $(\Bbb R[x], +,\sqsubseteq)$ forms a linearly ordered group.
• The same thing applies to $\Bbb Q[x]$. However, there is a proposition which states that any countable, dense, linearly ordered set is (order-) isomorphic to a subset of $\Bbb Q$. So there is an order-preserving injection from $\Bbb Q[x]$ to $\Bbb Q$ since $\Bbb Q[x]$ is dense and countable. (Note that such a function cannot preserve addition between the two linearly-ordered groups. One is Archimedean while the other is not)
• Let $(X,\leq)$ be a poset. A subset $L\subseteq X$ is called a lower-set of $X$ if for all $x\in L$ whenever $y\in X$ such that $y\leq x$ then $y\in L$. Denote by $\mathcal O(X)$ the set of all lower-sets of $X$. We can order $\mathcal O(X)$ by inclusion. This new poset is in fact a complete lattice where infimums are given by intersections (except for the empty-set of lower-sets) and supremums by unions.
• Let $\Sigma^*$ denote the set of all finite binary strings. Given two binary strings $u$ and $v$, let's say that $u\leq v$ if $u$ is an initial substring of $v$. That $\leq$ is a partial order is clear. This same relation can be extended to $\Sigma^{**}$, the set of all countable binary strings. (Both of these posets are trees which are posets such that every lower set is well-ordered by $\leq$. You might take the time to prove to yourself that although $\Sigma^*$ is countable, it still has an uncountable number of maximal chains)
• The collection of all subgroups of a group forms a complete lattice. And the collection of normal subgroups forms a complete sublattice of the subgroup lattice. The set of all topologies over a set form a complete lattice. The set of all ideals in a ring also form a complete lattice.

I also know some interesting theorems.

• In every non-empty finite poset, every chain is contained in a maximal chain; every antichain is contained in a maximal antichain; every element is greater than (or equal to) some minimal element; every element is less than (or equal to) some maximal element. In particular, there are maximal chains, maximal antichains, minimal elements, and maximal elements.
• Let $(X,\leq)$ be a finite poset. Then there is another partial order $\sqsubseteq$ of $X$ which extends $\leq$ and such that $(X,\sqsubseteq)$ is a linear order. (Proof by induction)
• If you have the Axiom of Choice to work with, you can extend the last result to show that all partial orderings have a linear extension (sources say that this can be proven with just the Ultrafilter lemma or Boolean Prime Ideal theorem, but I'm having difficulty finding a proof. However, the principle that every set can be linearly ordered implies the Axiom of Choice for finite sets; you can show that).
• (Dilworth's Theorem) Let $(X,\leq)$ be a finite poset. Let $k$ denote the maximum cardinality that an antichain of $X$ can attain. Then $X$ can be partitioned into $k$ chains.
• (Other results of Dilworth) Let $(X,\leq)$ be a finite poset of cardinality $n$. For each $t>0$, either $X$ contains a chain of length greater than $t$ or an antichain of size at least $\lceil n/t\rceil$. Further, $X$ either contains a chain of length greater than $\sqrt{n}$ or an antichain of size at least $\lceil\sqrt{n}\rceil$.
• Every countable, dense, linear ordering is order isomorphic to a subset of $\Bbb Q$. This problem is actually addressed on this site here.
• There is a parallel between monotonic functions and continuous functions which isn't seen too often. Namely, given two posets $(X,\leq)$ and $(Y,\preceq)$ a function $f:X\rightarrow Y$ is monotonic if and only if for every lower-set $L\subseteq Y$ then $f^{-1}(L)$ is a lower-set of $X$. This can be explained by the fact that the lower-sets of a poset form a basis for a topology on the underlying set (they form an Alexandrov topology, in fact).
• (Tarski's Fixed-Point Theorem) Let $(X,\leq)$ be a complete poset. Then the set of fixed-points of any monotonic map $f:X\rightarrow X$ forms a complete sublattice of $X$ (in particular, there is a fixed-point). This theorem can be used to prove Schroeder-Bernstein.
• (Bourbaki-Witt Theorem) Let $(X,\leq)$ be a chain-complete poset. Let $f:X\rightarrow X$ be an inflationary map (that is $x\leq f(x)$ for all $x\in X$). Then $f$ has a fixed-point.
• (Tarski Converse) If $(X,\leq)$ is a poset such that every monotonic endomorphism has a fixed-point, then $(X,\leq)$ is a complete poset.
• Every countable, dense, linear-order without a top or bottom is order isomorphic to $\Bbb Q$. (typically uses Dependent choice; might be able to force Countable choice to give us what we want)
• A poset has the least-upper-bound property if and only if it has the greatest-lower-bound property.
• If $A$ and $B$ are two countable dense subsets of $\Bbb R$ then $\Bbb R-A$ is order-isomorphic to $\Bbb R - B$. (Sit on that for a moment. What if $A$ is the algebraic real numbers and $B$ is the rational numbers?)
• The $M_3$-$N_5$ theorem states that a lattice is not distributive if and only if it contains a sublattice isomorphic to either $M_3$ (the "diamond lattice") or $N_5$ (the "pentagon lattice"). And a lattice is not modular if and only if it contains a sublattice isomorphic to $N_5$.

This is quite a big list; I hope you found something interesting to think about and share with your students (sorry, I didn't see your question sooner). If you have any questions, let me know.

Answer 3

In a partial order, the following are equivalent:

• Every infinite sequence has an increasing pair. That is, for all $x_1, x_2, \ldots$, there exist $i < j$ such that $x_i \leq x_j$.
• Every infinite sequence has an infinite increasing subsequence. That is, for all $x_1, x_2, \ldots$, there exist $i_1 < i_2 < \ldots$ such that for all $k$, $x_{i_k} \leq x_{i_{k+1}}$.

(Either of these is the definition of a well-partial-order.)