Page 77 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY 69
8 An ordinal computable truth predicate
We shall later define a truth predicate whose recursive definition is of the
form
F(α)= 1iff∃ν<αH(α,ν,F(ν))=1, 0 else.
We show that such recursions can be carried out within the collection of ordinal register computable functions: if H is computable then the recursive function F is computable. The computation will be based on a stack which can hold finite decreasing sequences of ordinals and some other information.
8.1 3-adic representations and ordinal stacks
We intend to use a stack that can hold a (finite) sequence α0 > α1 > ··· > αn−2 αn−1 of ordinals which is strictly decreasing except possibly for the last two ordinals. This sequence of ordinals can coded by the ordinal α = 3α0 + 3α1 + · · · + 3αn−1 . We state some facts of ordinal arithmetic and define computable functions for dealing with ordinals as stacks.
Proposition 8.1. Let > 1 be a fixed basis ordinal. An equality α=δα0 ·ζ0 +δα1 ·ζ1 +···+δαn−1 ·ζn−1
with α0 > α1 > ··· > αn−1 and 0 < ζ0,ζ1,...,ζn−1 < δ is called a δ-adic representation of α. We claim that every α ∈ Ord possesses a unique δ-adic representation.
Proof. Assume the property for β < α. Since the ordinal exponentiation ν → δν is continuous and strictly monotone there is a maximal α0 α such that δα0 α. Then
δα0+1=δα0 ·δ>α.
Since the ordinal multiplication ν → δα0 · ν is continuous and strictly monotone
thereisalargestζ0,0<ζ0 <δsuchthatδα0 ·ζ0 α.Then δα0 ·(ζ0 +1)=δα0 ·ζ0 +δα0 >α.
Since the ordinal addition ν → δα0 · ζ0 + ν is an increasing enumeration of the ordinals δα0 ·ζ0 there is β < δα0 α such that α = δα0 ·ζ0+β. By the inductive assumption, β has a δ-adic representation β = δα1 · ζ1 + · · · + δαn−1 · ζn−1. Since β<δα0 wehaveα1 <α0.Thus
α=δα0 ·ζ0 +δα1 ·ζ1 +···+δαn−1 ·ζn−1 is a δ-adic representation of α.