11
$\begingroup$

It is known that given an infinite poset, it always contains an infinite chain or antichain; moreover, there is a constructive proof that we can find a continuous chain in $P(\mathbb{N})$; so, in general, I'm asking if given a poset of a certain cardinality, we could always find a chain or antichain of the same cardinality.

$\endgroup$
3
  • 1
    $\begingroup$ Maybe off topic. What is a "continuous chain"? $\endgroup$
    – Srivatsan
    Commented Sep 14, 2011 at 0:47
  • 2
    $\begingroup$ @Srivatsan, in this case it seems to mean a chain of cardinality $2^{\aleph_0}$. $\endgroup$ Commented Sep 14, 2011 at 1:24
  • $\begingroup$ @Srivatsan, yes Henning is right. $\endgroup$ Commented Sep 14, 2011 at 10:07

5 Answers 5

10
$\begingroup$

In fact, there is a negative answer provable in ZFC. Since we have choice, well-order the interval $[0,1]$. Then let $x\sqsubset y$ if and only if the well-order agrees with the standard order of the reals and $x<y$. Then $[0,1]$ with the ordering $\sqsubset$ is an uncountable poset with neither an uncountable chain nor an uncountable anti-chain.

Consider any uncountable $S\subseteq[0,1]$. Let $z$ be the infimum of the set $$\{x\in [0,1]|\text{ there are uncountably many }y<x\text{ with }y\in S\}$$ $S$ cannot be a chain since otherwise, a countable increasing sequence of elements of $S$ converging to $z$ would be cofinal in $\omega_1$.

Similarly, we can take $w$ to be the supremum of the set $$\{x\in [0,1]|\text{ there are uncountably many }y>x\text{ with }y\in S\}$$ Then if $S$ was an anti-chain, then a countable decreasing sequence (according to the standard ordering of the reals) in $S$ would again be cofinal in $\omega_1$.

$\endgroup$
13
  • $\begingroup$ I don't understand your definition of $x \sqsubset y$: what are $x$ and $y$ here and how do they figure into the rest of the definition? $\endgroup$ Commented Sep 14, 2011 at 1:09
  • $\begingroup$ Sorry, x and y are taken to be real numbers in [0,1]. $\endgroup$ Commented Sep 14, 2011 at 1:10
  • $\begingroup$ To be clear, in the second and third paragraphs, do all references to order (infimum, $<$, increasing, etc) refer to the order defined in the first paragraph? $\endgroup$ Commented Sep 14, 2011 at 1:10
  • $\begingroup$ No, they refer to the standard ordering of the reals. $\endgroup$ Commented Sep 14, 2011 at 1:15
  • 6
    $\begingroup$ It's perhaps worth mentioning that this clever argument is attributed to Sierpinski. $\endgroup$
    – user83827
    Commented Sep 14, 2011 at 2:55
9
$\begingroup$

A Suslin tree is a poset (in fact, a tree) that has cardinality $\omega_1$ but every chain and every antichain is countable. The existence of a Suslin tree is neither provable nor disprovable in ZFC. Therefore, your question does not have an affirmitive answer provable in ZFC.

I do not know whether it has a negative answer (using something other than Suslin trees) provable in ZFC. Aubrey da Cunha has given a proof that the answer to the question is "no". That answer should be accepted over this one.

$\endgroup$
5
$\begingroup$

A natural negative answer is to take the poset $\bigcup_{n\in\omega} \{n\}\times\omega_n$, with two points comparable iff their first coordinates coincide. Any antichain here is countable, and any chain has size strictly below $\aleph_\omega$, which is the size of the whole set. Note that this does not use any form of choice.

$\endgroup$
0
$\begingroup$

This is true exactly for $\omega$ and for weakly compact cardinals. It is proved in

G.D. Badenhorst and T. Sturm, An order- and graph-theoretical characterisation of weakly compact cardinals, in Cycles and Rays (NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 301), 1990, pp.19-20, MR1096981.

$\endgroup$
0
$\begingroup$

This is the same answer as @aubrey's, but with an alternate proof.

Let $\preceq$ well-order the real numbers $\mathbb R$, and let $\leq$ be the usual ordering of $\mathbb R$. Then $\sqsubseteq$ defined by $x\sqsubseteq y$ if and only if $x\preceq y$ and $x\leq y$ is a partial order of $\mathbb R$.

We claim that every chain and antichain with respect to $\sqsubseteq$ is countable. To see this, let $C=\{c_\alpha:\alpha<|C|\}$ such that $\alpha<\beta$ if and only if $c_\alpha\prec c_\beta$.

We use the following lemma: given any increasing/decreasing sequence of reals, there is an increasing/decreasing sequence of rational numbers of the same cardinality (choose a rational between each term and its successor). Therefore every increasing/decreasing sequence of reals is countable.

If $C$ is a chain, then $\alpha<\beta$ implies $c_\alpha < c_\beta$, since $c_\alpha$ and $c_\beta$ are comparable by $\sqsubseteq$. Since there does not exist an uncountable increasing sequence of reals, $C$ is countable.

If $C$ is an antichain, then $\alpha<\beta$ implies $c_\alpha \not< c_\beta$ (equivalently, $c_\alpha >c_\beta$), since $c_\alpha$ and $c_\beta$ are incomparable by $\sqsubseteq$. Since there does not exist an uncountable decreasing sequence of reals, $C$ is countable.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .