×

Dilworth’s decomposition theorem for posets in ZF. (English) Zbl 1449.03016

Dilworth’s theorem (DT) is the following statement: If the maximum number of elements in an antichain of a poset \(P\) is a finite number, then it is equal to the minimum number of pairwise disjoint chains into which \(P\) can be decomposed. DT for finite posets is a theorem of ZF. DT is valid in ZFC, but DT does not imply AC in ZF. The Boolean prime ideal theorem (BPI) implies DT in ZF but BPI is strictly weaker than AC in ZF.
In this paper, the author shows DT using the propositional compactness theorem which is equivalent to BPI. Further on, he shows that BPI \(\rightarrow\) DT is not reversible in ZFA.
The author is interested in the strength of DT with respect to variants of AC. He proves that the axiom of choice for well-ordered families of non-empty sets does not imply DT in ZFA. This is done by introducing a new Fraenkel-Mostowski model.
He also shows that DT does not imply Marshall Hall’s theorem in ZFA.

MSC:

03E25 Axiom of choice and related propositions
03E35 Consistency and independence results
06A06 Partial orders, general
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI