equivalency of distinct ordinals

48 Views Asked by At

I've come across this statement:

it is readily checked that distinct ordinals $\alpha\neq\beta$ are not $L_{∞,ω}$-equivalent

Why ?

Does it even hold that as I'd guess they are not $L_{\kappa,\omega}$ equivalent for $\kappa=\text{card } \max \{ \alpha,\beta \} $ ?

1

There are 1 best solutions below

0
On BEST ANSWER

Let's prove, by transfinite induction, that for every ordinal $\alpha$, there exists a formula $\varphi_\alpha(x)$ of $L_{|\alpha|^+,\omega}$, such that if $\gamma$ is an ordinal and $\delta\in \gamma$, we have $\gamma\models \varphi_\alpha(\delta)$ if and only if $\delta = \alpha$.

Set $\varphi_\alpha(x)$ to be: $$\left(\bigwedge_{\beta<\alpha} \exists y\, (y < x\land \varphi_\beta(y))\right)\land \forall y\, \left(y < x \rightarrow \bigvee_{\beta<\alpha}\varphi_\beta(y)\right)$$ When $\gamma$ is an ordinal, $\delta\in \gamma$, and $\gamma\models \varphi_\alpha(\delta)$, we see that the elements of $\gamma$ less than $\delta$ are exactly the ordinals less than $\alpha$ (using the inductive hypothesis that $\beta$ is the unique element of $\gamma$ satisfying $\varphi_\beta(y)$), and hence $\delta = \alpha$. This completes the proof.

In case you are worried about vacuity in the base case: Note that when $\alpha = 0$, the formula $\varphi_0(x)$ is $\top \land \forall y\, (y<x\rightarrow \bot)$, since the empty conjunction is the true formula $\top$ and the empty disjunction is the false formula $\bot$. This is equivalent to $\forall y\, \lnot (y < x)$, which is true if and only if $x$ is the minimal element $0$ of $\gamma$.

Now consider the following sentence $\psi_\alpha$ of $L_{|\alpha|^+,\omega}$: $$\left(\bigwedge_{\beta<\alpha} \exists x\, \varphi_\beta(x)\right)\land \left(\forall x\, \bigvee_{\beta<\alpha}\varphi_\beta(x)\right)$$ If $\gamma$ is an ordinal and $\gamma\models \psi_\alpha$, then the elements of $\gamma$ are exactly the ordinals less than $\alpha$, so $\gamma = \alpha$.

Thus if $\alpha\neq \beta$ are distinct ordinals, we have $\alpha\models \psi_\alpha$ while $\beta\not\models \psi_\alpha$, and also $\alpha\not\models \psi_\beta$ while $\beta\models \psi_\beta$.

This shows that we can distinguish $\alpha$ and $\beta$ using $\psi_{\min(\alpha,\beta)}$. This is a sentence of $L_{\kappa,\omega}$, where $\kappa = \min(|\alpha|^+,|\beta|^+)$.

We can't do better than this in general, since there are distinct countable ordinals which are not elementarily ($L_{\omega,\omega}$) equivalent. To distinguish distinct countable ordinals, we need to use $L_{\omega_1,\omega}$.