Podemos demostrar que los números pares y los impares alternativa sin el uso de la inducción?

Question

Es un ejercicio simple para demostrar el uso de la inducción matemática de que si un número natural n > 1 no es divisible por 2, entonces n se puede escribir como m + m + 1 para algún número natural m. (Según la definición de número impar, este puede ser declarado como "todo número es par o impar", o como "todo número impar es mayor que un número par". Mi pregunta es, este puede ser probado sin la inducción? En otras palabras, este puede ser probado en la aritmética de Robinson? Si no, ¿cuál es ejemplo de un modelo no estándar de la aritmética de Robinson que no tienen esta propiedad?

La razón por la que estoy pidiendo es que la prueba de la irracionalidad de la raíz cuadrada de 2 es por lo general se presenta con un solo uso de la inducción (o un equivalente de la técnica). Pero la prueba depende del hecho de si k^2 es par, entonces k es par, y que el hecho de que a su vez depende del hecho de que el cuadrado de un número no divisible por 2 es un número no es divisible entre 2. Y ese hecho es, como lo que puedo decir, es una consecuencia de la proposición anterior. (Estoy abierto a la corrección en ese punto.) Así que si la proposición dependía de la inducción, a continuación, la prueba de que sqrt(2) es irracional dependería de dos aplicaciones de la inducción. (La razón por la que los antiguos Griegos no han sido conscientes de esto es que Euclides implícitamente asume la proposición anterior, cuando se define un número impar como "lo que no es divisible en dos partes iguales, o que la que se diferencia por una unidad de un número par".)

Cualquier ayuda sería muy apreciada.

Gracias de Antemano.

Answer 1

Tome $M = \{P = a_nx^n + \ldots + a_0 \in \Bbb Z[x] / a_n > 0 \}$, con la costumbre de la adición y multiplicación de polinomios. Interprete $S(P)$$P(X)+1$.

A continuación, $M$ es un modelo de Robinson aritmética, pero no son cadenas largas de "no-incluso" los números, tales como $X,X+1,X+2,\ldots$. Así, en este modelo, es falso que si $n$ no es ni siquiera, a continuación, $n+1$ es incluso.

Si se define "$n$ es impar" como "$\exists k / n= k+k+1$", entonces es falso que cada número es par o impar.

Sin embargo, sigue siendo cierto en $M$ que la suma es asociativa y conmutativa, y por tanto si $n$ es impar, a continuación, $n+1$ es aún, y si $n$ es incluso, a continuación, $n+1$ es impar. (usted necesitará un extraño modelo de este error)

---

Si quieres un modelo en el que $a^2-2b^2 = 0$ tiene una solución, usted puede recoger $M = \{ P \in \Bbb Z[X,Y]/(X^2-2Y^2) / \lim_{y \to \infty} P(\sqrt 2 y,y) = + \infty$ o $P \in \Bbb N \}$

Answer 2

Esto es sólo una respuesta parcial. Deje $\mathcal L =\{S,<\}$ ser el idioma con una única función de $S$ y una relación binaria $<$. Considerar la estructura $(\mathbb N, S,<)$ ($S$ es el sucesor de la función), a continuación, $E=\{2n:n\in\mathbb N\}$ no es definible en $(\mathbb N, S,<)$. Para ver esto consideremos la primaria de la extensión de $\mathfrak C=(\mathbb N\sqcup \mathbb Z, S,<)$, y definir un automorphism $\Phi:\mathfrak C\to \mathfrak C$ siguiente $\Phi(n)=n$ si $n\in\mathbb N$ $\Phi(n)=S(n)$ lo contrario. Es fácil ver, el uso de $\Phi$, que no hay ninguna fórmula de la definición de $E$.

Answer 3

Me parece haber encontrado una respuesta a mi propia pregunta, a partir de la página 49 de Edward Nelson el libro de Los Elementos (que fue un fallido intento de demostrar que la aritmética de Peano es inconsistente):

"Aquí hay una semántica indicación de que la inducción es necesaria para demostrar esto. Tome un modelo no estándar de $P$ y deje $\alpha$ ser un número no estándar. Tomar el externo set $U$ de todos los números normalizados, junto con todos los números obtenidos por varias ocasiones la aplicación de las funciones de los símbolos de $Q_{90}$$\alpha$. Entonces U es el universo de un modelo de $Q_{90}$, pero no hay ningún individuo $\beta$ $U$ tal que cualquiera de las $2 \beta = \alpha $ o $2 \beta + 1= \alpha $."

Aquí $P$ denota la aritmética de Peano y $Q_{90}$ indica Robinson aritmética básica de las propiedades de la adición, la multiplicación y la orden de agregado.

¿Alguien puede explicar lo de Nelson razonamiento? ¿Por qué no puede haber un $\beta$ $U$ tal que cualquiera de las $2 \beta = \alpha $ o $2 \beta + 1= \alpha $?

Answer 4

Me hicieron una pregunta similar: Incluso XOR Impar Infinitos?. No estoy seguro de que usted puede probar lo que usted está tratando de demostrar que incluso con la inducción.

Mi pregunta era acerca de una teoría que se me llame la Aritmética Modular (MA). Como Edward Nelson, me vino con MA como una herramienta para demostrar la PA es inconsistente. MA tiene el mismo axiomas como PA con la excepción de $\forall x(Sx \neq 0)$ se sustituye $\exists x(Sx=0)$. Suponiendo que podemos definir el módulo de función en PA, mi pregunta puede ser traducido en el PA. El número natural $n$ es impar si reúne ambas de las siguientes expresiones:

$O1: \forall x((x = 0 \lor x+x \neq 0) \mod n)$

$O2: \exists x((x+x = 1) \mod n)$

$n$ es incluso si ambas afirmaciones son falsas. No estoy seguro de cómo iba a definir a los "números pares y los impares alternativo". Mi pregunta fue: "es que cada número natural exclusivamente o, incluso, exclusivamente impar?":

$\forall n(\exists x((x \neq 0 \land x+x = 0) \mod n) \overline{\vee} \exists x((x+x = 1) \mod n))$

La respuesta a mi pregunta fue que no. Se comprobó $O2 \rightarrow O1$. Sin embargo, $O1 \rightarrow O2$ es falso. $O1$ es verdadera y $O2$ false en el 2-adics enteros, $Z_2$. No hay 2-ádico entero, $m \neq 0$, de tal manera que $2m=0 \overline{\vee} 2m=1$. La anterior afirmación es falsa también para $n = -1 = ...111 \in Z_2$.

Todos los modelos infinitos de MA no son estándar y son un segmento inicial de algún modelo de PA. $Z_2$ es un anillo, pero puede ser "ampliado" en un incontable, no estándar del modelo de PA. Creamos una copia de $Z_2$ que comienza con $0'$. Deje $S(-1)=0'$. Seguimos añadiendo copias de $Z_2''$ y deje $S(-1') = 0''$ para obtener un modelo de PA. Podemos demostrar que no son estándar de los números en este modelo que no son exclusivamente o, incluso, exclusivamente impar.

He leído que hay inductivo pruebas de $\forall x \exists y(x=y+y \lor x=S(y+y))$ en PA. Yo estaría interesado en cualquier prueba de la $\forall x \exists y(x=y+y \overline{\vee} x=S(y+y))$ en PA.