Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-22T14:23:54.102Z Has data issue: false hasContentIssue false
  • English
  • Français

Partition Theorems and Computability Theory

Published online by Cambridge University Press:  15 January 2014

Joseph R. Mileti
Joseph R. Mileti*
Affiliation:
Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, IL 60637, USA. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω with its set of predecessors, so n = {0, 1, 2, …, n − 1}.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 11 , Issue 3 , September 2005 , pp. 411 - 427
Copyright
Copyright © Association for Symbolic Logic 2005

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] Cholak, Peter, Guisto, Mariagnese, Hirst, Jewry, and Jockusch, Carl, Free sets and reverse mathematics, Reverse mathematics 2001 (Simpson, Stephen G., editor), Lecture Notes in Logic, vol. 22, AK Peters, 2005, pp. 104–119.Google Scholar
[2] Cholak, Peter A., Jockusch, Carl G., and Slaman, Theodore A., On the strength of Ramsey's theorem for pairs, The Journal of Symbolic Logic, vol. 66 (2001), no. 1, pp. 1–55.CrossRefGoogle Scholar
[3] Downey, Rod, Hirschfeldt, Denis R., Lempp, Steffen, and Solomon, Reed, A set with no infinite low subset in either it or its complement, The Journal of Symbolic Logic, vol. 66 (2001), no. 3, pp. 1371–1381.Google Scholar
[4] Downey, Rod, Jockusch, Carl G., and Stob, Michael, Array nonrecursive degrees and genericity, Computability, enumerability, unsolvability, London Mathematical Society Lecture Note Series, vol. 224, Cambridge Univ. Press, Cambridge, 1996, pp. 93–104.Google Scholar
[5] Erdös, P. and Rado, R., A combinatorial theorem, The Journal of the London Mathematical Society, vol. 25 (1950), pp. 249–255.CrossRefGoogle Scholar
[6] Hirst, Jeffry L., Combinatorics in subsystems of second order arithmetic, Ph.D. thesis, The Pennsylvania State University, 1987.Google Scholar
[7] Hummel, Tamara and Jockusch, Carl G. Jr., Generalized cohesiveness, The Journal of Symbolic Logic, vol. 64 (1999), no. 2, pp. 489–516.Google Scholar
[8] Hummel, Tamara Lakins, Effective versions of Ramsey's theorem: avoiding the cone above 0′, The Journal of Symbolic Logic, vol. 59 (1994), no. 4, pp. 1301–1325.Google Scholar
[9] Jockusch, Carl and Stephan, Frank, A cohesive set which is not high, Mathematical Logic Quarterly, vol. 39 (1993), no. 4, pp. 515–530.Google Scholar
[10] Jockusch, Carl and Stephan, Frank, Correction to: “A cohesive set which is not high” [Math. Logic Quart. 39 (1993), no. 4, 515–530], Mathematical Logic Quarterly, vol. 43 (1997), no. 4, p. 569.Google Scholar
[11] Jockusch, Carl G. Jr., Ramsey's theorem and recursion theory, Jurnal of Symbolic Logic, vol. 37 (1972), pp. 268–280.CrossRefGoogle Scholar
[12] Jockusch, Carl G. Jr. and Soare, Robert I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[13] Kanamori, Akihiro, The higher infinite: Large cardinals in set theory from their beginnings, second ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003.Google Scholar
[14] Kanamori, Akihiro and McAloon, Kenneth, On Gödel incompleteness and finite combinatorics, Annals of Pure and Applied Logic, vol. 33 (1987), no. 1, pp. 23–41.Google Scholar
[15] Mileti, Joseph R., Partition theorems and computability theory, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2004.Google Scholar
[16] Mileti, Joseph R., The canonical ramsey theorem and computability theory, to appear.Google Scholar
[17] Mileti, Joseph R., Ramsey degrees, to appear.Google Scholar
[18] Paris, J. and Harrington, Leo A., A mathematical incompleteness in Peano arithmetic, Handbook of mathematical logic (Barwise, Jon, editor), North–Holland Publishing Co., Amsterdam, 1977, pp. 1133–1142.Google Scholar
[19] Rado, Richard, Note on canonical partitions, The Bulletin of the London Mathematical Society, vol. 18 (1986), no. 2, pp. 123–126.Google Scholar
[20] Ramsey, F. P., On a problem in formal logic, Proceedings of the London Mathematical Society. Third series, vol. 30 (1930), pp. 264–286.Google Scholar
[21] Scott, Dana, Algebras of sets binumerable in complete extensions of arithmetic, Proceedings Symposia in Pure Mathematics, Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 117–121.Google Scholar
[22] Seetapun, David and Slaman, Theodore A., On the strength of Ramsey's theorem, Notre Dame Journal of Formal Logic, vol. 36 (1995), no. 4, pp. 570–582, Special Issue: Models of arithmetic.Google Scholar
[23] Simpson, Stephen G., Degrees of unsolvability: a survey of results, Handbook of mathematical logic (Barwise, Jon, editor), North-Holland, Amsterdam, 1977, pp. 1133–1142.Google Scholar
[24] Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.Google Scholar
[25] Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.Google Scholar
[26] Specker, E., Ramsey's theorem does not hold in recursive set theory, Logic Colloquium '69 (Proc. Summer School and Colloq., Manchester, 1969), North-Holland, Amsterdam, 1971, pp. 439–442.Google Scholar