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.
Given an infinite poset of a certain cardinality, does it contains always a chain or antichain of the same cardinality?
-
1Maybe off topic. What is a "continuous chain"? – 2011-09-14
-
2@Srivatsan, in this case it seems to mean a chain of cardinality $2^{\aleph_0}$. – 2011-09-14
-
0@Srivatsan, yes Henning is right. – 2011-09-14
4 Answers
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 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 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$.
-
0I 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? – 2011-09-14
-
0Sorry, x and y are taken to be real numbers in [0,1]. – 2011-09-14
-
0To 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? – 2011-09-14
-
0No, they refer to the standard ordering of the reals. – 2011-09-14
-
0The answer should now be fixed to make it clear that you could use either ordering. – 2011-09-14
-
0Thanks. I was worried for a minute about what to do about the case where the two displayed sets are empty, but I see a way around it. The key point is that $S$, being a subspace of $\mathbb{R}$, is separable in the usual topology on $\mathbb{R}$. – 2011-09-14
-
0How exactly does being separable fix this? – 2011-09-14
-
0@Carl, That's why I restricted to $[0,1]$. Now 1 is always in the first set and 0 is always in the second. – 2011-09-14
-
0@Jason DeVito: Say the first displayed set is empty. By separability take a countable sequence $(s_i)$ in $S$ which is increasing and cofinal in $S$ (so either $(s_i) \to \infty$ or $(s_i) \to \sup S$). Then for each $i$, $\{ x \in S : x < s_i\}$ is countable, and so $S$ is a countable union of countable sets. – 2011-09-14
-
0@Carl: Thanks! I think I finally understand this beautiful answer. (I haven't thought about order theory in a few years - this was a wonderful trip back through it. Thanks!!) – 2011-09-14
-
0@Aubrey de Cunha: if $1 \not \in S$? Maybe you meant $x \in [0,1]$, which I think works as well. – 2011-09-14
-
0@Carl: You are correct. That is what I meant. Edited. – 2011-09-14
-
6It's perhaps worth mentioning that this clever argument is attributed to Sierpinski. – 2011-09-14
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.
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.
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.