Rompecabezas: Puede aritmética ser axiomatized con un sencillo de dos-término de relación?

Question

Tras mi pregunta acerca de la definición de la multiplicación en términos de divisibilidad, pueden todos los de la aritmética ser axiomatized con un sencillo de dos-término de relación? Asaf Karagila comentarios sobre mi pregunta de que los tres períodos de la relación Resto es suficiente. Desde entonces he descubierto que los dos términos de la relación es satisfactoria, y este artículo de la Wikipedia está de acuerdo ("la lógica de primer orden es indecidible [...] a condición de que el lenguaje tiene al menos un predicado de arity al menos 2"). ¿Cuál es el predicado binario? ¿Cómo puede aritmética ser axiomatized en términos de la misma? Ya he descubierto la respuesta, por lo que me han etiquetado esto como un rompecabezas. Sin embargo, mi construcción es difícil y me pregunto si hay alguna de las maneras más fáciles.

EDIT: No hay respuestas todavía, así que estoy añadiendo algunos detalles más acerca de mi propia solución. Un predicado binario que creo que es suficiente es: R(2x+1,y) := Divide(x,y), R(2x,y) := Testbit(x,y). Un siguiente paso es la definición de la igualdad como x=y := ∀z:R(z,x)↔R(z,y). Todavía faltan las definiciones de 0, 1, adición y la multiplicación.

EDIT: Como se pide, voy a incluir el resto de mi intento de solución y ampliar la pregunta algo. Es mi solución correcta? Puede ser simplificado en forma significativa? Hay otros predicados binarios que trabajo? Lo que es más precisa y la forma correcta de plantear el problema? Lo siento si eso es demasiado. De todos modos, aquí está mi solución. Iniciar con la definición de la igualdad como:

x=y := ∀z:R(z,x)↔R(z,y)

lo que significa que la igualdad de las cosas tienen el mismo divisores y también el mismo conjunto de bits. A continuación definimos 0 y 1:

x=0 := ∀y:R(x,y)↔R(y,x)

Impar(x) := ∃y:y=0∧R(y,x)

x=1 := Impar(x)∧∀y:Impar(y)∧R(y,x)↔y=0

También con Impar, la divisibilidad puede ser descomprimido:

Divide(x,y) := ∀z:Impar(z)→(R(z,x)→R(z,y))

Ahora podemos definir 2:

PowerOf2(x) := ∃y:Impar(y)∧R(y,x)∧∀z:Impar(z)∧R(z,x)→y=z

Prime(x) := (x=1)∧∀y:Divide(y,x)↔(y=x∨y=1)

x=2 := PowerOf2(x)∧Prime(x)

Y también la multiplicación por 2:

F(x,y,w) := PowerOf2(w)∧Divide a(w,x)∧Divide a(w,y)

x=2*y := (∀z:Impar(z)→(Divide a(z,y)↔Divide a(z,x)))∧(∃w:F(x,y,w)∧∀z:F(x,y,z)→z=w)

Tener la multiplicación por 2 permite Testbit a ser descomprimido:

Testbit(x,y) := ∃z:z=2*s∧R(z,x)

Testbit nos da las potencias de 2:

x=Potencia(2,y) := ∀z:Testbit(z,x)↔z=y

Que, finalmente, los rendimientos de la función sucesor:

y=Sucesor(x) := ∃z∃w:z=Potencia(2,x)∧w=Potencia(2,y)∧w=2*z

Y también menos que:

x<y := (x=y)∧∃z∃w:z=Potencia(2,x)∧w=Potencia(2,y)∧Divide a(z,w)

Ahora además se puede definir:

a+b=c := ∀i:Testbit(i,c)↔(Testbit(i,a)⊕Testbit(i,b)⊕ ∃j:j<i∧Testbit(j,a)∧Testbit(j,b)∧∀k: k<i∧j<k)→(Testbit(k,a)⊕Testbit(k,b)))

Finalmente, con una definición de a+b=c y se Divide(x,y), siga la misma interpretación que se le da en la aceptó respuesta a mi pregunta anterior para definir la multiplicación en términos de divisibilidad y, además, entonces se hace.

Answer 1

Creo que el resultado es en realidad un caso especial de ($\star$) dado cualquier (finito) número arbitrario de las relaciones $R_1,R_2, \ldots R_r$ $\mathbb Z$ (con arbitraria arities), hay un solo de dos términos de la relación $A(x,y)$ $\mathbb Z$ todos los $R_i$ son definibles en términos de $A$.

Para probar ($\star$), por lo que será suficiente para mostrar la forma más débil ($\star\star$ ) : dados cualesquiera dos de dos términos de relaciones de $R_1(x,y)$$R_2(x,y)$$\mathbb Z$, hay dos términos de la relación $A(x,y)$ $\mathbb Z$ tal que $R_1$ $R_2$ ambos son definibles en términos de $A$ (de hecho, se sigue de ($\star\star$) por inducción que cualquier número finito de dos términos de relaciones puede ser generado por una sola de las dos términos de la relación, y si $\beta=(\beta_1,\beta_2)$ es cualquier bijection ${\mathbb Z} \to {\mathbb Z}^2$, podemos añadir los dos términos de relaciones $U_1(x,y):y=\beta_1(x)$ $U_2(x,y):y=\beta_2(x)$ . A continuación, $\beta(z)=(x,y)$ puede ser definido como:$U_1(z,x) \wedge U_2(z,y)$, por lo que el $\beta$ es definible. Esta se ocupa de relaciones con grandes arities).

Así que vamos a mostrar ($\star\star$) : tomar de dos relaciones $R_1(x,y)$$R_2(x,y)$$\mathbb Z$. Deje $X=\lbrace 501,601,701,801, \ldots ,1401\rbrace$ y $Y=\lbrace 10;11;12;13;14 \rbrace$. Desde $|X|=10$$|Y|=5$, tenemos $|X|<2^{|Y|}$ , por lo que hay una inyección de $\gamma : X \to {\cal P}(Y)$.

Definir los dos términos de la relación $A : {\mathbb Z}^2 \to \lbrace True,False \rbrace$ por los siguientes once (discontinuo y, por tanto, coherente) reglas :

(1) Por $x\in{\mathbb Z}$,$A(x,x)=(x=5)$.

(2) Por $x\in [|5(...)14|], y\in{\mathbb Z} \setminus \lbrace 5 \rbrace$ con $y \neq x$ ,$A(x,y)=(y=x+1)$.

(3) Por $x\in{\mathbb Z} \setminus [|5(...)15|], y \in [|5(...)8|]$,$A(x,y)=( x \equiv y-4 \ ({\rm mod} \ 100))$.

(4) Por $x\in{\mathbb Z} \setminus [|5(...)15|]$,$A(x,9)=(x\in X)$.

(5) Por $x\in X$$y\in Y$,$A(x,y)=(y\in \gamma(x))$.

(6) Por $x,y \in \mathbb Z$,$A(100x+1,100y+2)=(x=y)$.

(7) Por $x,y \in \mathbb Z$,$A(100x+2,100y+1)=(R_1(x,y))$.

(8) Por $x,y \in \mathbb Z$,$A(100x+1,100y+3)=(x=y)$.

(9) Por $x,y \in \mathbb Z$,$A(100x+3,100y+1)=(R_2(x,y))$.

(10) Por $x\not\in [|5(...)14|],y \in \mathbb Z$$x\neq 100y+4$,$A(x,100y+4)=(y=x)$.

(11) Por $x\in{\mathbb Z}, y\not\in [|x(...)14|], y\not\equiv 4 \ ({\rm mod} \ 100)$,$A(100x+4,y)=(y=100x+1)$.

Luego, utilizando sólo $A$, podemos sucesivamente definir el plazo de las relaciones "$x=5$", "$x=k$" para $2 \leq k \leq 14$, "x es igual a $k$ modulo de 100" para $1\leq k \leq 4$,"$x$ es en $X$", y finalmente "$x=k$" para cada individuo, $k\in X$ (usando la regla (5)).

A continuación, los dos términos de la relación de $D(x,y):y=100x+1$ puede ser definido : esto es $D_1(x,y) \vee D_2(x,y)$ donde $D_1(x,y)$ es $$ (x=5 \wedge y=501)\vee(x=6 \wedge y=601) \ldots \vee (x=14 \wedge y=1401) $$ y $D_2(x,y)$ es $$ (y\no\en [| 5(...)15 |]) \cuña (y\no\equiv 4 \ ({\rm mod} \ 100)) \wedge (\existe z \ (z \equiv 4 \ ({\rm mod} \ 100)) \wedge Una(x,z) \wedge a(z,y)). $$

Ahora podemos definir la $R_1(x,y)$ $$ \exists x' \ \existe y' \ \existe z \ (z \equiv 2 \ ({\rm mod} \ 100)) \wedge D(x,x') \wedge D(y,y') \wedge a(x',z) \wedge a(z,y') $$ y $R_2(x,y)$ $$ \exists x' \ \existe y' \ \existe z \ (z \equiv 3 \ ({\rm mod} \ 100)) \wedge D(x,x') \wedge D(y,y') \wedge a(x',z) \wedge a(z,y'), $$ lo cual termina la prueba.

Answer 2

Me voy a convertir mi comentario en una respuesta, sólo porque tengo curiosidad por ver lo que, si de algo está mal con esta construcción.

Deje $S$ ser un predicado binario. De manera informal, queremos $S(x,y)$ a significar "$y$ es un sucesor de $x$". No voy a asumir que la lógica subyacente incluye un predicados de igualdad, sino más bien definir de la siguiente manera:

Definición 1: $\displaystyle x = y \ \overset{\operatorname{def}}\iff\ \forall z: (S(z,x) \iff S(z,y))$

Es decir, $x$ $y$ son iguales si y sólo si tienen el mismo predecesor(s). Voy a reforzar esta definición con el siguiente axioma:

Axioma 2: $\displaystyle x = y \iff \forall z: (S(x,z) \iff S(y,z))$

Es decir, $x$ $y$ son iguales si y sólo si tienen el mismo sucesor(s). Después de haber definido un predicados de igualdad, voy a adoptar axiomas que indica que cada número tiene un único sucesor (arriba a la igualdad, como se define arriba):

Axioma 3: $\displaystyle \forall x\; \exists y: S(x,y)$

Axioma 4: $\displaystyle (S(x,y) \wedge S(x,z)) \implies y=z$

A partir de estos axiomas, podemos demostrar que todos los antecesores de un número son iguales:

Teorema 5: $\displaystyle (S(x,z) \wedge S(y,z)) \implies x=y$

Prueba: Supongamos lo contrario, es decir, que $\exists x,y,z: S(x,z) \wedge S(y,z) \wedge x \ne y$. Entonces, por el axioma 2 existe $w$ tal que cualquiera de las $S(x,w) \wedge \neg S(y,w)$ o $\neg S(x,w) \wedge S(y,w)$. Asumir WLOG la antigua: a continuación,$S(x,z) \wedge S(x,w)$, que por el axioma 4 implica $z=w$. Pero entonces, por definición, 1, $S(y,z) \iff S(y,w)$, lo que lleva a la contradicción $S(y,w) \wedge \neg S(y,w)$.

Voy a adoptar un axioma que indica que existe un número sin predecesores:

Axioma 6: $\displaystyle \exists y\; \forall x: \neg S(x,y)$

Por definición, 1, todos los $y$ la satisfacción de este axioma son iguales. Para mayor comodidad, voy a adoptar la constante símbolo $0$ para denotar uno de ellos. Por lo tanto:

Corolario 7: $\displaystyle y = 0 \iff \forall x: \neg S(x,y)$

En particular, el teorema 5 junto con este corolario implica que todos los números no es igual a $0$ tiene un único predecesor.

Por último, voy a adoptar un axioma esquema para la inducción; es decir, para cada fórmula $\phi$ el idioma de esta teoría, que no contenga $a$ o $b$ como variables libres, voy a adoptar el axioma:

Axioma esquema 8: $\displaystyle (\phi(0) \wedge \forall a,b: (\phi(a) \wedge S(a,b)) \implies \phi(b)) \implies \forall x: \phi$

donde $\phi(c)$ denota $\phi$ con todas las apariciones libres de la variable $x$ reemplazado por $c$.

---

Queda por definir la suma y la multiplicación, que voy a hacer en más o menos de forma habitual. Voy a empezar por definir de forma recursiva el predicado ternario $A$ como:

Definición 9: $\displaystyle A(x,y,z) \ \overset{\operatorname{def}}\iff\ (x=0 \wedge y=z) \vee (\exists u,v: S(u,x) \wedge S(y,v) \wedge A(u,v,z))$

El siguiente paso es probar que, para cada una de las $x$$y$, no existe un único $z$ (que podemos denotar por $x+y$) tal que $A(x,y,z)$:

Teorema 10: $\displaystyle \forall x,y\; \exists z: A(x,y,z)$

Prueba: Por definición, 9, $\forall y: A(0,y,y)$. Suponga que $\forall v\; \exists z: A(u,v,z)$$S(u,x)$; por el axioma 3, $\forall y\;\exists v: S(y,v)$, y por lo tanto, por definición, un 9 $\forall y\;\exists z: A(x,y,z)$. Por lo tanto, la conclusión se deduce por inducción (axioma esquema 8) en $\phi(x) = \forall y\;\exists z:A(x,y,z)$.

Teorema 11: $\displaystyle \forall y,z,w: A(x,y,z) \wedge A(x,y,w) \implies z = w$

Prueba: Nuevo sigue de la definición de la 9 y la singularidad de los sucesores (axioma 4) y predecesores (teorema 5) por inducción en $x$; omite porque me estoy poniendo demasiado cansado para escribir.

Del mismo modo, la multiplicación puede ser definido a través de los recursiva predicado $M$:

Definición 12: $\displaystyle M(x,y,z) \ \overset{\operatorname{def}}\iff\ (y=0 \wedge z=0) \vee (\exists u,v: S(u,y) \wedge M(x,u,v) \wedge A(x,v,z))$

De nuevo, porque estoy cansado, voy a omitir la prueba de que para cada una de las $x$ $y$ existe un único $z = x \cdot y$ que $M(x,y,z)$. Debe ser verdad, a menos que me has jodido en alguna parte. También debe ser posible demostrar que la adición y la multiplicación de los operadores definidos así satisfacer a todos los habituales de las propiedades algebraicas que quiero de los números naturales, pero no voy a tratar de hacer eso ahora.