Finite trees and the necessary use of large cardinals


Abstract
We introduce insertion domains that support the placement of new, higher, vertices into finite trees. We prove that every nonincreasing insertion domain has an element with simple structural properties in the style of classical Ramsey theory. This result is proved using standard large cardinal axioms that go well beyond the usual axioms for mathematics. We also establish that this result cannot be proved without these large cardinal axioms. We also introduce insertion rules that specify the placement of new, higher, vertices into finite trees. We prove that every insertion rule greedily generates a tree with these same structural properties; and every decreasing insertion rule generates (or admits) a tree with these same structural properties. It is also necessary and sufficient to use the same large cardinals (in the precise sense of Corollary D.25). The results suggest new areas of research in discrete mathematics called "Ramsey tree theory" and "greedy Ramsey theory" which demonstrably require more than the usual axioms for mathematics.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,062
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Godel's Unpublished Papers on Foundations of Mathematics.W. W. Tatt - 2001 - Philosophia Mathematica 9 (1):87-126.
The Metamathematics of Ergodic Theory.Jeremy Avigad - 2009 - Annals of Pure and Applied Logic 157 (2-3):64-76.
Subtle Cardinals and Linear Orderings.Harvey M. Friedman - 2000 - Annals of Pure and Applied Logic 107 (1-3):1-34.
Intuition and Its Object.Kai Hauser - 2015 - Axiomathes 25 (3):253-281.
Proof Theory in Philosophy of Mathematics.Andrew Arana - 2010 - Philosophy Compass 5 (4):336-347.

View all 6 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
358 ( #12,686 of 2,320,192 )

Recent downloads (6 months)
1 ( #830,753 of 2,320,192 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature