¿Se puede definir implícitamente la multiplicación a partir del sucesor?

Question

Una relación $R$ es definible implícitamente en una estructura $M$ si existe una fórmula $\varphi(\dot R)$ en el lenguaje de primer orden de $M$ ampliado para incluir la relación $R$ , de tal manera que $M\models\varphi(\dot R)$ sólo cuando $\dot R$ se interpreta como $R$ y no como cualquier otra relación. En otras palabras, la relación $R$ tiene una propiedad expresable de primer orden que sólo ella tiene.

(Los teóricos del modelo deben tener en cuenta que esto es definibilidad implícita en un modelo que no es lo mismo que la noción utilizada en Teorema de definibilidad implícita de Beth .)

La definibilidad implícita es una forma muy débil de definibilidad de segundo orden, que no implica cuantificadores de segundo orden. Dicho así, una relación definible implícitamente $R$ es uno que es definible en la estructura completa de segundo orden de Henkin del modelo, pero utilizando una fórmula con sólo cuantificadores de primer orden.

Ejemplos. He aquí algunos ejemplos de relaciones que son implícitamente definibles en una estructura, pero no definibles.

• El predicado $E$ pues ser par es definible implícitamente en el lenguaje de la aritmética con sucesor, $\langle\mathbb{N},S,0\rangle$ . Se define implícitamente por la propiedad de que $0$ es par y la paridad se alterna con la sucesión: $$E0\wedge \forall x\ (Ex\leftrightarrow\neg ESx).$$ Mientras tanto, ser par no es definible explícitamente en $\langle\mathbb{N},S,0\rangle$ ya que esa teoría admite la eliminación de cuantificadores, y todos los conjuntos definibles son finitos o cofinitos.

• La adición también es definible implícitamente en ese modelo, mediante la recursión habitual $a+0=a$ y $a+(Sb)=S(a+b)$ . Pero la adición no es definible explícitamente, de nuevo por la eliminación del argumento de los cuantificadores.

• La multiplicación es definible implícitamente a partir de la suma en el modelo estándar de la aritmética de Presburgo $\langle\mathbb{N},+,0,1\rangle$ . Esto se debe, de nuevo, a la recursividad habitual, $a\cdot 0=0$ , $a\cdot(b+1)=a\cdot b+a$ . Pero no es explícitamente definible, porque esta teoría admite un resultado relativo de QE hasta el lenguaje con congruencia mod $n$ por cada $n$ .

• La verdad de primer orden es definible implícitamente en el modelo estándar de la aritmética $\langle\mathbb{N},+,\cdot,0,1,<\rangle$ . La recursión de Tarski expresa propiedades del predicado de verdad que lo determinan completamente en el modelo estándar, pero por el teorema de Tarski sobre la no definibilidad de la verdad, éste no es un predicado definible.

Mi pregunta se refiere a las aplicaciones iteradas de la definibilidad implícita. Vimos que la adición era definible implícitamente sobre el sucesor, y la multiplicación es definible implícitamente sobre la adición, pero no veo ninguna manera de demostrar que la multiplicación es definible implícitamente sobre el sucesor.

Pregunta. ¿La multiplicación es definible implícitamente en $\langle\mathbb{N},S,0\rangle$ ?

En otras palabras, ¿podemos expresar una propiedad de la multiplicación $a\cdot b=c$ en su relación con el sucesor, que lo determina completamente en el modelo estándar?

Supongo que la respuesta es No pero no sé cómo demostrarlo.

Actualización. Quería mencionar una idea prometedora de Clemens Grabmayer para un Sí respuesta (ver su tuit ). La idea es que evidentemente la adición es definible a partir de la multiplicación y el sucesor (como se demostró por primera vez en la obra de Julia Robinson tesis y más convenientemente disponible en Boolos/Jeffrey, Computability & Logic, Sect. 21). Podríamos esperar usar esto para formar una definición implícita de la multiplicación a partir del sucesor. A saber, la multiplicación será una operación que obedece a la recursión habitual sobre la suma, pero sustituyendo las instancias de $+$ en esta definición con la noción de adición definida a partir de la multiplicación de esta manera inusual. Lo que quedaría por demostrar es que no puede haber una versión falsa de la multiplicación que proporcione una adición falsa, con respecto a la cual cumpla la definición recursiva de la multiplicación sobre la adición.

Answer 1

En contra de mis expectativas iniciales, la respuesta es sí.

Esta respuesta se basa en la idea de Clemens Grabmayer, que hace la observación de que la adición $+$ es definible a partir de la multiplicación $\cdot$ y sucesor.

La idea se generaliza a lo siguiente:

Teorema. Supongamos que la relación $R$ es definible implícitamente en el modelo $M$ que $S$ es definible implícitamente en la expansión $\langle M,R\rangle$ y que $R$ es definible explícitamente en $\langle M,S\rangle$ . Entonces $S$ es definible implícitamente en $M$ .

Prueba. Supongamos que $R$ es la única relación que cumple la sentencia $\varphi(\dot R)$ en $M$ en el lenguaje expandido con el predicado $\dot R$ . Supongamos que $S$ es la única relación que cumple la sentencia $\psi(R,\dot S)$ en $\langle M,R\rangle$ . Y supongamos que $R$ es definible mediante la fórmula $\theta(x,S)$ en $\langle M,S\rangle$ en que $Rx\leftrightarrow\theta(x,S)$ .

Dejemos que $\Phi(\dot S)$ sea la frase que afirma:

• $\varphi(\theta(x,\dot S))$ es decir, la relación definida por $\theta(x,\dot S)$ cumple con la propiedad $\varphi$ y
• $\psi(\theta(x,\dot S),\dot S)$ se mantiene, es decir, la afirmación $\psi(\dot R,\dot S)$ se mantiene donde $\dot R$ se interpreta mediante la relación definida por $\theta(x,\dot S)$ .

Afirmo que esta es una definición implícita de $S$ en $M$ . La razón es que cualquiera que sea la interpretación de la relación que se le dé a $\dot S$ tendrá la propiedad de que la relación extraída de ella a través de $\theta(x,\dot S)$ tendrá que ser $R$ ya que cumple con la definición implícita de $R$ dado por $\varphi$ . Y además, como $\Phi$ afirma que $\psi$ se cumple con $\dot S$ con respecto a esa relación, se deduce que $\dot S$ debe ser $S$ . $\Box$

El corolario es que:

Corolario. La multiplicación es definible implícitamente a partir del sucesor.

Prueba. La suma es definible implícitamente en $\langle\mathbb{N},S,0\rangle$ y la multiplicación es implícitamente definible sobre la suma $\langle\mathbb{N},S,0,+\rangle$ y por la observación de Boolos/Jeffrey, la suma es definible explícitamente a partir de la multiplicación y el sucesor. Así que estamos en el caso del teorema. $\Box$

Un ejemplo más llamativo podría ser:

Corolario. Verdad aritmética de primer orden para el modelo estándar de aritmética $\langle\mathbb{N},+,\cdot,0,1<\rangle$ es definible implícitamente sólo a partir del sucesor $\langle\mathbb{N},S,0\rangle$ .

Prueba. Pretendo utilizar el predicado de verdad trinario $\text{Tr}(\varphi,x,y,z)$ , que se mantiene cuando $\mathbb{N}\models\varphi[x,y,z]$ . Este predicado de verdad está caracterizado de forma única en el modelo estándar $\mathbb{N}$ cumpliendo la recursión de Tarski, por lo que es definible implícitamente en $\langle\mathbb{N},+,\cdot\rangle$ . Pero tanto la suma como la multiplicación son definibles a partir del predicado de verdad (por eso usamos la versión trinaria, ya que con sólo el sucesor no tenemos inicialmente ninguna codificación, pero una vez que obtenemos $+$ y $\times$ ), y ellos mismos son definibles implícitamente a partir del sucesor. Por lo tanto, según el teorema, la verdad es definible implícitamente a partir del sucesor. $\Box$

Y uno puede, por supuesto, iterar esto formando el predicado para la verdad-sobre-la-verdad, y la verdad-sobre-la-verdad y así sucesivamente, procediendo transfinitamente hacia arriba en la jerarquía durante bastante tiempo.

Pero, por último, permítanme mencionar que el teorema no llega a demostrar que la propiedad de ser implícitamente definible-sobre es transitiva. Eso parece ser falso a la luz de los contraejemplos discutidos en los comentarios.

Answer 2

Podemos dar explícitamente la definición implícita solicitada para la multiplicación: Es la única función sobre $(\mathbb{N},S,0)$ satisfactorio: \begin{align} 0a&=0\\ ab&=ba\\ a(bc)&=(ab)c\\ (Sa)S(ab) &= S(aS(bS(a))) \end{align} La última identidad es una ley distributiva, que se escribiría más familiarmente como $$(1+a)(1+ab) = 1+a(1+b(1+a))$$

Como es habitual en estas cuestiones, nos fijamos en los números de la forma $S^n0$ . Para cada número entero positivo $n$ , ese numeral es un término en el lenguaje del modelo. Cuantificamos sobre $n$ fuera del modelo.

Demostramos por inducción que para todo $m$ y $n$ los axiomas implican que el único valor posible para $S^m0\ S^n0$ es $S^{mn}0$ y así determinar la función de multiplicación en todo el dominio del modelo. Los casos inductivos se demuestran en el orden lexicográfico sobre $(m,n)$ por lo que podemos utilizar la hipótesis inductiva de $(m',n')$ siempre que $m'<m$ o $m'=m \wedge n'<n$ .

• El caso $m=0$ se deduce del primer axioma.

• El caso $m>n$ se desprende de $m'=n,n'=m$ .

• El caso $m=1$ , $n=1+k$ se desprende de \begin{array}{rll} S^m0\ S^n0 &=(SS^k0)S0 & \text{ by commutativity} \\ &=(SS^k0)S((S^k0)0)\ & \text{ by }m'=0, n'=k \\ &=S((S^k0)S(0(SS^k0))) & \text{ by distributing }a=S^k0, b=0 \\ &=S((S^k0)(S0)) & \text{ by }m'=0, n'=1+k\\ &=S(S^k0) & \text{ by }m'=1, n'=k\\ &=S^{mn}0 \end{array}

• El caso $1<m\le n$ , donde $m-1$ y $n$ tienen un factor común $h>1$ se desprende de \begin{array}{rll} S^m0\ S^n0 &= S^m0\ S^h0\ S^{n/h}0 &\text{ by }m'=h, n'=n/h\\ &= S^{h}0\ S^{mn/h}0 &\text{ by }m'=m, n'=n/h\\ &= S^{mn}0 &\text{ by }m'=h, n'=mn/h \end{array} Todas las hipótesis inductivas son anteriores a $(m,n)$ en el orden inductivo porque $h\le m-1<m$ y $n/h<n$ .

• En el caso $1<m\le n$ , donde $m-1$ y $n$ son relativamente primos, hay algo de $j$ con $$jn=1+k(m-1)$$ y \begin{align} \text{either }\ m=2,\ \ &1=j=m-1\\ \text{ or }\ \ m>2,\ \ &1\le j<m-1 \end{align} En ambos casos $0<k<n$ . Sea $M=m-1$ . Entonces \begin{array}{rll} S^j0\ S^m0\ S^n0 & = S^m0\ S^{jn}0 &\text{ by }m'=j, n'=n\\ &= S(S^M0)S(S^{kM}0) &\text{ by definitions of }j,k,M\\ &= S(S^M0)S(S^M0\ S^k0) &\text{ by }m'=M, n'=k\\ &= S((S^M0)S((S^k0)SS^M0)) &\text{ by distributing }a=S^M0, b=S^k0\\ &= S((S^M0)S(S^{k(1+M)}0)) &\text{ by }m'=1+M=m, n'=k\\ &= S^{1+M(1+k(1+M))}0 &\text{ by }m'=M, n'=1+k(1+M)\\ &= S^{mjn}0 &\text{ by definitions of }j,k,M \\ &= S^j0\ S^{mn}0 &\text{ by }m'=j, n'=mn \end{array} Ahora bien, como $S^m0\ S^n=0$ es un elemento del modelo estándar, es de la forma $S^p0$ . Si $mn\neq p$ entonces \begin{array}{rll} S^j0\ S^m0\ S^n0 &= S^j0 S^p0 & \text{ by definition of }p\\ &= S^{jp}0 &\text{ by }m'=j, n'=p\\ &\neq S^{jmn}0 &\text{ by }mn\neq p \\ &= S^j0\ S^{mn}0 &\text{ by }m'=j, n'=mn \end{array} lo que contradice lo que se acaba de demostrar. Esto descarta todas las opciones de $S^m0\ S^n0$ que no sea $S^{mn}0$ por lo que debe ser el caso que $S^m0\ S^n0 = S^{mn}0%$ como se desee.

Esto establece la afirmación de que los axiomas anteriores definen implícitamente la multiplicación en $(\mathbb{N}, 0, S)$ .