Buchholz psi functions

Buchholz's psi-functions are a hierarchy of single-argument ordinal functions introduced by German mathematician Wilfried Buchholz in 1986. These functions are a simplified version of the -functions, but nevertheless have the same strength as those. Later on this approach was extended by Jäger and Schütte.

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 be the class of additively principal ordinals. Buchholz showed following properties of this functions:

Fundamental sequences and normal form for Buchholz's function

Normal form

The normal form for 0 is 0. If is a nonzero ordinal number then the normal form for is where and and each is also written in normal form.

Fundamental sequences

The fundamental sequence for an ordinal number with cofinality is a strictly increasing sequence with length and with limit , where is the -th element of this sequence. If is a successor ordinal then and the fundamental sequence has only one element . If is a limit ordinal then .

For nonzero ordinals , written in normal form, fundamental sequences are defined as follows:

1. If where then and
2. If , then and ,
3. If , then and ,
4. If then and (and note: ),
5. If and then and ,
6. If and then and where .

Explanation

Buchholz is working in Zermelo–Fraenkel set theory, which means every ordinal is equal to set . Then the condition means that set includes all ordinals less than in other words .

The condition means that set includes:

• all ordinals from previous set ,
• all ordinals that can be obtained by summation the additively principal ordinals from previous set ,
• all ordinals that can be obtained by applying ordinals less than from the previous set as arguments of functions , where .

That is why we can rewrite this condition as:

Thus union of all sets with i.e. denotes the set of all ordinals which can be generated from ordinals by the functions + (addition) and , where and .

Then is the smallest ordinal that does not belong to this set.

Examples

Consider the following examples:

(since no functions and 0 + 0 = 0).

Then .

includes and all possible sums of natural numbers and therefore – first transfinite ordinal, which is greater than all natural numbers by its definition.

includes and all possible sums of them and therefore .

If then and .

If then and – the smallest epsilon number i.e. first fixed point of .

If then and .

the second epsilon number,

i.e. first fixed point of ,

, where denotes the Veblen function,

, where denotes the Feferman's function and is the Feferman–Schütte ordinal,

is the Ackermann ordinal,

is the small Veblen ordinal,

is the large Veblen ordinal,

Now let's research how works:

i.e. includes all countable ordinals. And therefore includes all possible sums of all countable ordinals and first uncountable ordinal which is greater than all countable ordinal by its definition i.e. smallest number with cardinality .

If then and .

where is a natural number, ,

For case the set includes functions with all arguments less than i.e. such arguments as

and then

In the general case:

We also can write:

Ordinal notation

Buchholz defined an ordinal notation associated to the function. We simultaneously define the sets and as formal strings consisting of indexed by , braces and commas in the following way:

• ,
• .
• .
• .

An element of is called a term, and an element of is called a principal term. By definition, is a recursive set and is a recursive subset of . Every term is either , a principal term or a braced array of principal terms of length . We denote by . By convention, every term can be uniquely expressed as either or a braced, non-empty array of principal terms. Since clauses 3 and 4 in the definition of and are applicable only to arrays of length , this convention does not cause serious ambiguity.

We then define a binary relation on in the following way:

• If , then:
• If for some , then is true if either of the following are true:
• If for some , then is true if either of the following are true:

is a recursive strict total ordering on . We abbreviate as . Although itself is not a well-ordering, its restriction to a recursive subset , which will be described later, forms a well-ordering. In order to define , we define a subset for each in the following way:

• Suppose that for some , then:

• If for some for some .

is a recursive relation on . Finally, we define a subset in the following way:

• For any , is equivalent to and, for any , .
• For any , is equivalent to and .

is a recursive subset of , and an element of is called an ordinal term. We can then define a map in the following way:

• If for some , then .
• If for some with , then , where denotes the descending sum of ordinals, which coincides with the usual addition by the definition of .

Buchholz verified the following properties of :

• The map is an order-preserving bijective map with respect to and . In particular, is a recursive strict well-ordering on .
• For any satisfying , coincides with the ordinal type of restricted to the countable subset .
• The Takeuti–Feferman–Buchholz ordinal coincides with the ordinal type of restricted to the recursive subset .
• The ordinal type of is greater than the Takeuti–Feferman–Buchholz ordinal.
• For any , the well-foundedness of restricted to the recursive subset in the sense of the non-existence of a primitive recursive infinite descending sequence is not provable under .
• The well-foundedness of restricted to the recursive subset in the same sense as above is not provable under .

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 . Namely, the set of predicates on ordinals in is defined in the following way:

• The predicate on an ordinal defined as belongs to .

• The predicate  on ordinals  with  defined as  and  belongs to .
• The predicate on ordinals  with an integer  defined as , , and  belongs to . Here  is a function symbol rather than an actual addition, and  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 on ordinals  with an integer  and defined as , , and  belongs to .

We note that those two formulations are not equivalent. For example,  is a valid formula which is false with respect to the second formulation because of , while it is a valid formula which is true with respect to the first formulation because of , , and . In this way, the notion of normal form heavily depends on the context. In both formulations, every ordinal in  can be uniquely expressed in normal form for Buchholz's function.

Extension

This ordinal collapsing function is a sophisticated extension of Buchholz's  by mathematician Denis Maksudov. The limit of this system, sometimes called the Extended Buchholz Ordinal, is much greater, equal to where denotes the first omega fixed point. The function is defined as follows:

• Define and for .

References