6
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ – bof Apr 29 '17 at 2:31
  • $\begingroup$ Yes, that is what I meant. Thanks for pointing this out. $\endgroup$ – Batominovski Apr 29 '17 at 6:40
  • 1
    $\begingroup$ 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. $\endgroup$ – bof Apr 29 '17 at 7:07
5
$\begingroup$

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.

$\endgroup$
0

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.