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.

Let $(X, \leq)$ be an infinite poset. Prove that there is an infinite $X' \subset X$ for which holds one of the following:

1) Induced order on $X'$ is linear.

2) $(X', \leq_\mathrm{ind})$ is antichain. (Every two elements in $X'$ are incomparable)


My attempt:

Let's start trying to construct a linearly ordered set $(X', \leq_\mathrm{ind})$ element by element. First we take some element $x_1 \in X$, then we take another $x_2 \in X$ such as $x_1 \leq x_2$ or $x_2 \leq x_1$. Basically, we take an element from $X$, if it is "good" we put it in our chain, otherwise we throw it away. We continue constructing the chain that way. If we do not stop at some finite step, then we are done, we have constructed linearly ordered subset.

If we do stop at some $x_n$ that means that we have finite amount of comparable elements, which means that $X \setminus X'$ is an antichain.


a) I am not sure about the soundness in the last step, could somebody please check it?

b) Can this be proved without a choice function?

share|improve this question
    
Your sentence «We continue constructing the chain that way.» is not sufficiently explicit. It is impossible to know how you intend to choose $x_3$! –  Mariano Suárez-Alvarez Jan 4 '12 at 19:16
    
I updated the question. So, basically we go through every possible element of $X$ (we can do that given the AC, I believe) –  Daniil Jan 4 '12 at 19:19
    
a) is wrong. For example, in $\mathbb N$ with relations $1 \leq 2$ and $3 \leq 4$ only, if you start with $1$ and then add $2$, you cannot add more elements, but $\mathbb N - \{1,2\}$ contains 3,4 so it is not an antichain. –  sdcvvc Jan 4 '12 at 19:20
    
But that procedure does not work without some form of backtracking: it may well be the case that your first 42 choices lead you to a maximal chain, which is finite, while there is an infinite chain somewhere else and no infinite antichain (consider the poset obtained from $\mathbb N$ and $\{1,\dots,42\}$ after identifying the two ones) –  Mariano Suárez-Alvarez Jan 4 '12 at 19:22
2  
Start with a maximal antichain $A$, which by assumption is finite. Show that for some $a \in A$, either $\{x \in X: x \le a\}$ or $\{x \in X: x \ge a\}$ is infinite. Recurse... –  Robert Israel Jan 4 '12 at 19:54
show 3 more comments

4 Answers

up vote 4 down vote accepted

If we also require that the infinite chain or anti-chain will be maximal, then we do need the axiom of choice. Indeed Zorn's lemma is a useful tool when finding maximal chains and anti-chains.

There is a choice principle called Hausdorff's maximality principle stating that in every partially ordered set there exists a maximal chain. It too is equivalent to the axiom of choice, so when you negate the axiom of choice you add a partially ordered set without a maximal chain.

For anti-chains there exists a similar principle, which too implies the axiom of choice.

If you just want to find an infinite anti-chain or chain, some axiom of choice may be needed. Indeed there are trees that every branch can be extended, but there is no infinite branch (thus no infinite chain).

On the other hand, there exists a model of ZF assuming some amount of finite choice, in which there exists a partially ordered set which is infinite but has no infinite chains or anti-chains.

The proof is quite complicated, but appears on Jech, The Axiom of Choice as the model given in Theorem 7.11 (p. 107) and in exercise 7.14 (p. 115)


Your proof is fine for the most, assuming the axiom of choice (or at least The Principle of Dependent Choice). However if we only remove a finite number of comparable elements we don't have to have an anti-chain left.

Dichotomy proofs should show that if condition I failed then condition II holds. And indeed, suppose that $X$ is infinite, but every chain is finite. We define a sequence of elements $x_n\in X$ by induction:

Let $x_0\in X$ be an element such that $X_0=\{x\in X\mid x\nleq x_0\land x_0\nleq x\}$ is infinite. If no element has this property, we can use the same induction to define an infinite chain (taking all the elements comparable with $x_0$ instead).

Suppose $x_n$ and $X_n$ were defined, let $x_{n+1}\in X_n$ be such that $X_{n+1}=\{x\in X_n\mid x\nleq x_{n+1}\land x_{n+1}\nleq x\}$ is infinite. If we got stuck at the $n$-th stage (that is $X_{n+1}$ is finite for every $x\in X_n$) then we can define an infinite chain *within $X_n$* by the same induction as in the first step.

I claim that $\{x_n\mid n\in\mathbb N\}$ is an infinite anti-chain. First note that $\ldots\subsetneq X_n\subsetneq X_{n-1}\subsetneq\ldots\subsetneq X$, and $x_n\in X_{n-1}$ and $x_0\in X$. Each $x_n$ defined $X_n$ and those are unique so $x_n\neq x_k$ for $n\neq k$.

Secondly, since $x_k\in X_{k-1}$ if $x_k$ and $x_n$ are comparable and $n<k$ then $x_k\in X_n$ which was defined as a set of elements incomparable with $x_n$ to begin with, therefore we have an infinite anti-chain.

share|improve this answer
    
That doesn't work. The problem is that different maximal chains can have the same maxima and minima. Let $X=\{\alpha,\omega\}\cup\mathbb{N}$ and define a partial order such that every element is comparable to itself, $\alpha$ is larger than every element, $\omega$ is smaller than every element and no other comparisons are possible. Then every maximal chain is of the form $\{\alpha,n,\omega\}$. –  Michael Greinecker Jan 4 '12 at 20:13
    
Could you please elaborate, what do you mean by "retrieve back the order"? And "maximal chain" = chain with maximal size? –  Daniil Jan 4 '12 at 20:14
    
@Michael: You are correct of course. I rectified my mistake. Funny that you chose $\omega$ to be an element smaller than all the natural numbers since $\omega$ is the supremum of the natural numbers (as ordinals). :-) –  Asaf Karagila Jan 4 '12 at 20:46
    
@Daniil: I have corrected the argument, as pointed by Michael. I removed the relevant part to your comment, but I did mean that the union of all maximal chains would result in the entire set $X$. Maximal chains are maximal with respect to inclusion, not to cardinality. –  Asaf Karagila Jan 4 '12 at 20:47
1  
@Michael: No... if every element can be compared with all but finitely many. Re-reading the induction, it seems that indeed there is a typo in the inductive step. I'll correct that. –  Asaf Karagila Jan 4 '12 at 22:09
show 4 more comments

The fact that every infinite partial order has either an infinite chain or an infinite antichain has a quick proof as a consequence of the infinite Ramsey theorem, which asserts that every coloring of pairs from an infinite set admits an infinite monochromatic subset. Namely, for any partial order, consider the coloring of pairs either as "comparable" or "incomparable," as the case may be for that pair. By Ramsey's theorem, there is an infinite monochromatic subset, meaning that all pairs from the subset are assigned the same color, and this subset therefore is either an infinite chain or an infinite antichain.

Meanwhile, Ramsey's theorem can apparantly be proved using only the principle of dependent choices---a weak choice principle, allowing one to make countably many choices in succession---for the proof of Ramsey's theorem given on the linked wikipedia page is an inductive argument, in each stage of which one makes countably many choices in succession.

share|improve this answer
add comment

One can use a free ultrafilter to get a reasonably slick argument that minimizes the amount of detail that has to be kept track of at the cost of using a different consequence of AC $-$ the Boolean prime ideal theorem, which is strictly weaker than AC and independent of Dependent Choice, which also suffices.

Let $\mathscr{U}$ be a free ultrafilter on $X$. For each $x\in X$ let $C(x)=\{y\in X:x\le y\lor y\le x\}$, and let $A(x)=X\setminus C(x)=\{y\in X:x\not\le y \land y\not\le x\}$; exactly one of $C(x)$ and $A(x)$ belongs to $\mathscr{U}$. Let $C=\{x\in X:C(x)\in\mathscr{U}\,\}$, and let $A=X\setminus C=\{x\in X:A(x)\in\mathscr{U}\,\}$. Exactly one of $A$ and $C$ belongs to $\mathscr{U}$; without loss of generality assume that $C\in\mathscr{U}$.

Fix $x_0\in C$, and let $C_0=C\cap C(x_0)\setminus\{x_0\}\in\mathscr{U}$. Given $C_n\in\mathscr{U}\,$ for some $n\in\omega$, choose $x_{n+1}\in C_n$ and let $C_{n+1}=C_n\cap C(x_{n+1})\setminus\{x_{n+1}\}\in\mathscr{U}\,$; clearly the construction goes through to $\omega$ to produce a set $\{x_n:n\in\omega\}$ of distinct elements of $X$. Moreover, for any $k<n<\omega$ we have $x_n\in C_k\subseteq C(x_k)$, so $\{x_n:n\in\omega\}$ is an infinite chain in $X$. (Had $A$ been a member of $\mathscr{U}\,$ instead of $C$, the set $\{x_n:n\in\omega\}$ would of course have been an infinite antichain.)

As JDH has already noted, this is essentially just the two-color case of the infinite Ramsey theorem, $\kappa\to(\omega)_2^2$. If one wanted to use a really big stick, one could beat the problem over the head with the Erdős-Dushnik-Miller theorem, $\kappa\to(\kappa,\omega)^2$, and conclude that either $X$ has a chain of cardinality $|X|$, or $X$ has an infinite antichain. (Here the rôles of chain and antichain can of course be reversed.)

share|improve this answer
    
Brian, I don't know how BPID is "more" than DC, since Cohen's basic model (as the Halpern-Levy model) is one that DC does not hold in but BPID does. The inverse implication does not hold either as there is a model in which Hahn-Banach fails (and thus BPID fails) but DC holds. –  Asaf Karagila Jan 5 '12 at 7:40
    
@Asaf: You’re right: I tend to think of BPI as ‘almost AC’ and of DC as a relatively weak condition and had completely forgotten that they’re actually independent of each other. I’ll change the wording. –  Brian M. Scott Jan 5 '12 at 7:56
    
Brian, after spending the past year with weak choice principles I can tell you that there are in essence three types of principles which are essentially independent of one another: 1. Bounded AC (e.g. DC) ; 2. Global principles (e.g. BPI); 3. The rest of them (e.g. SVC). There is a lot of compatibility and some implications but in essence each of those functions as a different other part of AC. –  Asaf Karagila Jan 5 '12 at 8:06
    
@Asaf: I actually know that when I stop to think, but it’s awfully tempting for a topologist to look at the Tikhonov theorem (AC) and its restriction to Hausdorff spaces (BPI) and think that they’re very, very close. –  Brian M. Scott Jan 5 '12 at 8:10
add comment

The following proof isn't terribly elegant, but works: Let $A$ be a maximal, finite anti-chain. For each point $x\in A$, let $\mathcal{L}(x)$ be the family of all maximal chains containing $x$. Clearly, $\bigcup_{x\in A}\mathcal{L}(x)=X$, so for some $x^*\in A$, the family $\mathcal{L}(x^*)$ is infinite. If it contains an infinite chain, we are done. Suppose not. Clearly, there must be either infinitely many chains in $\mathcal{L}(x^*)$ that contain an element smaller than $x^*$ or infinitely many chains in $\mathcal{L}(x^*)$ that contain an element larger than $x^*$. W.l.o.g., assume the latter. Let $\mathcal{L}^*(x^*)$ be the set of all maximal chains containing $x^*$ that contain an element larger than $x^*$. Every chain in $\mathcal{L}^*(x^*)$ is finite and hence well-ordered by $\leq$. Let $$\mathcal{T}_?=\bigg\{\{y:y\geq x^*\}\cap L:L\in\mathcal{L}^*(x^*)\bigg\}.$$ Let $\mathcal{T}$ be the family of all initial segments of $\mathcal{T}_?$. Now, $\mathcal{T}$ is an infinite tree. If every node has finite degree, an infinite path and hence chain containing $x^*$ exists by König's Lemma, which can not be. So there exists a node with infinite degree. The set of successors of this node forms an infinite anti-chain.

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.