4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You got your existential formula for the former and universal formula for the latter backward. $\endgroup$ – user21820 Jul 15 '15 at 7:10
  • $\begingroup$ The reverse embedding does not exist because $0\cdot x=0$ for any $x$, while for any $x$ we have $x+1\neq x$, so there is no value for $0$. $\endgroup$ – tomasz Jul 15 '15 at 18:04
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hmm, that's a similar argument to ZeroXLR's below, right? The idea is also that, for every $n$, $f(2) > n$, which is absurd. Is this correct? $\endgroup$ – Nagase Jul 15 '15 at 21:02
  • $\begingroup$ @Nagase: Correct. His solution is essentially the same idea, just rearranged a bit. I didn't bother using arbitrary $f(N+1)$ since using $f(2)$ already works. $\endgroup$ – user21820 Jul 16 '15 at 10:21

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.