Ramsey's theorem and recursion theory

DOI10.2307/2272972zbMath0262.02042OpenAlexW2131443763MaRDI QIDQ5677475

Publication date: 1972

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2272972

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Related Items (74)

An inside/outside Ramsey theorem and recursion theory ⋮ 1998 European Summer Meeting of the Association for Symbolic Logic ⋮ 2000 Annual Meeting of the Association for Symbolic Logic ⋮ Open Questions in Reverse Mathematics ⋮ Reduction games, provability and compactness ⋮ Reverse mathematical bounds for the termination theorem ⋮ The proof-theoretic strength of Ramsey's theorem for pairs and two colors ⋮ 2009 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '09 ⋮ Term extraction and Ramsey's theorem for pairs ⋮ Partial Orders and Immunity in Reverse Mathematics ⋮ Hindman's theorem for sums along the full binary tree, \(\Sigma^0_2\)-induction and the pigeonhole principle for trees ⋮ The metamathematics of Stable Ramsey’s Theorem for Pairs ⋮ RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS ⋮ RAMSEY-LIKE THEOREMS AND MODULI OF COMPUTATION ⋮ THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS ⋮ An infinite version of Arrow's theorem in the effective setting ⋮ NONSTANDARD MODELS IN RECURSION THEORY AND REVERSE MATHEMATICS ⋮ The uniform content of partial and linear orders ⋮ The Galvin-Prikry theorem and set existence axioms ⋮ Coloring trees in reverse mathematics ⋮ Cohesive sets and rainbows ⋮ Book review of: D. R. Hirschfeldt, Slicing the truth. On the computable and reverse mathematics of combinatorial principles ⋮ OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS ⋮ Upward closure and cohesive degrees ⋮ Primitive recursive reverse mathematics ⋮ HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK? ⋮ “Weak yet strong” restrictions of Hindman’s Finite Sums Theorem ⋮ The Paris-Harrington principle and second-order arithmetic -- bridging the finite and infinite Ramsey theorem ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ Controlling iterated jumps of solutions to combinatorial problems ⋮ Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective ⋮ Herrmann’s Beautiful Theorem on Computable Partial Orderings ⋮ Effectiveness of Hindman’s Theorem for Bounded Sums ⋮ Some Questions in Computable Mathematics ⋮ Remembering Ernst Specker (1920--2011) ⋮ Computability-theoretic and proof-theoretic aspects of partial and linear orderings ⋮ Some logically weak Ramseyan theorems ⋮ A Combinatorial Bound for a Restricted Form of the Termination Theorem ⋮ ZFC PROVES THAT THE CLASS OF ORDINALS IS NOT WEAKLY COMPACT FOR DEFINABLE CLASSES ⋮ An intuitionistic version of Ramsey's theorem and its use in program termination ⋮ The weakness of being cohesive, thin or free in reverse mathematics ⋮ Fast growing functions based on Ramsey theorems ⋮ The inductive strength of Ramsey's theorem for pairs ⋮ On the strength of König's duality theorem for infinite bipartite graphs ⋮ Computable Ramsey's theorem for pairs needs infinitely many \(\Pi ^0_2\) sets ⋮ Infinite chains and antichains in computable partial Orderings ⋮ The weakness of the pigeonhole principle under hyperarithmetical reductions ⋮ Ramsey's theorem for trees: the polarized tree theorem and notions of stability ⋮ An algebraic difference between isols and cosimple isols ⋮ 2003 Annual Meeting of the Association for Symbolic Logic ⋮ Forcing in Proof Theory ⋮ The canonical Ramsey theorem and computability theory ⋮ On uniform relationships between combinatorial problems ⋮ 2002 Annual Meeting of the Association for Symbolic Logic ⋮ 2008 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '08 ⋮ Partition Theorems and Computability Theory ⋮ Special issue: Selected papers of the workshop on model theory and computable model theory, Gainesville, FL, USA, February 5--10, 2007 ⋮ Chains and antichains in partial orderings ⋮ \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models ⋮ The polarized Ramsey's theorem ⋮ Thin set theorems and cone avoidance ⋮ Unnamed Item ⋮ RAMSEY’S THEOREM FOR PAIRS ANDKCOLORS AS A SUB-CLASSICAL PRINCIPLE OF ARITHMETIC ⋮ The atomic model theorem and type omitting ⋮ Pigeons do not jump high ⋮ Cone avoiding closed sets ⋮ Recursive Euler and Hamilton Paths ⋮ A packed Ramsey’s theorem and computability theory ⋮ The strength of Ramsey’s theorem for pairs over trees: I. Weak König’s Lemma ⋮ A dual form of Ramsey's theorem ⋮ Ultrafilters and types on models of arithmetic ⋮ Countable algebra and set existence axioms ⋮ Thin set versions of Hindman's theorem ⋮ In search of the first-order part of Ramsey's theorem for pairs

Cites Work

This page was built for publication: Ramsey's theorem and recursion theory