Difference between revisions of "Indescribable"

From Cantor's Attic
Jump to: navigation, search
(Facts: analogy)
(Matching variable name Removing the predicate)
 
(7 intermediate revisions by 2 users not shown)
Line 54: Line 54:
 
We say that $L_\alpha$ reflects $\varphi$ on $X$ iff $L_\alpha \models \varphi \implies \exists_{\beta \in X \cap \alpha} L_\beta \models \phi$. (definition 1.6)
 
We say that $L_\alpha$ reflects $\varphi$ on $X$ iff $L_\alpha \models \varphi \implies \exists_{\beta \in X \cap \alpha} L_\beta \models \phi$. (definition 1.6)
  
We call $\alpha$ $Q$-[[reflecting ordinal|reflecting]] on $X$ iff $\alpha$ reflects on $X$ every $Q$-sentence of $\mathcal{L}_\in$. &#40;definition 1.7)<!--This is probably not a good place for it, but I cannot organise it better by now.--> With full $\mathcal{L}$ this would yield &#40;weak) $Q$-indescribability on $X$. (above definition 1.7)
+
We call $\alpha$ $Q$-[[reflecting ordinal|reflecting]] on $X$ iff $\alpha$ reflects on $X$ every $Q$-sentence of $\mathcal{L}_\in$. &#40;definition 1.7)<!--This is probably not a good place for it, but I cannot organise it better by now.--> With full $\mathcal{L}$ this would yield weak $Q$-indescribability on $X$. (above definition 1.7)
  
 
Reflection/indescribability on $\mathrm{Ord}$ is simply called reflection/indescribability.
 
Reflection/indescribability on $\mathrm{Ord}$ is simply called reflection/indescribability.
 +
 +
===Removing the predicate===
 +
If we remove the predicate $S\subseteq V_\kappa$ from the definition of $\Pi_m^n$-indescribability, we get a much weaker notion. The resulting large cardinals need not be inaccessible, and in fact ZF proves existence of these cardinals. (This was left as an exercise on p.276 of F. R. Drake's <i>Set Theory: An Introduction to Large Cardinals</i>, with a detailed hint for how to show this.)
  
 
==Facts==
 
==Facts==

Latest revision as of 17:36, 4 July 2022

The Structure of Indescribability in Consistency Strength

A cardinal $\kappa$ is indescribable if it holds the reflection theorem up to a certain point. This is important to mathematics because of the concern for the reflection theorem. In more detail, a cardinal $\kappa$ is $\Pi_{m}^n$-indescribable if and only if for every $\Pi_{m}$ first-order sentence $\phi$:

$$\forall S\subseteq V_{\kappa}(\langle V_{\kappa+n};\in,S\rangle\models\phi\rightarrow\exists\alpha<\kappa(\langle V_{\alpha+n};\in,S\cap V_{\alpha}\rangle\models\phi))$$

Likewise for $\Sigma_{m}^n$-indescribable cardinals.

Here are some other equivalent definitions:

  • A cardinal $\kappa$ is $\Pi_m^n$-indescribable for $n>0$ iff for every $\Pi_m$ first-order unary formula $\phi$:

$$\forall S\subseteq V_\kappa(V_{\kappa+n}\models\phi(S)\rightarrow\exists\alpha<\kappa(V_{\alpha+n}\models\phi(S\cap V_\alpha)))$$

  • A cardinal $\kappa$ is $\Pi_m^n$-indescribable iff for every $\Pi_m$ $n+1$-th-order sentence $\phi$:

$$\forall S\subseteq V_\kappa(\langle V_\kappa;\in,S\rangle\models\phi\rightarrow\exists\alpha<\kappa(\langle V_\alpha;\in,S\cap V_\alpha\rangle\models\phi))$$

In other words, if a cardinal is $\Pi_{m}^n$-indescribable, then every $n+1$-th order logic statement that is $\Pi_m$ expresses the reflection of $V_{\kappa}$ onto $V_{\alpha}$. This exercises the fact that these cardinals are so large they almost resemble the order of $V$ itself. This definition is similar to that of shrewd cardinals, an extension of indescribable cardinals.

Variants

Language

$Q$-indescribable cardinals are those which have the property that for every $Q$-sentence $\phi$:

$$\forall S\subseteq V_\kappa(\langle V_\kappa;\in,S\rangle\models\phi\rightarrow\exists\alpha<\kappa(\langle V_\alpha;\in,S\cap V_\alpha\rangle\models\phi))$$ By extending languages of set theory, we can obtain many various sets $Q$, defining many different varieties of indescribability.

One example is Bagaria's extension of the Levy hierarchy using infinitary logic. This allows us to speak about $\Pi^1_\xi$-formulae for ordinal $\xi$, so using it we can speak about $\Pi^1_\xi$-indescribability. [1]

Higher-order

Totally indescribable cardinals are $\Pi_m^n$-indescribable for every natural $m$ and $n$ (equivalently $\Sigma_m^n$-indescribable for every natural m and n, equivalently $\Delta_m^n$-indescribable for every natural $m$ and $n$). This means that every (finitary) formula made from quantifiers, $\in$ and a subset of $V_{\kappa}$ reflects from $V_{\kappa}$ onto a smaller rank.

$\beta$-indescribable cardinals are those which have the property that for every first order sentence $\phi$:

$$\forall S\subseteq V_\kappa(\langle V_{\kappa+\beta};\in,S\rangle\models\phi\rightarrow\exists\alpha<\kappa(\langle V_{\alpha+\beta};\in,S\cap V_\alpha\rangle\models\phi))$$

There is no $\kappa$ which is $\kappa$-indescribable. A cardinal is $\Pi_{<\omega}^m$-indescribable iff it is $m$-indescribable for finite $m$. Every $\omega$-indescribable cardinal is totally indescribable.

Indescribable on a set

(from [1])

Language $\mathcal{L}$ has variables and quantifiers for all finite types (where variables of type 0 range over individuals, of type 1 – over sets of individuals etc.), a name (individual constant) for each set and a name (relation symbol) for each relation on sets. (§1) TODO: complete the definition $\mathcal{L}_\in$ is the sublanguage of $\mathcal{L}$ allowing only $\in$ as a relation symbol. (above definition 1.7)

We say that $\alpha\in\mathrm{Ord}$ reflects a sentence $\varphi$ of $\mathcal{L}$ on $X\subseteq\mathrm{Ord}$ iff $\alpha \models \varphi \implies \exists_{\beta \in X \cap \alpha} \beta \models \phi$. (definition 1.1)

We call $\alpha$ weakly $Q$-indescribable on $X$ iff $\alpha$ reflects on $X$ every $Q$-sentence of $\mathcal{L}$. (definition 1.1)

$R(\alpha)=\bigcup_{\beta<\alpha} \mathcal{P}(R(\beta))$ for an ordinal $\alpha$. We say that $R(\alpha)$ reflects $\varphi$ on $X$ iff $R(\alpha) \models \varphi \implies \exists_{\beta \in X \cap \alpha} R(\beta) \models \phi$. (definition 1.5)

We call $\alpha$ strongly $Q$-indescribable on $X$ iff $R(\alpha)$ reflects on $X$ every $Q$-sentence of $\mathcal{L}$. (definition 1.5)

We say that $L_\alpha$ reflects $\varphi$ on $X$ iff $L_\alpha \models \varphi \implies \exists_{\beta \in X \cap \alpha} L_\beta \models \phi$. (definition 1.6)

We call $\alpha$ $Q$-reflecting on $X$ iff $\alpha$ reflects on $X$ every $Q$-sentence of $\mathcal{L}_\in$. (definition 1.7) With full $\mathcal{L}$ this would yield weak $Q$-indescribability on $X$. (above definition 1.7)

Reflection/indescribability on $\mathrm{Ord}$ is simply called reflection/indescribability.

Removing the predicate

If we remove the predicate $S\subseteq V_\kappa$ from the definition of $\Pi_m^n$-indescribability, we get a much weaker notion. The resulting large cardinals need not be inaccessible, and in fact ZF proves existence of these cardinals. (This was left as an exercise on p.276 of F. R. Drake's Set Theory: An Introduction to Large Cardinals, with a detailed hint for how to show this.)

Facts

Here are some known facts about indescribability:

Weak $\Pi_2^0$-indescribability is equivalent to being uncountable and regular. (theorem 1.2)[1] Strong(definition 1.5)[1] $\Pi_2^0$-indescribability is equivalent to strong inaccessibility, $\Sigma_1^1$-indescribablity, $\Pi_n^0$-indescribability given any $n>1$, and $\Pi_0^1$-indescribability.[2] $\Pi_1^1$-indescribability is equivalent to weak compactness. [3],[2]

The property of being a limit ($\alpha = \sup (X \cap \alpha)$) is equivalent to weak $\Pi_0^0$-indescribablity on $X$ and to weak $\Sigma_2^0$-indescribablity on $X$. Mahloness on $X$ is equivalent to weak $\Pi_2^0$-indescribablity on $X$ and to weak $\Pi_0^1$-indescribablity on $X$. Weak $\Pi_n^1$-indescribablity on $X$ is equivalent to weak $\Sigma_{n+1}^1$-indescribablity on $X$. (theorem 1.3 i-iii)[1]

If $m>2$ or $n>0$, weak $\Pi_m^n$-indescribablity on $X$ is equivalent to $\Pi_m^n$-indescribablity on $X\cap\mathrm{Rg}$. If $m>3$ or $n>0$, weak $\Sigma_m^n$-indescribablity on $X$ is equivalent to $\Sigma_m^n$-indescribablity on $X\cap\mathrm{Rg}$. ($\mathrm{Rg}$ is the class of regular cardinals.) (theorem 1.3 iv)[1]

When $Q$ is $\Pi_m^n$ or $\Sigma_m^n$ for $n>0$, an ordinal is strongly $Q$-indescribable iff it is weakly $Q$-indescribable and strongly inaccessible (therefore strong and weak $Q$-inaccessibility coincide assuming GCH.). (after definition 1.5)[1]

$\Pi_n^m$-indescribablity is equivalent to $m$-$\Pi_n$-shrewdness (similarly with $\Sigma_n^m$). [4]

Ineffable cardinals are $\Pi^1_2$-indescribable and limits of totally indescribable cardinals. [5]

$\Pi_n^1$-indescribability is equivalent to $\Sigma_{n+1}^1$-Indescribability. [2]

If $m>1$, $\Pi_{n+1}^m$-indescribability is stronger (consistency-wise) than $\Sigma_n^m$ and $\Pi_n^m$-indescribability; every $\Pi_{n+1}^m$-indescribable cardinal is also both $\Sigma_n^m$ and $\Pi_n^m$-indescribable and a stationary limit of such for $m>1$.[2] If $m>1$, the least $\Pi_n^m$-indescribable cardinal is less than the least $\Sigma_n^m$-indescribable cardinal, which is in turn less than the least $\Pi_{n+1}^m$-indescribable cardinal.[2]

If $\kappa$ is $Π_n$-Ramsey, then $\kappa$ is $Π_{n+1}^1$-indescribable. If $X\subseteq\kappa$ is a $Π_n$-Ramsey subset, then $X$ is in the $Π_{n+1}^1$-indescribable filter.[6] If $\kappa$ is completely Ramsey, then $κ$ is $Π_1^2$-indescribable.[7]

Every $n$-Ramsey $κ$ is $Π^1_{2 n+1}$-indescribable. This is optimal, as $n$-Ramseyness can be described by a $Π^1_{2n+2}$-formula.[8] Every $<ω$-Ramsey cardinal is $∆^2_0$-indescribable.[8] Every normal $n$-Ramsey $κ$ is $Π^1_{2 n+2}$-indescribable. This is optimal, as normal $n$-Ramseyness can be described by a $Π^1_{2 n+3}$-formula.[8]

Every measurable cardinal is $\Pi_1^2$-indescribable. Although, the least measurable is $\Sigma_1^2$-describable. [3]

Every critical point of a nontrivial elementary embedding $j:M\rightarrow M$ for some transitive inner model $M$ of ZFC is totally indescribable in $M$. (For example, rank-into-rank cardinals, $0^{\#}$ cardinals, and $0^{\dagger}$ cardinals). [3]

If $2^\kappa\neq\kappa^+$ for some $\Pi_1^2$-indescribable cardinal, then there is a smaller $\lambda$ such that $2^\lambda\neq\lambda^+$. However, assuming the consistency of the existence of a $\Pi_n^1$-indescribable cardinal $\kappa$, it is consistent for $\kappa$ to be the least cardinal such that $2^\kappa\neq\kappa^+$. [9]

Transfinite $Π^1_α$-indescribable has been defined via finite games and it turns out that for infinite $α$, if $κ$ is $Π_α$-Ramsey, then $κ$ is $Π^1_{2 ·(1+β)+ 1}$-indescribable for each $β < \min \{α, κ^+\}$.[10]

$\mathrm{ZFC} + \mathrm{BTEE}$ (Basic Theory of Elementary Embeddings) proves that the critical point of $j$ is totally indescribable.[11]

$Π_{n+2}$-reflection is analogous to strong $Π_n^1$-indescribability for all $n>0$. In particular, $Π_3$-reflecting or 2-admissible ordinals can be called recursively weakly compact. (after definition 1.12)[1][12]

References

  1. 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
  2. Kanamori, Akihiro. The higher infinite. Second, Springer-Verlag, Berlin, 2009. (Large cardinals in set theory from their beginnings, Paperback reprint of the 2003 edition) www   bibtex
  3. Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www   bibtex
  4. Rathjen, Michael. The art of ordinal analysis. , 2006. www   bibtex
  5. Jensen, Ronald and Kunen, Kenneth. Some combinatorial properties of $L$ and $V$. Unpublished, 1969. www   bibtex
  6. Feng, Qi. A hierarchy of Ramsey cardinals. Annals of Pure and Applied Logic 49(3):257 - 277, 1990. DOI   bibtex
  7. Holy, Peter and Schlicht, Philipp. A hierarchy of Ramsey-like cardinals. Fundamenta Mathematicae 242:49-74, 2018. www   arχiv   DOI   bibtex
  8. Nielsen, Dan Saattrup and Welch, Philip. Games and Ramsey-like cardinals. , 2018. arχiv   bibtex
  9. Hauser, Kai. Indescribable Cardinals and Elementary Embeddings. 56(2):439 - 457, 1991. www   DOI   bibtex
  10. Sharpe, Ian and Welch, Philip. Greatly Erdős cardinals with some generalizations to the Chang and Ramsey properties. Ann Pure Appl Logic 162(11):863--902, 2011. www   DOI   MR   bibtex
  11. Corazza, Paul. The spectrum of elementary embeddings $j : V \to V$. Annals of Pure and Applied Logic 139(1--3):327-399, May, 2006. DOI   bibtex
  12. Madore, David. A zoo of ordinals. , 2017. www   bibtex
Main library