Let $\mathscr{L}=\{\leq\}$ be a one symbol first order language.
I am asked to:
- Give a formula $\phi(x)$ such that $\forall\alpha\neq0$ and $\forall\lambda<\alpha$ $$\langle\alpha,\in\rangle\models\phi[\lambda]\leftrightarrow\lambda\ limit$$
- 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.