Difference between revisions of "Buchholz's ψ functions"
(Created page with "Buchholz's \(\psi\) function is an ordinal collapsing function introduced by German mathematician Wilfried Buchholz's in 1981. ==Basic Notions== Small Greek letters always...") 
m (Denis Maksudov moved page Buchholz's ψ function to Buchholz's ψ functions) 
(No difference)

Revision as of 03:26, 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 On0<\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
Now we assign a fundamental sequence for each limit ordinal below the BachmannHoward ordinal. 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. If \(\alpha\) is a countable limit ordinal (i.e. \(\alpha\) is a limit ordinal less than \(\Omega\)) then \(\text{cof}(\alpha)=\omega\). The first uncountable ordinal \(\Omega\) is the least ordinal whose cofinality greater than \(\omega\) since \(\text{cof}(\Omega)=\Omega\).
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
 \(0 \in T\)
 if \(\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n\) and \(\alpha_1,\alpha_2,...,\alpha_n\in T\) then \(\alpha \in T\)
 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:
 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])\)
 if \(\alpha=\psi_0(0)\) or \(\alpha=\psi_{\nu+1}(0)\), then \(\operatorname{cof}(\alpha)=\alpha\) and \(\alpha[\eta]=\eta\)
 if \(\alpha=\psi_\omega(0)\), then \(\operatorname{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_\eta(0)\)
 if \(\alpha=\psi_{\nu}(\beta+1)\) then \(\operatorname{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta\)
 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])\)
 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:
collapsing functions based on a weakly Mahlo cardinal
References
1. W.Buchholz. A New System of ProofTheoretic Ordinal Functions. Annals of Pure and Applied Logic (1986),32