Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-07T22:23:08.293Z Has data issue: false hasContentIssue false
  • English
  • Français

Ramsey's theorem in the hierarchy of choice principles

Published online by Cambridge University Press:  12 March 2014

Andreas Blass
Andreas Blass*
Affiliation:
University of Michigan, Ann Arbor, Michigan 48109
Get access Rights & Permissions [Opens in a new window]

Extract

Ramsey's theorem [5] asserts that every infinite set X has the following partition property (RP): For every partition of the set [X]2 of two-element subsets of X into two pieces, there is an infinite subset Y of X such that [Y]2 is included in one of the pieces. Ramsey explicitly indicated that his proof of this theorem used the axiom of choice. Kleinberg [3] showed that every proof of Ramsey's theorem must use the axiom of choice, although rather weak forms of this axiom suffice. J. Dawson has raised the question of the position of Ramsey's theorem in the hierarchy of weak axioms of choice.

In this paper, we prove or refute the provability of each of the possible implications between Ramsey's theorem and the weak axioms of choice mentioned in Appendix A.3 of Jech's book [2]. Our results, along with some known facts which we include for completeness, may be summarized as follows (the notation being as in [2]):

A. The following principles do not (even jointly) imply Ramsey's theorem, nor does Ramsey's theorem imply any of them:

the Boolean prime ideal theorem,

the selection principle,

the order extension principle,

the ordering principle,

choice from wellordered sets (ACW),

choice from finite sets,

choice from pairs (C2).

B. Each of the following principles implies Ramsey's theorem, but none of them follows from Ramsey's theorem:

the axiom of choice,

wellordered choice (∀kACk),

dependent choice of any infinite length k (DCk),

countable choice (ACN0),

nonexistence of infinite Dedekind-finite sets (WN0).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 42 , Issue 3 , September 1977 , pp. 387 - 390
Copyright
Copyright © Association for Symbolic Logic 1977

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

[1]Halpern, J. D. and Lévy, A., The Boolean prime ideal theorem does not imply the axiom of choice, Proceedings of Symposia in Pure Mathematics, vol. 13 (1971), pp. 83–134.CrossRefGoogle Scholar
[2]Jech, T., The axiom of choice, North-Holland, Amsterdam, 1973.Google Scholar
[3]Kleinberg, E. M., The independence of Ramsey's theorem, this Journal, vol. 34 (1969), pp. 205–206.Google Scholar
[4]Pincus, D., Zermelo–Fraenkel consistency proofs by Fraenkel–Mostowski methods, this Journal, vol. 37 (1972), pp. 721–743.Google Scholar
[5]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
[6]Sierpinski, W., Fonctions additives non complètement additives et fonctions non mesurables, Fundamenta Mathematical, vol. 30 (1938), pp. 96–99.CrossRefGoogle Scholar
[7]Solovay, R. M., A model of set theory in which every set of reals is Lebesgue measurable, Annals of Mathematics, vol. 92 (1970), pp. 1–56.CrossRefGoogle Scholar