¿Limitada de la adición y la multiplicación pueden computables en un modelo no estándar de la aritmética?

Question

Que $M = (N, \oplus, \otimes, <_m a="" aritm="" de="" debido="" est="" href="https://en.wikipedia.org/wiki/Tennenbaum%27s_theorem" incomputables="" modelo="" no="" peano="" rel="nofollow noreferrer" sea="" un="" y="">Teorema de Tennenbaum.</_m>

Para $c \in N$, que $\oplus{<c b="a" c="" como="" contrario="" de="" definido="" es="" indefinido.="" lo="" ser="" si="" sigue:="">¿Hay un modelo no estándar $M$ de peano aritmética no estándar $c \in N$ tal que $\oplus{<c computables="" son="" y=""></c>

</c>

Answer 1

No.

Deje $A, B$ ser recursivamente inseparable r.e. los conjuntos. Para cualquier natural $k$, es cierto que

$$M \models \exists y. y < c \land \forall i<x . (i \in A \implies p_i \mid y) \land (i \in B \implies p_i \nmid y)$$

(donde $p_i$ $i$th prime) por recepción, hay un no naturales $k$ con la anterior propiedad. Deje $y$ ser el testimonio de la declaración.

Ahora, para cualquier natural $i$, se puede calcular el $p_i$, y si $\oplus_{<c}$ es computable, podemos buscar $q, r$ tal forma que:

$(\underbrace{q \oplus q \oplus \dots \oplus q}_{p_i\text{ times}})\oplus r = y <_M c$.

Si $r=0$, $r \in C$. De lo contrario,, $r \notin C$. $C$ de forma recursiva separa $A$$B$. Contradicción. $\square$