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[clarification needed] as those. Later on this approach was extended by Jäger[1] and Schütte.[2]

Definition

edit

Buchholz defined his functions as follows. Define:

  • Ωξ = ωξ if ξ > 0, Ω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 Cv(α)

where Cv(α) is the smallest set such that

  • Cv(α) contains all ordinals less than Ωv
  • Cv(α) is closed under ordinal addition
  • Cv(α) 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

edit

Let   be the class of additively principal ordinals. Buchholz showed following properties of this functions:

  •   [3]: 197 
  •   [3]: 197 
  •   [3]: 199 
  •   [3]: 197 
  •   [3]: 199 
  •   [3]: 199 
  •   [3]: 206 

Fundamental sequences and normal form for Buchholz's function

edit

Normal form

edit

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

edit

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

edit

Buchholz is working in Zermelo–Fraenkel set theory, that means every ordinal   is equal to set  . Then 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

edit

Buchholz[3] 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

edit

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.

References

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