Is there an embedding of $\langle \mathbb{N} \setminus \{0\}, \leq, \times, 1 \rangle$ into $\langle \mathbb{N}, \leq, +, 0 \rangle$?

Question

This appears to be a common beginning exercise in model theory (I found it both in Chang & Keisler and also in Manzano's Model Theory). It's not difficult to see that there is an embedding of $\langle \mathbb{N}, \leq, +, 0 \rangle$ into $\langle \mathbb{N}, \leq, \times, 1 \rangle$; just take the function $h(x) = 2^x$ (or something similar). On the other hand, it's also not very difficult (I think!) to see that the converse does not hold, for, if there were such an embedding $h$, then both $h(1) = 0$ and $h(0) = 0$, meaning that $h$ is not injective (and thus is not actually an embedding). But what about an embedding of $\langle \mathbb{N} \setminus \{0\}, \leq, \times, 1 \rangle$ into $\langle \mathbb{N}, \leq, +, 0 \rangle$?

It seems to me that there is no such embedding as well, but I can't work out an argument showing this impossibility. Clearly the above argument won't work, because it depended on $h(0)$. I thought of trying to show that there is an existential formula that's verified by the latter but not by the former, or conversely a universal formula verified by the former but not by the latter, but couldn't think of anything. I suppose there are other ways of showing this?

Any hints?

Answer 1

You are right. There is no such embedding and the argument to show this is quite simple. For, say there is such an embedding $\varepsilon : \langle \mathbb{N} \setminus \{0\}, \leq, \times, 1 \rangle \to \langle \mathbb{N}, \leq, +, 0 \rangle$. As a contradiction, I show that for each natural number $N \ge 1$, $\varepsilon(N+1)$ cannot itself be a natural number.

Denote $s \times t$ as simply $st$ and fix any natural number $x \ge 2$. Now, $Nx+x-1 < (N+1)x$. Also, $\varepsilon$ is injective and order/function-preserving. So, $\varepsilon(Nx+x-1) < \varepsilon((N+1)x) = \varepsilon(N+1) + \varepsilon(x)$. Thus, we have $\varepsilon(Nx+x-1) - \varepsilon(x) < \varepsilon(N+1)$.

Next, between $x$ ... $Nx+x-1$, there are(is) obviously $Nx-1$ distinct natural number(s) including $x$. But then, as $\varepsilon$ is injective and order-preserving, we must also have at least $Nx-1$ natural numbers between $\varepsilon(x)$ ... $\varepsilon(Nx+x-1)$ including $\varepsilon(x)$.

Hence, $Nx-1 \leq \varepsilon(Nx+x-1) - \varepsilon(x) < \varepsilon(N+1)$. Since this is true for all $x \geq 2$, $\varepsilon(N+1)$ must necessarily be larger than all natural numbers. So it cannot be one itself.

Answer 2

I assume you want an embedding that sends $\times$ to $+$, in which case it is impossible. $\def\nn{\mathbb{N}}$

$f(2^k) = k \cdot f(2)$ for any $k \in \nn$. [where $k \cdot$ is understood to mean "the sum of $k$ copies of"]

$f(2^k) \ge 2^k-1$ for any $k \in \nn$. [This is because you want $f$ to be an order-preserving injection.]

I leave you to prove that no value of $f(2)$ can make the above two statements true.