¿Incluso XOR impar Infinities?

Question

La Aritmética Modular (AM) tiene los mismos axiomas que la Aritmética Peano de primer orden (AP), excepto $\forall x (Sx \ne 0)$ se sustituye por $\exists x(Sx = 0)$ . ( http://en.wikipedia.org/wiki/Peano_axioms#First-order_theory_of_arithmetic ).

MA tiene modelos finitos arbitrariamente grandes basados en la aritmética modular. Todos los modelos finitos de MA tienen un número par o impar de elementos. Llamo a un modelo de MA "par" si satisface estas dos frases:

E1) $\exists x(x \ne 0 \land x+x = 0)$

E2) $\forall x(x+x \ne S0)$

Un modelo de MA es impar si satisface las dos cosas:

O1) $\forall x(x = 0 \lor x+x \ne 0)$

O2) $\exists x(x+x = S0)$

Podemos utilizar la compacidad para demostrar que MA tiene infinitos modelos de tamaño "par" añadiendo las definiciones pares anteriores como axiomas. Del mismo modo, podemos demostrar que hay infinitos modelos de tamaño "impar" de MA. Algunos conjuntos infinitos, como los enteros, no son ni pares ni Impares. Los enteros no son la base de un modelo de MA. Por ejemplo, el teorema del cuadrado (todo número es la suma de cuatro cuadrados) es un teorema tanto de MA como de PA. El teorema de los cuatro cuadrados es falso en los números enteros. Se ha conjeturado que los números complejos son una base para un modelo de MA. Si es así, los números complejos serían un modelo "impar" de MA.

Mi pregunta es si todo modelo de MA debe ser exclusivamente par o exclusivamente impar. ¿Es esta afirmación un teorema de MA?

$$\exists x(x \ne 0 \land x+x = 0) \ \overline{\vee}\ \exists x(x+x = S0)$$

Hice esta pregunta en stack exchange y no obtuve respuesta.

https://math.stackexchange.com/questions/214018/even-xor-impar-infinities

---

[ Lo siguiente se ha fusionado a partir de una respuesta - ed. ]

La prueba de Ashutosh se puede escribir como:

$\exists x\exists y( (x+x=0 \land y+y=1) \implies (x=0) )$

Esto responde a mi pregunta cuando $\exists x(x+x=1)$ es cierto, pero no dice nada sobre cuándo $\forall x(x+x \ne 1)$ es cierto. Emil y otros han afirmado que cualquier campo algebraicamente cerrado es un modelo de MA. La prueba de Ashutosh muestra que cualquier campo algebraicamente cerrado es impar porque $\exists x(x+x=1)$ es cierto.

Quiero aceptar la respuesta de Ben Crowell, pero tengo algunas reservas. La prueba comienza mostrando cómo cualquier modelo de MA puede expandirse a un modelo de PA. He presentado argumentos similares y siempre he supuesto que sería fácil de demostrar. Mi conjetura es cierta para todos los modelos finitos de MA, por lo que sólo tenemos que considerar los modelos infinitos. MA es omega inconsistente y cualquier modelo infinito debe tener elementos no estándar. El teorema de Tennebaum dice que la adición no es recursiva en los modelos no estándar de PA. ¿Puede la adición ser realmente recursiva en $A$ ¿el modelo de AP que construye? Parece que está asumiendo que podemos añadir números no estándar del modelo de AM. También me pregunto si está asumiendo $I$ es un modelo estándar de AP. No creo que haga ninguna diferencia, pero podría ser.

La prueba de Obo es mucho más sencilla y similar a una prueba que se me ocurrió. Mi prueba tenía el mismo error que la suya. Creo que se puede arreglar. En el caso de que tengamos $S(y+y)=p$ tenemos que demostrar también $y \ne p$ . $y \ne p$ puede ser verdadera sólo en modelos con tres o más elementos.

Esto no es un grupo de discusión así que no entraré en detalles de por qué no creo que los números complejos sean un modelo de MA. No creo que MA tenga modelos infinitos. Señalaré que MA demuestra muchas cosas interesantes sobre los modelos Impares. En un modelo impar la suma de todos los elementos es 0. Esto no se puede afirmar en primer orden. Creo que si tenemos una función sucesora definida sobre los números complejos podemos usarla para ordenar los reales. Sólo hay que ignorar los números con una componente imaginaria distinta de cero.

Quiero retractarme de mi afirmación de que el teorema de los cuatro cuadrados de Lagrange es un teorema de MA. Basé mi afirmación en el artículo de Andrew Boucher sobre la Aritmética General (AG). Boucher muestra que GA demuestra el teorema del cuatro cuadrado. Pensé que GA era una subteoría débil de MA porque GA tiene axiomas sucesores mucho más débiles. Releyendo el artículo veo que Boucher dice que utiliza la inducción de segundo orden. También dice que el sucesor es de segundo orden.

Answer 1

La respuesta es no. Basta con encontrar un modelo de MA que sea un dominio integral de la característica $0$ (por lo que O1 es verdadero y E1 falso) tal que $2$ no es invertible (por lo que E2 es verdadera y O2 falsa).

Un ejemplo de este modelo es el anillo de $2$ -enteros radicales $\mathbb Z_2$ . Esto es claramente un dominio, y $2$ no es una unidad, por lo que basta con demostrar que

Teorema: Para cualquier primo $p$ el anillo $\mathbb Z_p$ es un modelo de AM.

Prueba: El único problema es verificar que la inducción se mantiene. Supongamos que $\mathbb Z_p\models\phi(0)\land\forall x\,(\phi(x)\to\phi(x+1))$ , donde $\phi$ es una fórmula aritmética con parámetros de $\mathbb Z_p$ y poner $\phi(\mathbb Z_p):=\{a\in\mathbb Z_p:\mathbb Z_p\models\phi(a)\}$ .

Desde $\phi(\mathbb Z_p)$ es definible en $\mathbb Z_p$ también es definible en el campo $\mathbb Q_p$ dotado de un predicado unario para $\mathbb Z_p$ . Macintyre [1] demostró que tales estructuras admiten una forma de eliminación del cuantificador, y como corolario (Thm. 2 en la p. 609), todo conjunto infinito definible tiene un interior no vacío. Por lo tanto, hay $a_0\in\phi(\mathbb Z_p)$ y $k\ge0$ tal que $a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$ . Sea $a\in\mathbb Z_p$ sea arbitraria, y que $b< p^k$ sea un número natural tal que $b\equiv a-a_0\pmod{p^k}$ . Desde $\phi(\mathbb Z_p)$ es cerrado bajo sucesión, tenemos $a\in b+a_0+p^k\mathbb Z_p\subseteq\phi(\mathbb Z_p)$ . Así, $\phi(\mathbb Z_p)=\mathbb Z_p$ es decir, $\mathbb Z_p\models\forall x\,\phi(x)$ .    QED

Sospecho que los siguientes pueden funcionar como contramodelos adicionales (son dominios donde $2$ no es una unidad, la cuestión es si satisfacen la inducción):

• El anillo de enteros algebraicos $\tilde{\mathbb Z}$ . Una forma de eliminación de cuantificadores para $\tilde{\mathbb Z}$ fue demostrado por van den Dries [2] y Prestel y Schmid [3], pero las fórmulas básicas son algo confusas, por lo que no me queda claro inmediatamente si esto implica inducción.

• La localización de $\tilde{\mathbb Z}$ en un ideal máximo que contenga $2$ . La eliminación de los cuantificadores para este anillo (y otros similares) se reporta como Hecho 3 en [2], donde se atribuye a [4]. Parece que podría implicar la inducción por un argumento similar al de $\mathbb Z_p$ .

[1] Angus Macintyre, Sobre subconjuntos definibles de $p$ -Campos de la vida cotidiana Journal of Symbolic Logic 41 (1976), no. 3, pp. 605-610.

[2] Lou van den Dries, Teoría de la eliminación para el anillo de enteros algebraicos Journal of Pure and Applied Mathematics 388 (1988), pp. 189-205.

[3] A. Prestel y J. Schmid, Dominios existencialmente cerrados con relaciones radicales Journal of Pure and Applied Mathematics 407 (1990), pp. 178-201.

[4] Angus Macintyre, Kenneth McKenna, Lou van den Dries, Eliminación de cuantificadores en estructuras algebraicas , Advances in Mathematics 47 (1983), nº 1, pp. 74-87.

Answer 2

NOTA: La primera prueba es errónea porque utiliza la inducción de segundo orden. La segunda prueba también es errónea según el comentario de Wofsey.

Ashutosh en los comentarios ha demostrado que la exclusión se mantiene.

He aquí una prueba de la existencia.

Sea A los elementos del modelo. Sea p el predecesor de 0 en A. Sea T = S \ {(p,0)}. Entonces T induce el ordenamiento normal < en A, siendo p el elemento máximo. Se puede demostrar que (1) x < Sy implica x <= y.

Claramente p + p <= p. Sea x el menor elemento tal que x + x <= x. Afirmamos que x + x = 0 o x + x = 1. Supongamos que no. Entonces existe y tal que Sy = x y v tal que SSv = x + x y y < x y v < x + x. (y < x porque si no x = 0, entonces x + x = 0, una contradicción.) Pero v = y + y, y v < x + x <= x. Entonces v < Sy. Por (1) v <= y, contradiciendo la minimización de x.

ABOVE asumió la inducción de segundo orden. ABAJO funciona con inducción de primer orden (y es más fácil de arrancar...).

Afirmo: (x)(y(y+y=x v S(y+y)=x))

Pues esto es cierto cuando x = 0 (toma y = 0). Supongamos que es cierto para k. Si y+y=k, entonces S(y+y)=Sk. Y si S(y+y)=k, entonces Sy+Sy =Sk. Por tanto, si es cierto para k, entonces es cierto para Sk. Por inducción (¡de primer orden!), la afirmación es verdadera.

Sea p el predecesor de 0. Entonces por la afirmación y+y=p o S(y+y) = p para algún y. En el primer caso Sy+Sy = 1, en el segundo Sy+Sy = 0.

Answer 3

Esto es sólo un esbozo y puede estar equivocado, pero pensé en lanzarlo y ver si podía aprender algo de mis probables errores.

Dejemos que $I$ sea un modelo de AP y $M$ un modelo de MA. Sea $A=I\times M$ sea el modelo de PA definido tomando el producto cartesiano de los dos conjuntos y definiendo $S(i,m)=(i,S(m))$ si $S(m)\ne 0$ , si no $(S(i),0)$ .

Para comprobar que $A$ es un modelo de AP como se afirma, la cuestión principal es la verificación de la inducción. Supongamos que las hipótesis de la inducción se cumplen para algún conjunto K. Si K incluye $(i,0)$ entonces $(i,m)$ se incluye para todos los $m$ porque la inducción es una hipótesis de MA. Además, si $(i,0)$ está en K, entonces también lo está $(i+1,0)$ ya que uno de los axiomas de MA es que existe un $m$ cuyo sucesor es 0, y ya hemos comprobado que todos los $(i,m)$ están en K. Esto establece que la inducción se mantiene para $A$ .

Como en cualquier modelo de PA, la definición de S implica operaciones de suma y multiplicación definidas de forma única. Bajo esta definición de adición, cualquier miembro $(i,m)$ de A puede escribirse como $(i,0)+(0,m)$ y esta forma es única. Para dos elementos cualesquiera de A, tenemos entonces $(i,m)+(i',m')=(i+i',0)+(0,m)+(0,m')$ que es de la forma $(\ldots,m+m')$ .

Supongamos que la conjetura de Russell Easterly falla, por lo que no hay ningún $m$ en $M$ tal que $m+m=0$ o $m+m=1$ . Entonces no hay ningún $a$ en $A$ tal que $a+a$ es igual a $(1,0)$ o $(1,1)$ . Pero es un teorema en PA que para cualquier número $x$ , ya sea $x$ o $S(x)$ puede expresarse como $y+y$ Así que tenemos una contradicción.

Esto establece la parte "o", y el comentario de Ashutosh muestra que no es sólo o sino xor.

Creo que esto también lleva al hecho de que un modelo de MA es siempre isomorfo a un modelo de PA módulo uno de sus elementos. Dado que los modelos no estándar de la aritmética están bastante estudiados, creo que esto también caracteriza los posibles modelos no estándar de MA.