Editing Indescribable cardinal

{{Short description|Large cardinal number that is hard to describe in a given language}}

{{citations|date=June 2022}}

In [[set theory]], a branch of mathematics, a '''Q-indescribable cardinal''' is a certain kind of [[large cardinal]] number that is hard to axiomatize in some language ''Q''. There are many different types of indescribable cardinals corresponding to different choices of languages ''Q''. They were introduced by {{harvtxt|Hanf|Scott|1961}}.

A cardinal number <math>\kappa</math> is called '''<math>\Pi^n_m</math>-indescribable''' if for every <math>\Pi_m</math> proposition <math>\phi</math>, and set <math>A\subseteq V_\kappa</math> with <math>(V_{\kappa+n},\in,A)\vDash\phi</math> there exists an <math>\alpha<\kappa</math> with <math>(V_{\alpha+n},\in,A\cap V_\alpha)\vDash\phi</math>.<ref name="Drake74">{{cite book|author=Drake, F. R.|title=Set Theory: An Introduction to Large Cardinals (Studies in Logic and the Foundations of Mathematics ; V. 76)|publisher=Elsevier Science Ltd|year=1974|isbn=0-444-10535-2}}</ref> Following [[Levy hierarchy|Lévy's hierarchy]], here one looks at formulas with m-1 alternations of quantifiers with the outermost quantifier being universal. '''<math>\Sigma^n_m</math>-indescribable''' cardinals are defined in a similar way, but with an outermost existential quantifier. Prior to defining the structure <math>(V_{\kappa+n},\in,A)</math>, one new predicate symbol is added to the language of set theory, which is interpreted as <math>A</math>.<ref name="Jech2006">{{cite book
| last1=Jech | first1=Thomas
| title=Set Theory: The Third Millennium Edition, revised and expanded
| series=Springer Monographs in Mathematics
| date=2006
| isbn=3-540-44085-2
| doi=10.1007/3-540-44761-X
| page=295}}</ref> The idea is that <math>\kappa</math> cannot be distinguished (looking from below) from smaller cardinals by any formula of n+1-th order logic with m-1 alternations of quantifiers even with the advantage of an extra unary predicate symbol (for A).  This implies that it is large because it means that there must be many smaller cardinals with similar properties. {{citation needed|date=June 2023}}

The cardinal number <math>\kappa</math> is called '''totally indescribable''' if it is <math>\Pi^n_m</math>-indescribable for all positive integers ''m'' and ''n''.

If <math>\alpha</math> is an ordinal, the cardinal number <math>\kappa</math> is called '''<math>\alpha</math>-indescribable''' if for every formula <math>\phi</math> and every subset <math>U</math> of <math>V_\kappa</math> such that <math>\phi(U)</math> holds in <math>V_{\kappa+\alpha}</math> there is a some <math>\lambda<\kappa</math> such that <math>\phi(U\cap V_\lambda)</math> holds in <math>V_{\lambda+\alpha}</math>. If <math>\alpha</math> is infinite then <math>\alpha</math>-indescribable ordinals are totally indescribable, and if <math>\alpha</math> is finite they are the same as <math>\Pi^\alpha_\omega</math>-indescribable ordinals. There is no <math>\kappa</math> that is <math>\kappa</math>-indescribable, nor does <math>\alpha</math>-indescribability necessarily imply <math>\beta</math>-indescribability for any <math>\beta<\alpha</math>, but there is an alternative notion of [[shrewd cardinal]]s that makes sense when <math>\alpha\geq\kappa</math>: if <math>\phi(U,\kappa)</math> holds in <math>V_{\kappa+\alpha}</math>, then there are <math>\lambda<\kappa</math> and <math>\beta</math> such that <math>\phi(U\cap V_\lambda,\lambda)</math> holds in <math>V_{\lambda+\beta}</math>.<ref>M. Rathjen, "[https://web.archive.org/web/20240114000507/https://www1.maths.leeds.ac.uk/~rathjen/HIGH.pdf The Higher Infinite in Proof Theory]" (1995), p.20. Archived 14 January 2024.</ref> However, it is possible that a cardinal <math>\pi</math> is <math>\kappa</math>-indescribable for <math>\kappa</math> much greater than <math>\pi</math>.<ref name="Drake74" /><sup>Ch. 9, theorem 4.3</sup>

==Historical note==

Originally, a cardinal κ was called Q-indescribable if for every Q-formula <math>\phi</math> and relation <math>A</math>, if <math>(\kappa,<,A)\vDash\phi</math> then there exists an <math>\alpha<\kappa</math> such that <math>(\alpha,\in,A\upharpoonright\alpha)\vDash\phi</math>.<ref>K. Kunen, "Indescribability and the Continuum" (1971). Appearing in ''Axiomatic Set Theory: Proceedings of Symposia in Pure Mathematics, vol. 13 part 1'', pp.199--203</ref><ref name="Levy71">Azriel Lévy, "The Sizes of the Indescribable Cardinals" (1971). Appearing in ''Axiomatic Set Theory: Proceedings of Symposia in Pure Mathematics, vol. 13 part 1'', pp.205--218</ref> Using this definition, <math>\kappa</math> is <math>\Pi^1_0</math>-indescribable iff <math>\kappa</math> is regular and greater than <math>\aleph_0</math>.<ref name="Levy71" /><sup>p.207</sup> The cardinals <math>\kappa</math> satisfying the above version based on the cumulative hierarchy were called strongly Q-indescribable.<ref>{{cite journal
| last1=Richter | first1=Wayne
| last2=Aczel | first2=Peter
| url=https://www.duo.uio.no/handle/10852/44063
| title=Inductive Definitions and Reflecting Properties of Admissible Ordinals
| date=1974
| journal=Studies in Logic and the Foundations of Mathematics
| volume=79
| pages=301–381
| doi=10.1016/S0049-237X(08)70592-5| hdl=10852/44063
| hdl-access=free
}}</ref><!--Not clear what "sentence" means in this source, parameters appear in some proofs (e.g. on p.19)--> This property has also been referred to as "ordinal <math>Q</math>-indescribability".<ref>W. Boos, "[https://link.springer.com/chapter/10.1007/BFb0079417 Lectures on large cardinal axioms]". In ''Logic Conference'', Kiel 1974. Lecture Notes in Mathematics 499 (1975).</ref><sup>p.32</sup>

==Equivalent conditions==

A cardinal is <math>\Sigma^1_{n+1}</math>-indescribable iff it is <math>\Pi^1_n</math>-indescribable.<ref name="Hauser91">{{cite journal
| last1=Hauser | first1=Kai
| title=Indescribable Cardinals and Elementary Embeddings
| jstor=2274692
| journal=Journal of Symbolic Logic
| volume=56
| issue=2
| date=1991
| pages=439–457
| doi=10.2307/2274692}}</ref> A cardinal is [[Inaccessible cardinal|inaccessible]] if and only if it is <math>\Pi^0_n</math>-indescribable for all positive integers <math>n</math>, equivalently iff it is <math>\Pi^0_2</math>-indescribable, equivalently if it is <math>\Sigma^1_1</math>-indescribable.

<math>\Pi^1_1</math>-indescribable cardinals are the same as [[weakly compact cardinal]]s.<ref name="Kanamori03" /><sup>p. 59</sup>

The indescribability condition is equivalent to <math>V_\kappa</math> satisfying the [[reflection principle]] (which is provable in ZFC), but extended by allowing higher-order formulae with a second-order free variable.<ref name="Hauser91"/>

For cardinals <math>\kappa<\theta</math>, say that an elementary embedding <math>j:M\to H(\theta)</math> a ''small embedding'' if <math>M</math> is transitive and <math>j(\textrm{crit}(j))=\kappa</math>. For any natural number <math>1\leq n</math>, <math>\kappa</math> is <math>\Pi^1_n</math>-indescribable iff there is an <math>\alpha>\kappa</math> such that for all <math>\theta>\alpha</math> there is a small embedding <math>j:M\to H_\theta</math> such that <math>H(\textrm{crit}(j)^+)^M\prec_{\Sigma_n}H(\textrm{crit}(j)^+)</math>.<ref>{{cite journal
| last1=Holy | first1=Peter
| last2=Lücke | first2=Philipp
| last3=Njegomir | first3=Ana
| title=Small embedding characterizations for large cardinals
| journal=Annals of Pure and Applied Logic
| volume=170
| issue=2
| date=2019
| pages=251–271
| doi=10.1016/j.apal.2018.10.002 | doi-access=free| arxiv=1708.06103
}}</ref><sup>, Corollary 4.3</sup>

If [[Axiom of constructibility|V=L]], then for a natural number ''n''>0, an uncountable cardinal is Π{{su|p=1|b=''n''}}-indescribable iff it's (n+1)-stationary.<ref>{{cite journal
| last1=Bagaria | first1=Joan
| last2=Magidor | first2=Menachem | authorlink2=Menachem Magidor
| last3=Sakai | first3=Hiroshi
| title=Reflection and indescribability in the constructible universe
| journal=[[Israel Journal of Mathematics]]
| volume=208
| pages=1–11
| date=2015
| doi=10.1007/s11856-015-1191-7}}</ref>

==Enforceable classes==
For a class <math>X</math> of ordinals and a <math>\Gamma</math>-indescribable cardinal <math>\kappa</math>, <math>X</math> is said to be enforced at <math>\alpha</math> (by some formula <math>\phi</math> of <math>\Gamma</math>) if there is a <math>\Gamma</math>-formula <math>\phi</math> and an <math>A\subseteq V_\kappa</math> such that <math>(V_\kappa,\in,A)\vDash\phi</math>, but for no <math>\beta<\alpha</math> with <math>\beta\notin X</math> does <math>(V_\beta,\in,A\cap V_\beta)\vDash\phi</math> hold.<ref name="Drake74" /><sup>p.277</sup> <!--For example, the class of limit ordinals is enforced at any <math>\Pi^0_2</math>-indescribable, by the formula <math>\forall\gamma\exists\delta(\gamma,\delta\in\textrm{Ord}\implies\gamma\in\delta)</math>.-->This gives a tool to show necessary properties of indescribable cardinals.

==Properties==

The property of <math>\kappa</math> being <math>\Pi^1_n</math>-indescribable is <math>\Pi^1_{n+1}</math> over <math>V_\kappa</math>, i.e. there is a <math>\Pi^1_{n+1}</math> sentence that <math>V_\kappa</math> satisfies iff <math>\kappa</math> is <math>\Pi^1_n</math>-indescribable.<ref name="Kanamori03">{{cite book|last=Kanamori|first=Akihiro|author-link=Akihiro Kanamori|year=2003|publisher=Springer|title=The Higher Infinite : Large Cardinals in Set Theory from Their Beginnings|title-link=The Higher Infinite|edition=2nd|isbn=3-540-00384-3|doi=10.1007/978-3-540-88867-3_2|page=64}}</ref>  For <math>m>1</math>, the property of being <math>\Pi^m_n</math>-indescribable is <math>\Sigma^m_n</math> and the property of being <math>\Sigma^m_n</math>-indescribable is <math>\Pi^m_n</math>.<ref name="Kanamori03" /> Thus, for <math>m>1</math>, every cardinal that is either <math>\Pi^m_{n+1}</math>-indescribable or <math>\Sigma^m_{n+1}</math>-indescribable is both <math>\Pi^m_n</math>-indescribable and <math>\Sigma^m_n</math>-indescribable and the set of such cardinals below it is stationary. The consistency strength of <math>\Sigma^m_n</math>-indescribable cardinals is below that of <math>\Pi^m_n</math>-indescribable, but for <math>m>1</math> it is consistent with ZFC that the least <math>\Sigma^m_n</math>-indescribable exists and is above the least <math>\Pi^m_n</math>-indescribable cardinal (this is proved from consistency of ZFC with <math>\Pi^m_n</math>-indescribable cardinal and a <math>\Sigma^m_n</math>-indescribable cardinal above it).{{cn|date=June 2024}}

Totally indescribable cardinals remain totally indescribable in the [[constructible universe]] and in other canonical inner models, and similarly for <math>\Pi^m_n</math>- and <math>\Sigma^m_n</math>-indescribability.

For natural number <math>n</math>, if a cardinal <math>\kappa</math> is <math>n</math>-indescribable, there is an ordinal <math>\alpha<\kappa</math> such that <math>(V_{\alpha+n},\in)\equiv(V_{\kappa+n},\in)</math>, where <math>\equiv</math> denotes [[elementary equivalence]].<ref>W. N. Reinhardt, "[https://www.sciencedirect.com/science/article/pii/0003484370900112 Ackermann's set theory equals ZF]", pp.234--235. Annals of Mathematical Logic vol. 2, iss. 2 (1970).</ref> For <math>n=0</math> this is a biconditional (see [[Inaccessible_cardinal#Two_model-theoretic_characterisations_of_inaccessibility|Two model-theoretic characterisations of inaccessibility]]).

Measurable cardinals are <math>\Pi^2_1</math>-indescribable, but the smallest measurable cardinal is not <math>\Sigma^2_1</math>-indescribable.<ref name="Kanamori03" /><sup>p. 61</sup> However, assuming [[Axiom of choice|choice]], there are many totally indescribable cardinals below any measurable cardinal.

For <math>n\geq 1</math>, ZFC+"there is a <math>\Sigma^1_n</math>-indescribable cardinal" is equiconsistent with ZFC+"there is a <math>\Sigma^1_n</math>-indescribable cardinal <math>\kappa</math> such that <math>2^\kappa>\kappa^+</math>", i.e. "GCH fails at a <math>\Sigma^1_n</math>-indescribable cardinal".<ref name="Hauser91"/>

== References ==

*{{Citation | last1=Hanf | first1=W. P. | last2=Scott | first2=D. S. | author2-link=Dana Scott | title=Classifying inaccessible cardinals | year=1961 | journal=[[Notices of the American Mathematical Society]] | issn=0002-9920 | volume=8 | pages=445}}
* {{cite book|last=Kanamori|first=Akihiro|author-link=Akihiro Kanamori|year=2003|publisher=Springer|title=The Higher Infinite : Large Cardinals in Set Theory from Their Beginnings|title-link=The Higher Infinite|edition=2nd|isbn=3-540-00384-3|doi=10.1007/978-3-540-88867-3_2}}

=== Citations ===
{{Reflist}}

[[Category:Large cardinals]]