Ordinalize!

Peter Koepke University of Bonn

January 28, 2007

1 Introduction

Cantor’s ordinals extend the standard natural numbers ℕ into the transfinite:

0, 1, 2, 3, …, n, n + 1, … is continued by

ω, ω + 1, …, ω + n, …, ω + ω = ω · 2, ω + ω + 1 = ω · 2 + 1, … ω · ω = ω^{2}, …, ω^{3}, …, ω^{ω}, …, ω^{ω^{2}}, …, …

ω^{ω^{ω^{ω^{...}}}} , …, α, α + 1, . . . . . .

ℵ_{1}, ℵ_{1} + 1, …, ℵ_{2}, …, ℵ_{3}, …, ℵ_{ω}, . . . . . . . . . Whereas natural numbers are either 0 or successors, by the axiom of infinity there are limit ordinals like ω, ω + ω, …, ω · ω, . . .. The induction and recursion laws for ordinals extend the corresponding laws for natural numbers by limit laws, where the letter λ is used to denote limit ordinals.

A(0) ; \underline{A(n) → A(n + 1)} ; ∀nA(n) is extended to A(0) ; A(α) → A(α + 1) ; \underline{∀α < λA(α) → A(λ)} ; ∀αA(α)

The recursion law

\begin{matrix}F (0) = a_{0} \\ F (n + 1) = G(F (n), n) \end{matrix} is extended to \begin{matrix}F (0) = a_{0} \\ F (α + 1) = G(F (α), α) \\ F (λ) = G(F ↾ α) \end{matrix}

One can now go through various mathematical theories based on natural numbers and try to extend them to ordinals (Ordinalize!). This contribution to BIWOC indicates how computability on the natural numbers may be ordinalized.

2 Ordinal recursive functions

Arithmetic becomes ordinal arithmetic with the operations α + 0 = α α + (β + 1) = (α + β) + 1

α + λ = ⋃_{β<λ}(α + β)

and α · 0 = 0 α · (β + 1) = (α · β) + α

α · λ = ⋃_{β<λ}(α · β)

Problem 1 What can be defined in the structure (Ord, <, +, ·, …, 0, 1)?

Ordinal arithmetic suggests the following family of ordinal functions: Definition 1 The ordinal recursive functions form the smallest collection R of functions F : Ord^{i} → Ord such that

− the constant functions are in R − the projection functions are in R − the successor function α ↦ α + 1 is in R − the indicator function I_{<} : Ord^{2} → {0, 1}, I(α, β) = 1 iff α < β − R is closed under functional composition − R is closed under the following recursion schema, defining

F from G_{0}, G_{succ}, G_{lim}: F (0, p⃗) = G_{0}(p⃗)

F (α + 1, p⃗) = G_{succ}(F (α), α, p⃗)
F (λ, p⃗) = ⋃_{α<λ} G_{lim}(F (α), α, λ)

Example 1 The following functions are ordinal recursive:

− ordinal arithmetic − propositional logic (true∼ 1, false∼ 0):

(A ∧ B)(x⃗) = A(x⃗) · B(x⃗), ¬A(x⃗) = I_{<}(A(x⃗), 1)

− bounded quantification:

∃ν < αA(ν, x⃗) = ⋃_{ν<α} A(ν, x⃗)

− max(α, β) = α · I_{<}(β, α) + β · ¬I_{<}(β, α) − the indicator function for equality I_{=}(α, β) = (¬I_{<}(α, β)) ∧ (¬I_{<}(β, α)) − if F : Ord → Ord is ordinal recursive and strictly monotone and other

conditions hold then F^{−1} is ordinal recursive. − the sum S(α) (“= 2 + 4 + … + ν · 2 + … for ν < α”) of even ordinals by

the recursion

S(0) = 0, S(α + 1) = S(α) + α · 2, S(λ) = ⋃_{α<λ} S(α)

− define the Gödel pairing ⟨., .⟩ : Ord^{2} ↔ Ord by

⟨α, β⟩ = S(max(α, β)) + I_{<}(α, β) · α + ¬I_{<}(α, β) · (α + β)

− the projections ⟨α, β⟩ ↦ α and ⟨α, β⟩ ↦ β are ordinal recursive − via Gödel pairing and unpairing, ordinals may be seen as finite sequences

of ordinals, or as sequences of symbols

3 An ordinal language

Let the language L_{T} be appropriate for first-order structures of the type

(α, <, G, R)

where the Gödel pairing function G is viewed as a ternary relation on α and R is a unary relation on α. So the language consists of

− terms v_{n} and constants c_{ξ} for ξ ∈ Ord; c_{ξ} will be interpreted as ξ; − atomic formulas t_{1} ≡ t_{2}, t_{1} < t_{2}, Ġ(t_{1}, t_{2}, t_{3}) and Ṙ(t_{1}); − formulas ¬φ, (φ ∨ ψ), ∃v_{n} < tφ.

Note that all formulas of L_{T} are bounded. We assume an ordinal computable Gödelization such that for ζ < ξ:

φ\frac{c_{ζ}}{v_{n}} < (∃v_{n} < c_{ξ}φ).

Define the satisfaction relation (Ord, <, G, R) ⊧ φ for sentences φ as usual. Since φ is bounded,

(Ord, <, G, R) ⊧ φ iff (φ, <, G, R) ⊧ φ.

Definition 2 Define the bounded truth predicate T ⊆ Ord by

T (α) iff α is a bounded L_{T} -sentence and (α, <, G, T ∩ α) ⊨ α. In short

T (α) iff (α, T ∩ α) ⊨ α.

Theorem 1 The truth predicate T is ordinal recursive. Proof The characteristic function χ_{T} can be defined by

χ_{T} (α) = \{ \begin{matrix}1 iff ∃ν < αH(α, ν, χ_{T} (ν)) = 1 \\ 0 else \end{matrix}

with

H(α, ν, χ) = 1 iff α is an L_{T} -sentence and

∃ξ, ζ < α(α = c_{ξ} ≡ c_{ζ} ∧ ξ = ζ)

or ∃ξ, ζ < α(α = c_{ξ} < c_{ζ} ∧ ξ < ζ)
or ∃ξ, ζ, η < α(α = Ġ(c_{ξ}, c_{ζ}, c_{η}) ∧ η = G(ξ, ζ))
or ∃ξ < α(α = Ṙ(c_{ξ}) ∧ ν = ξ ∧ χ = 1)
or ∃φ < α(α = ¬φ ∧ ν = φ ∧ χ = 0)
or ∃φ, ψ < α(α = (φ ∨ ψ) ∧ (ν = φ ∨ ν = ψ) ∧ χ = 1)
or ∃n < ω∃ξ < α∃φ < α(α = ∃v_{n} < c_{ξ}φ ∧ ∃ζ < ξν = φ\frac{c_{ζ}}{v_{n}} ∧ χ = 1).

χ_{T} (α) = \{ \begin{matrix}1 iff ∃ν < αH(α, ν, χ_{T} (ν)) = 1 \\ 0 else \end{matrix}

is equivalent to

χ_{T} (α) = ⋃_{ν<α} H(α, ν, χ_{T} (ν))

and thus χ_{T} is ordinal recursive. □

4 Constructibility

Definition 3 The constructible model L was defined by Gödel:

L_{0} = ∅
L_{α+1} = Def(L_{α}) = the set of first-order definable subsets of (L_{α}, ∈)
L_{λ} = ⋃_{α<λ} L_{α}
L = ⋃_{α∈Ord} L_{α}

L is the ⊆-minimal inner model of the Zermelo-Fraenkel axioms ZFC. The bounded truth predicate T is just as strong as the constructible model:

Theorem 2 For ordinals μ and α define “sections” of the truth predicate by

X(μ, α) = {β < μ|T (G(α, β))}.

Set S = {X(μ, α)|μ, α ∈ Ord}. Then S = {x ⊆ Ord |x ∈ L}.

Proof (Sketch for ⊇) Show that (Ord, S, <, =, ∈, G) satisfies a natural theory of sets of ordinals; mathematics can be done in (Ord, S, <, =, ∈, G); define a version of Gödel’s L inside (Ord, S, <, =, ∈, G); thus every constructible set of ordinals is an element of S. □

Thus ordinal recursive functions lead to an ordinal recursion theory where ordinal recursive sets are the constructible sets.

Problem 2 Is there a reasonable recursion theory for the ordinal recursive classes with respect to ordinal recursive reducibility? Is that reducibility equivalent to Δ_{1}^{1} reducibility over L?

5 Ordinal programming languages

The essential recursion

χ_{T} (α) = \{ \begin{matrix}1 iff ∃ν < αH(α, ν, χ_{T} (ν)) = 1 \\ 0 else \end{matrix}

can be described in a recursive pseudo language like

define T(alpha) by
   input alpha
   let nu=0
   while nu<alpha
      if H(alpha,nu,T(nu))=1 return 1
      nu=nu+1
   return 0

Problem 3 Can one generalize other programming languages or language constructs to the ordinals?

6 Ordinal machines

6.1 Ordinal stack machines

Recursive programs on ordinals as above can be interpreted on machines with finite descending ordinal stacks

α_{0}(t) > α_{1}(t) > … > α_{l(t)−1}(t).

The machines works in ordinal time t with the following behaviour at limit ordinals λ:

− if (α_{0}(t), …, α_{l−1}(t)) is eventually konstant before time λ then set

(α_{0}(λ), …, α_{l−1}(λ)) = (α_{0}(t), …, α_{l−1}(t))

for sufficiently high t < λ. Also let l be maximal with that property. − if lim inf_{t→λ} α_{l}(t) is defined, set l(λ) = l + 1 and α_{l}(λ) = lim inf_{t→λ} α_{l}(t) − if lim inf_{t→λ} α_{l}(t) is undefined, set l(λ) = l

6.2 Ordinal Turing machines

− use standard Turing programs − employ lim inf-rules as limit rules for tape contents and state − The truth predicate T can be calculated by an ordinal Turing machine,

writing T successively on one of the tapes. − Thus: a set of ordinals is ordinal Turing computable iff it is constructible.

6.3 Ordinal register machines

− use standard register programs, i.e., goto programs − employ lim inf-rules for register contents and state − An ordinal stack can be simulated by an ordinal register machine. − Thus: a set of ordinals is ordinal register computable iff it is constructible.

6.4 Nondeterministic computations

A class C of sets of ordinals is nondeterministically ordinal computable if there is an ordinal Turing machine M with ordinal parameters such that for x ⊆ Ord

x ∈ C iff ∃yM accepts (x, y)

Problem 4 What is the class N = {x ⊆ Ord |{x} is non-deterministically ordinal computable}?

7 An application: fine structure for the constructible model

Apart from leading to satisfying models of infinitary computation, ordinal computability also starts to have applications in other fields. We indicate how the Jensen fine structure of the constructible hierarchy may be reconstructed within ordinal computability. We base our approach on Silver machines.

Definition 4 Consider M = (Ord, <, M), M : Ord^{<ω} ⇀ Ord. For α ∈ Ord let

M^{α} = (α, <, M ∩ α^{<ω});

for a set X ⊆ α let M^{α}[X] be the substructure of M^{α} generated by X. M is a Silver machine iff it satisfies

− Condensation: for α ∈ Ord and X ⊆ α there is a unique β such that M^{β} ≅ M^{α}[X];

− Finiteness property: for α ∈ Ord there is a finite set z ⊆ α such that for

all X ⊆ α + 1

M^{α+1}[X] ⊆ M^{α}[(X ∩ α) ∪ z] ∪ {α};

− Collapsing property: if the limit ordinal β is singular in L then there is α < β and a finite set p ⊆ Ord such that M[α ∪ p] ∩ β is cofinal in β.

Jack Silver defined Silver machines within the constructible model L and used them to give simple proofs of the combinatorial principles □ and Morass. We can naturally define a Silver machine from the bounded truth predicate T.

Definition 5 Consider the structure (Ord, <, T). Define a Skolem function by

h(α) = \{ \begin{matrix}β, if α = ∃v_{n} < c_{ξ}φ and β is minimal s. th. (α, <, G, T) ⊧ φ\frac{c_{β}}{v_{n}} \\ 0, else \end{matrix}

Let G_{1}, G_{2} be the inverses of the Gödel pairing function. Code h, G_{1}, G_{2} into a machine function M by

M(0, α) = h(α), M(1, α) = G_{1}(α), M(2, α) = G_{2}(α).

Theorem 3 M = (Ord, <, M) as defined in the previous definition is a Silver machine.

Proof (Sketch) Condensation: For α ∈ Ord and X ⊆ α there is a unique β such that M^{β} ≅ M^{α}[X]. Proof by induction on α: Let Y = M^{α+1}[X]. By inductive assumption: π :

Y ∩ α ≅ M^{β}. If α ∉ Y, then Y = Y ∩ α ≅ M^{β}. If α ∈ Y, then Y ≅ M^{β+1}; for this one mainly has to show that

π(h(α)) = h(β).

Finiteness: Observe that M^{α+1}[X] ⊆ M^{α}[(X ∩α)∪{h(α), G_{1}(α), G_{2}(α)}]∪{α} and so z = {h(α), G_{1}(α), G_{2}(α)} may be taken as the desired finite set. Collapsing: If the limit ordinal β is singular in L then there is α < β and a finite set p ⊆ Ord such that M[α ∪ p] ∩ β is cofinal in β. This holds because every constructible set of ordinals including a singularizing cofinal set for β can be decoded from T with the help of h. □

Problem 5 Can one construe fine structural constructions like the definition of □- sequences as computations of ordinal machines?