Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T09:19:44.134Z Has data issue: false hasContentIssue false

Partition Theorems and Computability Theory

Published online by Cambridge University Press:  15 January 2014

Joseph R. Mileti*
Affiliation:
Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, IL 60637, USA. E-mail: mileti@math.uchicago.edu

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}.

Information

Type
Research Article
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.)

Article purchase

Temporarily unavailable