Elementary $2$-equivalence $X=(A, <^X)$ with $N=(\mathbb{N}, <)$. Conclusions.

Question

Let structure $X=(A,<^X)$ be linear order on $A$ such that it is elementary $2$-equiavalent to $N=(\mathbb{N}, <)$. Can we conlude that: (a) $A$ is infinity. (b) $A$ has an the smallest element
(c) Each element of $A$ has only finitely many elements lower from self.

I try to solve this, I ask you for checking my reasoning.
First of all, what does it mean that $A\equiv_2B$ ? We know that $A$ and $B$ can't be distinguished each other using at most $2$ (it is about depth) quantifiers.

(a) $A$ is infinite. Yes, because we know that for $N$: $\forall_{n\in\mathbb{N}} \exists_{m\in \mathbb{N}}m>n$. We used only two quantifiers, hence $X$ is also infinite.
(b) The same as (a) because $\exists_{m\in \mathbb{N}}\forall_{n\in\mathbb{N}\setminus \{m\}} m<n$
(c) I think that answer is negative. It is sufficient to show that for $N$ number two is not sufficient to express property (c).

To my eye, we may show that $(\mathbb{R}, <)$ is not distinguishable from $(\mathbb{N}, <)$ - it is easy to show strategy for duplication - only two stages. Now, because $(\mathbb{R}, <)$ don't satisfy property (c) and is not distinguishable from $(\mathbb{N}, <)$. Consequently, $N$ can't be concluded in our task.

Can you check my solution ?

Answer 1

There is a (fairly) elementary solution to (c): consider $A={\bf N}\sqcup {\bf Z}$ (where ${\bf Z}$ is put after ${\bf N}$). It is easy to check that $A$ is elementarily equivalent to ${\bf N}$ using Ehrenfeucht-Fraïssé games, and it clearly has elements with infinitely many elements below.

Answer 2

Note: the following answer is flawed, specifically the "basic result" is false. I still leave it because there are relevant comments below.

There is a notion that is relevant here, but I cannot remember its name. I think it is $\infty$-something, at least in french. It might be a little overkill, but not too much I beleive.

Anyway, let's say that two structures $\mathcal{M},\mathcal{S}$ with base sets $M,S$ are $\infty$-equivalent if there is a set $\mathcal{F}$ of partial isomorphisms $\mathcal{M} \rightarrow \mathcal{S}$ (that is maps from a substructure of $\mathcal{M}$ onto a substructure of $\mathcal{N}$ that are monomorphisms) such that $\forall \sigma \in \mathcal{F}, \forall s \in S, \exists m \in M, \exists \sigma' \in \mathcal{F}, \sigma \cup \{(m,s)\}\subset \sigma'$. So any element of $\mathcal{F}$ be extended in $\mathcal{F}$ by any value in $S$.

The basic result here is:

-Any two $\infty$-equivalent structures are elementary equivalent (thus, elementary $2$-equivalent). this is actually false

This is proved by induction on the complexity of formulas, using the fact that the variables in formulas belong to a finite set and that finite substructures in one structure have isomorphic counterparts in the other because of the existence of $\mathcal{F}$. I leave it to you to prove them, but I can edit with details if needed.

Now, regarding your problem, define $\mathcal{M} : = (\mathbb{N} \times \{0;1\},\prec)$, $\prec$ is $ \{((m,t),(n,t)) \ | \ m <n \in \mathbb{N}\} \cup \{((m,0),(n,1)) \ | \ m,n \in \mathbb{N}\}$. $\mathcal{M}$ is the sum of $\mathcal{N}$ with itself (this is a standard order-theory construction), and it is well-ordered.

Moreover, $\mathcal{M}$ is $\infty$-equivalent to $\mathcal{N}$.

Indeed, the set $\mathcal{F}$ consisting of all isomorphisms between finite substructures of $\mathbb{N} \times \{0;1\}$ and finite substructures of $\mathcal{N}$ of same cardinal satisfies the property. Hence $\mathcal{M}$ is elementary $2$-equivalent to $\mathcal{N}$ despite the fact that in it $(0,1)$ has infinitely many elements below itself.

---

If you're into model theory, you will often come across this fact that non-uniform finiteness cannot be captured by elementary equivalency (let alone weaker forms of equivalency). This is strongly linked to a fundamental result in model theory called the compactness theorem, which I suggest you look into.