Proof theory of indescribable cardinals
Toshiyasu Arai(Chiba)
I will explain how to lift up the ordinal analyses to a Π1n+1- indescribable cardinals. This yields a proof-theoretic reduction of the existence of a Π1n+1-indescribable cardinal to iterations of Π1n-indescribabilities over ZF+V=L.
PLAN of the talk 1. Π1n-indescribability, pp. 4-9
2. Reduction of Π1N+1-indescribability, pp. 10-24
1 Π1n-indescribability
Ordinal analyses in [Rathjen94], [A09] yield a proof-theoretic re- duction of Π3-reflecting ordinals to iterations of recursively Mahlo operations.
Recall that a Π3-reflecting ordinal is a recursive analogue of the weakly compact cardinal, i.e., Π11-indescribable cardinal, and a ΠN+2-reflecting ordinal is a recursive analogue of Π1N-indescribable cardinal for N ≥ 1.
For a universal ΠN-formula ΠN(a)
P ∈ RMN(X ) :⇔ ∀b ∈ P [P |= ΠN(b) → ∃Q ∈ X ∩ P (Q |= ΠN(b))] (read:P is Π -reflecting on X .)
Let <ε be a ∆-predicate such that for any transitive and well- founded model V of KPω, <ε is a canonical well ordering of type εK+1 for the order type K of the class Ord of ordinals in V , and P ∈ RMN(a; ≺) iff
a ∈ P ∈ !{RMN(RMN(b; ≺)) : b ∈ P |= b ≺ a}
for the ΠN-recursively Mahlo operation RMN and definable rela- tions ≺.
Theorem 1.1 ([A∞2]) For each N ≥ 2, KPΠN+1 is ΠN+1- conservative over the theory
The easier half, KPΠN+1 , V ∈ RMN(*ωn(K + 1)+; <ε) for each n < ω, follows from metainduction on n using the fact that for each n, the transfinite induction up to *ωn(K + 1)+ along <ε is provable in KPω, and a fortiori in KPΠN+1, and RMN(a; <ε) is
a ΠN+1-definable class: Assume ∀b <ε a(V ∈ RMN(b; <ε)) and a ΠN-sentence ϕ holds in V . Then for each b <ε a, the ΠN+1- sentence θ :⇔ (V ∈ RMN(b; <ε))∧ϕ holds in the ΠN+1-reflecting universe V . Pick a transitive P ∈ V so that P contains parameters occurring in θ, and θ holds in P . Since P |= V ∈ RMN(b; <ε) iff P ∈ RMN(b; <ε), this means that V ∈ RMN(a; <ε).
For the other half I need an ordinal analysis based on cut- elimination with operator controlled derivations.
In lifting up Theorem 1.1 to the indescribable cardinals, a re- cent characterization of Π1n+1-indescribability due to J. Bagaria, M. Magidor and H. Sakai, is helpful.
Definition 1.2 Let κ be a regular uncountable cardinal, and n ∈ ω. S ⊂ κ is said to be Π1n-indescribable in κ if for any A ⊂ Vκ and any Π1n-formula ϕ with Vκ |= ϕ[A] there exists a µ ∈ S such that Vµ |= ϕ[A∩Vµ]. κ is said to be Π1n-indescribable iff κ itself is Π1n-indescribable in κ.
Π1N-Mahlo operation MN:
κ ∈ M (S) iff S ∩ κ is Π1 -indescribable in κ
Definition 1.3 n-stationary subsets, and (n + 1)-club (closed and unbounded) subsets of a regular uncountable cardinal κ are defined by recursion on n ≥ −1 as follows.
1. S ⊂ κ is (−1)-stationary in κ if S is unbounded in κ.
2. For n ≥ 0, S ⊂ κ is n-stationary in κ if S meets every n-club subset of κ.
3. C ⊂ κ is (n + 1)-club in κ if C is n-stationary in κ, and λ ∈ C for all Π1n-indescribable λ <κ such that C ∩ λ is n-stationary in λ, where λ is defined to be Π1−1-indescribable iff λ is a limit ordinal.
‘S ⊂ κ is n-stationary’ is Π1n+1-definable uniformly on regular uncountable cardinals κ, while ‘C ⊂ κ is n-club’ is Π1n-definable.
The case n = 0 of the following theorem is due to [Jensen72]. Theorem 1.4 ([Bagaria-Magidor-Sakai∞], cf. [Hellsten03])
Assume V = L. Let n ∈ ω. Then the following are equivalent for every Π1n-indescribable cardinal K:
1. K is Π1n+1-indescribable.
2. For any n-stationary subset S of K, there exists a Π1n-indescribable cardinal λ < K such that S ∩ λ is n-stationary in λ.
2 Reduction of Π1N+1-indescribability
The Π1N-Mahlo operation MN is Π1N+1-definable uniformly on any regular uncountable cardinals. Hence the operation MN can be iterated along any definable relations in Π1N+1-indescribable car- dinals K as in ΠN+1-reflecting ordinals. By ‘definable’ relation, I mean a definable relation on the universe V , in which a Π1N+1- indescribable cardinal exists.
Let <ε be a ∆-predicate such that for any transitive and well- founded model V of KPω, <ε is a canonical well ordering of type εI+1 for the order type I of the class Ord of ordinals in V .
I will show that the assumption of the Π1N+1-indescribability is proof-theoretically reducible to iterations of an operation along initial segments of <ε over ZF+V=L. The operation is a mixture of Π1N-Mahlo operation MN and Mostowski collapsings.
Let K be a Π1N+1-indescribable cardinal. For α <ε εK+1 and finite sets Θ ⊂f in (K + 1), Πn+1-classes M hαn[Θ] are defined so that the following holds.
Theorem 2.1 ([A∞3], [A∞4]) 1. For each n < ω,
ZF+(V = L)+(K is Π1N+1-indescribable) , K ∈ M hωnn(I+1)[∅]. 2. For any Σ1N+2-sentences ϕ, if
ZF + (V = L) + (K is Π1n+1-indescribable) , ϕLK, then we can find an n < ω such that
ZF + (V = L) + (K ∈ Mhωnn(I+1)[∅]) , ϕLK.
Let us recall ordinals for ZF+V=L in [A∞1]. Let I be a weakly inaccessible cardinal.
Definition 2.2 For X ⊂ LI, HullΣn(X) denotes the Σn-Skolem hull of X in LI. a ∈ HullΣn(X) ⇔ {a} ∈ ΣLnI(X) (a ∈ LI).
Definition 2.3 (Mostowski collapsing function F )
By the Condensation Lemma we have an isomorphism (Mostowski collapsing function)
F : HullΣn(X) ↔ Lγ
for an ordinal γ ≤ I such that F ! Y = id ! Y for any transitive
Let us denote, though I 4∈ dom(F ) = HullΣn(X) F (I) := γ.
Let us denote the isomorphism F on HullΣn(X) ↔ Lγ by FXΣn. In what follows K denotes a Π1N+1-indescribable cardinal, and I the least weakly inaccessible cardinal above K.
Definition 2.4 Hα,n(X) is a Skolem hull of {0, K, I}∪X under the functions +, α 6→ ωα,
ΨI,n !α, Ψκ,n!α (regular κ <I ), the Σn-definability: X 6→ HullΣn(X ∩ I)
and the Mostowski collapsing functions
(x = Ψκ,nγ, δ) 6→ Fx∪{κ}Σ1 (δ) (κ ∈ R) and
(x = ΨI,nγ, δ) 6→ FxΣn(δ). For κ ≤ I
Γ denotes a sequent, a finite set of sentences. Its intended mean- ing is the disjunction "{A : A ∈ Γ}.
The idea of the controlled derivations due to [Buchholz92] is to consider a relation
H ,a Γ
where the set k(A) of L-ranks rkL(c) of sets c occurring in sentences A ∈ Γ together with the depth a of derivations are controlled by Skolem hulls H in such a way that
{a} ∪ k(A) ⊂ H
and simultaneously the L-rank of witnessing sets is to be bounded by the depths.
Let us see how the class M hαn[Θ] looks like through cut-elimination. Over ZF + (V = L) with K ∈ MN, the Π1N+1-indescribability of K is codified using the L-least counter example S ∈ HullΣ1({K, K+}) to the Π1N+1-indescribability of K.
H ,a! Γ, ¬τN(S, K) H ,ar Γ, ∀ρ ∈ MN ∩ K[τN(S, ρ)]
H ,a Γ (RefK)
where τN(S, ρ) says that S is N -thin(non-stationary)
τN(S, ρ) :⇔ ∃C ⊂ ρ[(C is N -club)ρ ∧ (S ∩ C = ∅)] (Σ1N+1 on ρ)
Let us try to show the following lemma by induction on ξ.
Lemma 2.5 (?) For Π1N+1-sentences A and a ξ-times iterations M hξ of MN
H ,ξ AK ⇒ ∀π ∈ M hξ(Aπ is true).
H ,ξ AK ⇒ ∀π ∈ M hξ(Aπ is true).
H ,ξ! AK, ¬τN(S, K) H ,ξr AK, ∀ρ ∈ MN ∩ K[τN(S, ρ)]
H ,ξ AK (RefK)
Let π ∈ M hξ. IH yields ∀ρ ∈ MN ∩ π[Aπ ∨ τN(S, ρ)] and
∀ρ ∈ M hξ! ∩ π[Aρ ∨ ¬τN(S, ρ)]. Supposing
M hξ! ⊂ MN (1)
we have ∀ρ ∈ M hξ! ∩ π[Aρ ∨ Aπ].
H ,ξ AK ⇒ ∀π ∈ M hξ(Aπ is true). On the other hand we have π ∈ M hξ ∧ ξ/ ∈ H ∩ ξ.
Moreover suppose
π ∈ M hξ ∧ ξ/ ∈ H ∩ ξ ⇒ π ∈ MN(M hξ!) (2) Then Proposition 2.6 with Aπ ∨ ∀ρ ∈ M hξ! ∩ π Aρ yields Aπ. Proposition 2.6 Let A be a Π1N+1-sentence, and π ∈ MN(X).
If ∀ρ ∈ X ∩ π[Lλ |= A], then Lπ |= A.
H ,ξ AK ⇒ ∀π ∈ M hξ(Aπ is true).
For a true literal (d ∈ S), where S ⊂ K such that S ∈ HullIΣ1({K, K+}) and d ∈ K. (d ∈ S)π ≡ (d ∈ (S ∩ π)).
H ,ξ d ∈ S (
#)
We have d ∈ H ∩ K, and hence d < π if
π ∈ M hξ ⇒ H ∩ K ⊂ π (3)
H ,ξ AK ⇒ ∀π ∈ M hξ(Aπ is true).
{H[{rkL(C)}] ,ξ(C) (S ∩ C 4= ∅) : C is N -club in K} H ,ξ ¬τN(S, K) (S ∈ HullΣ1({K, K+})) (
#)
Let π ∈ M hξ, and suppose τN(S, π), i.e., S ∩ π is N -thin, and let C0 := µC ∈ Lπ+[(C ⊂ π is N -club) ∧ (S ∩ C = ∅)]
It turns out that the multiplication C of C0 is also N -club in K: C = {γ ∈ K : ∃x, y < K(γ = π · x + y ∧ y ∈ C0 ∪ {0})}. Since C ∈ HullΣ1({K, K+, π, π+}) ⊂ H[{π}], we have
H[{π}] ,ξ(C) (S ∩ C 4= ∅)
H ,ξ AK ⇒ ∀π ∈ M hξ(Aπ is true).
H[{π}] ,ξ(C) (S ∩ C 4= ∅) IH yields ∀ρ ∈ M hξ(C)(S ∩ C ∩ ρ 4= ∅), and
∅ = S ∩ C0 = S ∩ C ∩ π 4= ∅ by Proposition 2.6 if
π ∈ M hξ ∧ ξ(C) ∈ H[{π}] ∩ ξ ⇒ π ∈ MN(M hξ(C)) (4) Finally let us define classes M hξ.
π ∈ M hξ ⇒ H ∩ K ⊂ π (3)
M hξ! ⊂ MN (1)
π ∈ M hξ ∧ ξ(C) ∈ H[{π}] ∩ ξ ⇒ π ∈ MN(M hξ(C)) (4) Definition 2.7 Let Θ ⊂f in (K + 1) and K ≥ π be regular uncountable. Then π ∈ M hαn[Θ] iff
Hα,n(π) ∩ K ⊂ π & α ∈ Hα,n[Θ](π)
& ∀ξ ∈ Hξ,n[Θ ∪ {π}](π) ∩ α[π ∈ MN(M hξn[Θ ∪ {π}])]
References
[A97] T. Arai, A sneak preview of proof theory of ordinals, an invited talk at Kobe seminar on Logic and Computer Science, 5-6 Dec. 1997. appeared in Ann. Japan Asso. Phil. Sci. 20(2012), 29-47. [A09] T. Arai, Iterating the recursively Mahlo operations, 13th LMPS(2009), pp. 21-35.
[A∞1] T. Arai, Lifting up the proof theory to the countables: Zermelo-Fraenkel’s set theory, submitted. arXiv: 1101.5660.
[A∞2] T. Arai, Conservations of first-order reflections, submitted. arXiv 1204.0205. [A∞3] T. Arai, Proof theory of weak compactness, submitted. arXiv:1111.0462. [A∞4] T. Arai, Proof theory of Π1n-indescribability, in preparation.
[Bagaria-Magidor-Sakai∞] J. Bagaria, M. Magidor and H. Sakai, private communication.
[Buchholz92] W. Buchholz, A simplified version of local predicativity, P. H. G. Aczel, H. Simmons and S. S. Wainer(eds.), Proof Theory, Cambridge UP, 1992, pp. 115-147.
[Hellsten03] A. Hellsten, Diamonds on large cardinals, Ann. Acad. Sci. Fenn., Ser. A I, Diss. 133, 2003. [Jensen72] R. Jensen, The fine structure of the constructible hierarchy, AML 4(1972), 229-308.
