Elementary ordinal representation systems for KP theories

Osamu Takaki ^{∗}

                        takaki@i.h.kyoto-u.ac.jp

Research Fellow of the Japan Society for the Promotion of Science, Mathematical Science Group, Faculty of Integrated Human Studies

Elementary ordinal representation systems (which we abbreviate to EORSs) have been developed for establishing proof theoretic ordinals of set theoretical or arithmetical systems. This article is devoted to mention some relationships between several EORSs, which are (essentially) define by W.Buchholz and M.Rathjen (cf. [1], [2], [5] and [3]).

In order to obtain proof theoretic ordinals of set theoretic systems based on KP (Kripke-Platek set theory) such as KPi and KPM by using the method called “collapsing method”, one can deal with several large cardinals and admissible ordinals. For example, he can first consider a certain cardinal κ and an admissible ordinal α corresponding to κ and a system KP^{∗} which is based on KP and characterized by α, and next he can define certain sets of ordinals and functions by employing κ (which are called “Skolem hulls and collapsing functions”) and, by using such sets and functions, establish an EORS which bears |KP^{∗}| (the proof theoretic ordinal of KP^{∗}).

Observing these inventions such as Skolem hulls, collapsing functions, and EORSs, we can expect a possibility of existence of primitive recursive ordinals corresponding to large cardinals (and admissible ordinals) which are employed for establishing the proof theoretic ordinals. In fact, in [6] and [7], we define “proof-theoretically regular ordinals” which are primitive recursive analogues of several regular cardinals. Since these ordinals are defined by using some EORSs, they deeply depends on the EORSs with which we define them. Therefore, it is necessary to check relationships between EORSs. The results of this article imply that EORSs defined in this article share a certain initial segment of proof-theoretically regular ordinals (see Co.10 and Co.17).

Let + denote ordinary (noncommutative) ordinal addition. An ordinal α > 0 is called an additive principal number iff ∀ β, γ (β, γ < α ⇒ α+β < α). Let AP denote the class of additive principal numbers. The Veblen function φ is defined by: φαβ is the βth element γ of AP such that ∀ ξ < α (φξγ = γ). For example, φ0α is the αth additive principal number (= ω^{1+α}), and φ1α is the αth ε-number (= ε_{α}). An ordinal γ > 0 is said to be strongly critical iff ∀ α, β (β, α < γ ⇒ φαβ < γ). For each ordinal α, let Γ_{α} denote the αth strongly critical ordinal.

Let Reg denote the class of (uncountable) regular cardinals, Ω_{α} denote the αth cardinal, and let I denote the least weakly inaccessible cardinal.

Definition 1 (Skolem hulls and Collapsing functions based on I: Buchholz [2]) For each α < Γ_{I+1} and β < I, we define a set C^{I}(α, β) and a function ψ_{I}^{α} : Reg ∩ I → I by recursion on α, as follows. (I1) β ∪ {0, I} ⊂ C^{I}(α, β). (I2,3) If γ, δ ∈ C^{I}(α, β), then γ + δ, φγδ ∈ C^{I}(α, β). (I4) If γ ∈ C^{I}(α, β), then Ω_{γ} ∈ C^{I}(α, β). (I5) If γ ∈ C^{I}(α, β) ∩ α and κ ∈ C^{I}(α, β) ∩ Reg ∩ I, then ψ_{I}^{γ}(κ) ∈ C^{I}(α, β). ψ_{I}^{α}(κ) := min{ρ < κ : C^{I}(α, ρ) ∩ κ = ρ&κ ∈ C^{I}(α, ρ)}.

Definition 2 We define a set T (I), as follows. ^{1} (T_{I}1) 0, I ∈ T (I). (T_{I}2) If α, β ∈ T (I) ∩ (α + β), then α + β ∈ T (I).

∗The authors is supported by grant of JSPS No.11-3979.

1One can consider each EORS to be formalized as a set of finite strings of suitable symbols (for example, see Sec.2 in [4]). Indeed, we can regard each EORS as a primitive recursive order structure.

(T_{I}3) If α, β ∈ T (I) ∩ φαβ and (φαβ < I or (α = 0 & β > I)), then φαβ ∈ T (I). (T_{I}4) If α ∈ T (I) ∩ Ω_{α} and 0 < α < I, then Ω_{α} ∈ T (I). (T_{I}5) If γ = ψ_{I}^{α}(κ), α ∈ C^{I}(α, γ) and α, κ ∈ T (I), then γ ∈ T (I).

Lemma 3 Every element of T (I) has a unique expression by symbols 0, I, +, φ, Ω and ψ_{I}.

Theorem 4 (Buchholz [2] (See also [3].)) ψ_{I}^{ε_{I+1}}(Ω_{1}) = T (I) ∩ Ω_{1} = |KPi|.

We next define an EORS for KPM, which is based on [5]. Let M denote the least weakly Mahlo cardinal.

Definition 5 (Skolem hulls and Collapsing functions based on M) For each α < Γ_{M+1} and β < M, we define a set C^{M}(α, β) and functions χ^{α}, ψ_{M}^{α} by recursion on α, as follows. (M1) β ∪ {0, M} ⊂ C^{M}(α, β). (M2,3) If γ, δ ∈ C^{M}(α, β), then γ + δ, φγδ ∈ C^{M}(α, β). (M4) If γ ∈ C^{M}(α, β), then Ω_{γ} ∈ C^{M}(α, β). (M5) If γ, δ ∈ C^{M}(α, β) and γ < α, then χ^{γ}(δ) ∈ C^{M}(α, β). (M6) If γ ∈ C^{M}(α, β) ∩ α and κ ∈ C^{M}(α, β) ∩ Reg ∩ M, then ψ_{M}^{γ}(κ) ∈ C^{M}(α, β). χ^{α}(δ) := the δ^{th} regular cardinal π < M s.t. C^{M}(α, π) ∩ M = π. ψ_{M}^{α}(κ) ≃ min{ρ < κ : C^{M}(α, ρ) ∩ κ = ρ & κ ∈ C^{M}(α, ρ)}.

Definition 6 We define a set T (M), as follows. (T_{M}1) 0, M ∈ T (M). (T_{M}2) If α, β ∈ T (M) ∩ (α + β), then α + β ∈ T (M). (T_{M}3) If α, β ∈ T (M) ∩ φαβ and (φαβ < M or (α = 0 & β > M)), then φαβ ∈ T (M). (T_{M}4) If α ∈ T (M) ∩ Ω_{α} and 0 < α < M, then Ω_{α} ∈ T (M). (T_{M}5) If γ = χ^{ξ}(α), α < γ, ξ ∈ C^{M}(ξ, γ) and ξ, α ∈ T (M), then γ ∈ T (M). (T_{M}6) If γ = ψ_{M}^{α}(κ), α ∈ C^{M}(α, γ) and α, κ ∈ T (M), then γ ∈ T (M).

Lemma 7 (1) Every element of T (M) has a unique expression by symbols 0, M, +, φ, Ω, χ and ψ_{M}.

(2) ψ_{M}^{ε_{M+1}}(Ω_{1}) = T (M) ∩ Ω_{1}.

Definition 8 We define a mapping ∗ from T (I) to T (M) by recursion on the structure of each element of T (I), as follows.

(i) 0^{∗} := 0 and I^{∗} := χ^{0}(0). (ii) (α + β)^{∗} := α^{∗} + β^{∗}. (iii) (φαβ)^{∗} := φα^{∗}β^{∗}. (iv) (Ω_{α})^{∗} := Ω_{α^{∗}}.

(v) (ψ_{I}^{α}(κ))^{∗} := ψ_{M}^{α^{∗}}(κ^{∗}).

Theorem 9 Let ∗⌈_{T (I)∩Ω_{1}} denote the restriction of ∗ to T (I) ∩ Ω_{1}. Then, ∗⌈_{T (I)∩Ω_{1}} is the identity function from T (I) ∩ Ω_{1} to ψ_{M}^{ε_{I+1}}(Ω_{1}), that is, for each γ ∈ T (I) ∩ Ω_{1}, γ^{∗} = γ.

The most important point of the proof of Th.9 is to check that ∗ is well-defined to be a strictly order-preserving function from T (I) to T (M) and that every γ less than ψ_{M}^{ε_{I+1}}(Ω_{1}) contains no symbol in T (M) which can not be interpreted with symbols in T (I).

Corollary 10 (1) ψ_{I}^{ε_{I+1}}(Ω_{1}) = ψ_{M}^{ε_{I+1}}(Ω_{1}) = |KPi|.

(2) ∀τ ∈ T (I) ∩ Reg ( ψ_{I}^{τ} (Ω_{1}) ∈ T (I) ⇒ τ^{∗} ∈ T (M) ∩ Reg & ψ_{M}^{τ^{∗}}(Ω_{1}) ∈ T (M) & ψ_{I}^{τ} (Ω_{1}) = ψ_{M}^{τ^{∗}}(Ω_{1}) ).

In [6], we define a “proof-theoretically regular ordinal based on an EORS T ” to be an element of T which is of the form ψ^{κ}(Ω_{1}) for some κ ∈ Reg, where ψ^{κ} is a collapsing function with which T is constructed (see [6] or [7] for details). Therefore, Co.10.(2) means that every proof-theoretically regular ordinal based on T (I) is that based on T (M).

We next compare T (M) with another EORS denoted by T_{B}(M) which is (essentially) defined in [1].

Definition 11 For ordinals α < Γ_{M+1} and β < M, we define a set B^{M}(α, β) and a function ψ_{B}^{α} : Reg ∩ (M + 1) → On by recursion on α, as follows. (B1) β ∪ {0, M} ⊂ B^{M}(α, β). (B2,3) If γ, δ ∈ B^{M}(α, β), then γ + δ, φγδ ∈ B^{M}(α, β). (B4) If γ ∈ B^{M}(α, β), then Ω_{γ} ∈ B^{M}(α, β). (B5) If γ ∈ B^{M}(α, β)∩α, κ ∈ B^{M}(α, β)∩Reg∩(M +1) and γ, κ ∈ B^{M}(γ, ψ_{B}^{γ}(κ)), then ψ_{B}^{γ}(κ) ∈ B^{M}(α, β). ψ_{B}^{α}(κ) := min{ρ ∈ D_{κ}(α) : B^{M}(α, ρ) ∩ κ ⊆ ρ}, where

D_{κ}(α) := \{ \begin{matrix}\{ζ ∈ Reg ∩ (M + 1) : α ∈ B^{M}(α, M) ⇒ α ∈ B^{M}(α, ζ)\} & if κ = M; \\ \{ζ : κ ∈ B^{M}(α, κ) ⇒ κ ∈ B^{M}(α, ζ)\} & if κ < M. \end{matrix}

Definition 12 We define a set T_{B}(M), as follows. (T_{B}1) 0, M ∈ T_{B}(M). (T_{B}2) α, β ∈ T_{B}(M) ∩ (α + β) ⇒ α + β ∈ T_{B}(M). (T_{B}3) If α, β ∈ T_{B}(M) ∩ φαβ and (φαβ < M or (α = 0 & β > M)), then φαβ ∈ T_{B}(M). (T_{B}4) If α ∈ T_{B}(M) ∩ Ω_{α} and 0 < α < M then Ω_{α} ∈ T_{B}(M). (T_{B}5) If γ = ψ_{B}^{α}(κ), α, κ ∈ C^{I}(α, γ) and α, κ ∈ T_{B}(M), then γ ∈ T_{B}(M).

Lemma 13 Every element of T_{B}(M) has a unique expression by symbols 0, M, +, φ, Ω and ψ_{B}.

Theorem 14 (Buchholz [1]) ψ_{B}^{ε_{M+1}}(Ω_{1}) = T_{B}(M) ∩ Ω_{1} ≥ |KPM|.

Definition 15 We define a mapping ♯ from T_{B}(M) to T (M) by recursion on the structure of each element of T_{B}(M), as follows.

(i) 0^{♯} := 0 and M^{♯} := M. (ii) (α + β)^{♯} := α^{♯} + β^{♯}. (iii) (φαβ)^{♯} := φα^{♯}β^{♯}. (iv) (Ω_{α})^{♯} := Ω_{α^{♯}}.

(v) If γ =nf ψ_{B}^{α}(κ), then (ψ_{B}^{α}(κ))^{♯} := \{ \begin{matrix}χ^{α^{♯}}(0) & if κ = M; \\ ψ_{M}^{α^{♯}}(κ^{♯}) & if κ < M. \end{matrix}

Theorem 16 (1) ♯ is well-defined to be a strictly order-preserving function from T_{B}(M) to T (M).

(2) ♯⌈_{ψ_{B}^{ε_{ψ{0 \atop B} (M)+1}} (Ω_{1})} is the identity function from ψ_{B}^{ε_{ψ{0 \atop B} (M)+1}}(Ω_{1}) to ψ_{M}^{ε_{I+1}}(Ω_{1}).

Corollary 17 (1) ψ_{M}^{ε_{M+1}}(Ω_{1}) ≥ ψ_{B}^{ε_{M+1}}(Ω_{1}).

(2) ∀τ ∈ T (I)∩Reg ( ψ_{I}^{τ} (Ω_{1}) ∈ T (I) ⇒ ∃κ ∈ T_{B}(M)∩Reg ( ψ_{B}^{κ}(Ω_{1}) ∈ T_{B}(M) & ψ_{I}^{τ} (Ω_{1}) = ψ_{B}^{κ}(Ω_{1}) ) ).

References

[1] W. Buchholz, A note on the ordinal analysis of KPM, Proceedings Logic Colloquium ’90 (Edited by J. Väänänen), (1992) p1-9.

[2] W. Buchholz, A simplified version of local predicativity, Proof Theory (Edited by P. Aczel, H. Simmons and S. Wainer), (1993) p117-147.

[3] W. Pohlers. Subsystems of set theory and second order number theory, Handbook of Proof Theory (Edited by S. R. Buss), (1998) p209-335.

[4] M. Rathjen, Proof-theoretic analysis of KPM, Archive for Mathematical Logic, 30 (1991) p377-403.

[5] M. Rathjen, The higher infinite in proof theory, Logic Colloquium ’95, Lecture Notes in Logic, 11 (1998) p275-304.

[6] O. Takaki, Primitive recursive analogues of the least regular cardinal and the least weakly inaccessible cardinal, Submitted for publication.

[7] O. Takaki, Proof-theoretically inaccessible ordinals and Proof-theoretically Mahlo ordinals, Preprint.