Buchholz psi functions explained

\psi _{\nu(\alpha)} introduced by German mathematician Wilfried Buchholz in 1986. These functions are a simplified version of the \theta -functions, but nevertheless have the same strength as those. Later on this approach was extended by Jäger^[1] and Schütte.^[2]

Definition

Buchholz defined his functions as follows. Define:

• Ω_ξ = ω_ξ if ξ > 0, Ω₀ = 1

The functions ψ_v(α) for α an ordinal, v an ordinal at most ω, are defined by induction on α as follows:

• ψ_v(α) is the smallest ordinal not in C_v(α)

where C_v(α) is the smallest set such that

• C_v(α) contains all ordinals less than Ω_v
• C_v(α) is closed under ordinal addition
• C_v(α) is closed under the functions ψ_u (for u≤ω) applied to arguments less than α.

The limit of this notation is the Takeuti–Feferman–Buchholz ordinal.

Properties

Let

P be the class of additively principal ordinals. Buchholz showed following properties of this functions:\psi _{\nu(0)=\Omega} _{\nu,} ^[3] \psi _{\nu(\alpha)\in} P, \psi _{\nu(\alpha+1)} = min \{\gamma\in P: \psi _{\nu(\alpha)<\gamma\}if} \alpha\in C _{\nu(\alpha),} \Omega _{\nu\le\psi} _{\nu(\alpha)<\Omega} _{\nu+1} \psi ^{\alpha} _{0 (\alpha) = \omega} if \alpha<\varepsilon _{0,} \psi ^{\Omega _{\nu+\alpha}} _{\nu(\alpha) = \omega} if \alpha<\varepsilon _{\Omega _{\nu+1}} and \nu ≠ 0 , \theta(\varepsilon _{\Omega _{\nu+1}} , 0 ) = \psi(\varepsilon _{\Omega _{\nu+1}} ) for 0 <\nu\le\omega.

Fundamental sequences and normal form for Buchholz's function

Normal form

The normal form for 0 is 0. If

\alpha is a nonzero ordinal number \alpha<\Omega _{\omega} then the normal form for \alpha is \alpha = \psi _{\nu _{1}} (\beta _{1)+\psi} ^{\nu _{2}} (\beta _{2)+ … +\psi} ^{\nu _{k}} (\beta _{k)} where \nu _{i\inN} _{0,} k\in N _{>0} , \beta _{i\in} C _{\nu _{i}} (\beta _{i)} and \psi _{\nu _{1}} (\beta _{1)\geq\psi} ^{\nu _{2}} (\beta _{2)\geq … \geq\psi} ^{\nu _{k}} (\beta _{k)} and each \beta _{i} is also written in normal form.

Fundamental sequences

The fundamental sequence for an ordinal number

\alpha with cofinality \operatorname{cof}(\alpha) = \beta is a strictly increasing sequence (\alpha[ η ]) _{η<\beta} with length \beta and with limit \alpha , where \alpha[ η ] is the η -th element of this sequence. If \alpha is a successor ordinal then \operatorname{cof}(\alpha) =1 and the fundamental sequence has only one element \alpha[ 0 ] = \alpha -1 . If \alpha is a limit ordinal then \operatorname{cof}(\alpha)\in\{\omega\} \cup \{\Omega _{\mu+1} \mid\mu\geq 0 \} .

For nonzero ordinals

\alpha<\Omega _{\omega} , written in normal form, fundamental sequences are defined as follows:

1. If

\alpha = \psi _{\nu _{1}} (\beta _{1)+\psi} ^{\nu _{2}} (\beta _{2)+ … +\psi} ^{\nu _{k}} (\beta _{k)} where k\geq 2 then \operatorname{cof}(\alpha) = \operatorname{cof}(\psi _{\nu _{k}} (\beta _{k))} and \alpha[ η ] = \psi _{\nu _{1}} (\beta _{1)+ … +\psi} ^{\nu _{k-1}} (\beta _{k-1} ) + (\psi _{\nu _{k}} (\beta _{k)[η]),}

1. If

\alpha = \psi _{0} ( 0 ) =1 , then \operatorname{cof}(\alpha) =1 and \alpha[ 0 ] =0 ,

1. If

\alpha = \psi _{\nu+1} ( 0 ) , then \operatorname{cof}(\alpha) = \Omega _{\nu+1} and \alpha[ η ] = \Omega _{\nu+1} [ η ] =η ,

1. If

\alpha = \psi _{\nu} (\beta +1 ) then \operatorname{cof}(\alpha) = \omega and \alpha[ η ] = \psi _{\nu} (\beta) ⋅ η (and note: \psi _{\nu(0)=\Omega} _{\nu} ),

1. If

\alpha = \psi _{\nu} (\beta) and \operatorname{cof}(\beta)\in\{\omega\}\cup\{\Omega _{\mu+1} \mid\mu<\nu\} then \operatorname{cof}(\alpha) = \operatorname{cof}(\beta) and \alpha[ η ] = \psi _{\nu} (\beta[ η ]) ,

1. If

\alpha = \psi _{\nu} (\beta) and \operatorname{cof}(\beta)\in\{\Omega _{\mu+1} \mid\mu\geq\nu\} then \operatorname{cof}(\alpha) = \omega and \alpha[ η ] = \psi _{\nu(\beta[\gamma[η]])} where \left\{\begin{array}{lcr} \gamma[ 0 ] = \Omega _{\mu} \ \gamma[ η+1 ] = \psi _{\mu(\beta[\gamma[η]])\ \end{array}\right.} .

Explanation

Buchholz is working in Zermelo–Fraenkel set theory, that means every ordinal

\alpha is equal to set \{\beta\mid\beta<\alpha\} . Then condition C ^{0 (\alpha) = \Omega} _{\nu} means that set C ^{0 (\alpha)} _{\nu} includes all ordinals less than \Omega _{\nu} in other words C ^{0 (\alpha) = \{\beta\mid\beta<\Omega} _{\nu\}} .

The condition

C ^{n +1} _{\nu} (\alpha) = C ^{n(\alpha)} _{\nu} \cup \{\gamma \mid P(\gamma) \subseteq C ^{n(\alpha)\}} _{\nu} \cup \{\psi _{\mu(\xi)} \mid \xi \in \alpha \cap C ^{n(\alpha)} _{\nu} \wedge \mu \leq \omega\} means that set C ^{n +1} _{\nu} (\alpha) includes:

• all ordinals from previous set

C ^{n(\alpha)} _{\nu} ,

• all ordinals that can be obtained by summation the additively principal ordinals from previous set

C ^{n(\alpha)} _{\nu} ,

• all ordinals that can be obtained by applying ordinals less than

\alpha from the previous set C ^{n(\alpha)} _{\nu} as arguments of functions \psi _{\mu} , where \mu\le\omega .

That is why we can rewrite this condition as:

C ^{n +1} _{\nu} (\alpha) = \{\beta + \gamma,\psi _{\mu(η)\mid\beta,} \gamma, η \in C ^{n(\alpha)\wedge η <\alpha} _{\nu} \wedge \mu \leq \omega\}.

Thus union of all sets

C ^{n} _{\nu} (\alpha) with n<\omega i.e. C _{\nu(\alpha)} = c up _{n} C ^{n} _{\nu} (\alpha) denotes the set of all ordinals which can be generated from ordinals <\aleph _{\nu} by the functions + (addition) and \psi _{\mu} ( η ) , where \mu\le\omega and η <\alpha .

Then

\psi _{\nu(\alpha)} = min \{\gamma \mid \gamma \not\in C _{\nu(\alpha)\}} is the smallest ordinal that does not belong to this set.

Examples

Consider the following examples:

C ^{0 (\alpha) = \{ 0 \}} _{0} = \{\beta\mid\beta< 1 \}, C _{0(0)=\{0\}} (since no functions \psi( η < 0 ) and 0 + 0 = 0).

Then

\psi _{0(0)=1} .C _{0(1)} includes \psi _{0(0)=1} and all possible sums of natural numbers and therefore \psi _{0(1)=\omega} – first transfinite ordinal, which is greater than all natural numbers by its definition.C _{0(2)} includes \psi _{0(0)=1,} \psi _{0(1)=\omega} and all possible sums of them and therefore \psi ^{2} _{0 ( 2 ) = \omega} .

If

\alpha = \omega then C ^{2 ,\ldots,\psi( 3 ) = \omega} _{0 (\alpha) = \{ 0 ,\psi( 0 ) =1 ,\ldots,\psi( 1 ) = \omega,\ldots,\psi( 2 ) = \omega} ^{3,} \ldots\} and \psi ^{\omega} _{0 (\omega) = \omega} .

If

\alpha = \Omega then C _{0(\alpha)=\{0,\psi(0)} = 1 , \ldots, \psi( 1 ) = \omega, \ldots, \psi(\omega) = \omega ^{\omega,} \ldots, \psi(\omega ^{\omega)} = \omega ^{\omega ^{\omega}} ,\ldots\} and \psi _{0(\Omega)=\varepsilon} _{0} – the smallest epsilon number i.e. first fixed point of \alpha = \omega ^{\alpha} .

If

\alpha = \Omega +1 then C _{0(\alpha)=\{0,1,\ldots,\psi} _{0(\Omega)=\varepsilon} _{0,\ldots,\varepsilon} _{0+\varepsilon} _{0,\ldots,\psi} _{1(0)=\Omega,\ldots\}} and \psi _{0(\Omega+1)=\varepsilon} ^{\varepsilon _{0+1}} ^{0 \omega = \omega} .\psi _{0(\Omega2)=\varepsilon} _{1} the second epsilon number,\psi ^{2 )} _{0 (\Omega} = \varepsilon _{\varepsilon _{…}} = \zeta _{0} i.e. first fixed point of \alpha = \varepsilon _{\alpha} ,\varphi(\alpha,\beta) = \psi ^{\alpha( 1+ \beta))} _{0 (\Omega} , where \varphi denotes the Veblen function,\psi ^{\Omega) = \Gamma} _{0= \varphi( 1 , 0 , 0 ) = \theta(\Omega, 0 )} , where \theta denotes the Feferman's function and \Gamma _{0} is the Feferman–Schütte ordinal,\psi ^{\Omega ^{2}} _{0 (\Omega} ) = \varphi( 1 , 0 , 0 , 0 ) is the Ackermann ordinal,\psi ^{\Omega ^{\omega}} _{0 (\Omega} ) is the small Veblen ordinal,\psi ^{\Omega ^{\Omega}} _{0 (\Omega} ) is the large Veblen ordinal,\psi _{0(\Omega\uparrow\uparrow\omega)} = \psi _{0(\varepsilon} _{\Omega+1} ) = \theta(\varepsilon _{\Omega+1} , 0 ).

Now let's research how

\psi _{1} works:C ^{0 ( 0 ) = \{\beta\mid\beta<\Omega} _{1 \} = \{ 0 ,\psi( 0 )} = 1 , 2 , \ldots googol , \ldots, \psi _{0(1)=\omega,} \ldots, \psi _{0(\Omega)} = \varepsilon _{0,\ldots} \ldots,\psi ^{\Omega ^{\Omega+\Omega} ^{2}} _{0 ,\ldots,\psi(\Omega} ),\ldots\} i.e. includes all countable ordinals. And therefore C _{1(0)} includes all possible sums of all countable ordinals and \psi _{1(0)=\Omega} _{1} first uncountable ordinal which is greater than all countable ordinal by its definition i.e. smallest number with cardinality \aleph _{1} .

If

\alpha =1 then C _{1(\alpha)=\{0,\ldots,\psi} _{0(0)} = \omega, \ldots, \psi _{1(0)} = \Omega,\ldots,\Omega + \omega,\ldots,\Omega + \Omega,\ldots\} and \psi ^{\Omega +1} _{1 ( 1 ) = \Omega\omega = \omega} .\psi ^{2= \omega} _{1 ( 2 ) = \Omega\omega} ^{\Omega+2} , \psi _{1(\psi} _{1(0))=\psi} ^{2= \omega} ^{1 (\Omega) = \Omega} ^{\Omega+\Omega} , \psi _{1(\psi} _{1(\psi} _{1(0)))} = \omega ^{\Omega + \omega ^{\Omega+\Omega}} = \omega ^{\Omega ⋅ \Omega} = (\omega ^{\Omega} ) ^{\Omega=\Omega} ^{\Omega,} \psi ^{4 ( 0 ) = \Omega} _{1} ^{\Omega ^{\Omega}} , \psi ^{k +1} _{1} ( 0 ) = \Omega\uparrow\uparrow k where k is a natural number, k \geq 2 ,\psi _{1(\Omega} _{2)} = \psi ^{\omega( 0 )} _{1} = \Omega \uparrow\uparrow \omega = \varepsilon _{\Omega+1} .

For case

\psi(\psi _{2(0))=\psi(\Omega} _{2)} the set C _{0(\Omega} _{2)} includes functions \psi _{0} with all arguments less than \Omega _{2} i.e. such arguments as 0 , \psi _{1(0),} \psi _{1(\psi} _{1(0)),} \psi ^{3 ( 0 ),\ldots,} _{1} \psi ^{\omega( 0 )} _{1}

and then

\psi _{0(\Omega} _{2)} = \psi _{0(\psi} _{1(\Omega} _{2))} = \psi _{0(\varepsilon} _{\Omega+1} ).

In the general case:

\psi _{0(\Omega} _{\nu+1} ) = \psi _{0(\psi} _{\nu(\Omega} _{\nu+1} )) = \psi _{0(\varepsilon} ^{\Omega _{\nu+1}} ) = \theta(\varepsilon _{\Omega _{\nu+1}} , 0 ).

We also can write:

\theta(\Omega _{\nu,0)=\psi} _{0(\Omega} ^{\Omega)} ^{\nu} (for 1 \le\nu)<\omega

Ordinal notation

(OT,<) associated to the \psi function. We simultaneously define the sets T and PT as formal strings consisting of 0 , D _{v} indexed by v \in \omega + 1 , braces and commas in the following way:0 \in T ∧ 0 \in PT ,\forall (v, a) \in (\omega + 1 ) x T( D _{va} \in T ∧ D _{va} \in PT) .\forall (a _{0,} a _{1)} \in PT ^{2 ((a} _{0 ,} a _{1)} \in T) .\exists s (a _{0} = s) ∧ (a _{0,} a _{1)} \in T x PT → (s, a _{1)} \in T .

An element of

T is called a term, and an element of PT is called a principal term. By definition, T is a recursive set and PT is a recursive subset of T . Every term is either 0 , a principal term or a braced array of principal terms of length \geq 2 . We denote a \in PT by (a) . By convention, every term can be uniquely expressed as either 0 or a braced, non-empty array of principal terms. Since clauses 3 and 4 in the definition of T and PT are applicable only to arrays of length \geq 2 , this convention does not cause serious ambiguity. a < b on T in the following way:b = 0 → a < b = \bot a = 0 → (a < b \leftrightarrow b ≠ 0 )

• If

a ≠ 0 ∧ b ≠ 0 , then:

• • If

a = D _{ua'} ∧ b = D _{vb'} for some ((u, a'), (v, b')) \in ((\omega + 1 ) x T) ^{2} , then a < b is true if either of the following are true:u < v u = v ∧ a' < b'

• • If

a = (a _{0,} ..., a _{n)} ∧ b = (b _{0,} ..., b _{m)} for some (n, m) \in \N ^{2} ∧ 1 \leq n + m , then a < b is true if either of the following are true:\forall i \in \N ∧ i \leq n(n < m ∧ a _{i} = b _{i)} \exists k \in \N\forall i \in \N ∧ i < k(k \leq min\{n, m\} ∧ a _{k} < b _{k} ∧ a _{i} = b _{1)} < is a recursive strict total ordering on T . We abbreviate (a < b) \or (a = b) as a \leq b . Although \leq itself is not a well-ordering, its restriction to a recursive subset OT \subset T , which will be described later, forms a well-ordering. In order to define OT , we define a subset G _{ua} \subset T for each (u, a) \in (\omega + 1 ) x T in the following way:a = 0 → G _{ua} = \varnothing

• Suppose that

a = D _{va'} for some (v, a') \in (\omega + 1 ) x T , then:u \leq v → G _{ua} = \{a'\} \cup G _{ua'} u > v → G _{ua} = \varnothing

• If

a = (a _{0,} ..., a _{k)} for some (a _{i)} ^{k} ^{i =0} \in PT ^{k} for some k \in \N \backslash \{ 0 \}, G _{ua} = c up ^{k} _{i =0} G _{ua} _{i} .b \in G _{ua} is a recursive relation on (u, a, b) \in (\omega + 1 ) x T ^{2} . Finally, we define a subset OT \subset T in the following way:0 \in OT

• For any

(v, a) \in (\omega + 1 ) x T , D _{va} \in OT is equivalent to a \in OT and, for any a' \in G _{va} , a' < a .

• For any

(a _{i)} ^{k} ^{i =0} \in PT ^{k} , (a _{0,} ..., a _{k)} \in OT is equivalent to (a _{i)} ^{k} ^{i =0} \in OT and a _{k} \leq ... \leq a _{0} .OT is a recursive subset of T , and an element of OT is called an ordinal term. We can then define a map o: OT → C _{0(\varepsilon} ^{\Omega _{\omega+1}} ) in the following way:a = 0 → o(a) = 0

• If

a = D _{va'} for some (v, a') \in (\omega + 1 ) x OT , then o(a) = \psi _{v(o(a'))} .

• If

a = (a _{0,} ..., a _{k)} for some (a _{i)} ^{k} ^{i =0} \in (OT \cap PT) ^{k+1} with k \in \N \backslash \{ 0 \} , then o(a) = o(a _{0)} \# ... \# o(a _{k)} , where \# denotes the descending sum of ordinals, which coincides with the usual addition by the definition of OT .

Buchholz verified the following properties of

o :

• The map

o is an order-preserving bijective map with respect to < and \in . In particular, o is a recursive strict well-ordering on OT .

• For any

a \in OT satisfying a < D _{10} , o(a) coincides with the ordinal type of < restricted to the countable subset \{x \in OT | x < a\} .

• The Takeuti-Feferman-Buchholz ordinal coincides with the ordinal type of

< restricted to the recursive subset \{x \in OT | x < D _{10\}} .

• The ordinal type of

(OT, <) is greater than the Takeuti-Feferman-Buchholz ordinal.

• For any

v \in \N \backslash \{ 0 \} , the well-foundedness of < restricted to the recursive subset \{x \in OT | x < D _{0D} _{v+1} 0 \} in the sense of the non-existence of a primitive recursive infinite descending sequence is not provable under ID _{v} .

• The well-foundedness of

< restricted to the recursive subset\{x \in OT | x < D _{0D} _{\omega0\}} in the same sense as above is not provable under \Pi ^{1} _{1} - CA _{0} .

Normal form

The normal form for Buchholz's function can be defined by the pull-back of standard form for the ordinal notation associated to it by

o . Namely, the set NF of predicates on ordinals in C _{0(\varepsilon} ^{\Omega _{\omega} +1} ) is defined in the following way:

• The predicate

\alpha = _{NF} 0 on an ordinal \alpha \in C _{0(\varepsilon} ^{\Omega _{\omega} +1} ) defined as \alpha = 0 belongs to NF .

• The predicate

\alpha _{0} = _{NF} \psi _{k _{1}} (\alpha _{1)}  on ordinals \alpha _{0,} \alpha _{1} \in C _{0(\varepsilon} ^{\Omega _{\omega} +1} )  with k _{1} = \omega + 1  defined as \alpha _{0} = \psi _{k _{1}} (\alpha _{1)}  and \alpha _{1} = C _{k _{1}} (\alpha _{1)}  belongs to NF .

• The predicate

\alpha _{0} = _{NF} \alpha _{1} + ... + \alpha _{n} on ordinals \alpha _{0,} \alpha _{1,} ..., \alpha _{n} \in C _{0(\varepsilon} ^{\Omega _{\omega} +1} )  with an integer n > 1  defined as \alpha _{0} = \alpha _{1} + ... + \alpha _{n} , \alpha _{1} \geq ... \geq \alpha _{n} , and \alpha _{1,} ..., \alpha _{n} \in AP  belongs to NF . Here +  is a function symbol rather than an actual addition, and AP  denotes the class of additive principal numbers.

It is also useful to replace the third case by the following one obtained by combining the second condition:

• The predicate

\alpha _{0} = _{NF} \psi _{k _{1}} (\alpha _{1)} + ... + \psi _{k _{n}} (\alpha _{n)} on ordinals \alpha _{0,} \alpha _{1,} ..., \alpha _{n} \in C _{0(\varepsilon} ^{\Omega _{\omega} +1} )  with an integer n > 1  and k _{1,} ..., k _{n} \in \omega + 1 defined as \alpha _{0} = \psi _{k _{1}} (\alpha _{1)} + ... + \psi _{k _{n}} (\alpha _{n)} , \psi _{k _{1}} (\alpha _{1)} \geq ... \geq \psi _{k _{n}} (\alpha _{n)} , and \alpha _{1} \in C _{k _{1}} (\alpha _{1),} ..., \alpha _{n} \in C _{k _{n}} (\alpha _{n)} \in AP  belongs to NF .

We note that those two formulations are not equivalent. For example,

\psi _{0(\Omega)} + 1 = _{NF} \psi _{0(\zeta} _{1)} + \psi _{0(0)}  is a valid formula which is false with respect to the second formulation because of \zeta _{1} ≠ C _{0(\zeta} _{1)} , while it is a valid formula which is true with respect to the first formulation because of \psi _{0(\Omega)} + 1 = \psi _{0(\zeta} _{1)} + \psi _{0(0)} , \psi _{0(\zeta} _{1),} \psi _{0(0)} \in AP , and \psi _{0(\zeta} _{1)} \geq \psi _{0(0)} . In this way, the notion of normal form heavily depends on the context. In both formulations, every ordinal in C _{0(\varepsilon} ^{\Omega _{\omega} +1} )  can be uniquely expressed in normal form for Buchholz's function.

References

1. G. Jäger. ρ-inaccessible ordinals, collapsing functions and a recursive notation system. Archiv für Mathematische Logik und Grundlagenforschung. 24. 1. 1984. 49–62. 10.1007/BF02007140. 38619369.
2. W.. Buchholz. Schütte. K.. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der H~-Separation und Bar-Induktion. Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. Klasse. 1983.
3. Buchholz . W. . 1986 . A new system of proof-theoretic ordinal functions . Annals of Pure and Applied Logic . en . 32 . 195–207 . 10.1016/0168-0072(86)90052-7. free .