Misplaced Pages

Rathjen's psi function

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (October 2022) (Learn how and when to remove this message)

In mathematics, Rathjen's  ψ {\displaystyle \psi } psi function is an ordinal collapsing function developed by Michael Rathjen. It collapses weakly Mahlo cardinals M {\displaystyle M} to generate large countable ordinals. A weakly Mahlo cardinal is a cardinal such that the set of regular cardinals below M {\displaystyle M} is closed under M {\displaystyle M} (i.e. all normal functions closed in M {\displaystyle M} are closed under some regular ordinal < M {\displaystyle <M} ). Rathjen uses this to diagonalise over the weakly inaccessible hierarchy.

It admits an associated ordinal notation T ( M ) {\displaystyle T(M)}  whose limit (i.e. ordinal type) is ψ Ω ( χ ε M + 1 ( 0 ) ) {\displaystyle \psi _{\Omega }(\chi _{\varepsilon _{M}+1}(0))} , which is strictly greater than both | K P M | {\displaystyle \vert KPM\vert } and the limit of countable ordinals expressed by Rathjen's ψ {\displaystyle \psi } . | K P M | {\displaystyle \vert KPM\vert } , which is called the "Small Rathjen ordinal" is the proof-theoretic ordinal of K P M {\displaystyle {\mathsf {KPM}}} , Kripke–Platek set theory augmented by the axiom schema "for any Δ 0 {\displaystyle \Delta _{0}} -formula H ( x , y ) {\displaystyle H(x,y)}  satisfying ∀ x ∃ y ( H ( x , y ) ) {\displaystyle \forall x\,\exists y\,(H(x,y))} , there exists an addmissible set z {\displaystyle z}  satisfying ∀ x ∈ z ∃ y ( H ( x , y ) ) {\displaystyle \forall x\in z\,\exists y\,(H(x,y))} ". It is equal to ψ Ω ( ψ χ ε M + 1 ( 0 ) ( 0 ) ) {\displaystyle \psi _{\Omega }(\psi _{\chi _{\varepsilon _{M}+1}(0)}(0))} in Rathjen's ψ {\displaystyle \psi } function.

Definition

Restrict π {\displaystyle \pi } and κ {\displaystyle \kappa } to uncountable regular cardinals < M {\displaystyle <M} ; for a function f {\displaystyle f} let dom ⁡ ( f ) {\displaystyle \operatorname {dom} (f)} denote the domain of f {\displaystyle f} ; let cl M ⁡ ( X ) {\displaystyle \operatorname {cl} _{M}(X)} denote X ∪ { α < M : α  is a limit point of  X } {\displaystyle X\cup \{\alpha <M:\alpha {\text{ is a limit point of }}X\}} , and let enum ⁡ ( X ) {\displaystyle \operatorname {enum} (X)} denote the enumeration of X {\displaystyle X} . Lastly, an ordinal α {\displaystyle \alpha } is said to be to be strongly critical if φ α ( 0 ) = α {\displaystyle \varphi _{\alpha }(0)=\alpha } .

For α ∈ Γ M + 1 {\displaystyle \alpha \in \Gamma _{M+1}} and β ∈ M {\displaystyle \beta \in M} :

β ∪ { 0 , M } ⊆ B n ( α , β ) γ = γ 1 + ⋯ + γ k  and  γ 1 , … , γ k ∈ B n ( α , β ) → γ ∈ B n + 1 ( α , β ) γ = φ γ 0 ( γ 1 )  and  γ 0 , γ 1 ∈ B n ( α , β ) → γ ∈ B n + 1 ( α , β ) π ∈ B n ( α , β ) and  γ < π → γ ∈ B n + 1 ( α , β ) δ , η ∈ B n ( α , β ) ∧ δ < α ∧ η ∈ dom ⁡ ( χ δ ) → χ δ ( η ) ∈ B n + 1 ( α , β ) B ( α , β ) ⋃ n < ω B n ( α , β ) χ α = enum ⁡ ( cl ⁡ ( κ : κ ∉ B ( α , κ ) ∧ α ∈ B ( α , κ ) } ) ) . {\displaystyle {\begin{aligned}&\beta \cup \{0,M\}\subseteq B^{n}(\alpha ,\beta )\gamma =\gamma _{1}+\cdots +\gamma _{k}{\text{ and }}\gamma _{1},\ldots ,\gamma _{k}\in B^{n}(\alpha ,\beta )\\&\rightarrow \gamma \in B^{n+1}(\alpha ,\beta )\gamma =\varphi _{\gamma _{0}}(\gamma _{1}){\text{ and }}\gamma _{0},\gamma _{1}\in B^{n}(\alpha ,\beta )\rightarrow \gamma \in B^{n+1}(\alpha ,\beta )\pi \in B^{n}(\alpha ,\beta )\\&{\text{and }}\gamma <\pi \rightarrow \gamma \in B^{n+1}(\alpha ,\beta )\delta ,\eta \in B^{n}(\alpha ,\beta )\land \delta <\alpha \land \eta \in \operatorname {dom} (\chi _{\delta })\\&\rightarrow \chi _{\delta }(\eta )\in B^{n+1}(\alpha ,\beta )B(\alpha ,\beta )\\&\bigcup _{n<\omega }B^{n}(\alpha ,\beta )\chi _{\alpha }\\&=\operatorname {enum} (\operatorname {cl} (\kappa :\kappa \notin B(\alpha ,\kappa )\land \alpha \in B(\alpha ,\kappa )\})).\end{aligned}}}

If κ = χ α ( β + 1 ) {\displaystyle \kappa =\chi _{\alpha }(\beta +1)} for some ( α , β ) ∈ Γ M + 1 × M {\displaystyle (\alpha ,\beta )\in \Gamma _{M+1}\times M} , define κ − := χ α ( β ) {\displaystyle \kappa ^{-}:=\chi _{\alpha }(\beta )} using the unique ( α , β ) {\displaystyle (\alpha ,\beta )} . Otherwise if κ = χ α ( 0 ) {\displaystyle \kappa =\chi _{\alpha }(0)} for some α ∈ Γ M + 1 {\displaystyle \alpha \in \Gamma _{M+1}} , then define κ − := sup ( SC M ⁡ ( α ) ∪ { 0 } ) {\displaystyle \kappa ^{-}:=\sup(\operatorname {SC} _{M}(\alpha )\cup \{0\})} using the unique α {\displaystyle \alpha } , where SC M ⁡ ( α ) {\displaystyle \operatorname {SC} _{M}(\alpha )} is a set of strongly critical ordinals < M {\displaystyle <M} explicitly defined in the original source.

For α ∈ Γ M + 1 {\displaystyle \alpha \in \Gamma _{M+1}} :

κ − ∪ { κ − , M } ⊂ C κ n ( α ) γ = γ 1 + ⋯ + γ k  and  γ 1 , … , γ k ∈ C n ( α ) → γ ∈ C n + 1 ( α ) γ = φ γ 0 ( γ 1 ) ∧ γ 0 , γ 1 ∈ C n ( α , β ) → γ ∈ C n + 1 ( α ) π ∈ C κ n ( α ) ∩ κ ∧ γ < π ∧ π ∈ R → γ ∈ C κ n + 1 ( α ) γ = χ δ ( η ) ∧ δ , η ∈ C κ n ( α ) → γ ∈ C κ n + 1 ( α ) γ = Φ δ ( η ) ∧ δ , η ∈ C κ n ( α ) ∧ 0 < δ ∧ δ , η < M → γ ∈ C κ n + 1 ( α ) β < α ∧ π , β ∈ C κ n ( α ) ∧ β ∈ C π ( β ) → ψ π ( β ) ∈ C κ n + 1 ( α ) C κ ( α ) := ⋃ C κ n ( α ) : n < ω . {\displaystyle {\begin{aligned}&\kappa ^{-}\cup \{\kappa ^{-},M\}\subset C_{\kappa }^{n}(\alpha )\gamma =\gamma _{1}+\cdots +\gamma _{k}{\text{ and }}\gamma _{1},\ldots ,\gamma _{k}\in C^{n}(\alpha )\rightarrow \gamma \in C^{n+1}(\alpha )\gamma =\varphi _{\gamma _{0}}(\gamma _{1})\land \gamma _{0},\gamma _{1}\in C^{n}(\alpha ,\beta )\\&\rightarrow \gamma \in C^{n+1}(\alpha )\pi \in C_{\kappa }^{n}(\alpha )\cap \kappa \land \gamma <\pi \land \pi \in {\textrm {R}}\\&\rightarrow \gamma \in C_{\kappa }^{n+1}(\alpha )\gamma =\chi _{\delta }(\eta )\land \delta ,\eta \in C_{\kappa }^{n}(\alpha )\rightarrow \gamma \in C_{\kappa }^{n+1}(\alpha )\\&\gamma =\Phi _{\delta }(\eta )\land \delta ,\eta \in C_{\kappa }^{n}(\alpha )\land 0<\delta \land \delta ,\eta <M\rightarrow \gamma \in C_{\kappa }^{n+1}(\alpha )\beta <\alpha \land \pi ,\beta \in C_{\kappa }^{n}(\alpha )\land \beta \in C_{\pi }(\beta )\rightarrow \psi _{\pi }(\beta )\in C_{\kappa }^{n+1}(\alpha )C_{\kappa }(\alpha ):=\bigcup _{C_{\kappa }^{n}(\alpha ):n<\omega }.\end{aligned}}}
ψ κ ( α ) := min ( { ξ : ξ ∉ C κ ( α ) } ) . {\displaystyle \psi _{\kappa }(\alpha ):=\min(\{\xi :\xi \notin C_{\kappa }(\alpha )\}).}

Explanation

  • Restrict π {\displaystyle \pi } to uncountable regular cardinals.
  • enum ⁡ ( X ) {\displaystyle \operatorname {enum} (X)} is a unique increasing function such that the range of  enum ⁡ ( X ) {\displaystyle \operatorname {enum} (X)} is exactly X {\displaystyle X} .
  • cl ⁡ ( X ) {\displaystyle \operatorname {cl} (X)} is the closure of X {\displaystyle X} , i.e. X ∪ { β ∈ Lim ∣ sup ( X ∩ β ) = β } {\displaystyle X\cup \{\beta \in \operatorname {Lim} \mid \sup(X\cap \beta )=\beta \}} , where Lim {\displaystyle \operatorname {Lim} } denotes the class of non-zero limit ordinals.
  • B 0 ( α , β ) = β ∪ { 0 , M } {\displaystyle B_{0}(\alpha ,\beta )=\beta \cup \{0,M\}}
  • B n + 1 ( α , β ) = { γ + δ , φ γ ( δ ) , χ μ ( δ ) | γ , δ , μ ∈ B n ( α , β ) ∧ μ < α } {\displaystyle B_{n+1}(\alpha ,\beta )=\{\gamma +\delta ,\varphi _{\gamma }(\delta ),\chi _{\mu }(\delta )|\gamma ,\delta ,\mu \in B_{n}(\alpha ,\beta )\land \mu <\alpha \}}
  • B ( α , β ) = ⋃ n < ω B n ( α , β ) {\displaystyle B(\alpha ,\beta )=\bigcup _{n<\omega }B_{n}(\alpha ,\beta )}
  • χ α ( β ) = enum ⁡ ( cl ⁡ ( { π : B ( α , π ) ∩ M ⊆ π ∧ α ∈ B ( α , π ) } ) ) = enum ⁡ ( { β ∈ Lim ∣ sup { π : B ( α , π ) ∩ M ⊆ π ∧ α ∈ B ( α , π ) } ∩ β ) = β } {\displaystyle \chi _{\alpha }(\beta )=\operatorname {enum} (\operatorname {cl} (\{\pi :B(\alpha ,\pi )\cap M\subseteq \pi \land \alpha \in B(\alpha ,\pi )\}))=\operatorname {enum} (\{\beta \in \operatorname {Lim} \mid \sup\{\pi :B(\alpha ,\pi )\cap M\subseteq \pi \land \alpha \in B(\alpha ,\pi )\}\cap \beta )=\beta \}}
  • C 0 ( α , β ) = β ∪ { 0 , M } {\displaystyle C_{0}(\alpha ,\beta )=\beta \cup \{0,M\}}
  • C n + 1 ( α , β ) = { γ + δ , φ γ ( δ ) , χ μ ( δ ) , ψ π ( μ ) | γ , δ , μ , π ∈ B n ( α , β ) ∧ μ < α } {\displaystyle C_{n+1}(\alpha ,\beta )=\{\gamma +\delta ,\varphi _{\gamma }(\delta ),\chi _{\mu }(\delta ),\psi _{\pi }(\mu )|\gamma ,\delta ,\mu ,\pi \in B_{n}(\alpha ,\beta )\land \mu <\alpha \}}
  • C ( α , β ) = ⋃ n < ω C n ( α , β ) {\displaystyle C(\alpha ,\beta )=\bigcup _{n<\omega }C_{n}(\alpha ,\beta )}
  • ψ π ( α ) = min ( { β : C ( α , β ) ∩ π ⊆ β ∧ α ∈ C ( α , β ) } ) {\displaystyle \psi _{\pi }(\alpha )=\min(\{\beta :C(\alpha ,\beta )\cap \pi \subseteq \beta \land \alpha \in C(\alpha ,\beta )\})}

Rathjen originally defined the  ψ {\displaystyle \psi } function in more complicated a way in order to create an ordinal notation associated to it. Therefore, it is not certain whether the simplified OCF above yields an ordinal notation or not. The original  χ {\displaystyle \chi } functions used in Rathjen's original OCF are also not so easy to understand, and differ from the  χ {\displaystyle \chi } functions defined above.

Rathjen's ψ {\displaystyle \psi } and the simplification provided above are not the same OCF. This is partially because the former is known to admit an ordinal notation, while the latter isn't known to admit an ordinal notation. Rathjen's ψ {\displaystyle \psi } is often confounded with another of his OCFs which also uses the symbol ψ {\displaystyle \psi } , but they are distinct notions. The former one is a published OCF, while the latter one is just a function symbol in an ordinal notation associated to an unpublished OCF.

References

  1. Rathjen, Michael (1990). "Ordinal Notation Based on a Weakly Mahlo Cardinal" (PDF). University of Leeds. Retrieved 2021-09-18.
  2. Rathjen, Michael (1994-01-01). "Collapsing functions based on recursively large ordinals: A well-ordering proof for KPM". Archive for Mathematical Logic. 33 (1): 35–55. doi:10.1007/BF01275469. ISSN 1432-0665. S2CID 35012853.
  3. Rathjen, Michael (1989-09-04). "Proof-theoretic analysis of KPM" (PDF). University of Leeds. Retrieved 2021-09-18.
Categories: