Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-08T06:29:47.913Z Has data issue: false hasContentIssue false
  • English
  • Français

ON RAMSEY’S THEOREM AND THE EXISTENCE OF INFINITE CHAINS OR INFINITE ANTI-CHAINS IN INFINITE POSETS

Published online by Cambridge University Press:  09 March 2016

ELEFTHERIOS TACHTSIS
ELEFTHERIOS TACHTSIS*
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF THE AEGEAN KARLOVASSI 83200, SAMOS, GREECEE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Ramsey’s Theorem is naturally connected to the statement “every infinite partially ordered set has either an infinite chain or an infinite anti-chain”. Indeed, it is a well-known result that Ramsey’s Theorem implies the latter principle.

In the book “Consequences of the Axiom of Choice” by P. Howard and J. E. Rubin, it is stated as unknown whether the above implication is reversible, that is whether the principle “every infinite partially ordered set has either an infinite chain or an infinite anti-chain” implies Ramsey’s Theorem. The purpose of this paper is to settle the aforementioned open problem. In particular, we construct a suitable Fraenkel–Mostowski permutation model ${\cal N}$ for ZFA and prove that the above principle for infinite partially ordered sets is true in ${\cal N}$, whereas Ramsey’s Theorem is false in ${\cal N}$. Then, based on the existence of ${\cal N}$ and on results of D. Pincus, we show that there is a model of ZF which satisfies “every infinite partially ordered set has either an infinite chain or an infinite anti-chain” and the negation of Ramsey’s Theorem.

In addition, we prove that Ramsey’s Theorem (hence, the above principle for infinite partially ordered sets) is true in Mostowski’s linearly ordered model, filling the gap of information in the book “Consequences of the Axiom of Choice”.

Keywords

Primary 03E25Secondary 03E3505D10Axiom of Choiceweak forms of the Axiom of ChoiceRamsey’s Theorempartially ordered setschains in partially ordered setsanti-chains in partially ordered setsFraenkel–Mostowski (FM) permutation models for ZFAPincus’ transfer theorems
Type
Articles
Information
The Journal of Symbolic Logic , Volume 81 , Issue 1 , March 2016 , pp. 384 - 394
Copyright
Copyright © The Association for Symbolic Logic 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Blass, A., Ramsey’s theorem in the hierarchy of choice principles, this Journal, vol. 42 (1977), pp. 387–390.Google Scholar
Cohen, P. J., Set Theory and the Continuum Hypothesis, Benjamin, New York, 1966.Google Scholar
Drake, F. R., Set Theory. An Introduction to Large Cardinals, North-Holland, Amsterdam, 1974.Google Scholar
Forster, T. E., Truss, J. K., Ramsey’s theorem and König’s Lemma. Archive for Mathematical Logic, vol. 46 (2007), pp. 37–42.Google Scholar
Hall, E. J., Shelah, S., Partial choice functions for families of finite sets. Fundamenta Mathematicae, vol. 220 (2013), pp. 207–216.Google Scholar
Hirschfeldt, D. R. and Shore, R. A., Combinatorial Principles Weaker than Ramsey’s Theorem for Pairs, this Journal, vol. 72 (2007), pp. 171–206.Google Scholar
Howard, P. and Rubin, J. E., Consequences of the Axiom of Choice, Mathematical Survays and Monographs, American Mathematical Society, vol. 59, Providence, RI, 1998. (http://www.consequences.emich.edu/conseq.htm is the website of the AC project).Google Scholar
Howard, P., Saveliev, D. I., Tachtsis, E., On the set-theoretic strength of the existence of disjoint cofinal sets in posets without maximal elements. Mathematical Logic Quarterly, accepted.Google Scholar
Jech, T. J., The Axiom of Choice, Studies in Logic and the Foundations of Mathematics, vol. 75, North-Holland, Amsterdam, 1973.Google Scholar
Jech, T., Set Theory, The Third Millennium Edition, Revised and Expanded, Springer, Berlin, 2002.Google Scholar
Kleinberg, E. M., The independence of Ramsey’s theorem, this Journal, vol. 34 (1969), pp. 205–206.Google Scholar
Lolli, G., On Ramsey’s theorem and the axiom of choice. Notre Dame Journal of Formal Logic, vol. 18 (1977), pp. 599–601.Google Scholar
Pincus, D., Zermelo-Fraenkel consistency results by Fraenkel-Mostowski methods, this Journal, vol. 37 (1972), pp. 721–743.Google Scholar
Ramsey, F. P., On a Problem of Formal Logic, Proceedings of the London Mathematical Society, Series 2, vol. 30 (1929), pp. 264–286.Google Scholar