The extended Wilfried Buchholz's functions

Section 1

Published in April 2017

Section 2

Published in July 2020

The extended Wilfried Buchholz’s functions are my extension of original Buchholz’s functions and were created in April 2017. In the same month I also defined the fundamental sequences, which you can see above, and much later, in July 2020, developed the ordinal notation, which is below.

Ordinal notation associated to the extended Wilfried Buchholz's functions

We assume that <...> is a primitive recursive coding function on finite sequences of natural numbers.

1. Definition of set T

1. 0∈T

2. If α_1,…,α_n ∈ T then <1,α_1,…,α_n> ∈ T

3. If α, β ∈ T then <2,α,β> ∈ T

2. Definition of V:On→T

1. V(0) = 0

2. V(α_1+…+ α_n) = <1,V(α_1),…,V( α_n)>

3. V(ψ_α(β)) = <2,V(α),V(β)>

3. Definition of o:T→On

1. o(0) = 0

2. o(<1,α_1,…,α_n> ) = o(α_1)+…+o(α_n)

3. o(<2,α,β>) = ψ_{o(α)}(o(β))

4. Conventions

1. 1’ is an abbreviation of <2,0,0>

2. ω’ is an abbreviation of <2,0,<2,0,0>>

3. <α_1,…,α_m> = <β_1,…,β_n> ⇔ m = n and α_i = β_i for 1 ≤ i ≤ n

4. α ⊴ β ⇔ α ⊲ β or α = β

5. Definition of ⊗

α⊗η = 0 if η = 0

α⊗η = α if η = 1

α⊗η = <1,α,…,α> with η α's if η ≥ 2

Below we simultaneously define:

1. Sets of terms OT, P,

2. Coefficient sets G_ν(α) for α,ν∈OT,

3. A linear ordering ⊲ on OT.

6. Definition of sets OT, P:

1. If α=0 then α∈OT

2. If α=<1,α_1,...,α_n> and n≥2 and α_1,...,α_n ∈ P and α_n ⊴ … ⊴ α_1 ⊲ α then α∈OT

3. If α=<2,ν,β> and ν,β∈OT and G_ν(β) ⊲ β then α∈OT and α∈P

7. Definition of G_ν(α) for α,ν∈OT

1. G_ν(0)=∅

2. G_ν(<1,α_1,…,α_n>) = G_ν(α_1) ∪… ∪ G_ν(α_n)

3. G_ν(<2,μ,β>) = ∅ if μ ⊲ ν

4. G_ν(<2,μ,β>) = {β} ∪ G_ν(μ) ∪ G_ν(β) if ν ⊴ μ

G_ν(β) ⊲ β ⇔ o(β)∈C_{o(ν)}(o(β))

Note: G_ν(β) ⊲ β abbreviates “γ⊲β for all γ∈G_ν(β)”

8. Definition of ⊲ for OT

All terms are supposed to be elements of OT.

a) 0 ⊲ α if 1’ ⊴ α.

b) <2,ν,α> ⊲ <2,μ,β> iff one of the following cases holds:

1. ν ⊲ μ,

2. ν = μ and α ⊲ β.

c) <1,α_1,…,α_m> ⊲ <1,β_1,…,β_n> (2 ≤ m, 2 ≤ n) iff one of the following cases holds:

1. m < n and α_i = β_i for 1 ≤ i ≤ m,

2. there exists a k such that 1 ≤ k ≤ min{m,n} and α_k ⊲ β_k and α_i = β_i for 1 ≤ i < k.

d) Let β = <2,γ,δ>. Then

1. <1,α_1,…,α_k> ⊲ β if α_1 ⊲ β,

2. β ⊲ <1,α_1,…,α_k> if β ⊴ α_i for some 1 ≤ i ≤ k.

Note: α⊲β and α,β∈OT ⇔ o(α)<o(β)

9. Definition of fundamental sequences for α∈OT

1. If α =0 then R(α)=0 and α hasn’t a fundamental sequence.

2. If α=<2,0,0> then R(α)= α=1’ and α[0]=0.

3. If α=<2,β,0> with R(β)=1' then R(α)=α and α[η]=η.

4. If α=<2,β,0> and R(β)∉{0,1’} then R(α)=R(β) and α[η] =<2,β[η],0>.

5. If α = <1,α_1,…,α_k> and k≥2 then R(α) = R(α_k) and

α[η] = <1,α_1,…,α_k[η]> if α_k[η] = <2,β,γ>,

α[η] = <1,α_1,…,α_{k-1},β_1,…,β_m> if α_k[η] = <1,β_1,…,β_m>,

α[η] = <1,α_1,…,α_{k-1}> if α_k[η] = 0 and k>2,

α[η] = α_1 if α_k[η] = 0 and k = 2.

6. If α=<2,β,γ> and R(γ)=1’ then R(α)=ω’ and α[η]=<2,β,γ[0]>⊗η.

7. If α=<2,ν,β> and R(β)∈{ω’}∪{<2,μ,0>|0⊲ μ⊴ν} then R(α)=R(β) and α[η]=<2,ν,β[η]>.

8. If α=<2,ν,β> and R(β)=<2,μ,0> and ν⊲μ then R(α)=ω’ and α[η]=<2,ν,β[γ[η]]> with γ[0]=<2,μ[0],0> and γ[η+1]=<2,μ[0],β[γ[η]]>.

10. Definition of FGH for α∈OT and n∈ℕ

1. If R(α)=0 then f(α,n)=n+1

2. If R(α)=1’ then f(α,n)= γ[n] where γ[0]=n and γ[m+1]= f(α[0],γ[m])

3. If R(α)=ω’ then f(α,n)= f(α[n],n)

If α = V(β) then for the function of fast-growing hierarchy f_β(n) = f(α,n)

11. Definition of hyperoperations for α∈OT and n,k∈ℕ\{0}

1. If R(α)∈{0,1’} then h(n,α,1)=n

2. If R(α)=0 then h(n,α,k+1)=h(n,α,k)+n

3. If R(α)=1’ then h(n,α,k+1)=h(n,α[0],h(n,α,k))

4. If R(α)=ω’ then h(n,α,k)= h(n,α[k],n)

If α = V(β) then for extended arrows n↑^βk = h(n,α,k)

12. References

1. Buchholz's articles: [1] [2]

2. Deedlit's posts: [3] [4]

3. P進大好きbot’s notation: [5]