# An excercise about the definability of limit ordinal and equality in structures $\langle\alpha\in Ord,\in\rangle$

Let $$\mathscr{L}=\{\leq\}$$ be a one symbol first order language.

1. Give a formula $$\phi(x)$$ such that $$\forall\alpha\neq0$$ and $$\forall\lambda<\alpha$$ $$\langle\alpha,\in\rangle\models\phi[\lambda]\leftrightarrow\lambda\ limit$$
2. Fix an $$0<\alpha<\omega^2$$. Find a closed formula $$\sigma_\alpha$$ such that $$\langle\beta,\in\rangle\models\sigma_\alpha\leftrightarrow\beta=\alpha$$

For the first point I tried to implement the fact that if $$\lambda$$ is limit it cannot be a successor of any ordinal, and hence of any ordinal in $$\alpha$$. Then I came up with: $$\phi(x): \forall\gamma\exists\delta(\delta\leq\lambda\land\lnot(\delta=\gamma\lor \delta\leq\gamma))$$ Is this correct or close to be?

For the second point I am completely lost. Trying to reason in the case $$\alpha<\omega$$ I think we could formalize the fact that $$\alpha\in\omega$$ and $$\beta\in\omega$$ has exactly $$\alpha$$ elements, and hence are the same ordinal, with a first order closed formula. The fact is that our languag e does not contain a constant intepreted in $$0$$ and hence I cannot write one.

If the approach correct how to do it? Moreover what about the transfinite case? I do not think a similar reasoning is viable there. Any hint or help would be most pelased

Take care: if your language is $$\{\leq\}$$ and your model is $$\langle \alpha, \in \rangle$$, then you must interpret $$x \leq y$$ by membership, as $$x \in y$$, and not as $$x \in y \vee x = y$$.

You give the following candidate solution $$\phi(\lambda)$$ for the first problem: $$\forall\gamma\exists\delta(\delta\leq\lambda\land\lnot(\delta=\gamma\lor \delta\leq\gamma))$$

Your candidate formula holds in the structure $$\langle \alpha, \in \rangle$$, precisely if $$\lambda$$ satisfies $$\forall \gamma \in \alpha. \exists \delta \in \alpha. (\delta \in \lambda \wedge \delta \neq \gamma \wedge \delta\ \not\in \gamma)$$

This formula does not characterize limit ordinals. If $$\lambda$$ satisfies this statement, then you can take $$\gamma = \lambda$$ and conclude the existence of $$\delta \in \alpha$$ that satisfies both $$\delta \in \lambda$$ and $$\delta \not\in \lambda$$, a contradiction. Thus, no $$\lambda$$ satisfies $$\varphi$$.

To obtain a correct solution for Problem 1, you could start by constructing a formula $$\psi(L,P)$$ formalizing "$$L$$ is the successor of $$P$$". The following choice of $$\psi$$ works (as you should very carefully check!)

$$P \leq L \wedge \neg \exists Q. (P \leq Q \wedge Q \leq L)$$

The zero ordinal has no elements, so we can characterize it as the unique $$x$$ that satisfies the formula $$\forall P. \neg (P \leq x)$$. The limit ordinals are precisely the ones that are neither the zero ordinal nor a successor ordinal, so we can define $$\phi(\lambda)$$ as

$$(\exists Q. Q \leq \lambda) \wedge \neg(\exists P. \psi(\lambda,P))$$

For the second problem, notice that any ordinal less than $$\omega^2$$ has the form $$\omega \cdot n + k$$ for some natural numbers $$n,k$$. A case analysis on $$n,k$$ allows you to tackle both the finite and the transfinite cases. For example, you could try formalizing the following:

If $$n=0$$, the sentence stating we have exactly $$k$$ elements works. Hint: one can write "we have exactly 2 elements" as $$\exists e_1. \exists e_2. \neg(e1 = e2) \wedge (\forall x. x = e_1 \vee x = e_2)$$

For $$n > 0$$ and $$k=0$$, we have exactly $$n-1$$ limit ordinals $$\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_{n-1}$$, and any ordinal larger than $$\lambda_{n-1}$$ has a successor. (You tell me: what about $$n=1$$?)

For $$n > 0$$ and $$k > 0$$, we have exactly $$n$$ limit ordinals $$\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_{n}$$, and $$\lambda_n$$ has exactly $$k-1$$ successors.