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 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:

If where then and
If, then and,
If, then and,
If then and,
If and then and,
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 + and, where and.
Then is the smallest ordinal that does not belong to this set.
Examples
Consider the following examples:
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,
, where denotes the Veblen function,
, where denotes the Feferman's function and is the Feferman–Schütte 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.
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.