Difference between revisions of "Buchholz's ψ functions"

From Cantor's Attic
Jump to: navigation, search
Line 12: Line 12:
  
 
<math>P=\{\alpha\in On|0<\alpha\wedge\forall\xi,\eta<\alpha(\xi+\eta\in\alpha)\}=\{\omega^\beta|\beta\in On\}</math>
 
<math>P=\{\alpha\in On|0<\alpha\wedge\forall\xi,\eta<\alpha(\xi+\eta\in\alpha)\}=\{\omega^\beta|\beta\in On\}</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>
  
 
== Definition ==
 
== Definition ==
Line 22: Line 26:
  
 
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\).
 +
 +
We define <math>\alpha=_{NF}\psi_\nu(\beta)</math> iff <math>\alpha=\psi_\nu(\beta)</math> and <math>\beta\in C_\nu(\beta)</math>
  
 
== Properties ==
 
== Properties ==
Line 39: 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.  
  
At first we define the normal form for ordinals
+
We define the set \(T\) consisting of zero and all ordinals expressible using Buchholz's function
 
+
<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}\psi_\nu(\beta)</math> iff <math>\alpha=\psi_\nu(\beta)</math> and <math>\beta\in C_\nu(\beta)</math>
+
 
+
After this we define the set \(T\) consisting of zero and all ordinals expressible using Buchholz's function
+
  
 
#<math>0 \in T</math>
 
#<math>0 \in T</math>
Line 51: Line 51:
 
#if <math>\alpha=_{NF}\psi_\nu(\beta)</math> and <math>\nu,\beta\in T</math> and <math>\nu\le\omega</math> then <math>\alpha \in T</math>
 
#if <math>\alpha=_{NF}\psi_\nu(\beta)</math> and <math>\nu,\beta\in T</math> and <math>\nu\le\omega</math> then <math>\alpha \in T</math>
  
For nonzero ordinals <math>\alpha\in T</math> we the define fundamental sequences as follows:
+
For nonzero ordinals <math>\alpha\in T</math> we define the fundamental sequences as follows:
  
 
#if <math>\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n</math> then <math>\text{cof} (\alpha)= \text{cof} (\alpha_n)</math> and <math>\alpha[\eta]=\alpha_1+\alpha_2+\cdots+(\alpha_n[\eta])</math>
 
#if <math>\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n</math> then <math>\text{cof} (\alpha)= \text{cof} (\alpha_n)</math> and <math>\alpha[\eta]=\alpha_1+\alpha_2+\cdots+(\alpha_n[\eta])</math>

Revision as of 10:45, 19 May 2018

Buchholz's \(\psi\) function is an ordinal collapsing function introduced by German mathematician Wilfried Buchholz's 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_{\alpha+1}=\aleph_{\alpha+1}\).

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_1\geq\alpha_2\geq\cdots\geq\alpha_n\) and \(\alpha_1,\alpha_2,...,\alpha_n\in P\)

Definition

Buchholz's \(\psi\) function is 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 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 function

  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]])\) where \(\gamma[0]=\Omega_\mu\) and \(\gamma[\eta+1]=\psi_\mu(\beta[\gamma[\eta]])\)

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