The canonical Ramsey theorem and computability theory |
| |
Authors: | Joseph R Mileti |
| |
Institution: | Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, Illinois 61801 |
| |
Abstract: | Using the tools of computability theory and reverse mathematics, we study the complexity of two partition theorems, the Canonical Ramsey Theorem of Erdös and Rado, and the Regressive Function Theorem of Kanamori and McAloon. Our main aim is to analyze the complexity of the solutions to computable instances of these problems in terms of the Turing degrees and the arithmetical hierarchy. We succeed in giving a sharp characterization for the Canonical Ramsey Theorem for exponent 2 and for the Regressive Function Theorem for all exponents. These results rely heavily on a new, purely inductive, proof of the Canonical Ramsey Theorem. This study also unearths some interesting relationships between these two partition theorems, Ramsey's Theorem, and König's Lemma. |
| |
Keywords: | Computability theory Ramsey theory recursion theory reverse mathematics |
|
| 点击此处可从《Transactions of the American Mathematical Society》浏览原始摘要信息 |
| 点击此处可从《Transactions of the American Mathematical Society》下载免费的PDF全文 |
|