I'm not sure if I should ask here or over at math.stackexchange.com, but I think here it's a bit more fitting. This question stems from a homework problem:


Given some class of formulas $Q$ we call a cardinal $\kappa$ $Q$-weakly indescribable if for every $Q$-sentence $\phi$ and $R\subset\kappa$, $\langle\kappa,\in,R\rangle\models\phi$ implies that there is some $\alpha<\kappa$ such that $\langle\alpha,\in,R\cap\alpha\rangle\models\phi$.


The exercise asks to show that $\kappa$ is $\Pi_0^1$-weakly indescribable exactly when it is regular. One part (namely that a regular cardinal is $\Pi_0^1$-weakly indescribable) is easy, but I am unsure about the other direction. If we had $R\subset\kappa\times\kappa$ then it would be fairly easy to "code" the singularity of $\kappa$ into $R$, but I don't see how to do this when $R$ is a subset of $\kappa$. Of course, we have that $\kappa$ can be mapped injectively onto $\kappa\times\kappa$ but -at least to the best of my knowledge- that would require some form of inductive definition, which on principle uses functions, objects that do not exist when our universe is $\langle\kappa,\in,R\rangle$.

After giving it a lot of thought, I actually checked a paper by Levy ("The size of the indescribable cardinals") in which he uses binary predicates, and I also tried to find an old paper by Hanf and Scott ("Classifying inaccessible cardinals") but it turns out that the library threw away most of the Notices of AMS volumes when they moved to a smaller building.

So my question is:

Can we somehow define the bijection inside $\langle\kappa,\in,R\rangle$, or on? And if not is there some other way to prove this?


Disclosure: Even though this is formally homework, we are allowed to use that $R\subseteq\kappa\times\kappa$. Hence this is more of a personal question that arose from the fact that I got stuck on this for a long time.

  • $\begingroup$ Yes, check out pg. 30 in Jech, "Set Theory." There's a section on "The Canonical Well-Ordering of $\alpha \times \alpha$." $\endgroup$ Oct 10 '11 at 3:09
  • $\begingroup$ @Amit: Jech defines the well ordering of $(\kappa,\kappa)$ as "the order type of $\{(\alpha,\beta):(\alpha,\beta)<(\kappa,\kappa)\}$". My problem is how to define this when our universe is κ. Jech says that two well orders have the same order type when they are isomorphic. How could you say this when you don't have functions? I'm beginning to feel that I'm missing something obvious here. :( $\endgroup$
    – Apostolos
    Oct 10 '11 at 5:43
  • 3
    $\begingroup$ Hmm, let me think about this. When I've seen "indescribability," I usually see the universe $V_\kappa$ being used, not $\kappa$. $\endgroup$ Oct 10 '11 at 8:01

First off, note that being weakly $\Pi^1_0$-indescribable is actually the same as being weakly $\Sigma_1^1$-indescribable. Let $\phi(x_0...x_n,S)$ be some formula, say $\exists X(\psi(X,x_0...x_n,S))$, where $\psi(X,x_0...x_n,S)$ is $\Pi^1_0$. Then let $C$ be witness to this, and let $$(\alpha,\beta)=\operatorname{ot}\big\{(\gamma,\zeta)\lt(\alpha,\beta)|\gamma,\zeta\lt\kappa\big\}.$$ Then, $C\times S\subseteq\kappa$, and so, if $$(\kappa,\in,C\times S)\vDash\psi\big(\operatorname{dom}(C\times S),x_0...x_n,\operatorname{ran}(C\times S)\big),$$ then there is some $\alpha\lt\kappa$ such that $$(\alpha,\in, C\times S\cap\alpha)\vDash\psi\big(\operatorname{dom}(C\times S\cap\alpha),x_0...x_n,\operatorname{ran}(C\times S\cap \alpha)\big),$$ and therefore $(\alpha,\in,S\cap\alpha)\vDash\phi(X,x_0...x_n,S)$. You can formalize $\alpha\in \operatorname{dom}(C\times S)$ by $$\exists\beta,X\;\Big(\forall\gamma,\zeta\big(\exists Y(Y=X\leftrightarrow\gamma=\alpha\land\zeta=\beta)\big)\land X\in C\times S\Big).$$

Now, assume to the contrary that $\kappa$ is irregular. Let $C$ be cofinal in $\kappa$, with $|C|\lt\kappa$. Let $\lambda=|C|$. Then $$(\kappa,\in,\lambda,C)\vDash C\text{ is cofinal in }\mathit{Ord}\land\exists x(x=\lambda\land x=|C|).$$ Then, if $$(\alpha,\in,\lambda\cap\alpha,C\cap\alpha)\vDash C\cap\alpha\text{ is cofinal in }\mathit{Ord}\land\exists x(x=\lambda\land x=|C\cap\alpha|),$$ $\alpha\gt\lambda$, and $|C\cap\alpha|\lt\lambda$. But $|C\cap\alpha|=\lambda$. Contradiction.

For completeness, I will mention the secondary case. Let $\kappa$ be regular uncountable. Let $M_0$ be the Skolem hull of $\emptyset$ in $\kappa$. Then $|M_0|=\omega$ is less than $(\kappa,\in,S)$, so that $\alpha_0=\text{sup}M_0$ is less than $\kappa$. Then let $M_{n+1}$ be the Skolem hull of $\alpha_n$ in $(\kappa,\in,S)$, and $\text{sup}M_n=\alpha_{n+1}$. Then let $\alpha=\lim_{n\rightarrow\omega}\alpha_n$.

Edit: It seems that the question is actually asking about how to define the pairing function $(\alpha,\beta)$ in $\kappa$. I am not exactly sure how you could define this.

  • 2
    $\begingroup$ You use a pairing function, starting in the third sentence of the answer. If I understand the question correctly, it's exactly about how to define a pairing function with the limited available material, and this answer doesn't seem to address that issue. $\endgroup$ Sep 8 '19 at 12:01
  • $\begingroup$ Could you explain you confusion a bit better? I defined the pairing function, and I defined $dom(C\times S)$, and $ran(C\times S)$. I believe I have defined all the necessary terms. $\endgroup$
    – Master
    Sep 8 '19 at 14:45
  • $\begingroup$ I noticed a typo one on of the lines. Is it clearer now? $\endgroup$
    – Master
    Sep 8 '19 at 14:48
  • $\begingroup$ Wait. I think I figured out the question. I will edit this in a minute. $\endgroup$
    – Master
    Sep 8 '19 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.