# Dilworth's Theorem and Mirsky's Theorem for Infinite Posets?

I know that there is an infinite partially ordered set that violates Dilworth's Theorem and one that violates Mirsky's Theorem. Unfortunately, I do not have access to the references for these counterexamples. I have a few questions.

1. Can somebody please provide an explicit counterexample for each theorem?

2. I would like to know if there is an infinite partially ordered set that violates both theorems. I am curious whether these theorems are true duals in the sense that a partially ordered set satisfies one of them if and only if it satisfies both.

Let me call a partially ordered set $$P$$ Dilworth if the width of $$P$$ (i.e., the supremum of the cardinalities of antichains in $$P$$) is the same as the smallest cardinal number $$c$$ such that there exists a family $$\mathcal{C}$$ of chains in $$P$$ such that $$P=\bigcup\mathcal{C}$$ and $$|\mathcal{C}|=c$$. A partially ordered set $$P$$ is Mirsky if the height of $$P$$ (i.e., the supremum of the cardinalities of chains in $$P$$) is the same as the smallest cardinal number $$a$$ such that there exists a family $$\mathcal{A}$$ of antichains in $$P$$ such that $$P=\bigcup\mathcal{A}$$ and $$|\mathcal{A}|=a$$.

For example, finite and countably infinite partially ordered sets are both Dilworth and Mirsky. More generally, a partially ordered set of finite width is Dilworth, whereas a partially ordered set of finite height is Mirsky. That is, the questions above can be rephrased as follows.

1. Please give me an example of a non-Dilworth partially ordered set and an example of a non-Mirsky partially ordered set.

2. Is there a partially ordered set which is simultaneously non-Dilworth and non-Mirsky? Does it hold that a partially ordered set is Dilworth if and only if it is Mirsky?

• A problem with your definitions is that the maximum cardinality of a chain (or antichain) does not necessarily exist, e.g., a poset may have a chain (or antichain) of cardinality $n$ for every finite $n$ but no infinite chain (or antichain). Would you like to rephrase your question in terms of suprems? – bof Apr 29 '17 at 2:31
• Yes, that is what I meant. Thanks for pointing this out. – Batominovski Apr 29 '17 at 6:40
• However there is no need to change "minimum" to "infimum" because cardinal numbers are well-ordered (assuming the axiom of choice of course). I have edited your question to change this back and to improve the English grammar. – bof Apr 29 '17 at 7:07

## 1 Answer

1a. Let $\kappa$ be an uncountable cardinal. Partially order the Cartesian product $P_\kappa=\kappa\times\kappa$ so that $$\langle\alpha,\beta\rangle\le\langle\alpha',\beta'\rangle\iff\alpha\le\alpha'\ \text{ and }\ \beta\le\beta'.$$ Then every antichain in $P_\kappa$ is finite, but $P_\kappa$ is not the union of $\lt\kappa$ chains. As $P_\kappa$ has cardinality $\kappa$ and height $\kappa,$ it is Mirsky but not Dilworth.

1b. Let $\kappa$ be an uncountable cardinal. Partially order the Cartesian product $Q_\kappa=\kappa\times\kappa$ so that $$\langle\alpha,\beta\rangle\lt\langle\alpha',\beta'\rangle\iff\alpha\lt\alpha'\ \text{ and } \beta\gt\beta'.$$ then every chain in $Q_\kappa$ is finite, but $Q_\kappa$ is not the union of $\lt\kappa$ antichains. As $Q_\kappa$ has cardinality $\kappa$ and width $\kappa,$ it is Dilworth but not Mirsky.

2a. If all chains and antichains in a partially ordered set $P$ are finite, then $P$ is finite by Ramsey's theorem. However, there is a poset $P$ of cardinality $2^{\aleph_0}$ in which all chains and antichains are countable; of course such a $P$ is not the union of countably many chains or antichains, so it is neither Dilworth not Mirsky. The example is due to Sierpiński: take the intersection of two linear orderings of $\mathbb R,$ the usual ordering and a well-ordering.

2b. I've already given natural examples of posets which are Mirsky but not Dilworth or Dilworth but not Mirsky. Still, it may be worth pointing out that, given a poset $P$ which is neither Dilworth nor Mirsky, we can trivially make it Mirsky-but-not-Dilworth by adjoining a large chain, or make it Dilworth-but-not-Mirsky by adjoining a large antichain.

Of course, any poset of finite height or width is both Dilworth and Mirsky.