Difference between revisions of "Admissible"

From Cantor's Attic
Jump to: navigation, search
(Higher admissibility: 2-admissible almost defined)
(2-admissible)
Line 12: Line 12:
 
*
 
*
 
*
 
*
== Computably inaccessible ordinal ==
+
== Higher admissibility ==
 +
=== Computably inaccessible ordinal ===
  
An ordinal $\alpha$ is ''computably [[inaccessible]]'', also known as ''recursively inaccessible'', if it is admissible and a limit of admissible ordinals.<cite>Madore2017:OrdinalZoo</cite> If <math>f</math> enumerates admissible ordinals, recursively inaccessible ordinals are exactly the ordinals <math>\alpha</math> where <math>\alpha=f(\alpha)</math>.<!--Barwise, Admissible Sets and Structures (p.176)-->
+
An ordinal $\alpha$ is ''computably [[inaccessible]]'', also known as ''recursively inaccessible'', if it is admissible and a limit of admissible ordinals.<cite>Madore2017:OrdinalZoo</cite> If <math>f</math> enumerates admissible ordinals, recursively inaccessible ordinals are exactly the ordinals <math>\alpha</math> where <math>\alpha=f&#40;\alpha)</math>.<!--Barwise, Admissible Sets and Structures (p.176)-->
  
== Recursively Mahlo and further ==
+
=== Recursively Mahlo ===
 
An ordinal $α$ is ''recursively [[Mahlo]]'' iff for any [https://en.wikipedia.org/wiki/Alpha_recursion_theory $α$-recursive function] $f : α → α$ there is an admissible $β < α$ closed under $f$.<cite>Madore2017:OrdinalZoo</cite>
 
An ordinal $α$ is ''recursively [[Mahlo]]'' iff for any [https://en.wikipedia.org/wiki/Alpha_recursion_theory $α$-recursive function] $f : α → α$ there is an admissible $β < α$ closed under $f$.<cite>Madore2017:OrdinalZoo</cite>
  
There are also ''recursively [[weakly compact]]'' i.e. ''$Π_3$-[[reflecting ordinal|reflecting]]'' or ''2-admissible'' ordinals.<cite>Madore2017:OrdinalZoo</cite> More generally, $Π_{n+2}$-reflection is analogous to strong $Π_n^1$-[[indescribable|indescribability]] for all $n>0$. &#40;after definition 1.12)<cite>RichterAczel1974:InductiveDefinitions</cite>
+
===2-admissible===
 +
We call $\kappa\in\mathrm{Ad}$ ''2-admissible'' iff every $\xi<\kappa$ such that $\{\xi\}_\kappa$ maps $\kappa$-recursive functions to $\kappa$-recursive functions has a witness &#40;$\alpha\in\mathrm{Ad}$ such that $\xi<\alpha<\kappa$ and $\{\xi\}_\kappa$ maps $\alpha$-recursive functions to $\alpha$-recursive functions). &#40;$\mathrm{Ad}$ is the class of admissible ordinals greater than $\omega$.) ''TODO: complete definition'' &#40;definition 1.15)<cite>RichterAczel1974:InductiveDefinitions</cite>
  
==Higher admissibility==
+
2-admissible ordinals are precisely the $Π_3$-[[reflecting ordinal]]s. &#40;theorem 1.16)<cite>RichterAczel1974:InductiveDefinitions</cite>
 +
 
 +
2-admissibility is a recursive analogue of 2-regularity, which is equivalent to [[weakly compact|weak compactness]]. &#40;theorem 1.14)<cite>RichterAczel1974:InductiveDefinitions</cite> ''2-admissible'' ordinals can be called ''recursively weakly compact''.<cite>Madore2017:OrdinalZoo</cite> More generally, $Π_{n+2}$-reflection is analogous to strong $Π_n^1$-[[indescribable|indescribability]] for all $n>0$. &#40;after definition 1.12)<cite>RichterAczel1974:InductiveDefinitions</cite>
 +
 
 +
===$\Sigma_n$-admissible===
 
[[File:AdmissibilityImplicationDiagram.png|thumb|Some implications between admissibility-related conditions.]]
 
[[File:AdmissibilityImplicationDiagram.png|thumb|Some implications between admissibility-related conditions.]]
  
 
Admissibility has been extended using stronger collection axioms. One common formulation is that an ordinal $\alpha$ is $\Sigma_n$'''-admissible''' if $L_\alpha\vDash\textrm{RST}\cup\Sigma_n\textrm{-collection}$<!--Kranakis citation-->, where $\textrm{RST}$ denotes rudimentary set theory, i.e. Kripke-Platek set theory without the $\Sigma_0$-collection axiom<!--Aczel citation here-->.
 
Admissibility has been extended using stronger collection axioms. One common formulation is that an ordinal $\alpha$ is $\Sigma_n$'''-admissible''' if $L_\alpha\vDash\textrm{RST}\cup\Sigma_n\textrm{-collection}$<!--Kranakis citation-->, where $\textrm{RST}$ denotes rudimentary set theory, i.e. Kripke-Platek set theory without the $\Sigma_0$-collection axiom<!--Aczel citation here-->.
  
\(\Sigma_n\)-admissible ordinals need not necessarily satisfy the \(\Sigma_n\)-separation schema. For example, the least \(\Sigma_2\)-admissible ordinal doesn't satisfy \(\Sigma_2\)-separation.<!--Let this ordinal be α. L_α satisfies Σ_2-collection, but α-2-stable ordinals below aren't unbounded in α. Cf. https://www1.maths.leeds.ac.uk/~rathjen/HIGH.pdf#page=19-->
+
$\Sigma_n$-admissible ordinals need not necessarily satisfy the $\Sigma_n$-separation schema. For example, the least $\Sigma_2$-admissible ordinal doesn't satisfy $\Sigma_2$-separation.<!--Let this ordinal be α. L_α satisfies Σ_2-collection, but α-2-stable ordinals below aren't unbounded in α. Cf. https://www1.maths.leeds.ac.uk/~rathjen/HIGH.pdf#page=19-->
  
 
Here are some properties of $\Sigma_n$-admissibility:
 
Here are some properties of $\Sigma_n$-admissibility:
 
*$\Sigma_1$-admissibility is equivalent to $\Sigma_0$-admissibility.
 
*$\Sigma_1$-admissibility is equivalent to $\Sigma_0$-admissibility.
*For $n>1$, $\Sigma_n$-admissibility can be couched in terms of [[Reflecting ordinal|reflection]] onto sets of [[stable]] ordinals (Kranakis), and the smallest $\Sigma_n$-admissible ordinal is greater then the smallest [[nonprojectible]] ordinal and weaker variants of [[stable]] ordinals but smaller than the height of the [[Transitive ZFC model|minimal model of ZFC]] (if it exists).<cite>Madore2017:OrdinalZoo</cite>
+
*For $n>1$, $\Sigma_n$-admissibility can be couched in terms of [[Reflecting ordinal|reflection]] onto sets of [[stable]] ordinals &#40;Kranakis), and the smallest $\Sigma_n$-admissible ordinal is greater then the smallest [[nonprojectible]] ordinal and weaker variants of [[stable]] ordinals but smaller than the height of the [[Transitive ZFC model|minimal model of ZFC]] &#40;if it exists).<cite>Madore2017:OrdinalZoo</cite>
 
+
We call $\kappa\in\mathrm{Ad}$ 2-admissible iff every $\xi<\kappa$ such that $\{\xi\}_\kappa$ maps $\kappa$-recursive functions to $\kappa$-recursive functions has a witness &#40;$\alpha\in\mathrm{Ad}$ such that $\xi<\alpha<\kappa$ and $\{\xi\}_\kappa$ maps $\alpha$-recursive functions to $\alpha$-recursive functions). ($\mathrm{Ad}$ is the class of admissible ordinals greater than $\omega$.) ''TODO: complete definition'' It is a a recursive analogue of 2-regularity. (definition 1.15)<cite>RichterAczel1974:InductiveDefinitions</cite>
+
  
 
==Cofinality and projectum==
 
==Cofinality and projectum==
 
Two concepts used in the study of admissible ordinals are $\Sigma_1$-cofinality and $\Sigma_1$-projecta.
 
Two concepts used in the study of admissible ordinals are $\Sigma_1$-cofinality and $\Sigma_1$-projecta.
*The $\Sigma_1$-cofinality of $\beta$ is the least $\xi$ such that there exists a $\Sigma_1$-definable function mapping $\xi$ cofinally into $\beta$. (W. Maass, [https://igi-web.tugraz.at/PDF/4.pdf#page=3 Inadmissibility, tame R.E. sets and the admissible collapse], 1976)
+
*The $\Sigma_1$-cofinality of $\beta$ is the least $\xi$ such that there exists a $\Sigma_1$-definable function mapping $\xi$ cofinally into $\beta$. &#40;W. Maass, [https://igi-web.tugraz.at/PDF/4.pdf#page=3 Inadmissibility, tame R.E. sets and the admissible collapse], 1976)
*The $\Sigma_n$-projectum of $\beta$ is equal to<!--but not defined as--> the least $\delta$ such that some $\Sigma_n(L_\alpha)$-definable function maps a subset of $<!--\omega-->\delta$ onto $L_\beta$ (K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf#page=50 An introduction to the fine structure of the constructible hierarchy], 1972). (However note that when using the Jensen hierarchy instead of the hierarchy $L$, as the original source does, that behavior may change)
+
*The $\Sigma_n$-projectum of $\beta$ is equal to<!--but not defined as--> the least $\delta$ such that some $\Sigma_n&#40;L_\alpha)$-definable function maps a subset of $<!--\omega-->\delta$ onto $L_\beta$ &#40;K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf#page=50 An introduction to the fine structure of the constructible hierarchy], 1972). &#40;However note that when using the Jensen hierarchy instead of the hierarchy $L$, as the original source does, that behavior may change)
**Alternatively, when $n=1$, the $\Sigma_1$-projectum of $\beta$ has been given as the least $\gamma\le\beta$ such that a $\beta$-recursive one-to-one function $f:\beta\rightarrow\gamma$ exists. (W. Maass, [https://igi-web.tugraz.at/PDF/4.pdf#page=3 Inadmissibility, tame R.E. sets and the admissible collapse], 1976)<nowiki>[</nowiki>Barwise<!-- "Part C: α-Recursion-->, p.157] This is claimed to extend to $n>1$ in [https://arxiv.org/pdf/math/9609203.pdf]
+
**Alternatively, when $n=1$, the $\Sigma_1$-projectum of $\beta$ has been given as the least $\gamma\le\beta$ such that a $\beta$-recursive one-to-one function $f:\beta\rightarrow\gamma$ exists. &#40;W. Maass, [https://igi-web.tugraz.at/PDF/4.pdf#page=3 Inadmissibility, tame R.E. sets and the admissible collapse], 1976)<nowiki>[</nowiki>Barwise<!-- "Part C: α-Recursion-->, p.157] This is claimed to extend to $n>1$ in [https://arxiv.org/pdf/math/9609203.pdf]
**Alternatively, the $\Sigma_n$-projectum of $\alpha$ is the smallest $\rho$ such that there exists a $\Sigma_n(L_\alpha)$ function $f$ with $f^{\prime\prime}L_\rho=L_\alpha$.<cite>Jech2003:SetTheory</cite><sup>p.549</sup>
+
**Alternatively, the $\Sigma_n$-projectum of $\alpha$ is the smallest $\rho$ such that there exists a $\Sigma_n&#40;L_\alpha)$ function $f$ with $f^{\prime\prime}L_\rho=L_\alpha$.<cite>Jech2003:SetTheory</cite><sup>p.549</sup>
  
$\Delta_n$-projecta are similar to $\Sigma_n$-projecta, except that its behavior lacks the involvement of a bounded subset of $<!--\omega-->\delta$, employing just the ordinal $<!--\omega-->\delta$ instead. (Compare Σ<sub>n</sub>: [https://core.ac.uk/download/pdf/30905237.pdf#page=50], Δ<sub>n</sub>: [https://core.ac.uk/download/pdf/30905237.pdf#page=52])
+
$\Delta_n$-projecta are similar to $\Sigma_n$-projecta, except that its behavior lacks the involvement of a bounded subset of $<!--\omega-->\delta$, employing just the ordinal $<!--\omega-->\delta$ instead. &#40;Compare Σ<sub>n</sub>: [https://core.ac.uk/download/pdf/30905237.pdf#page=50], Δ<sub>n</sub>: [https://core.ac.uk/download/pdf/30905237.pdf#page=52])
 
===Properties===
 
===Properties===
*$\beta$ is admissible iff $\Sigma_1\textrm{-cof}(\beta)=\beta$ (W. Maass, [https://igi-web.tugraz.at/PDF/4.pdf#page=3 Inadmissibility, tame R.E. sets and the admissible collapse], 1976).
+
*$\beta$ is admissible iff $\Sigma_1\textrm{-cof}&#40;\beta)=\beta$ &#40;W. Maass, [https://igi-web.tugraz.at/PDF/4.pdf#page=3 Inadmissibility, tame R.E. sets and the admissible collapse], 1976).
**Note that although admissibility is considered to be "recursive regularity"<cite>Arai97:P</cite><sup>p.4</sup>, $\Sigma_1\textrm{-cof}$ behaves differently with respect to admissibles than $\textrm{cof}$ does with respect to regular cardinals. For example, $\textrm{cof}(\omega_1\times 2)=\omega_1$, however $\Sigma_1\textrm{-cof}(\omega_1^{CK}\times 2)=\omega$. (This is because there's a one-to-one map $f:\omega_1^{CK}\rightarrow\omega$ that's $\omega_1^{CK}$-recursive<!--Barwise, "Part C: α-Recursion (p.157)-->,therefore also $\omega_1^{CK}\times 2$-recursive)
+
**Note that although admissibility is considered to be "recursive regularity"<cite>Arai97:P</cite><sup>p.4</sup>, $\Sigma_1\textrm{-cof}$ behaves differently with respect to admissibles than $\textrm{cof}$ does with respect to regular cardinals. For example, $\textrm{cof}&#40;\omega_1\times 2)=\omega_1$, however $\Sigma_1\textrm{-cof}&#40;\omega_1^{CK}\times 2)=\omega$. &#40;This is because there's a one-to-one map $f:\omega_1^{CK}\rightarrow\omega$ that's $\omega_1^{CK}$-recursive<!--Barwise, "Part C: α-Recursion (p.157)-->,therefore also $\omega_1^{CK}\times 2$-recursive)
*$\beta$ is [[Stable#Variants|nonprojectible]] iff $\Sigma_1\textrm{-proj}(\beta)=\beta$ (K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf#page=39 An introduction to the fine structure of the constructible hierarchy], 1972).
+
*$\beta$ is [[Stable#Variants|nonprojectible]] iff $\Sigma_1\textrm{-proj}&#40;\beta)=\beta$ &#40;K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf#page=39 An introduction to the fine structure of the constructible hierarchy], 1972).
**For the first alternative definition of the $\Sigma_1$-projectum, compare to Rathjen's description of nonprojectible ordinals (M. Rathjen, [https://www1.maths.leeds.ac.uk/~rathjen/ICMend.pdf#page=18 The Art of Ordinal Analysis]).
+
**For the first alternative definition of the $\Sigma_1$-projectum, compare to Rathjen's description of nonprojectible ordinals &#40;M. Rathjen, [https://www1.maths.leeds.ac.uk/~rathjen/ICMend.pdf#page=18 The Art of Ordinal Analysis]).
*A more fine but extendable result, if we assume $n>1$ and $\omega\beta=\beta$, then $\Sigma_&#x6e;\textrm{-proj}(\beta)>\omega$ iff $\beta$ begins a $\Sigma_n$-gap. (K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf#page=50 An introduction to the fine structure of the constructible hierarchy], 1972)<!--Patterns of Projecta also mentions this result via their definition of projectum, but it's the same theorem also proven by Jensen-->. Similarly, if $\Delta_n\textrm{-proj}(\beta)>\omega$ then $\beta$ begins a $\Delta_n$-gap.
+
*A more fine but extendable result, if we assume $n>1$ and $\omega\beta=\beta$, then $\Sigma_&#x6e;\textrm{-proj}&#40;\beta)>\omega$ iff $\beta$ begins a $\Sigma_n$-gap. &#40;K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf#page=50 An introduction to the fine structure of the constructible hierarchy], 1972)<!--Patterns of Projecta also mentions this result via their definition of projectum, but it's the same theorem also proven by Jensen-->. Similarly, if $\Delta_n\textrm{-proj}&#40;\beta)>\omega$ then $\beta$ begins a $\Delta_n$-gap.
*When $\beta$ is admissible{{citation needed}}<!--I think because it requires β-recursion theory, which implicitly assumes β admissible-->, $L_\beta\vDash``\Sigma_1\textrm{-cof}(\beta)\textrm{ is a cardinal}"$ and $L_\beta\vDash``\Sigma_1\textrm{-proj}(\beta)\textrm{ is a cardinal}"$. (W. Maass, [https://igi-web.tugraz.at/PDF/4.pdf#page=3 Inadmissibility, tame R.E. sets and the admissible collapse], 1976)
+
*When $\beta$ is admissible{{citation needed}}<!--I think because it requires β-recursion theory, which implicitly assumes β admissible-->, $L_\beta\vDash``\Sigma_1\textrm{-cof}&#40;\beta)\textrm{ is a cardinal}"$ and $L_\beta\vDash``\Sigma_1\textrm{-proj}&#40;\beta)\textrm{ is a cardinal}"$. &#40;W. Maass, [https://igi-web.tugraz.at/PDF/4.pdf#page=3 Inadmissibility, tame R.E. sets and the admissible collapse], 1976)
*Applying a result from [[Heights_of_models#ZFC_without_the_powerset_axiom|here]], $L_&#x7b;\Sigma_1\textrm{-cof}(\beta&#x29;}$[[Stable|$\prec_{\Sigma_1}$]]$L_\beta$ and $L_&#x7b;\Sigma_1\textrm{-proj}(\beta&#x29;}\prec_{\Sigma_1}L_\beta$.
+
*Applying a result from [[Heights_of_models#ZFC_without_the_powerset_axiom|here]], $L_&#x7b;\Sigma_1\textrm{-cof}&#40;\beta&#x29;}$[[Stable|$\prec_{\Sigma_1}$]]$L_\beta$ and $L_&#x7b;\Sigma_1\textrm{-proj}&#40;\beta&#x29;}\prec_{\Sigma_1}L_\beta$.
 
<!--Σ_n-projecta of a constant ordinal may decrease as n increases. [https://math.stackexchange.com/questions/1635440/an-exercise-in-fine-structure-of-constructible-universe-concerning-projectum-pat]-->
 
<!--Σ_n-projecta of a constant ordinal may decrease as n increases. [https://math.stackexchange.com/questions/1635440/an-exercise-in-fine-structure-of-constructible-universe-concerning-projectum-pat]-->
  
 
===Patterns===
 
===Patterns===
Sometimes, some unintuitive patterns arise in projecta of an ordinal, such as $\Sigma_1\textrm{-proj}(\alpha&#x29;=\Sigma_2\textrm{-proj}(\alpha&#x29;>\Sigma_3\textrm{-proj}(\alpha&#x29;$&#x2e; In fact, for any binary string, there exists some ordinal $\alpha$ whose sequence $(\Sigma_k\textrm{-proj&#x7d;(\alpha&#x29;)_{0\le k\le n}$ has pairwise comparisons $>$, $=$ each determined by that string. <sup>citation needed</sup><!--https://www.jstor.org/stable/2273621? https://mathoverflow.net/questions/67933/sequences-of-projecta-in-the-constructible-hierarchy?-->
+
Sometimes, some unintuitive patterns arise in projecta of an ordinal, such as $\Sigma_1\textrm{-proj}&#40;\alpha&#x29;=\Sigma_2\textrm{-proj}&#40;\alpha&#x29;>\Sigma_3\textrm{-proj}&#40;\alpha&#x29;$&#x2e; In fact, for any binary string, there exists some ordinal $\alpha$ whose sequence $&#40;\Sigma_k\textrm{-proj&#x7d;&#40;\alpha&#x29;)_{0\le k\le n}$ has pairwise comparisons $>$, $=$ each determined by that string. <sup>citation needed</sup><!--https://www.jstor.org/stable/2273621? https://mathoverflow.net/questions/67933/sequences-of-projecta-in-the-constructible-hierarchy?-->
  
 
{{references}}
 
{{references}}

Revision as of 07:51, 14 May 2022


    This article is a stub. Please help us to improve Cantor's Attic by adding information.

An ordinal $\gamma$ is admissible if the $L_\gamma$ level of the constructible universe satisfies the Kripke-Platek axioms of set theory. The term was coined by Richard Platek in 1966.

The smallest admissible ordinal is often considered to be $\omega$, the least infinite ordinal. However, some authors include Infinity in the KP axioms, in which case $\omega_1^{CK}$,[1] the least non-computable ordinal, is the least admissible. More generally, for any real $x$, the least ordinal not computable from $x$ is denoted $\omega_1^x$, and is also admissible. Indeed, one has $L_{\omega_1^x}[x]\models\text{KP}$.

The smallest limit of admissible ordinals, $\omega_\omega^{CK}$, is not admissible.[1]

Equivalent definitions

The following properties are also equivalent to admissibility:

Higher admissibility

Computably inaccessible ordinal

An ordinal $\alpha$ is computably inaccessible, also known as recursively inaccessible, if it is admissible and a limit of admissible ordinals.[1] If \(f\) enumerates admissible ordinals, recursively inaccessible ordinals are exactly the ordinals \(\alpha\) where \(\alpha=f(\alpha)\).

Recursively Mahlo

An ordinal $α$ is recursively Mahlo iff for any $α$-recursive function $f : α → α$ there is an admissible $β < α$ closed under $f$.[1]

2-admissible

We call $\kappa\in\mathrm{Ad}$ 2-admissible iff every $\xi<\kappa$ such that $\{\xi\}_\kappa$ maps $\kappa$-recursive functions to $\kappa$-recursive functions has a witness ($\alpha\in\mathrm{Ad}$ such that $\xi<\alpha<\kappa$ and $\{\xi\}_\kappa$ maps $\alpha$-recursive functions to $\alpha$-recursive functions). ($\mathrm{Ad}$ is the class of admissible ordinals greater than $\omega$.) TODO: complete definition (definition 1.15)[2]

2-admissible ordinals are precisely the $Π_3$-reflecting ordinals. (theorem 1.16)[2]

2-admissibility is a recursive analogue of 2-regularity, which is equivalent to weak compactness. (theorem 1.14)[2] 2-admissible ordinals can be called recursively weakly compact.[1] More generally, $Π_{n+2}$-reflection is analogous to strong $Π_n^1$-indescribability for all $n>0$. (after definition 1.12)[2]

$\Sigma_n$-admissible

Some implications between admissibility-related conditions.

Admissibility has been extended using stronger collection axioms. One common formulation is that an ordinal $\alpha$ is $\Sigma_n$-admissible if $L_\alpha\vDash\textrm{RST}\cup\Sigma_n\textrm{-collection}$, where $\textrm{RST}$ denotes rudimentary set theory, i.e. Kripke-Platek set theory without the $\Sigma_0$-collection axiom.

$\Sigma_n$-admissible ordinals need not necessarily satisfy the $\Sigma_n$-separation schema. For example, the least $\Sigma_2$-admissible ordinal doesn't satisfy $\Sigma_2$-separation.

Here are some properties of $\Sigma_n$-admissibility:

  • $\Sigma_1$-admissibility is equivalent to $\Sigma_0$-admissibility.
  • For $n>1$, $\Sigma_n$-admissibility can be couched in terms of reflection onto sets of stable ordinals (Kranakis), and the smallest $\Sigma_n$-admissible ordinal is greater then the smallest nonprojectible ordinal and weaker variants of stable ordinals but smaller than the height of the minimal model of ZFC (if it exists).[1]

Cofinality and projectum

Two concepts used in the study of admissible ordinals are $\Sigma_1$-cofinality and $\Sigma_1$-projecta.

  • The $\Sigma_1$-cofinality of $\beta$ is the least $\xi$ such that there exists a $\Sigma_1$-definable function mapping $\xi$ cofinally into $\beta$. (W. Maass, Inadmissibility, tame R.E. sets and the admissible collapse, 1976)
  • The $\Sigma_n$-projectum of $\beta$ is equal to the least $\delta$ such that some $\Sigma_n(L_\alpha)$-definable function maps a subset of $\delta$ onto $L_\beta$ (K. Devlin, An introduction to the fine structure of the constructible hierarchy, 1972). (However note that when using the Jensen hierarchy instead of the hierarchy $L$, as the original source does, that behavior may change)
    • Alternatively, when $n=1$, the $\Sigma_1$-projectum of $\beta$ has been given as the least $\gamma\le\beta$ such that a $\beta$-recursive one-to-one function $f:\beta\rightarrow\gamma$ exists. (W. Maass, Inadmissibility, tame R.E. sets and the admissible collapse, 1976)[Barwise, p.157] This is claimed to extend to $n>1$ in [1]
    • Alternatively, the $\Sigma_n$-projectum of $\alpha$ is the smallest $\rho$ such that there exists a $\Sigma_n(L_\alpha)$ function $f$ with $f^{\prime\prime}L_\rho=L_\alpha$.[3]p.549

$\Delta_n$-projecta are similar to $\Sigma_n$-projecta, except that its behavior lacks the involvement of a bounded subset of $\delta$, employing just the ordinal $\delta$ instead. (Compare Σn: [2], Δn: [3])

Properties

  • $\beta$ is admissible iff $\Sigma_1\textrm{-cof}(\beta)=\beta$ (W. Maass, Inadmissibility, tame R.E. sets and the admissible collapse, 1976).
    • Note that although admissibility is considered to be "recursive regularity"[4]p.4, $\Sigma_1\textrm{-cof}$ behaves differently with respect to admissibles than $\textrm{cof}$ does with respect to regular cardinals. For example, $\textrm{cof}(\omega_1\times 2)=\omega_1$, however $\Sigma_1\textrm{-cof}(\omega_1^{CK}\times 2)=\omega$. (This is because there's a one-to-one map $f:\omega_1^{CK}\rightarrow\omega$ that's $\omega_1^{CK}$-recursive,therefore also $\omega_1^{CK}\times 2$-recursive)
  • $\beta$ is nonprojectible iff $\Sigma_1\textrm{-proj}(\beta)=\beta$ (K. Devlin, An introduction to the fine structure of the constructible hierarchy, 1972).
    • For the first alternative definition of the $\Sigma_1$-projectum, compare to Rathjen's description of nonprojectible ordinals (M. Rathjen, The Art of Ordinal Analysis).
  • A more fine but extendable result, if we assume $n>1$ and $\omega\beta=\beta$, then $\Sigma_n\textrm{-proj}(\beta)>\omega$ iff $\beta$ begins a $\Sigma_n$-gap. (K. Devlin, An introduction to the fine structure of the constructible hierarchy, 1972). Similarly, if $\Delta_n\textrm{-proj}(\beta)>\omega$ then $\beta$ begins a $\Delta_n$-gap.
  • When $\beta$ is admissible[ citation needed ], $L_\beta\vDash``\Sigma_1\textrm{-cof}(\beta)\textrm{ is a cardinal}"$ and $L_\beta\vDash``\Sigma_1\textrm{-proj}(\beta)\textrm{ is a cardinal}"$. (W. Maass, Inadmissibility, tame R.E. sets and the admissible collapse, 1976)
  • Applying a result from here, $L_{\Sigma_1\textrm{-cof}(\beta)}$$\prec_{\Sigma_1}$$L_\beta$ and $L_{\Sigma_1\textrm{-proj}(\beta)}\prec_{\Sigma_1}L_\beta$.

Patterns

Sometimes, some unintuitive patterns arise in projecta of an ordinal, such as $\Sigma_1\textrm{-proj}(\alpha)=\Sigma_2\textrm{-proj}(\alpha)>\Sigma_3\textrm{-proj}(\alpha)$. In fact, for any binary string, there exists some ordinal $\alpha$ whose sequence $(\Sigma_k\textrm{-proj}(\alpha))_{0\le k\le n}$ has pairwise comparisons $>$, $=$ each determined by that string. citation needed

References

  1. Madore, David. A zoo of ordinals. , 2017. www   bibtex
  2. Richter, Wayne and Aczel, Peter. Inductive Definitions and Reflecting Properties of Admissible Ordinals. Generalized recursion theory : proceedings of the 1972 Oslo symposium, pp. 301-381, 1974. www   bibtex
  3. Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www   bibtex
  4. Arai, Toshiyasu. A sneak preview of proof theory of ordinals. , 1997. www   bibtex
Main library