Hay una incrustación de $\langle \mathbb{N} \setminus \{0\}, \leq, \times, 1 \rangle$ a $\langle \mathbb{N}, \leq, +, 0 \rangle$?

Question

Este parece ser un principio común de ejercicio en el modelo de la teoría (lo he encontrado tanto en Chang & Keisler y también en el Manzano del Modelo de la Teoría). No es difícil ver que hay una incrustación de $\langle \mathbb{N}, \leq, +, 0 \rangle$ a $\langle \mathbb{N}, \leq, \times, 1 \rangle$; acaba de tomar la función de $h(x) = 2^x$ (o algo similar). Por otro lado, tampoco es muy difícil (creo!) a ver que a la inversa no se sostiene, para que, si hubiera una incrustación $h$,$h(1) = 0$$h(0) = 0$, lo que significa que $h$ no es inyectiva (y por lo tanto no es en realidad una incrustación). Pero, ¿qué acerca de una incrustación de $\langle \mathbb{N} \setminus \{0\}, \leq, \times, 1 \rangle$ a $\langle \mathbb{N}, \leq, +, 0 \rangle$?

A mí me parece que no hay tal incrustación así, pero no puedo trabajar fuera un argumento que muestra esta imposibilidad. Claramente el argumento anterior no funciona, porque dependía de $h(0)$. Pensé en tratar de mostrar que no hay una fórmula existencial que es verificado por el último, pero no por la primera, o a la inversa, una fórmula universal verificado por el primero pero no el último, pero no podía pensar en nada. Supongo que hay otras maneras de demostrar esto?

Cualquier sugerencias?

Answer 1

Supongo que usted quiere una incrustación que envía a$\times$$+$, en cuyo caso es imposible. $\def\nn{\mathbb{N}}$

$f(2^k) = k \cdot f(2)$ cualquier $k \in \nn$. [donde $k \cdot$ se entiende por "la suma de $k$ copias de"]

$f(2^k) \ge 2^k-1$ cualquier $k \in \nn$. [Esto es porque desea $f$ a ser un fin de la preservación de la inyección.]

Os dejo para demostrar que no hay ningún valor de $f(2)$ puede hacer que los dos anteriores declaraciones de la verdad.

Answer 2

Estás en lo correcto. No hay tal incorporación y el argumento para demostrar esto es bastante simple. Para, dicen que no hay es una incrustación $\varepsilon : \langle \mathbb{N} \setminus \{0\}, \leq, \times, 1 \rangle \to \langle \mathbb{N}, \leq, +, 0 \rangle$. Como una contradicción, voy a mostrar que para cada número natural $N \ge 1$, $\varepsilon(N+1)$ no puede ser un número natural.

Denotar $s \times t$ simplemente como $st$ y corregir cualquier número natural $x \ge 2$. Ahora, $Nx+x-1 < (N+1)x$. También, $\varepsilon$ es inyectiva y el orden/la función de la preservación. Por eso, $\varepsilon(Nx+x-1) < \varepsilon((N+1)x) = \varepsilon(N+1) + \varepsilon(x)$. Por lo tanto, tenemos $\varepsilon(Nx+x-1) - \varepsilon(x) < \varepsilon(N+1)$.

Siguiente, entre $x$ ... $Nx+x-1$, hay(es) obviamente $Nx-1$ natural distinta número(s) incluida $x$. Pero entonces, como $\varepsilon$ es inyectiva y el orden-la conservación, también debemos tener al menos $Nx-1$ números naturales entre $\varepsilon(x)$ ... $\varepsilon(Nx+x-1)$ incluyendo $\varepsilon(x)$.

Por lo tanto, $Nx-1 \leq \varepsilon(Nx+x-1) - \varepsilon(x) < \varepsilon(N+1)$. Como esto es cierto para todos $x \geq 2$, $\varepsilon(N+1)$ necesariamente debe ser mayor que todos los números naturales. Así que no puede ser uno en sí.