Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Maybe off topic. What is a "continuous chain"? –  Srivatsan Sep 14 '11 at 0:47
2  
@Srivatsan, in this case it seems to mean a chain of cardinality $2^{\aleph_0}$. –  Henning Makholm Sep 14 '11 at 1:24
    
@Srivatsan, yes Henning is right. –  natema Sep 14 '11 at 10:07
add comment

4 Answers

up vote 10 down vote accepted

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

share|improve this answer
    
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? –  Pete L. Clark Sep 14 '11 at 1:09
    
Sorry, x and y are taken to be real numbers in [0,1]. –  Aubrey da Cunha Sep 14 '11 at 1:10
    
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? –  Jason DeVito Sep 14 '11 at 1:10
    
No, they refer to the standard ordering of the reals. –  Aubrey da Cunha Sep 14 '11 at 1:15
6  
It's perhaps worth mentioning that this clever argument is attributed to Sierpinski. –  user83827 Sep 14 '11 at 2:55
show 8 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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