Difference between revisions of "Buchholz's ψ functions"

From Cantor's Attic
Jump to: navigation, search
Line 37: Line 37:
 
== Fundamental sequences ==
 
== Fundamental sequences ==
  
Now we assign a fundamental sequence for each limit ordinal below the Bachmann-Howard ordinal. 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. If <math>\alpha</math> is a countable limit ordinal (i.e. <math>\alpha</math> is a limit ordinal less than <math>\Omega</math>) then <math>\text{cof}(\alpha)=\omega</math>. The first uncountable ordinal <math>\Omega</math> is the least ordinal whose cofinality greater than <math>\omega</math> since <math>\text{cof}(\Omega)=\Omega</math>.
+
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
 
At first we define the normal form for ordinals

Revision as of 07:54, 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\}\)

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\).

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.

At first we define the normal form for ordinals

\(\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\)

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

After this 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 the define 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