1
$\begingroup$

Let $\mathscr{L}=\{\leq\}$ be a one symbol first order language.
I am asked to:

  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

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.