6
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe you should point out that these are not "trivial examples" that you can show in five minutes. Most of these would require you to talk about the axiom of choice, and about topology and so on and so forth. This is why I picked my example, it's a nice trick that is easy to explain to anyone that already has a basic grasp in partial orders and set inclusion. $\endgroup$ – Asaf Karagila Aug 4 '14 at 22:35
  • $\begingroup$ Yeah these aren't the most trivial examples, but the OP did say 'interesting' and that's what I ran with. Since they asked this question late in the semester, I figured the discussion would be more of an overview anyway. @AsafKaragila while you're here, would you happen to know a reference which shows that the PBI theorem implies every partial order has a linear extension? I'm about to ask this as a question, if you don't. $\endgroup$ – Robert Wolfe Aug 4 '14 at 22:47
  • $\begingroup$ There are at least two proofs appearing on the site. At least one is by me. So no need to ask a duplicate question. $\endgroup$ – Asaf Karagila Aug 4 '14 at 22:48
  • $\begingroup$ @AsafKaragila ok thanks. I'll look. $\endgroup$ – Robert Wolfe Aug 4 '14 at 22:49
  • 1
    $\begingroup$ Look no further. And recall that BPI is equivalent to the compactness theorem of FOL. Also Brian does it directly from ultrafilters. $\endgroup$ – Asaf Karagila Aug 4 '14 at 22:50
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Just one question, I couldn't see at the first sight why this function is interesting or important, because it preserves order? $\endgroup$ – user42912 May 12 '14 at 19:00
  • $\begingroup$ Yes, because it means that we can think about every partial order as if it was sets ordered by inclusion. It also means that no matter how complicated a countable partial order is, it can be embedded into $\mathcal P(\Bbb N)$ ordered by inclusion. $\endgroup$ – Asaf Karagila May 12 '14 at 19:06
  • $\begingroup$ Can I say in some sense the properties and theorems which holds for sets holds for every partial order? $\endgroup$ – user42912 May 13 '14 at 8:32
  • $\begingroup$ I'm not sure what you mean by that. $\endgroup$ – Asaf Karagila May 13 '14 at 8:33
  • $\begingroup$ For example in the category of groups, if there were isomorphisms between $G_1$ and $G_2$ it means that $G_1$ and $G_2$ has the same group structure. For example using Cayley theorem I can say the theorems which holds for permutation groups holds for groups in general. $\endgroup$ – user42912 May 13 '14 at 8:40
1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.