Premium
Reverse mathematics and infinite traceable graphs
Author(s) -
Cholak Peter,
Galvin David,
Solomon Reed
Publication year - 2012
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201020066
Subject(s) - mathematics , reverse mathematics , ramsey theory , discrete mathematics , tuple , graph theory , lattice (music) , graph , combinatorics , axiom , physics , geometry , acoustics
We analyze three applications of Ramsey’s Theorem for 4‐tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA 0 .