2
$\begingroup$

If I have an infinite partially ordered set $P$ where every chain has finite order and I take some maximal element $x_1$ (which must exists because our chains are finite) and then I take a maximal element $x_2\in P-{x_1}$ is it true that $\{x_1,x_2\}$ is an anti chain?

I don't think it is but I am not quite sure to find a counterexample.

What I think is true, but not quite sure how to prove it. $\downarrow$

If I take some element $x_1\in P$ and then consider its maximal chain $T_1$ and consider the maximal element $t_1\in T_1$ and then take some $x_2\in P-T_1$ and consider its maximal chain $T_2$ with maximal element $t_2$ and continue this, then $\{t_1,t_2,t_3...\}$ is an anti chain.

Is any of this true?

$\endgroup$
  • $\begingroup$ What if $x_2$ is in the same chain as $x_1$? $\endgroup$ – Git Gud Oct 16 '14 at 9:10
  • $\begingroup$ OK what about the one I thought might be true? $\endgroup$ – H_B Oct 16 '14 at 9:13
  • $\begingroup$ the chains have finite elements, there are infinite chains because every singleton is a chain. $\endgroup$ – H_B Oct 16 '14 at 9:20
  • $\begingroup$ what I am trying to do is suppose there are only chains with finite amount of elements, and prove that there must be an infinite anti-chain. $\endgroup$ – H_B Oct 16 '14 at 9:21
  • $\begingroup$ Now I get it. And I misread your last paragraph at first. I think your idea works. $\endgroup$ – Git Gud Oct 16 '14 at 9:24
0
$\begingroup$

No, none of it is true.

If $x_1$ is a maximal element of $P$ and $x_2\in P-x_1$, is $\{x_1,x_2\}$ an antichain? No, this fails when $P$ is a $2$-element chain.

"Take some element $x_1$ and consider its maximal chain $T_1$." What do you mean by "its" maximal chain? You mean, a maximal chain $T_1$ containing $x_1$, picked at random from the many maximal chains containing $x_1$? (Fine, but since the element $x_1$ isn't mentioned again, why bother with $x_1$? Why not just choose a maximal chain $T_1$?) Then $T_1$ will have a maximal element $t_1$, since all chains in $P$ are finite; and then $t_1$ is a maximal element of $P$, since $T_1$ is a maximal chain.

Are you going to get an infinite antichain this way? Not necessarily. What if $P$ happens to have a greatest element? Whatever you take for $x_1$ and $T_1$, you're going to end up with that top element of $P$ as your $t_1$. Needless to say, that $t_1$ is not going to be part of an infinite antichain. Sorry!

It is true that every infinite partially ordered set has either an infinite chain or an infinite antichain. Do you know a theorem from analysis, that any infinite sequence of real numbers contains a monotonic subsequence? The theorem you're trying to prove is a generalization of that, so maybe the proof of that analysis theorem has some idea you can use.

| cite | improve this answer | |
$\endgroup$

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.