Difference between revisions of "Buchholz's ψ functions"

From Cantor's Attic
Jump to: navigation, search
 
(6 intermediate revisions by the same user not shown)
Line 1: Line 1:
Buchholz's \(\psi\) function is an ordinal collapsing function introduced by German mathematician Wilfried Buchholz's in 1981.  
+
Buchholz's functions are a hierarchy of single-argument ordinal functions \( (\psi _{\nu }:On\rightarrow On)_{\nu\le\omega}\)  introduced by German mathematician Wilfried Buchholz in 1981.  
  
 
==Basic Notions==
 
==Basic Notions==
Line 15: Line 15:
 
For every <math>\alpha\notin P</math> there exist unique set <math>P(\alpha)=\{\alpha_1, \alpha_2, ... ,\alpha_n\}</math> such that <math>\alpha=\alpha_1+\alpha_2+ \cdots+\alpha_n</math> and <math>\alpha>\alpha_1\geq\alpha_2\geq \cdots\geq\alpha_n</math> and <math>\alpha_1, \alpha_2, ... ,\alpha_n\in P</math>
 
For every <math>\alpha\notin P</math> there exist unique set <math>P(\alpha)=\{\alpha_1, \alpha_2, ... ,\alpha_n\}</math> such that <math>\alpha=\alpha_1+\alpha_2+ \cdots+\alpha_n</math> and <math>\alpha>\alpha_1\geq\alpha_2\geq \cdots\geq\alpha_n</math> and <math>\alpha_1, \alpha_2, ... ,\alpha_n\in P</math>
  
<math>\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n</math> iff <math>\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n</math> and <math>\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_n</math> and <math>\alpha_1,\alpha_2,...,\alpha_n\in P</math>
+
<math>\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n</math> iff <math>\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n</math> and <math>\alpha>\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_n</math> and <math>\alpha_1,\alpha_2,...,\alpha_n\in P</math>
  
 
== Definition ==
 
== Definition ==
Buchholz's \(\psi\) function is defined as follows:
+
Buchholz's functions are defined as follows:
  
 
* \(C_\nu^0(\alpha) = \Omega_\nu\),
 
* \(C_\nu^0(\alpha) = \Omega_\nu\),
 
* \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma | P(\gamma) \subseteq C_\nu^n(\alpha)\} \cup \{\psi_\mu(\xi) | \xi \in \alpha \cap C_\nu^n(\alpha) \wedge \xi \in C_\mu(\xi) \wedge \mu \leq \omega\}\),
 
* \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma | P(\gamma) \subseteq C_\nu^n(\alpha)\} \cup \{\psi_\mu(\xi) | \xi \in \alpha \cap C_\nu^n(\alpha) \wedge \xi \in C_\mu(\xi) \wedge \mu \leq \omega\}\),
 
* \(C_\nu(\alpha) = \bigcup_{n < \omega} C_\nu^n (\alpha)\),
 
* \(C_\nu(\alpha) = \bigcup_{n < \omega} C_\nu^n (\alpha)\),
* \(\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}\),
+
* \(\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}\).
  
 
In other words \(\psi_\nu(\alpha)\) is the least ordinal number which cannot be generated from ordinals less than \(\Omega_\nu\) by  applying of addition and the functions \(\psi_{\mu}(\eta)\) with \(\eta < \alpha\) and \(\mu \le \omega\).
 
In other words \(\psi_\nu(\alpha)\) is the least ordinal number which cannot be generated from ordinals less than \(\Omega_\nu\) by  applying of addition and the functions \(\psi_{\mu}(\eta)\) with \(\eta < \alpha\) and \(\mu \le \omega\).
Line 31: Line 31:
 
== Properties ==
 
== Properties ==
  
Buchholz showed following properties of those functions:
+
Buchholz showed the following properties of those functions:
  
 
*\(\psi_\nu(0)=\Omega_\nu\),
 
*\(\psi_\nu(0)=\Omega_\nu\),
Line 45: Line 45:
 
The fundamental sequence for an ordinal number <math>\alpha</math> with cofinality <math>\text{cof}(\alpha)=\beta</math> is a strictly increasing sequence <math>(\alpha[\eta])_{\eta<\beta}</math> with length <math>\beta</math> and with limit <math>\alpha</math>, where <math>\alpha[\eta]</math> is the <math>\eta</math>-th element of this sequence.  
 
The fundamental sequence for an ordinal number <math>\alpha</math> with cofinality <math>\text{cof}(\alpha)=\beta</math> is a strictly increasing sequence <math>(\alpha[\eta])_{\eta<\beta}</math> with length <math>\beta</math> and with limit <math>\alpha</math>, where <math>\alpha[\eta]</math> is the <math>\eta</math>-th element of this sequence.  
  
We define the set \(T\) consisting of zero and all ordinals expressible using Buchholz's function and the operation of addition
+
We define the set \(T\) consisting of zero and all ordinals expressible using Buchholz's functions and the operation of addition
  
 
#<math>0 \in T</math>
 
#<math>0 \in T</math>
Line 58: Line 58:
 
#if <math>\alpha=\psi_{\nu}(\beta+1)</math> then <math>\operatorname{cof}(\alpha)=\omega</math> and <math>\alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta</math>
 
#if <math>\alpha=\psi_{\nu}(\beta+1)</math> then <math>\operatorname{cof}(\alpha)=\omega</math> and <math>\alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta</math>
 
#if <math>\alpha=\psi_{\nu}(\beta)</math> and <math>\operatorname{cof}(\beta)\in\{\omega\}\cup\{\Omega_{\mu+1}\mid\mu<\nu\}</math> then <math>\operatorname{cof}(\alpha)=\operatorname{cof}(\beta)</math> and <math>\alpha[\eta]=\psi_{\nu}(\beta[\eta])</math>
 
#if <math>\alpha=\psi_{\nu}(\beta)</math> and <math>\operatorname{cof}(\beta)\in\{\omega\}\cup\{\Omega_{\mu+1}\mid\mu<\nu\}</math> then <math>\operatorname{cof}(\alpha)=\operatorname{cof}(\beta)</math> and <math>\alpha[\eta]=\psi_{\nu}(\beta[\eta])</math>
#if <math>\alpha=\psi_{\nu}(\beta)</math> and <math>\operatorname{cof}(\beta)\in\{\Omega_{\mu+1}\mid\mu\geq\nu\}</math> then <math>\operatorname{cof}(\alpha)=\omega</math> and <math>\alpha[\eta]=\psi_\nu(\beta[\gamma[\eta]])</math> where <math>\gamma[0]=\Omega_\mu</math> and <math>\gamma[\eta+1]=\psi_\mu(\beta[\gamma[\eta]])</math>
+
#if <math>\alpha=\psi_{\nu}(\beta)</math> and <math>\operatorname{cof}(\beta)\in\{\Omega_{\mu+1}\mid\mu\geq\nu\}</math> then <math>\operatorname{cof}(\alpha)=\omega</math> and <math>\alpha[\eta]=\psi_\nu(\beta[\gamma[\eta]])</math> with <math>\gamma[0]=\Omega_\mu</math> and <math>\gamma[\eta+1]=\psi_\mu(\beta[\gamma[\eta]])</math>
 +
 
 +
==Takeuti-Feferman-Buchholz ordinal==
 +
 
 +
The Takeuti-Feferman-Buchholz ordinal is equal to \(\psi_0(\varepsilon_{\Omega_\omega+1})\) using Buchholz \(\psi\)-notaion and also it is equal to \(\theta_{\varepsilon_{\Omega_\omega+1}}(0)\)  using Feferman \(\theta\)-notation. This ordinal  is the limit of both notations. The name of the ordinal was proposed by David Madore.
  
 
==See also ==
 
==See also ==

Latest revision as of 13:34, 27 May 2018

Buchholz's functions are a hierarchy of single-argument ordinal functions \( (\psi _{\nu }:On\rightarrow On)_{\nu\le\omega}\) introduced by German mathematician Wilfried Buchholz in 1981.

Basic Notions

Small Greek letters always denote ordinals. Each ordinal \(\alpha\) is identified with the set of its predecessors \(\alpha=\{\beta|\beta<\alpha\}\).

\(On\) denotes the class of all ordinals.

We define \(\Omega_0=1\) and \(\Omega_{\nu}=\aleph_{\nu}\) for \(\nu>0\).

An ordinal \(\alpha\) is an additive principal number if \(\alpha>0\) and \(\xi+\eta<\alpha\) for all \(\xi,\eta<\alpha\). Let \(P\) denote the set of all additive principal numbers i.e.

\(P=\{\alpha\in On|0<\alpha\wedge\forall\xi,\eta<\alpha(\xi+\eta\in\alpha)\}=\{\omega^\beta|\beta\in On\}\)

For every \(\alpha\notin P\) there exist unique set \(P(\alpha)=\{\alpha_1, \alpha_2, ... ,\alpha_n\}\) such that \(\alpha=\alpha_1+\alpha_2+ \cdots+\alpha_n\) and \(\alpha>\alpha_1\geq\alpha_2\geq \cdots\geq\alpha_n\) and \(\alpha_1, \alpha_2, ... ,\alpha_n\in P\)

\(\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n\) iff \(\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n\) and \(\alpha>\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_n\) and \(\alpha_1,\alpha_2,...,\alpha_n\in P\)

Definition

Buchholz's functions are defined as follows:

  • \(C_\nu^0(\alpha) = \Omega_\nu\),
  • \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma | P(\gamma) \subseteq C_\nu^n(\alpha)\} \cup \{\psi_\mu(\xi) | \xi \in \alpha \cap C_\nu^n(\alpha) \wedge \xi \in C_\mu(\xi) \wedge \mu \leq \omega\}\),
  • \(C_\nu(\alpha) = \bigcup_{n < \omega} C_\nu^n (\alpha)\),
  • \(\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}\).

In other words \(\psi_\nu(\alpha)\) is the least ordinal number which cannot be generated from ordinals less than \(\Omega_\nu\) by applying of addition and the functions \(\psi_{\mu}(\eta)\) with \(\eta < \alpha\) and \(\mu \le \omega\).

We define \(\alpha=_{NF}\psi_\nu(\beta)\) iff \(\alpha=\psi_\nu(\beta)\) and \(\beta\in C_\nu(\beta)\)

Properties

Buchholz showed the following properties of those functions:

  • \(\psi_\nu(0)=\Omega_\nu\),
  • \(\psi_\nu(\alpha)\in P\),
  • \(\psi_\nu(\alpha+1)=\text{min}\{\gamma\in P| \psi_\nu(\alpha)<\gamma\}\text{ if }\alpha\in C_\nu(\alpha)\),
  • \(\Omega_\nu\le\psi_\nu(\alpha)<\Omega_{\nu+1}\),
  • \(\alpha\le\beta\Rightarrow\psi_\nu(\alpha)\le\psi_\nu(\beta)\),
  • \(\psi_0(\alpha)=\omega^\alpha \text{ if }\alpha<\varepsilon_0\),
  • \(\psi_\nu(\alpha)=\omega^{\Omega_\nu+\alpha} \text{ if }\alpha<\varepsilon_{\Omega_\nu+1} \text{ and } \nu\neq 0\).

Fundamental sequences

The fundamental sequence for an ordinal number \(\alpha\) with cofinality \(\text{cof}(\alpha)=\beta\) is a strictly increasing sequence \((\alpha[\eta])_{\eta<\beta}\) with length \(\beta\) and with limit \(\alpha\), where \(\alpha[\eta]\) is the \(\eta\)-th element of this sequence.

We define the set \(T\) consisting of zero and all ordinals expressible using Buchholz's functions and the operation of addition

  1. \(0 \in T\)
  2. if \(\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n\) and \(\alpha_1,\alpha_2,...,\alpha_n\in T\) then \(\alpha \in T\)
  3. if \(\alpha=_{NF}\psi_\nu(\beta)\) and \(\nu,\beta\in T\) and \(\nu\le\omega\) then \(\alpha \in T\)

For nonzero ordinals \(\alpha\in T\) we define the fundamental sequences as follows:

  1. if \(\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n\) then \(\text{cof} (\alpha)= \text{cof} (\alpha_n)\) and \(\alpha[\eta]=\alpha_1+\alpha_2+\cdots+(\alpha_n[\eta])\)
  2. if \(\alpha=\psi_0(0)\) or \(\alpha=\psi_{\nu+1}(0)\) then \(\operatorname{cof}(\alpha)=\alpha\) and \(\alpha[\eta]=\eta\)
  3. if \(\alpha=\psi_\omega(0)\) then \(\operatorname{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_\eta(0)\)
  4. if \(\alpha=\psi_{\nu}(\beta+1)\) then \(\operatorname{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta\)
  5. 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[\eta]=\psi_{\nu}(\beta[\eta])\)
  6. if \(\alpha=\psi_{\nu}(\beta)\) and \(\operatorname{cof}(\beta)\in\{\Omega_{\mu+1}\mid\mu\geq\nu\}\) then \(\operatorname{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_\nu(\beta[\gamma[\eta]])\) with \(\gamma[0]=\Omega_\mu\) and \(\gamma[\eta+1]=\psi_\mu(\beta[\gamma[\eta]])\)

Takeuti-Feferman-Buchholz ordinal

The Takeuti-Feferman-Buchholz ordinal is equal to \(\psi_0(\varepsilon_{\Omega_\omega+1})\) using Buchholz \(\psi\)-notaion and also it is equal to \(\theta_{\varepsilon_{\Omega_\omega+1}}(0)\) using Feferman \(\theta\)-notation. This ordinal is the limit of both notations. The name of the ordinal was proposed by David Madore.

See also

Other ordinal collapsing functions:

Madore's ψ function

Jäger's ψ functions

collapsing functions based on a weakly Mahlo cardinal

References

1. W.Buchholz. A New System of Proof-Theoretic Ordinal Functions. Annals of Pure and Applied Logic (1986),32