3
$\begingroup$

The Dilworth theorem for finite posets implies that a finite poset contains either a "large" chain or a "large" antichain. I am sure I saw an infinite version of this :

An infinite poset has either an infinite chain or an infinite antichain.

But I can't find a reference to that statement. What is the reference or a proof?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

This is studied in Reverse Mathematics as the Chain Antichain Principle (CAC) and it is observed that it follows from Ramsey's theorem.

Improve this answer
$\endgroup$
1
5
$\begingroup$

There is an exercise in Stanley's Enumerative Combinatorics (Ex. 12 in Chapter 3 of Vol. 1): "True or false: if every chain and every antichain of a poset $P$ is finite, then $P$ is finite." It also contains a direct proof in the Solutions section, not using Ramsey theorem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I should mention that in Reverse Mathematics, the form of Ramsey's theorem that is needed here is quite weak -- weaker than the statement that for each $f:\mathbb N\to\mathbb N$, range($f$) exists as a set. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Oct 30, 2019 at 7:18
  • $\begingroup$ @BjørnKjos-Hanssen well, probably this is not logical, but methodological difference $\endgroup$
    – Fedor Petrov
    Commented Oct 30, 2019 at 7:37
  • $\begingroup$ Yes.. and nice that Stanley is available free online $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Oct 30, 2019 at 12:57
  • $\begingroup$ Stanley himself is on MO sometimes. $\endgroup$
    – user6976
    Commented Oct 30, 2019 at 17:35

You must log in to answer this question.