Partitions of trees and ACA^_0

DOI10.1007/S00153-009-0122-XzbMATH Open1172.03006arXiv0809.2267OpenAlexW1982258664MaRDI QIDQ1016503FDOQ1016503

Authors: Bernard Anderson, Jeffry L. Hirst 

Publication date: 6 May 2009

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Abstract: We show that a version of Ramsey's theorem for trees for arbitrary exponents is equivalent to the subsystem ACA' of reverse mathematics.

Full work available at URL: https://arxiv.org/abs/0809.2267

Recommendations

• scientific article; zbMATH DE number 887757
• Ramsey's theorem for trees: the polarized tree theorem and notions of stability
• Abstract approach to Ramsey theory and Ramsey theorems for finite trees
• On the Ramsey numbers of trees with small diameter
• Reverse mathematics, computability, and partitions of trees
• Dual Ramsey theorem for trees
• Large Finite Sets
• The strength of the tree theorem for pairs in reverse mathematics
• Big Ramsey degrees of 3-uniform hypergraphs are finite
• The Ramsey numbers of trees versus \(W_{6}\) or \(W_{7}\)

zbMATH Keywords

treesreverse mathematicsRamsey's theorem

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Second- and higher-order arithmetic and fragments (03F35)

Cites Work

• Title not available (Why is that?)
• The canonical Ramsey theorem and computability theory
• The polarized Ramsey's theorem
• Reverse mathematics, computability, and partitions of trees

Cited In (4)

• Generalized (\(P\), \(\omega\))-partitions and generating functions for trees
• Coloring trees in reverse mathematics
• On the strength of Ramsey's theorem for trees
• A note on Ramsey theorems and Turing jumps

This page was built for publication: Partitions of trees and \({{\text \textsf{ACA}}^\prime_{0}}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016503)