Appendix A: The Stationary Ramsey Property
Reprinted from Crangle et al. (2014)
All results in this section are taken from Friedman 2001. All of these results, with the exception of Theorem 9.1.1, iv ↔ v → vi, are credited in (Friedman 2001) to James Baumgartner. Below, λ always denotes a limit ordinal.
Definition A.1
We say that C ⊆ λ is unbounded if and only for all α < λ there exists β ∈ C such that β ≥ α.
Definition A.2
We say that C ⊆ λ is closed if and only if for all limit ordinals x < λ, if the sup of the elements of C below x is x, then x ∈ C.
Definition A.3
We say that A ⊆ λ is stationary if and only if it intersects every closed unbounded subset of λ.
Definition A.4
For sets A, let S(A) be the set of all subsets of A. For integers k ≥ 1, let Sk(A) be the set of all k element subsets of A.
Definition A.5
Let k ≥ 1. We say that λ has the k-SRP if and only if for every f:Sk(λ) → {0, 1}, there exists a stationary E ⊆ λ such that f is constant on Sk(E). Here SRP stands for “stationary Ramsey property.”
The k-SRP is a particularly simple large cardinal property. To put it in perspective, the existence of an ordinal with the 2-SRP is stronger than the existence of higher order indescribable cardinals, which is stronger than the existence of weakly compact cardinals, which is stronger than the existence of cardinals which are, for all k, strongly k-Mahlo (see Theorem A.1 below, and Friedman 2001, Lemma 1.11).
Our main results are stated in terms of the stationary Ramsey property. In particular, we use the following extensions of ZFC based on the SRP.
Definition A.6
SRP+ = ZFC + “for all k there exists an ordinal with the k-SRP”. SRP = ZFC + {there exists an ordinal with the k-SRP}k. We also use SRP[k] for the formal system ZFC + (∃λ)(λ has the k-SRP).
For technical reasons, we will need to consider some large cardinal properties that rely on regressive functions.
Definition A.7
We say that f:Sk(λ) → λ is regressive if and only if for all A ∈ Sk(λ), if min(A) > 0 then f(A) < min(A). We say that E is f-homogenous if and only if E ⊆ λ and for all B, C ∈ Sk(E), f(B) = f(C).
Definition A.8
We say that f:Sk(λ) → S(λ) is regressive if and only if for all A ∈ Sk(λ), f(A) ⊆ min(A). (We take min(∅) = 0, and so f(∅) = ∅). We say that E is f-homogenous if and only if E ⊆ λ and for all B, C ∈ Sk(E), we have f(B) ∩ min(B ∪ C) = f(C) ∩ min(B ∪ C).
Definition A.9
Let k ≥ 1. We say that α is purely k-subtle if and only if
-
(i)
α is an ordinal;
-
(ii)
For all regressive f:Sk(α) → α, there exists A ∈ Sk+1(α\{0, 1}) such that f is constant on Sk(A).
Definition A.10
We say that λ is k-subtle if and only if for all closed unbounded C ⊆ λ and regressive f:Sk(λ) → S(λ), there exists an f-homogenous A ∈ Sk+1(C).
Definition A.11
We say that λ is k-almost ineffable if and only if for all regressive f:Sk(λ) → S(λ), there exists an f-homogenous A ⊆ λ of cardinality λ.
Definition A.12
We say that λ is k-ineffable if and only if for all regressive f:Sk(λ) → S(λ), there exists an f-homogenous stationary A ⊆ λ.
Theorem A.1
Let k ≥ 2. Each of the following implies the next, over ZFC.
-
i.
there exists an ordinal with the k-SRP.
-
ii.
there exists a (k − 1)-ineffable ordinal.
-
iii.
there exists a (k − 1)-almost ineffable ordinal.
-
iv.
there exists a (k − 1)-subtle ordinal.
-
v.
there exists a purely k-subtle ordinal.
-
vi.
there exists an ordinal with the (k − 1)-SRP.
Furthermore, i, ii are equivalent, and iv, v are equivalent. There are no other equivalences. ZFC proves that the least ordinal with properties i - vi (whichever exist) form a decreasing (≥) sequence of uncountable cardinals, with equality between i, ii, equality between iv, v, and strict inequality for the remaining consecutive pairs.
Proof
i ↔ ii is from Friedman (2001), Theorem 1.28, iv ↔ v is from Friedman (2001), Corollary 2.17. The strict implications ii → iii → iv → vi are from Friedman (2001), Theorem 1.28. Same references apply for comparing the least ordinals. □
Definition A.13
We follow the convention that for integers p ≤ 0, a p-subtle, p-almost ineffable, p-ineffable ordinal is a limit ordinal, and that the ordinals that are 0-subtle, 0-almost ineffable, 0-ineffable, or have the 0-SRP, are exactly the limit ordinals. An ordinal is called subtle, almost ineffable, ineffable, if and only if it is 1-subtle, 1-almost ineffable, 1-ineffable.
Appendix B: Formal Systems Used
PFA Polynomial function arithmetic. Based on 0, successor, addition, multiplication, and bounded induction. Same as IΣ0 (Hajek and Pudlak 1993, p. 29, 405).
EFA Exponential function arithmetic. Based on 0, successor, addition, multiplication, exponentiation and bounded induction. Same as IΣ0(exp) (Hajek and Pudlak 1993, p. 37, 405).
RCA0 Recursive comprehension axiom naught. Our base theory for Reverse Mathematics (Simpson 2009).
WKL0 Weak Konig’s Lemma naught. Our second level theory for Reverse Mathematics (Simpson 2009).
ACA0 Arithmetic comprehension axiom naught. Our third level theory for Reverse Mathematics (Simpson 2009).
ACA′ Arithmetic comprehension axiom prime. ACA0 together with “for all n < ω and x ⊆ ω, the n-th Turing jump of x exists”.
Z2 s order arithmetic as a two sorted first order theory (Simpson 2009).
Z3 Third order arithmetic as a three sorted first order theory. Extends Z2 with a new sort for sets of subsets of ω.
Z(C) Zermelo set theory (with the axiom of choice). This is the same as ZF(C) without the axiom scheme of replacement.
ZF(C)\P ZF(C) without the power set axiom (Kanamori 1994).
ZF(C) Zermelo Frankel set theory (with the axiom of choice). ZFC is the official theoretical gold standard for mathematical proofs (Kanamori 1994).
SRP[k] ZFC + (∃λ)(λ has the k-SRP), for fixed k. Appendix A.
SRP ZFC + (∃λ)(λ has the k-SRP), as a scheme in k. Appendix A.
SRP+ ZFC + (∀k)(∃λ)(λ has the k-SRP). Appendix A.
