Autor Tema: La Aritmética Recursiva Primitiva

0 Usuarios y 1 Visitante están viendo este tema.

22 Junio, 2023, 12:07 am
Respuesta #10

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Demostramos ahora el resultado fundamental para manejar la lógica de ARP con naturalidad:

Teorema de deducción  Si se cumple

\( \alpha_1,\ldots, \alpha_n, \alpha\mathop{\vdash}\limits_{\rm ARP}\beta \)

y en la deducción no se usan las reglas \( S_1 \) ni \( I_0 \) respecto de variables que estén en \( \alpha \), entonces

\( \alpha_1,\ldots, \alpha_n\mathop{\vdash}\limits_{\rm ARP}\alpha\rightarrow \beta \)

En otras palabras: para demostrar \( \alpha\rightarrow \beta \) a partir de unas premisas, podemos añadir \( \alpha \) como premisa y deducir \( \beta \). Luego discutiremos por qué es necesario limitar el uso de las reglas \( S_1 \) e \( I_0 \). De momento, y antes de probar el teorema, vamos a ver que estas restricciones hacen que para el uso práctico del teorema de deducción convenga probar esta variante más técnica:

Teorema de deducción (variante) A partir de una deducción

\( \alpha_1,\ldots, \alpha_n, \alpha\mathop{\vdash}\limits_{\rm ARP}\beta \)

en la que no se usen \( S_1 \) ni \( I_0 \) respecto de variables que estén en \( \alpha \) podemos construir una deducción

\( \gamma_1,\ldots, \gamma_r, \alpha_1,\ldots, \alpha_n\mathop{\vdash}\limits_{\rm ARP}\alpha\rightarrow \beta \),

donde \( \gamma_1, \ldots, \gamma_r \) son teoremas de ARP, en la cual sólo se usan las reglas \( S_1 \) e \( I_0 \) respecto de variables respecto a las que ya se usaban estas reglas en la deducción dada o bien respecto de variables que podemos elegir arbitrariamente.

Observemos que esta versión implica la anterior, ya que los teoremas \( \gamma_1,\ldots, \gamma_r \) se pueden suprimir de la lista de premisas incluyendo sus demostraciones en la deducción.

Para entender por qué esta versión es preferible en la práctica a la anterior, antes de demostrar nada, vamos  a ver un uso típico del teorema de deducción. Concretamente, vamos a usarlo para demostrar este teorema:

\( x+z=y+z\rightarrow x=y \)


Comentario de la demostración
La prueba es por inducción sobre \( z \).

Las líneas (1) y (2) son parte de la definición de suma. Más precisamente, si consideramos que en la definición de suma aparece otra variable distinta de \( x, y \), entonces estas líneas se obtienen de aplicar la regla \( S_1 \) a dicha variable.

En la línea (3) añadimos como hipótesis \( x+0=y+0 \) (llamaremos hipótesis a las premisas que luego vayamos a eliminar usando el teorema de deducción). A partir de este punto está prohibido usar las reglas \( S_1 \) e \( I_0 \) respecto de las variables \( x, y \).

Deducimos obviamente (4) por la regla de transitividad y usamos el teorema de deducción para concluir la implicación (5).

En este punto marcamos las líneas (3) y (4) con una raya vertical para indicar que no podemos usarlas en lo sucesivo, pues, ninguna de ellas es un teorema de ARP que hayamos demostrado, sino que parten de la hipótesis provisional (3) que hemos introducido para probar (5).

Notemos que (5) es el caso \( z=0 \) que tenemos que probar para razonar por inducción sobre \( z \).

La línea (6) es la hipótesis de inducción para \( z \), y tenemos que probar que lo mismo vale para \( Sz \) (esto lo obtendremos en la línea (14)). A partir de aquí está prohibido usar las reglas \( S_1 \) e \( I_0 \) respecto de \( x, y, z \).

De cara a probar (14), en la línea (7) tomamos como hipótesis el antecedente de la fórmula que queremos demostrar. Así estamos encajando dos usos del teorema de deducción. Esto nos vuelve a obligar a no usar las reglas prohibidas respecto de \( x, y, z \), pero ya teníamos de antes esta restricción.

Vamos deduciendo (8), (9), (10), y en (11) usamos uno de los axiomas de Peano que hemos demostrado. En (12) usamos \( S_1 \) dos veces, pero respecto de las variables permitidas \( u, v \).

En (13) hemos aplicado dos veces el modus ponens. Con esto termina la segunda aplicación del teorema de deducción, que nos permite escribir la implicación (14). A partir de aquí ya podríamos usar las reglas prohibidas respecto de \( x, y, z \) si no fuera porque todavía estamos dentro de la primera aplicación del teorema de deducción, que sigue prohibiéndolo. En cualquier caso, marcamos las líneas 7-13, pues todas ellas dependen de la hipótesis (7) que ya hemos dejado de suponer.

A su vez, en (15) completamos la primera aplicación del teorema de deducción y así tenemos probada la implicación que exige la regla \( I \). Marcamos las líneas que ya no podemos usar y a partir de este punto ya podemos aplicar cualquier regla de inferencia. En particular podemos usar \( I \) (respecto de \( z) \), que se demuestra usando \( I_0 \), luego hubiera sido incorrecto usarla antes de cerrar los razonamientos hipotéticos auxiliares. El resultado es la línea (16), que es lo que queríamos probar.
[cerrar]

Ahora vamos a razonar que para justificar que los usos que hemos hecho del teorema de deducción son legítimos necesitamos la segunda versión que hemos dado del teorema de deducción. Vamos a razonar en un contexto general, aunque el ejemplo anterior sirve de ilustración.

Uso práctico del teorema de deducción
Imaginemos que estamos construyendo una deducción \( \delta_1,\ldots, \delta_m \) a partir de unas premisas \( \alpha_1,\ldots, \alpha_n \) (que podemos suponer que están incluidas entre las fórmulas \( \delta_i \)). En nuestro ejemplo no tenemos premisas.

En un momento dado añadimos una fórmula \( \alpha \) como hipótesis y continuamos deduciendo sin usar \( S_1 \) ni \( I_0 \) respecto de las variables de \( \alpha \). Esto es lo que hacemos en nuestro ejemplo, por ejemplo en la línea (6).

Luego añadimos \( \alpha' \) como hipótesis y evitamos usar \( S_1 \) e \( I_0 \) respecto de variables en \( \alpha' \) o en \( \alpha \). En nuestro ejemplo hacemos eso en la línea (7) y así llegamos a la línea (13).

En general tenemos una deducción:

\( \delta_1, \ldots, \delta_m, \alpha, \delta_{m+2}, \ldots, \delta_{m+m'}, \alpha', \delta_{m+m'+2}\ldots, \beta'. \)

En este punto aplicamos el teorema de deducción, que nos da una deducción

\( \gamma_1, \ldots, \gamma_r, \delta_1, \ldots, \delta_m,\alpha, \delta_{m+2}, \ldots, \delta_{m+m'}\mathop{\vdash}\limits_{\rm ARP}\alpha'\rightarrow \beta'
 \)
en la que podemos asegurar que no se usa \( S_1 \) ni \( I_0 \) respecto de las variables de \( \alpha \).

Ahora prolongamos esta deducción —y en la práctica marcaremos las líneas comprendidas entre \( \alpha' \) y \( \beta' \) con una línea vertical para indicar que ya no contamos con ellas— sin usar \( S_1 \) ni \( I_0 \) respecto de las variables de \( \alpha \), hasta llegar a

\( \gamma_1, \ldots, \gamma_r, \delta_1, \ldots, \delta_m,\alpha, \delta_{m+2}, \ldots, \beta. \)

Aquí podemos aplicar por segunda vez el teorema de deducción, que nos da una deducción

\( \gamma_1, \ldots, \gamma_{r+r'}, \delta_1, \ldots, \delta_m \mathop{\vdash}\limits_{\rm ARP}\alpha\rightarrow \beta.
 \)

Desde aquí —tras haber marcado las líneas entre \( \alpha \) y \( \beta \)— continuamos deduciendo hasta llegar a

\( \gamma_1, \ldots, \gamma_{r+r'}, \delta_1, \ldots, \delta_m,\ldots, \epsilon \)

y con esto podemos concluir que

\( \alpha_1,\ldots, \alpha_n  \mathop{\vdash}\limits_{\rm ARP}\epsilon, \)

sin más que incorporar a la deducción las demostraciones de los teoremas \( \gamma_i \) y las deducciones de las fórmulas \( \delta_i \) a partir de las premisas.

Así hemos encadenado dos usos del teorema de deducción, pero igualmente podríamos haber encadenado cualquier número de usos. La clave está en que cada vez que lo aplicamos —en virtud del segundo enunciado— podemos asegurar que la deducción que obtenemos no usa las reglas \( S_1 \) e \( I_0 \) respecto de variables prohibidas por las aplicaciones que tenemos pendientes.

Más en general, ahora es claro que no debe preocuparnos insertar un teorema de ARP en una deducción en la que estemos aplicando el teorema de deducción por la posibilidad de que su demostración requiera usos prohibidos de \( S_1 \) o \( I_0 \), pues dicho teorema siempre puede incorporarse a la lista de teoremas \( \gamma_i \) y posponer la inclusión de su demostración hasta el momento en que ya hemos terminado de aplicar el teorema de deducción.

Lo que si tenemos que cuidar es no usar ninguna regla de inferencia derivada que requiera un uso de \( S_1 \) o \( I_0 \) respecto de variables prohibidas. Ciertamente, las reglas \( I_1, I_2 \) o \( I \) esconden un uso \( I_0 \) respecto de la misma variable, por lo que tampoco podemos usarlas respecto de variables prohibidas.

En cambio, no sucede lo mismo con las demás reglas de inferencia que hemos demostrado. En ninguna de ellas se usa \( I_0 \) y sólo se aplica \( S_1 \) a teoremas que podemos incluir en la lista de los \( \gamma_i \) respecto de variables que podemos elegir arbitrariamente.

Por ejemplo, para probar la primera regla del valor absoluto, partiendo de \( s = t \), usamos \( S_2 \) para concluir que \( |s-t| = |s-s| \) y, a partir del teorema \( |x-x|=0 \) (donde la variable \( x \) la elegimos nosotros), por \( S_1 \) obtenemos que \( |s-s|=0 \), y así concluimos \( |s-t|=0 \).

Similarmente, para la segunda regla, si partimos de \( |s-t|=0 \), concluimos \( s=t \) aplicando \( S_1 \) al teorema  \( 0\dot{-} x = 0 \) y a otras propiedades de la resta truncada, pero siempre respecto de variables \( x \) elegidas libremente (pues si un teorema vale para una variable, también es un teorema la fórmula que resulta de sustituirla por otra).

El lector puede comprobar fácilmente que todos los usos de \( S_1 \) en las pruebas de reglas de inferencia que hemos visto (salvo en las de inducción) son de este tipo y, por consiguiente, ninguna de ellas entra en conflicto con el uso del teorema de deducción. Más aún, en el caso de las reglas de inducción, sólo tenemos un uso de \( I_0 \) respecto de la misma variable y, a lo sumo, usos admisibles de \( S_1 \), es decir, aplicaciones de la regla a teoremas respecto de variables que podemos elegir.
[cerrar]

Tengo que continuar en otro mensaje porque, al parecer, éste es ya demasiado largo.

22 Junio, 2023, 12:08 am
Respuesta #11

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Demostración del teorema de deducción
Sea \( \delta_1,\ldots, \delta_m \) una deducción con premisas \( \alpha_1,\ldots, \alpha_n, \alpha \) que termina en \( \delta_m\equiv \beta \) y vamos a ver cómo construir la deducción requerida de \( \alpha\rightarrow \beta \). Sea \( R\equiv 1\dot{-} t_\alpha \), que es un término en el que aparecen las mismas variables que en \( \alpha \).

Pongamos que \( \delta_i\equiv s_i=t_i \), y vamos a demostrar que \( \delta'_i\equiv R\cdot s_i=R\cdot t_i \) es una consecuencia de las premisas para todo \( i \). En particular, para \( i=m \) tendremos probado

\( |R\cdot s_m-R\cdot t_m|=0, \)

de donde, por la propiedad 4 del valor absoluto, se sigue que \( R\cdot |s_m-t_m|=0 \), que es lo mismo que \( (1\dot{-}  t_\alpha)\cdot t_\beta = 0 \), y esto es, por definición, \( \alpha\rightarrow \beta \).

Además comprobaremos que en la deducción de \( \delta'_i \) sólo se usan las reglas \( S_1 \) o \( I_0 \) respecto de variables respecto a las que ya se usaban estas reglas en la deducción de \( \delta_i \) o bien respecto de variables que podemos elegir libremente y teoremas que podemos incorporar a la lista de los \( \gamma_i \).

De hecho, en el paso de \( \delta'_m \) a \( \alpha\rightarrow \beta \) ya hemos necesitado algunas de estas aplicaciones: primero la primera regla del valor absoluto y luego tres aplicaciones de \( S_1 \) a la propiedad 4 del valor absoluto respecto de variables \( x, y, z \) que podemos elegir libremente.

Razonamos inductivamente, es decir, suponemos que tenemos ya deducciones de las fórmulas \( \delta'_j \), para \( j<i \), y vamos a ver cómo construir una deducción de \( \delta'_i \) en las condiciones requeridas. Para ello distinguimos varios casos:

Si \( \delta_i \equiv \alpha \), entonces hay que probar

\( \delta'_i \equiv (1\dot{-}  |s_i-t_i|)\cdot s_i=(1\dot{-}  |s_i-t_i|)\cdot t_i, \)

y esta fórmula se deduce aplicando \( S_1 \) (respecto de variables \( x, y \) elegidas libremente) a la fórmula en verde en el último spoiler de la respuesta #9 (que incluimos entre los teoremas \( \gamma_i \)).

Si \( \delta_i \equiv s_i = t_i \) es un axioma o una premisa \( \alpha_j \), entonces podemos incluir \( \delta_i \) en nuestra deducción (como axioma o premisa) y \( \delta'_i \equiv R\cdot s_i=R\cdot t_i \) se obtiene aplicando la regla \( S_2 \) al término \( R\cdot x \).

Por consiguiente, basta probar que si \( \delta_i \) se sigue de fórmulas anteriores de la deducción mediante una de las cuatro reglas de inferencia primitivas, entonces \( \delta'_i \) puede deducirse de las fórmulas correspondientes de la demostración que estamos construyendo. Equivalentemente, basta probar que cada regla de inferencia sigue siendo válida si sus fórmulas se multiplican por \( R \).

  • Para la regla \( S_1 \) se trata de ver que

    \( \begin{array}{c}
    R\cdot s_1(x)=R\cdot s_2(x)\\
    \hline
    R\cdot s_1(t)=R\cdot s_2(t)
    \end{array} \)

    es una regla de inferencia válida, lo cual es cierto (es un caso particular de \( S_1 \)) siempre y cuando la variable \( x \) no aparezca en \( R \), y esto lo tenemos garantizado por la hipótesis del teorema, ya que las variables de \( R \) son las de la premisa \( \alpha \) y suponemos que en la demostración nunca se usa \( S_1 \) respecto de variables presentes en \( \alpha \). Además, con esto estamos usando \( S_1 \) en la nueva deducción respecto de una variable respecto a la cual ya se usaba \( S_1 \) en la deducción original.

  • Para la regla \( S_2 \) tenemos que demostrar que

    \( \begin{array}{c}
    R\cdot t_1=R\cdot t_2\\
    \hline
    R\cdot s(t_1)=R\cdot s(t_2)
    \end{array} \)

    es una regla de inferencia válida. Vamos a probar, de hecho, el teorema

    \( R\cdot t_1=R\cdot t_2\rightarrow R\cdot s(t_1)=R\cdot s(t_2). \)

    La regla se sigue, entonces, de aplicar MP (y sólo tenemos que incorporar este teorema, y los necesarios para demostrar MP, a la lista de los \( \gamma_i \)). En primer lugar observamos que

    \( R\cdot t_1=R\cdot t_2\rightarrow (R=0\lor t_1=t_2), \)

    pues, por definición de la implicación y la disyunción, se trata de la fórmula

    \( (1\dot{-} |R\cdot t_1-R\cdot t_2|)\cdot  R \cdot |t_1-t_2|, \)

    y, como \( R\equiv 1-t_\alpha \), por la propiedad 4 del valor absoluto, esto equivale a

    \( (1\dot{-}  R\cdot |t_1-t_2|)\cdot R\cdot |t_1-t_2|=0, \)

    que es un caso particular de \( (1\dot{-}  x)\cdot x = 0 \).

    Por otra parte,

    \( R=0\rightarrow R\cdot s(t_1)=R\cdot s(t_2), \)

    \( t_1=t_2\rightarrow R\cdot s(t_1)=R\cdot s(t_2). \)

    La primera implicación se debe a que, por definición, es la fórmula

    \( (1\dot{-}  R)\cdot R\cdot |s(t_1)-s(t_2)|=0 \)

    y sabemos que \( (1\dot{-}  R)\cdot R = 0 \). La segunda es un caso particular del último teorema de la respuesta #9 aplicado al término \( R\cdot z \), donde \( z \) es cualquier variable que no esté en \( R \). Por la regla del dilema concluimos

    \( (R=0\lor t_1=t_2)\rightarrow R\cdot s(t_1)=R\cdot s(t_2), \)

    y la regla del silogismo hipotético aplicada a la fórmula en azul nos da la conclusión.

  • Para la regla \( T \) tenemos que demostrar

    \( \begin{array}{ccc}
    R\cdot t_1=R\cdot t_2&&R\cdot t_1=R\cdot t_3\\
    \hline
    &R\cdot t_2=R\cdot t_3
    \end{array}
     \)
    que no es sino un caso particular de \( T \).

  • Para la regla \( I_0 \) tenemos que probar:

    \( \begin{array}{c}
    R\cdot s_1(0)=R\cdot s_2(0),\ R\cdot s_1(Sx)=R\cdot h(x, s_1(x)),\ R\cdot s_2(Sx)=R\cdot h(x,s_2(x))\\
    \hline
    R\cdot s_1(x)=R\cdot s_2(x)
    \end{array}
     \)
    bajo el supuesto de que la variable \( x \) no está en \( R \).

    Veamos en primer lugar que la regla de inferencia siguiente es válida:

    \( \begin{array}{ccc}
    s_1=t_1&&s_2=t_2\\
    \hline
    &s_1=s_2\rightarrow t_1=t_2
    \end{array}
     \)

    En efecto, por la regla \( S_2 \), de las premisas (aplicando \( S_1 \) a teoremas que incluimos en la lista de los \( \gamma_i \) respecto de variables elegidas libremente) obtenemos

    \( |s_1-s_2|=|t_1-s_2|,\qquad |t_1-s_2|=|t_1-t_2|, \)

    luego por transitividad concluimos que \( |s_1-s_2|=|t_1-t_2| \).

    De aquí, por \( S_2 \),

    \( (1\dot{-}  |s_1-s_2|)\cdot |t_1-t_2|=(1\dot{-}  |s_1-s_2|)\cdot |s_1-s_2|=0, \)

    y esta última fórmula es \( s_1=s_2\rightarrow t_1=t_2 \).

    Por consiguiente, de las premisas de la regla de inducción deducimos

    \( R\cdot h(x, s_1(x))=R\cdot h(x, s_2(x))\rightarrow R\cdot s_1(Sx)=R\cdot s_2(Sx). \)

    Por otra parte, un caso particular del teorema que hemos enunciado en verde más arriba es:

    \( R\cdot s_1(x)=R\cdot s_2(x)\rightarrow R\cdot h(x, s_1(x))=R\cdot h(x, s_2(x)), \)

    y, encadenando las dos implicaciones, por la regla del silogismo hipotético obtenemos

    \( R\cdot s_1(x)=R\cdot s_2(x)\rightarrow R\cdot s_1(Sx)=R\cdot s_2(Sx). \)

    Como también contamos con la premisa \( R\cdot s_1(0)=R\cdot s_2(0) \), la regla de inducción general \( I \) nos permite concluir \( R\cdot s_1(x)=R\cdot s_2(x) \). Como ya hemos señalado, el uso de \( I \) conlleva únicamente un uso de \( I_0 \) respecto de la misma variable a la que se aplicaba \( I_0 \) a la deducción dada y aplicaciones típicas de \( S_1 \) a teoremas que podemos incorporar a la lista de los \( \gamma_i \), luego no hemos incorporado ningún uso de \( I_0 \) respecto de ninguna variable "nueva".
[cerrar]

Vamos a discutir ahora por qué el teorema de deducción necesita restringir el uso de las reglas \( S_1 \) e \( I_0 \) (y, más en general, de todas las reglas de inducción).

En realidad, la justificación irrebatible de que dichas restricciones son necesarias es que si el teorema de deducción fuera cierto sin ellas nos permitiría "demostrar" falsedades.

Ejercicio interesante Dar dos "demostraciones" en ARP de \( 1=0 \) (o algo parecido), la primera que falle únicamente por una aplicación de la regla \( S_1 \) prohibida por el teorema de deducción y la segunda por una aplicación de una regla de inducción prohibida igualmente.

Las observaciones siguientes pueden ayudar a resolver el ejercicio:

Desde un punto de vista semántico, la regla \( S_1 \) afirma que las variables representan números arbitrarios, por lo que lo que vale para un \( x \) vale para cualquier otro término. Sin embargo, cuando tomamos una hipótesis para aplicar el teorema de deducción, las variables que aparecen en ella dejan de ser números arbitrarios y pasan a representar números que cumplen la hipótesis.

Por ejemplo, si consideramos la demostración que hemos usado en el mensaje anterior para ilustrar el uso del teorema de deducción, en la línea (3) hemos supuesto que \( x+0 = y+0 \), y esto no es cierto para todo \( x, y \). No es cierto que cualquier par de números naturales cumplan esa igualdad, por lo que si sustituimos uno de ellos por otro elegido con mala idea, podemos obtener una conclusión falsa, a partir de la cual "demostrar" una implicación falsa (mediante el teorema de deducción mal aplicado) que a su vez nos dé una falsedad obvia, como \( 1 = 0 \).

Lo mismo sucede si aplicamos las reglas de inducción. Por ejemplo, \( I \), que es la más clara, requiere probar que \( \alpha(x)\rightarrow \alpha(Sx) \), para todo número natural \( x \), pero si la variable \( x \) aparece en una hipótesis que estamos suponiendo, entonces \( x \) ya no es un número arbitrario, sino uno que cumple la hipótesis, y puede ocurrir que la implicación \( \alpha(x)\rightarrow \alpha(Sx) \) sea falsa en general, pero verdadera para los \( x \) que cumplen la hipótesis. En tal caso, la premisa de \( I \) no estaría justificada y la aplicación de \( I \) nos puede llevar a una conclusión falsa.

En la práctica, esta restricción sobre el uso de las reglas indicadas la aplican los matemáticos instintivamente cuando distinguen entre variables generales que representan números arbitrarios (las que introducen con expresiones de la forma: "Sean \( x, y \) dos números naturales cualesquiera") y variables particulares (las que introducen con expresiones de la forma: "Tomemos \( x, y \) que cumplan tal cosa").

En el primer caso, si un matemático ha dicho: "Sean \( x, y \) dos números naturales cualesquiera", no tendrá inconveniente en decir luego: "en particular, esto vale para \( y=0 \)" (con lo que está aplicando \( S_1 \)), pero si ha introducido unas variables en la forma "Consideremos dos números que cumplan que \( x \) divide a \( y \)", luego no se le ocurrirá decir: "En particular, esto vale para \( x = 5, y = 7 \)", por lo que él mismo se estará prohibiendo emplear \( S_1 \).

Reducción al absurdo Del teorema de deducción se sigue inmediatamente que en ARP también podemos razonar por reducción al absurdo:

Teorema (Reducción al absurdo)
Si se cumple

\( \alpha_1,\ldots, \alpha_n, \lnot \alpha\mathop{\vdash}\limits_{\rm ARP}\beta\land \lnot\beta \)

y en la deducción no se usan las reglas \( S_1 \) ni \( I_0 \) respecto de variables que aparecen en \( \alpha \), entonces

\( \alpha_1,\ldots, \alpha_n\mathop{\vdash}\limits_{\rm ARP}\alpha. \)

Demostración
Por el teorema de deducción, de \( \alpha_1\ldots, \alpha_n \) se deduce la implicación \( \lnot\alpha\rightarrow (\beta\land \lnot\beta) \), pero \( \lnot(\beta\land\lnot\beta) \) es uno de los teoremas que hemos probado sobre los conectores, luego la regla del modus tollens nos da \( \lnot\lnot\alpha \) y la doble negación nos permite concluir \( \alpha \).
[cerrar]

Igualmente se justifica la variante consistente en suponer \( \alpha \) y concluir \( \lnot\alpha \). Es claro que en la práctica podemos usar este teorema en las mismas condiciones que el teorema de deducción. No es necesario llegar a tener en una misma línea la contradicción \( \beta\land\lnot\beta \), sino que en la práctica basta con que lleguemos a \( \beta \) y \( \lnot\beta \) en dos líneas distintas, ya que siempre podrían juntarse con la regla de introducción del conjuntor.



Nota En esta nota (que no será necesaria posteriormente) vamos a suponer que el lector conoce el cálculo proposicional ordinario, basado en el lenguaje formal \( \mathcal L_{\rm cp} \) que consta de variables proposicionales \( p, q, r,\ldots \) y de los conectores \( \lnot, \land, \lor, \rightarrow, \leftrightarrow \).

Si \( A(p_1,\ldots, p_n) \) es una fórmula de \( \mathcal L_{\rm cp} \) cuyas variables se encuentren entre las indicadas y \( \alpha_1,\ldots, \alpha_n \) son fórmulas de \( \mathcal L_{\rm arp} \), llamaremos \( A(\alpha_1,\ldots, \alpha_n) \) a la fórmula de \( \mathcal L_{\rm arp} \) que resulta de sustituir cada \( p_i \) por \( \alpha_i \) y reinterpretar los conectores como los definidos en \( \mathcal L_{\rm arp} \). Explícitamente:

  • Si \( A\equiv p_i \), entonces \( A(\alpha_1,\ldots, \alpha_n)\equiv \alpha_i \),

  • Si \( A\equiv \lnot B \), entonces \( A(\alpha_1,\ldots, \alpha_n)\equiv \lnot B(\alpha_1,\ldots, \alpha_n) \),

  • Si \( A\equiv B\lor C \), entonces \( A(\alpha_1,\ldots, \alpha_n)\equiv B(\alpha_1,\ldots, \alpha_n)\lor C(\alpha_1,\ldots, \alpha_n) \),

  • Si \( A\equiv B\land C \), entonces \( A(\alpha_1,\ldots, \alpha_n)\equiv B(\alpha_1,\ldots, \alpha_n)\land C(\alpha_1,\ldots, \alpha_n) \),

  • Si \( A\equiv B\rightarrow C \), entonces \( A(\alpha_1,\ldots, \alpha_n)\equiv B(\alpha_1,\ldots, \alpha_n)\rightarrow C(\alpha_1,\ldots, \alpha_n) \),

  • Si \( A\equiv B\leftrightarrow C \), entonces \( A(\alpha_1,\ldots, \alpha_n)\equiv B(\alpha_1,\ldots, \alpha_n)\leftrightarrow C(\alpha_1,\ldots, \alpha_n) \).
donde los conectores a la derecha son los definidos en ARP.

Llamaremos tautologías de ARP a las fórmulas de la forma \( A(\alpha_1,\ldots,\alpha_n) \), donde \( A(p_1,\ldots, p_n) \) es una tautología del cálculo proposicional.

En estos términos, los resultados que hemos probado sobre el cálculo proposicional en ARP permiten probar el teorema siguiente:

Teorema Todas las tautologías son teoremas de ARP.

La prueba se basa en el teorema de completitud del cálculo proposicional, que afirma que todas las tautologías pueden demostrarse formalmente usando únicamente la regla del Modus Ponens tomando como axiomas lógicos las tautologías de los tipos siguientes:

  • \( p\rightarrow (q\rightarrow p) \)
  • \( (p\rightarrow (q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow r)) \)
  • \( (\lnot p\rightarrow \lnot q)\rightarrow (q\rightarrow p) \)
  • \( p\rightarrow p\lor q,\quad q\rightarrow p\lor q \)
  • \( (p\rightarrow r)\rightarrow ((q\rightarrow r)\rightarrow (p\lor q \rightarrow r)) \)
  • \( p\rightarrow (q\rightarrow p\land q)) \)
  • \( p\land q\rightarrow p,\qquad p\land q\rightarrow q \)
  • \( (p\rightarrow q)\rightarrow((q\rightarrow p)\rightarrow (p\leftrightarrow q)) \)
  • \( (p\leftrightarrow q)\rightarrow (p\rightarrow q),\qquad(p\leftrightarrow q)\rightarrow (q\rightarrow p) \)
Ahora bien, con lo visto en los últimos mensajes todas las fórmulas de ARP de la forma \( A(\alpha_1, \ldots, \alpha_n) \), donde \( A \) es uno de los axiomas lógicos anteriores son demostrables en ARP (comprobarlo es un ejercicio saludable) y es claro que una demostración en el cálculo proposicional de una tautología \( A(p_1,\ldots, p_n) \) da lugar a una demostración en ARP de la tautología \( A(\alpha_1,\ldots, \alpha_n) \), pues los axiomas de la demostración se transforman en teoremas de ARP y si una fórmula se deduce por MP de dos anteriores, su fórmula correspondiente en ARP también se deduce por MP en ARP de las fórmulas correspondientes a las premisas.



Ejercicio Demostrar en ARP los teoremas siguientes:
  • \( x=0\lor x=S(x\dot{-} 1) \).
  • \( x+z=y+z\rightarrow x=y \).
  • \( x+y=0\leftrightarrow x=0\land y=0 \).
  • \( xy=0\leftrightarrow x=0\lor y=0 \).
1) se prueba por inducción sobre \( x \).

2) lo hemos tomado como ejemplo de uso del teorema de deducción (sería un sano ejercicio dar pruebas de los demás apartados con el mismo nivel de detalle que hemos dado para el caso de 2).

3) se prueba naturalmente usando 1) y el primer axioma de Peano (aunque ya hemos usado este hecho anteriormente valiéndonos de una demostración artificiosa).

4) se prueba fácilmente usando 1) y 3).

23 Junio, 2023, 07:28 pm
Respuesta #12

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Una forma habitual de definir formalmente la relación de orden usual entre números naturales en contextos aritméticos es

\( x \leq y \equiv \exists z x+z = y \).

No podemos hacer esto literalmente en ARP, porque no contamos con el cuantificador existencial \( \exists \), pero esto es más aparente que real. El hecho de que en ARP no tengamos un signo \( \exists \) no significa que no podamos formular enunciados de existencia, sino que nos vemos obligados a describir explícitamente el número que afirmamos que existe (ARP nos fuerza a la constructividad, y eso puede verse como una virtud).

Por ejemplo, en este caso, el número \( z \) que atestigua que \( x \) es menor o igual que \( y \) es necesariamente \( z = y\dot{-} x \), por lo que podemos adoptar esta definición:

Definición \( x\leq y\equiv x + (y\dot{-} x) = y \).

En este mensaje doy las propiedades básicas de la relación de orden, que el lector puede tratar de probar por sí mismo sin abrir los spoilers.

A partir de aquí nos limitaremos a esbozar las demostraciones como se hace en cualquier libro de matemáticas no dedicado concretamente a la lógica, es decir, no detallaremos los usos de las reglas \( S_1, S_2 \) y \( T \) que permiten justificar las manipulaciones obvias con igualdades, usaremos tácitamente cualquier tautología o cualquier regla de inferencia lógica del cálculo proposicional que necesitemos, etc.

Transformar estos esbozos de demostración en demostraciones detalladas es una tarea que el lector debería ver como tediosa, pero sin dificultad. Si no es así, si alguien considera dudoso que un argumento dado puede formalizarse en APR usando de forma rutinaria los recursos que hemos presentado hasta ahora, sería interesante discutirlo en el hilo de comentarios.

  • \( x\leq x+y \).
    Por la propiedad 6 de la resta truncada.

    Observemos que esta propiedad expresa esencialmente un cuantificador existencial. Lo que dice aquí es que si existe un \( y \) tal que \( z = x+y \), entonces \( x\leq z \).

  • \( x\leq x \).
    Obvio.

  • \( x\leq y\land y\leq x\rightarrow x=y \).

    Demostración
    Tenemos que \( x+(y\dot{-} x)=y \), \( y+(x\dot{-}  y)=x \), luego

    \( x+(y\dot{-}  x)+(x\dot{-}  y)=x, \)

    luego \( (y\dot{-}  x)+(x\dot{-}  y)=0 \), luego \( x\dot{-}  y=0=y\dot{-}  x \) (por el apartado 3 del ejercicio del mensaje anterior), luego

    \( x = x+(y\dot{-} x) = y. \)
    [cerrar]
  • \( x\leq y\land y\leq z\rightarrow x\leq z \).

    Demostración
    Tenemos \( x+(y\dot{- } x)=y \), \( y+(z\dot{-} y)=z \), luego

    \( x+(y\dot{-}  x)+(z\dot{-}  y)=z, \)

    luego \( x\leq z \) por el apartado 1.
    [cerrar]
  • \( 0\leq x \).
    Obvio.

  • \( x\leq Sx \).

    Spoiler
    \( x+(Sx\dot{-}  x) = x+((x+1)\dot{-}  x) = x+1=Sx \).
    [cerrar]
  • \( x\leq y\lor y\leq x \).

    Por inducción sobre \( y \).
    Spoiler
    Para \( y=0 \) es claro. Si vale para \( y \), en el caso \( x\leq y \) tenemos \( x\leq y\leq Sy \), mientras que si \( y\leq x \), entonces \( y+(x\dot{-}  y)=x \). Si \( x\dot{-}  y=0 \), entonces \( y=x \) y \( x\leq Sy \). Si \( x\dot{-}  y\neq 0 \), entonces, por el primer apartado del ejercicio del mensaje anterior, \( y+S((x\dot{-}  y)\dot{-}  1))=x \), luego \( Sy+((x\dot{-}  y)\dot{-}  1)=x \), luego \( Sy\leq x \) por el apartado 1.
    [cerrar]
  • \( y\leq Sx\leftrightarrow y\leq x\lor y=Sx \).

    Spoiler
    Si \( y\leq Sx \), entonces \( y+(Sx\dot{-}  y)=Sx \). Si \( Sx\dot{-}  y=0 \), queda \( y=Sx \) y, en caso contrario, \( y+S((Sx\dot{-}  y)\dot{-}  1)=Sx \), luego \( y+((Sx\dot{-}  y)\dot{-}  1)=x \), luego \( y\leq x \), por el apartado 1.

    Si \( y\leq x\lor y=Sx \), en el segundo caso es claro que \( y\leq Sx \), mientras que en el primero \( y+(x\dot{-}  y)=x \), luego \( y+S(x\dot{-}  y)=Sx \), luego \( y\leq Sx \), de nuevo por el apartado 1.
    [cerrar]
  • \( x\leq y\leftrightarrow x+z\leq y+z \).

    Spoiler
    Si \( x\leq y \), entonces \( x+(y\dot{-}  x)=y \), luego \( x+z+(y\dot{-}  x)=y+z \), luego \( x+z\leq y+z \) por el apartado 1.

    Si \( x+z\leq y+z \), entonces \( x\leq y\lor y\leq x \), pero si se da el segundo caso, por la parte ya probada, \( y+z\leq x+z \), luego \( x+z=y+z \), luego \( x=y \), luego \( x\leq y \).
    [cerrar]
  • \( z\neq 0\land xz=yz\rightarrow x=y \).

    Spoiler
    Podemos suponer que \( x\leq y \). Entonces \( x+(y\dot{-}  x)=y \), luego

    \( xz+(y\dot{-}  x)z = yz = xz, \)

    luego \( (y\dot{-}  x)z=0 \), luego, por el apartado 4 del ejercicio del mensaje anterior, \( y\dot{-}  x=0 \), luego \( x=y \).
    [cerrar]
  • \( x\leq y\rightarrow xz\leq yz \).

    Spoiler
    \( x+(y\dot{-}  x)=y \), luego \( xz+(y\dot{-}  x)z=yz \), luego \( xz\leq yz \).
    [cerrar]
  • \( z\neq 0\land xz\leq yz\rightarrow x\leq y \).

    Spoiler
    Se cumple \( x\leq y\lor y\leq x \), pero en el segundo caso \( yz\leq xz \), luego \( yz=xz \), luego \( y=x \), luego \( x\leq y \).
    [cerrar]

Definimos \( x<y\equiv x\leq y\land x\neq y \). Las propiedades obvias de esta relación se deducen inmediatamente de las propiedades correspondientes de \( \leq \) y de las del igualador.

Ahora podemos precisar 6 y afirmar que \( x <Sx \), pues si fuera \( x = Sx = x+1 \), sería \( 0 = 1 = S0 \), en contradicción con el primer axioma de Peano.

Observemos que 5 expresa que \( 0 \) es el menor número natural, mientras que 8 expresa que \( Sx \) es el siguiente de \( x \) en el sentido de que es el menor número natural mayor que \( x \).

De las propiedades de la relación de orden que hemos demostrado se siguen ya sin dificultad todas las propiedades elementales de uso habitual, como \( x\leq y\land x'\leq y'\rightarrow x+x'\leq y+y' \), etc.

27 Junio, 2023, 09:19 pm
Respuesta #13

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahora estamos en condiciones de extender la lógica de ARP:

Definición Si \( \alpha\equiv s_1=s_2 \) es una fórmula de \( \mathcal L_{\rm arp} \) cuyas variables estén entre \( x_1,\ldots, x_n \), definimos el funtor \( \chi_\alpha\equiv\chi[\alpha] \) dado por

\( \chi_\alpha(x_1,\ldots, x_n)=1\dot{-} t_\alpha\equiv 1\dot{-} |s_1-s_2|. \)

La identidad  \( \chi_\alpha\equiv\chi[\alpha] \) significa que normalmente escribiremos \( \chi_\alpha \), pero cuando queramos poner una fórmula explícita y sea engorroso ponerla como subíndice escribiremos \( \chi[\alpha] \).

Así, teniendo en cuenta las reglas de inferencia enunciadas al principio de la respuesta #9, se cumple que

\( \chi_\alpha(x_1,\ldots, x_n)=1\leftrightarrow \alpha(x_1,\ldots, x_n), \)

\( \chi_\alpha(x_1,\ldots, x_n)=0\leftrightarrow \lnot\alpha(x_1,\ldots, x_n). \)

Dada una fórmula \( \alpha(x_1,\ldots, x_n,x) \), consideramos el funtor definido por las ecuaciones

\( M_\alpha(x_1,\ldots, x_n,0)=\chi_\alpha(x_1,\ldots, x_n,0), \)

\( M_\alpha(x_1,\ldots, x_n, Sx)=M_\alpha(x_1,\ldots, x_n, x)+\chi[M_\alpha(x_1,\ldots, x_n, x)=0\land \chi_\alpha(x_1,\ldots, x_n,Sx)=1]\cdot(x+2). \)

Notemos que —abreviando \( x_1,\ldots, x_n \) como \( \bar x \)— la sucesión

\( M_\alpha(\bar x, 0),\quad M_\alpha(\bar x, 1),\quad M_\alpha(\bar x, 2),\quad\ldots \)

toma el valor \( 0 \) hasta que aparece el primer \( x \) que cumple \( \alpha(\bar x, x) \), y a partir de ese momento toma el valor \( x+1 \).

Definimos
\( \exists u\leq x\,\alpha(x_1,\ldots, x_n,u)\equiv M_\alpha(x_1,\ldots, x_n, x)\neq 0, \)

\( \forall u\leq x\,\alpha(x_1,\ldots, x_n, u)\equiv \lnot\exists u\leq x\,\lnot\alpha(x_1,\ldots, x_n, u), \)

\( \mu u\leq x\,\alpha(x_1,\ldots, x_n, u)\equiv M_\alpha(x_1,\ldots, x_n, x)\dot{-} 1. \)

\( \exists! u\leq x\alpha(x_1,\ldots, x_n, u)\equiv\exists u\leq x\,\alpha(x_1,\ldots, x_n,u)\land \)

\( \forall u\leq x\forall v\leq x(\alpha(x_1,\ldots, x_n,u)\land\alpha(x_1,\ldots, x_n,v)\rightarrow u = v). \)

Notemos que, a pesar de la notación que empleamos, ninguna de cuatro expresiones anteriores contiene la variable \( u \).

Las consideraciones precedentes muestran que se cumple

\( \vDash \exists u\leq x\,\alpha(x_1,\ldots, x_n,u)[v] \)

si y sólo si existe un número natural \( m\leq v(x) \) tal que \( \vDash \alpha[v_u^m] \), de modo que una transcripción al español de

\( \exists u\leq x\,\alpha(x_1,\ldots, x_n,u) \)
es
Existe un número natural \( u\leq x \) que cumple \( \alpha(x_1,\ldots, x_n,u) \).

Por consiguiente
\( \forall u\leq x\,\alpha(x_1,\ldots, x_n, u) \)

es "No existe un \( u\leq x \) que no cumpla \( \alpha(x_1,\ldots, x_n,u) \).", que es lo mismo que

Para todo número natural \( u\leq x \) se cumple \( \alpha(x_1,\ldots, x_n,u) \).

Esto implica a su vez que \( \exists! u\leq x\alpha(x_1,\ldots, x_n, u) \) significa:

Existe un único \( u\leq x \) que cumple \( \alpha(x_1,\ldots, x_n,u) \).

Por último, es claro que \( N(\mu u\leq x\,\alpha(x_1,\ldots, x_n, u))[v] \) es el mínimo número natural \( m\leq v(x) \) que cumple \( \vDash \alpha[v_u^m] \), o bien \( 0 \) si no existe tal mínimo.

Pero esto es sólo el significado que tienen las fórmulas y el término que acabamos de definir.
Ahora vamos a ver que podemos demostrar los hechos que cabe esperar. En los resultados siguientes escribiremos \( \alpha(x) \) en lugar de \( \alpha(x_1,\ldots, x_n, x) \), de modo que no supondremos que \( x \) es la única variable de \( \alpha \).

  • \( \mu u\leq x\,\alpha(u)\leq x \).

    Demostración
    Por inducción sobre \( x \). Para \( x=0 \) tenemos que

    \( \mu u\leq 0\,\alpha(u)=M_\alpha(0)\dot{-} 1=\chi_\alpha(0)\dot{-} 1=0\leq 0, \)

    pues \( \chi_\alpha(0) \) sólo puede valer \( 0 \) o \( 1 \).

    Si vale para \( x \), distinguimos dos casos:

    Si \( M_\alpha(x)\neq 0 \), entonces \( M_\alpha(Sx)=M_\alpha(x) \), luego

    \( \mu u\leq Sx\, \alpha(u)=\mu u\leq x\,\alpha(u)\leq x\leq Sx. \)

    Si \( M_\alpha(x)=0 \), entonces

    \( M_\alpha(Sx)=\chi[M_\alpha(x)=0\land \chi_\alpha(Sx)=1]\cdot(x+2)\leq x+2, \)

    luego \( \mu u\leq Sx\,\alpha(u)=M_\alpha(Sx)\dot{-} 1\leq (x+2)\dot{-} 1=Sx \).
    [cerrar]
  • \( y\leq x\land \alpha(y)\rightarrow (\exists u\leq x\,\alpha(u)\land\mu u\leq x\,\alpha(u)\leq y) \).

    Demostración
    Por inducción sobre \( x \). Para \( x=0 \) tenemos \( y=0 \), \( \alpha(0) \), luego

    \( M_\alpha(0)=\chi_\alpha(0)=1\neq 0 \),

    luego \( \exists u\leq 0\,\alpha(0) \). Además, \( \mu u\leq 0\,\alpha(u)= M_\alpha(0)\dot{-} 1 = 1\dot{-} 1 = 0 \), luego \( \mu u\leq 0\,\alpha(u)\leq y \).

    Supuesto para \( x \), si \( y\leq Sx\land \alpha(y) \), o bien \( y\leq x \) o bien \( y=Sx \). En el primer caso, por hipótesis de inducción, \( \exists u\leq x\,\alpha(u) \), es decir, \( M_\alpha(x)\neq 0 \), luego \( M_\alpha(Sx)\neq 0 \), luego también se cumple \( \exists u\leq Sx\,\alpha(u) \).

    Además, \( M_\alpha(Sx)=M_\alpha(x) \), luego \( \mu u\leq Sx\,\alpha(u)=\mu u\leq x\,\alpha(u)\leq y \).

    Si \( y=Sx \), tenemos \( \chi_\alpha(Sx)=1 \) luego, o bien \( M_\alpha(x)\neq 0 \), o bien

    \( \chi[M_\alpha(x)=0\land \chi_\alpha(Sx)=1]\cdot(x+2)\neq 0, \)

    y en ambos casos \( M_\alpha(Sx)\neq 0 \), luego \( \exists u\leq Sx\,\alpha(u) \).

    Si \( M_\alpha(x)\neq 0 \), entonces \( M_\alpha(Sx)=M_\alpha(x) \), luego

    \( \mu u\leq Sx\,\alpha(u)=\mu u\leq x\,\alpha(u)\leq x\leq Sx. \)

    Si \( M_\alpha(x)=0 \), entonces

    \( M_\alpha(Sx)=\chi[M_\alpha(x)=0\land \chi_\alpha(Sx)=1]\cdot(x+2)=x+2, \)

    luego \( \mu u\leq Sx\,\alpha(u) =Sx\leq y \).
    [cerrar]
  • \( \exists u\leq x\,\alpha(u)\rightarrow \alpha(\mu u\leq x\,\alpha(u)) \).

    Demostración
    Por inducción sobre \( x \). Para \( x=0 \) tenemos \( \chi_\alpha(0)=M_\alpha(0)\neq 0 \), luego se cumple \( \alpha(0) \) y además \( \mu u\leq 0\,\alpha(u)= M_\alpha(0)\dot{-} 1=1\dot{-} 1 = 0 \), luego se cumple \( \alpha(\mu u\leq 0\,\alpha(u)) \).

    Si vale para \( x \) y \( \exists u\leq Sx\,\alpha(u) \), entonces \( M_\alpha(Sx)\neq 0 \). Distinguimos dos casos:

    Si \( M_\alpha(x)\neq 0 \), entonces \( \exists u\leq x\,\alpha(u) \), luego por hipótesis de inducción \( \alpha(\mu u\leq x\,\alpha(u)) \). Además \( \mu u\leq x\,\alpha(u)=M_\alpha(x)\dot{-} 1 \). En este caso \( M_\alpha(Sx)=M_\alpha(x) \), luego \( \mu u\leq Sx\,\alpha(u)=\mu u\leq x\,\alpha(u) \), luego \( \alpha(\mu u\leq Sx\,\alpha(u)) \).

    Si \( M_\alpha(x)=0 \), necesariamente

    \( \chi[M_\alpha(x)=0\land \chi_\alpha(Sx)=1]\cdot(x+2)\neq 0, \)

    luego \( \chi_\alpha(Sx)=1 \), luego se cumple \( \alpha(Sx) \). Además

    \( M_\alpha(Sx)=\chi[M_\alpha(x)=0\land \chi_\alpha(Sx)=1]\cdot(x+2)=x+2, \)

    luego \( \mu u\leq Sx\,\alpha(u)=(x+2)\dot{-} 1=Sx \), luego \( \alpha(\mu u\leq Sx\,\alpha(u)) \).
    [cerrar]

    Recapitulando lo que hemos obtenido, por una parte podemos introducir el particularizador y el mínimo así:

    \( y\leq x\land \alpha(y)\rightarrow (\exists u\leq x\, \alpha(u)\land \mu u\leq x \alpha(u)\leq y\land \alpha(\mu u\leq x\,\alpha(u)))
     \)

    y, por otra, podemos eliminar el particularizador así:

    \( \exists u\leq x\,\alpha(u)\rightarrow (\mu u\leq x \alpha(u)\leq x\land \alpha(\mu u\leq x\,\alpha(u))). \)

    Para el cuantificador universal tenemos, por una parte la eliminación:

  • \( y\leq x\land \forall u\leq x\,\alpha(u)\rightarrow \alpha(y) \).

    Demostración
    Si  \( y\leq x\land \forall u\leq x\,\alpha(u) \) y \( \lnot \alpha(y) \), entonces \( \exists u\leq x\,\lnot\alpha(u) \), luego \( \lnot \forall u\leq x\,\alpha(u) \) y tenemos una contradicción.
    [cerrar]

    Mientras que la introducción del generalizador tiene que formularse como regla de inferencia:

  • Regla de Introducción del Generalizador:
    \( {\rm (IG)}\ \begin{array}{c}
    y\leq x\rightarrow \alpha(y)\\
    \hline
    \forall u\leq x\,\alpha(u)
    \end{array}
     \)

    Demostración
    Si suponemos la premisa, pero negamos la conclusión, tenemos que \( \exists u\leq x\,\lnot\alpha(u) \), luego \( \mu u\leq x\,\lnot\alpha (u)\leq x \) y \( \lnot\alpha(\mu u\leq x\, \lnot\alpha(u)) \), pero aplicando la regla \( S_1 \) a la variable \( y \) en la premisa, obtenemos \( \alpha(\mu u\leq x\,\lnot\alpha(u)) \) y tenemos una contradicción.

    Esta aplicación de \( S_1 \) respecto de una variable que aparece en la premisa hace que no podamos aplicar el teorema de deducción para concluir la implicación
    \( (y\leq x\rightarrow \alpha(y))\rightarrow \forall u\leq x\,\alpha(u) \)

    Por el mismo motivo, no es lícito usar IG si estamos usando el teorema de deducción y no podemos usar \( S_1 \) respecto de la variable \( y \).

    Ejercicio Deducir una contradicción de este falso teorema, y también usando IG ilegítimamente en una aplicación del teorema de deducción.
    [cerrar]

Podemos considerar también las variantes

\( \forall u<x\,\alpha(u)\equiv \forall u\leq x(u<x\rightarrow \alpha(u)), \)

\( \exists u<x\,\alpha(u)\equiv \exists u\leq x(u<x\land \alpha(u)), \)

y a partir de los resultados ya probados es fácil probar que cumplen los resultados obvios que cabe esperar que cumplan.

Inducción completa Ahora es fácil probar la regla de inducción completa:

\( \begin{array}{c}
\forall u<x\,\phi(u)\rightarrow \phi(x)\\
\hline
\phi(x)
\end{array}
 \)

Demostración
Probamos por inducción \( \psi(x)\equiv \forall u<x\,\phi(u) \). Se cumple trivialmente para \( x=0 \) y, si vale para \( x \), por la premisa de la regla, tenemos \( \phi(x) \), de donde se deduce claramente que \( \forall u<Sx\, \phi(u) \).

Con esto tenemos probado \( \psi(x) \), luego en particular se cumple \( \psi(Sx)\equiv \forall u<Sx\,\phi(u) \), luego haciendo \( u=x \) obtenemos \( \phi(x) \).
[cerrar]

Observemos que, como la regla de inducción completa se prueba por inducción sobre la variable \( x \), no será lícito usarla en contextos en los que el teorema de deducción prohíba usar \( I_0 \) respecto a \( x \).

Con esto tenemos ya completamente expuesta la lógica de la Aritmética Recursiva Primitiva. En los próximos mensajes veremos algunos ejemplos de lo que podemos hacer con ella.

30 Junio, 2023, 01:47 pm
Respuesta #14

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Veamos algunos ejemplos sencillos de lo que supone trabajar en ARP. Probar las propiedades básicas de la suma y el producto nos ha dado un poco de guerra porque todavía no teníamos plenamente desarrollada la lógica de ARP, por lo que conviene comparar con lo que cuesta ahora estudiar la potenciación.

A partir de ahora ya no escribiremos nunca \( St \), sino que en su lugar escribiremos \( t+1 \), puesto que la fórmula \( Sx = x+1 \) es un teorema de ARP que nos permite transformar cualquier expresión que contenga un término \( St \) por la que resulta de sustituirlo por \( t+1 \), y viceversa.

Potenciación Con lo que sabemos de ARP, para definir la potenciación de números naturales basta con definirla como el funtor diádico determinado por las fórmulas

\( x^0 = 1,\qquad x^{y+1} = x^y\cdot x \)

Sabemos que estas ecuaciones son ciertamente la definición de un funtor de ARP, y las propiedades siguientes se demuestran fácilmente por inducción, sin necesidad de ninguna idea específica de ARP, es decir, con los mismos argumentos con los que podemos verlas demostradas en cualquier libro que exponga la aritmética elemental:

  • \( x^{y+z}=x^yx^z \),
  • \( (xy)^z=x^zy^z \),
  • \( (x^y)^z = x^{yz} \),
  • \( x>0\rightarrow 0^x=0 \),
  • \( 1^x =x \),
  • \( x\leq y\rightarrow x^z\leq y^z \),
  • \( x\geq 1\land y\leq z\rightarrow x^y\leq x^z \),
  • \( x\geq 2\rightarrow y< x^y \).
Veamos la última como ejemplo:

Demostración
Razonamos por inducción sobre \( y \). Para \( y=0 \) es inmediato. Supuesto cierto para \( y \), o bien \( y=0 \), en cuyo caso se cumple que \( y+1=1< x=x^1=x^{y+1} \), o bien \( y\geq 1 \), en cuyo caso

\( x^{y+1}=x^y\cdot x \geq x^y\cdot 2> y\cdot 2=y+y\geq y+1. \)
[cerrar]

División euclídea El teorema de la división euclídea dice que, para todo dividendo \( D \) y todo divisor \( d\neq 0 \), existen un único cociente \( c \) y un único resto \( r \) tales que \( D = dc+r \) y \( 0\leq r<d \).

El problema a la hora de formalizar esto en ARP es que no podemos formalizar el "existen". Ahora bien, esto tiene dos soluciones posibles. Una es observar que, necesariamente, \( c\leq D \) y \( r<d \), por lo que podemos formalizar la existencia como \( \exists c\leq D \exists r\leq d \). En general, para enunciar un teorema de existencia en ARP tenemos que ser capaces de acotar los números que queremos probar que existen.

Pero en realidad podemos hacer algo más fino, y es definir funtores que calculen explícitamente los números cuya existencia queremos probar. Vamos a emplear esta estrategia. Para ello definimos los funtores diádicos:

\( c(D, d)=\mu u\leq D\, D<d(u+1),\qquad r(D, d)=D\dot{-} d\cdot c(D, d) \),

y con ellos vamos a probar el teorema siguiente. Notemos que la primera afirmación es la existencia del cociente y el resto euclídeos y la segunda es la unicidad:

Teorema 1) \( d\neq 0\rightarrow D = d\cdot c(D, d)+r(D, d)\land r(D, d)<d \).

2) \( d\neq 0\land D = d\cdot c+ r\land r<d\rightarrow c = c(D, d)\land r = r(D, d) \).

Demostración
1) Como \( d\neq 0 \), tenemos que \( 1\leq d \), luego

\( D\leq dD<dD+d=d(D+1), \)

y esto prueba que \( \exists u\leq D\,D<d(u+1) \), luego \( D<d\cdot (c(D, d)+1) \). Tiene que ser \( d\cdot c(D, d)\leq D \), pues si fuera \( D<d\cdot c(D,d) \), entonces \( c(D, d)\neq 0 \), luego, llamando \( c'\equiv c(D, d)\dot{-} 1 \), se cumpliría \( c(D, d)=c'+1 \), luego \( c'<c(D, d) \) y \( D<d\cdot (c'+1) \), en contra de la minimalidad de \( c(D,d) \). Así pues:

\( d\cdot c(D, d)\leq D<d\cdot (c(D, d)+1). \)

Por la definición de \( \leq \), la primera desigualdad implica que

\( D=d\cdot c(D, d)+r(D,d). \)

Tiene que ser \( r(D, d)<d \), pues si \( d\leq r(D, d) \), entonces

\( d+(r(D, d)\dot{-} d)=r(D, d) \)

y así

\( D=d\cdot c(D, d)+d+(r(D, d)\dot{-} d)=d\cdot (c(D, d)+1)+(r(D, d)\dot{-} d), \)

luego \( d\cdot (c(D, d)+1)\leq D \), contradicción.

2) Tenemos que \( dc\leq D=dc+r<dc+d=d(c+1) \), luego la minimalidad de \( c(D, d) \) implica que \( c(D, d)\leq c \). Si la desigualdad fuera estricta, \( c(D, d)+1\leq c \), luego

\( D<d(c(D, d)+1)\leq dc\leq dc+r=D, \)

y tenemos una contradicción. Por lo tanto, \( c=c(D, d) \), y como

\( d\cdot c(D, d)+r(D, d)=D=d\cdot c+r=d\cdot c(D, d)+r, \)

también \( r=r(D, d) \).
[cerrar]

Por ejemplo, ahora podemos clasificar a los números naturales en pares e impares, según si \( r(D, 2)=0 \) o \( r(D, 2)=1 \). Equivalentemente, por la unicidad de la división euclídea, los números pares son los de la forma \( 2n \) y los impares los de la forma \( 2n+1 \). Es fácil probar que
\( r(ab,2)=r(a, 2)r(b, 2), \)

de modo que el producto de par por par o par por impar es par, mientras que el producto de impares es impar.

Pares ordenados Ahora podemos formalizar la definición de par ordenado que dimos en este mensaje. Informalmente, el par ordenado \( \left<x, y\right>_2 \) determinado por dos números naturales \( x,y \) es el número natural

\( \left<x, y \right>_2 =  \dfrac{(x+y)(x+y+1)}2+x \).

La formalización en ARP es ahora muy simple:

Definición Consideramos el funtor definido por:

\( \left<x, y\right>_2=c\bigl((x+y)(x+y+1), 2\bigr)+x. \)

Claramente, el dividendo en el funtor cociente euclídeo es el producto de un número par por uno impar, por lo que la división es exacta, es decir, \( r\bigl((x+y)(x+y+1), 2\bigr)=0 \), por lo que el teorema de la división euclídea nos da que

\( 2\left<x, y\right>_2=(x+y)(x+y+1)+2x.  \)

Observemos ahora que

\( (z+1)(z+2)=z^2+3z+2\geq 2z+2>2z. \)

Por lo tanto, si definimos el funtor

\( F(z)=\mu u\leq z+1\ (2z<u(u+1)), \)

tenemos que \( z+1 \) cumple la propiedad considerada, luego

\( 2z<F(z)(F(z)+1)\qquad \mbox{y}\qquad F(z)\leq z+1. \)

No puede ser \( F(z)=0 \), luego si definimos \( G(z)=F(z)\dot{-} 1 \), se cumple que \( F(z)=G(z)+1 \) y, como \( G(z)<F(z) \), no puede cumplir la propiedad que define a \( F \), luego

\( G(z)(G(z)+1)\leq 2z<(G(z)+1)(G(z)+2),\qquad G(z)\leq z. \)

Observemos además que si un \( r \) cumple

\( r(r+1)\leq 2z<(r+1)(r+2), \)

necesariamente \( r=G(z) \), pues por la minimalidad de \( F \) tenemos \( F(z)\leq r+1 \), luego \( G(z)\leq r \) y, si la desigualdad fuera estricta, \( G(z)+1\leq r \), luego

\( (G(z)+1)(G(z)+2)\leq r(r+1)\leq 2z, \)

y tenemos una contradicción. Definimos el funtor

\( z_1=c\bigl(2z\dot{-} G(z)(G(z)+1),2\bigr). \)

Es fácil ver que el argumento de \( c \) es par, por lo que

\( 2z=G(z)(G(z)+1)+2z_1 \).

Además se cumple que \( z_1\leq G(z) \), pues si fuera \( G(z)<z_1 \), entonces

\( 2G(z)<2z_1=2z\dot{-} G(z)(G(z)+1), \)

luego \( 2G(z)+G(z)(G(z)+1)<2z \), luego \( G(z)^2+3G(z)+1\leq 2z \). Otra vez, distinguiendo casos según si \( G(z) \) es par o impar, se comprueba que el miembro izquierdo siempre es impar, por lo que no puede darse la igualdad, luego

\( (G(z)+1)(G(z)+2)=G(z)^2+3G(z)+2\leq 2z, \)

en contradicción con la construcción de \( G \).

Por lo tanto, \( z_1\leq G(z) \), luego el funtor

\( z_2=G(z)\dot{-} z_1 \)

cumple \( G(z)=z_1+z_2 \) y

\( 2z=G(z)(G(z)+1)+2z_1=(z_1+z_2)(z_1+z_2+1)+2z_1=2\left<z_1,z_2\right>_2, \)

luego \( z=\left<z_1,z_2\right>_2 \).

El teorema siguiente recoge las propiedades que hemos demostrado de los funtores \( \left<x,y\right>_2 \), \( z_1 \) y \( z_2 \) junto con algunas más:

Teorema Se cumple:
  • \( z=\left<z_1,z_2\right>_2 \),
  • \( z_1+ z_2\leq z \),
  • \( z=\left<x, y\right>_2\rightarrow x=z_1\land y=z_2 \).
Demostración
Ya hemos demostrado la primera afirmación, y también la segunda, pues hemos visto que \( z_1+z_2 = G(z)\leq z \).

Si \( z=\left<x, y\right>_2 \), llamando \( r=x+y \), tenemos que \( 2z=r(r+1)+2x \), con \( x\leq r \), luego

\( r(r+1)\leq 2z\leq r^2+r+2x\leq r^2+3r<r^2+3r+2=(r+1)(r+2), \)

y antes hemos probado que esto implica \( r=G(z)=z_1+z_2 \), luego

\( (z_1+z_2)(z_1+z_2+1)+2z_1=2z=r(r+1)+2x \)

implica que \( 2x=2z_1 \), luego \( x=z_1 \), y entonces \( z_1+z_2=x+y \) implica que \( y=z_2 \).
[cerrar]

Con esto hemos probado que cada número natural \( z \) se expresa de forma única como un par \( \left<z_1,z_2\right>_2 \) de números naturales. Tanto la función que a cada par de números naturales le asigna el número \( \left<z_1,z_2\right>_2 \) como las proyecciones que a cada \( z \) le asignan sus coordenadas \( z_1 \) y \( z_2 \) son funciones recursivas primitivas.

Sucesiones finitas Ahora podemos formalizar la codificación de las sucesiones finitas de números naturales expuesta en este mensaje.

Concretamente, podemos considerar el funtor

\( \left<x, y, z\right>_3=\left<\left<x, y\right>_2, z\right>_2 \)

y las proyecciones \( z^3_1=(z_1)_1 \), \( z^3_2=(z_1)_2 \), \( z^3_3=z_2 \), de modo que

\( z=\left<z_1,z_2,z_3\right>,\qquad z = \left<u, v, w\right>_3\rightarrow u = z_1\land v=z_2\land w=z_3. \)

Así, podemos identificar los números naturales con las ternas de números naturales. En general, podemos definir los funtores

\( \left<x_1,\ldots, x_n\right>_n=\left<\left<x_1,\ldots, x_{n-1}\right>_{n-1},x_n\right>_2 \)

y las proyecciones

\( p^n_i(z)=p^{n-1}_i(z_1) \),   para \( i<n \),
\( p^n_n(z)=z_2 \).

Si definimos \( \left<x\right>_1=x \), estas definiciones coinciden con las que ya teníamos en el caso \( n=2 \).

Nota Observemos que no hemos definido un funtor \( \left<x_1,\ldots, x_n\right>_n \) de rango \( n+1 \), sino infinitos funtores de rango \( n \). Igualmente, la definición de las proyecciones no es la definición de un único funtor \( p^n_i(z) \) de rango \( 3 \), sino que estamos definiendo infinitos funtores de rango \( 1 \), cada uno con su propia definición.

Razonando por inducción sobre \( n \), se prueba sin dificultad que

\( z=\left<p^n_1(z),\ldots, p^n_n(z)\right>_n,\quad z=\left<x_1,\ldots, x_n\right>_n\rightarrow x_1=z_1\land \cdots \land x_n=z_n.
 \)

(Ojo, no me refiero a aplicar ninguna de las reglas de inducción de ARP, sino que las fórmulas anteriores representan infinitos teoremas de ARP, y lo que digo es que, suponiendo que ya hemos demostrado los teoremas correspondientes a \( n \), podemos probar los correspondientes a \( n+1 \), con lo que tenemos infinitas demostraciones, cada una más larga que la anterior.)

Finalmente definimos una nueva familia de infinitos funtores:

\( \left<x_1,\ldots, x_n\right>^n_\infty=\left<n \dot{-}1,\left<x_1,\ldots, x_n\right>_n\right>_2+1. \)

De este modo, ya no tenemos que un mismo natural codifica sucesiones de longitudes distintas, sino que, con este criterio, cada número natural no nulo \( s \) codifica una única sucesión (siempre podemos interpretarlo como un par, considerar el \( n \) que sale de sumar \( 1 \) a su primera componente, e interpretar su segunda componente como una sucesión de longitud \( n \) precisamente.

Podemos considerar que el número natural \( 0 \) codifica la sucesión vacía que tiene \( 0 \) términos. Más precisamente, definimos la longitud de un número natural como

\( \ell(s)=(1\dot{-}(1\dot{-} s))((s\dot{-}1)_1+1). \)

Así, \( \ell(0)=0 \), mientras que si \( s\neq 0 \), entonces \( \ell(s)>0 \) y \( (s\dot{-}1)_1=\ell(s)\dot{-}1 \).

Para definir las proyecciones definimos primero el funtor

\( R(s, 0)=(s\dot{-} 1)_2,\qquad R(s, i+1)=R(s, i)_1. \)

\( p^\infty_i(s)=(1\dot{-} i)R\bigl(s, (s\dot{-}1)_1\bigr)+(1\dot{-} (1\dot{-} i))R\bigl(s, (s\dot{-} 1)_1\dot{-} i\bigr)_2. \)

Notemos que la segunda definición se puede expresar más naturalmente, así:

\( p^\infty_i(s)=\begin{cases}{R\bigl(s, (s\dot{-}1)_1\bigr)}&\text{si}& i=0,\\
R\bigl(s, (s\dot{-} 1)_1\dot{-} i\bigr)_2& \text{si}& i>0.\end{cases} \)

Notemos que \( p^\infty_i(s) \) es un funtor de rango \( 2 \), es decir, que ahora no tenemos infinitos funtores de rango \( 1 \), sino que tanto \( i \) como \( s \) son argumentos de un mismo funtor.

Ejemplo Si \( s= \left<3, 2, 7\right>_\infty=\left<2, \left<\left<3,2\right>_2, 7\right>_2\right>_2+1 \), tenemos que

\( R(s, 0)=\left<\left<3,2\right>_2, 7\right>_2,\quad R(s, 1)=\left<3,2\right>_2,\quad R(s, 2)=3, \)

luego \( p^\infty_0(s)=R(s,2)=3 \), \( p^\infty_1(s)=R(s, 1)_2=2 \), \( p^\infty_2(s)=R(s, 0)_2=7 \).

Nota A partir de ahora escribiremos \( s_i\equiv p^\infty_i(s) \).

Notemos que \( \ell(s)\leq s \) y \( \forall i<\ell(s)\, s_i\leq s \).

Veamos que todo número natural, visto como sucesión, está unívocamente determinado por sus proyecciones.

Teorema \( \ell(s)=\ell(t)\land (\forall i<\ell(s)\, s_i=t_i)\rightarrow s=t \).

Demostración
Si \( \ell(s)=\ell(t)=0 \), entonces \( s=t=0 \). Supongamos que \( \ell(s)=\ell(t)>0 \). Entonces

\( l=(s\dot{-} 1)_1=\ell(s)\dot{-} 1=\ell(t)\dot{-} 1=(t\dot{-} 1)_1. \)

Veamos por inducción que

\( i\leq l \rightarrow R(s, l\dot{-} i)=R(t, l\dot{-} i). \)

Para \( i=0 \) tenemos que

\( R(s, l)=s_0=t_0=R(t, l). \)

Si es cierto para \( i<l \), entonces \( i+1\leq l \), luego \( i+1+(l\dot{-} (i+1))=l \), de donde \( (l\dot{-}(i+1))+1=l\dot{-} i \). Por lo tanto,

\( R(s, l\dot{-}(i+1))_1=R(s, (l\dot{-} (i+1))+1)=R(s, l\dot{-} i)=R(t, l\dot{-} i)=R(t, l\dot{-} (i+1))_1. \)

Por otra parte,

\( R(s, l\dot{-}(i+1))_2=s_{i+1}=t_{i+1}=R(t, l\dot{-}(i+1))_2, \)

luego \( R(s, l\dot{-}(i+1))=R(t, l\dot{-}(i+1)) \). Esto completa la inducción y, aplicándolo a \( i=l \) obtenemos

\( (s\dot{-} 1)_2=R(s, 0)=R(t, 0)=(t\dot{-} 1)_2, \)

pero \( (s\dot{-} 1)_1=l=(t\dot{-} 1)_1 \), luego de hecho \( s\dot{-} 1=t\dot{-} 1 \), luego \( s=t \).
[cerrar]

Una comprobación rutinaria muestra que

\( p^\infty_i(\left<x_0,\ldots, x_{n-1}\right>^n_\infty)=x_i, \)

lo que prueba que toda sucesión finita de números naturales está codificada por un número natural. En la práctica podemos omitir el superíndice \( n \) en el funtor \( \left<x_0,\ldots, x_{n-1}\right>^n_\infty \), puesto que éste se deduce del número de argumentos.

No debemos confundir un número natural \( n \) con la sucesión de longitud \( 1 \) que lo tiene como único término. Ésta viene dada por el funtor

\( \left<n\right>_\infty = \left<0,n\right>_2+1. \)

Manipulación de sucesiones Definimos ahora algunos conceptos elementales sobre sucesiones, como lo que significa que una sucesión extienda a otra, o lo que es el principio y el final de una sucesión hasta o desde una posición prefijada, etc.

Observemos que, una vez queda claro que estos conceptos son definibles en ARP, lo que cuesta dar pruebas detalladas no se debe a limitaciones lógicas de ARP, sino a que son conceptos técnicos, de modo que costaría lo mismo dar las mismas pruebas en una teoría tan cómoda desde un punto de vista lógico como ZFC. De hecho, la moraleja que el lector debería sacar de estos ejemplos es que, una vez comprobado que los conceptos se pueden definir, las demostraciones de las propiedades básicas son pura rutina, sin que el hecho de estar trabajando en ARP sea determinante para nada.

Diremos que una sucesión \( t \) extiende a otra \( s \) si

\( s\sqsubseteq t\equiv \ell(s)\leq \ell(t)\land \forall i<\ell(s)\, s_i=t_i. \)

Es fácil ver que:
  • \( s\sqsubseteq s \),
  • \( s\sqsubseteq t\land t\sqsubseteq s\rightarrow s=t \),
  • \( s\sqsubseteq t\land t\sqsubseteq u\rightarrow s\sqsubseteq u \),
  • \( 0\sqsubseteq s \),
Definimos

\( s\frown\left<n\right>= (1\dot{-} s)\left<n\right>_\infty+(1\dot{-} (1\dot{-} s))(\left<\ell(s),\left<(s\dot{-} 1)_2,n\right>_2\right>_2+1).
 \)

Una comprobación rutinaria muestra que

\( \ell(s\frown \left<n\right>)=\ell(s)+1,\quad  s\sqsubseteq s\frown  \left<n\right>,\quad  (s\frown  \left<n\right>)_{\ell(s)}=n.
 \)

Vemos así que \( s\frown \left<n\right> \) no es sino la sucesión que resulta de añadir \( n \) como último término a la sucesión representada por \( s \). Más en general, definimos

\( s\frown t = F(s, t, \ell(t)), \)

donde \( F \) es el funtor dado por

\( F(s,t, 0)=s,\qquad F(s, t,n+1)=F(s, t, n)\frown \left<t_n\right>. \)

De nuevo una comprobación rutinaria muestra que

\( \ell(s\frown t)=\ell(s)+\ell(t), \quad \forall i<\ell(s) (s\frown t)_i=s_i,\quad \forall i<\ell(t)\,(s\frown t)_{\ell(s)+i}=t_i.
 \)

En particular, \( s\sqsubseteq s\frown t \).

Definimos la restricción de una sucesión mediante el funtor dado por

\( s|_0=0,\qquad s|_{i+1}=s|_i\frown \ \left<s_i\right>. \)

Es fácil probar que \( i\leq \ell(s)\rightarrow \ell(s|_i)=i\land s|_i\sqsubseteq s. \) Más aún, si \( t\sqsubseteq s \), entonces \( t=s|_{\ell(t)} \).

Similarmente definimos \( s|^i= F(s, i, \ell(s)\dot{-} i) \), donde

\( F(s,i, 0)=s_i,\qquad F(s, i, n+1)=F(s, i, n)\frown \left<s_{i+n}\right>. \)

Así, si \( i\leq \ell(s) \), se cumple que \( \ell(s|^i)=\ell(s)\dot{-}i \) y \( s=s|_i\frown  s|^i \).

A partir de este momento ya no usaremos más los funtores \( \left<x_1,\ldots, x_n\right>_n \) ni sus proyecciones correspondientes, sino que siempre que hablemos de sucesiones de números naturales consideraremos los funtores \( \left<x_1,\ldots, x_n\right>_\infty \) y las proyecciones dadas por el funtor \( p^\infty_i(s) \), de rango \( 2 \).

Si \( F(x_1,\ldots, x_{n+1}) \) es un funtor de rango \( n+1 \), podemos definir a partir de él otro funtor igualmente de rango \( n+1 \) dado por

\( F|_0(x_1,\ldots, x_n)=0,\  F|_{x+1}(x_1,\ldots, x_n)=F|_x(x_1,\ldots, x_n)\frown \left<F(x_1,\ldots, x_n, x)\right>.
 \)

Es claro que \( \ell(F|_x(x_1,\ldots, x_n))=x \) y

\( \forall i<x\, F|_x(x_1,\ldots, x_n)_i=F(x_1,\ldots, x_n, i). \)

Más explícitamente:

\( F|_x(x_1,\ldots, x_n) = \left<F(x_1,\ldots, x_n,0),\ldots, F(x_1,\ldots, x_n,n-1)\right>_\infty. \)

Con esto podemos definir un funtor \( F(x_1, \ldots, x_n, n) \) suponiendo definidos los valores \( F(x_1,\ldots, x_n,0),\ldots, F(x_1,\ldots, x_n,n-1) \). Más precisamente:

Teorema (Recursión completa) Si \( G \) es un funtor de rango \( n+2 \), existe un funtor \( F \) de rango \( n+1 \) tal que

\( F(x_1,\ldots, x_n, x)=G(x_1,\ldots, x_n, x, F|_x(x_1,\ldots, x_n)). \)

Demostración
Definimos un funtor \( H \) mediante

\begin{array}{r@{\ }c@{\ }l}
H(x_1,\ldots, x_n,0)&=&0,\\[1mm]
H(x_1,\ldots, x_n,x+1)&=&H(x_1,\ldots, x_n,x)\frown \left<G(x_1,\ldots, x_n, x, H(x_1,\ldots, x_n, x))\right>.
\end{array}

Y a su vez,
\( F(x_1,\ldots, x_n, x)=H(x_1,\ldots, x_n,x+1)_x. \)

Veamos que \( F \) cumple lo requerido. Por aligerar la notación escribiremos \( \bar x \) en lugar de \( x_1,\ldots, x_n \). En primer lugar, una simple inducción nos da que \( \ell(H(\bar x,x))=x \). En segundo lugar, \( H(\bar x, x)=F|_x(\bar x) \). En efecto, para \( x=0 \) es

\( H(\bar x,0)=0=F|_0(\bar x), \)

y si vale para \( x \), entonces, como \( \ell(H(\bar x, x+1))=x+1 \), la definición de \( H \) implica que

\( H(\bar x, x+1)=H(\bar x, x)\frown \left<H(\bar x, x+1)_x\right>, \)

luego por la hipótesis de inducción y la definición de \( F \):

\( H(\bar x, x+1)=F|_x(\bar x)\frown  \left<F(\bar x,x)\right>=F|_{x+1}(\bar x) \).

Finalmente probamos por inducción que \( F \) cumple la propiedad del enunciado:

\( F(\bar x,0)=H(\bar x,1)_0=G(\bar x,0,0)=G(\bar x, 0, F|_0(\bar x)), \)

\( F(\bar x, x+1)=H(\bar x, x+2)_{x+1}=G(\bar x, x+1, H(\bar x, x+1))=G(\bar x, x+1, F|_{x+1}(\bar x)). \)
[cerrar]

Por ejemplo, ahora podemos definir la sucesión de Fibonacci en ARP:

\( F(0) = F(1) = 1, \quad F(n+1) = F(n\dot{-}1)+F(n). \)

Para ajustarnos al teorema anterior definimos el funtor

\( G(x, s) = \cases{1&si $\ell(s)\leq 1$,\cr s_{\ell(s)\dot{-} 2}+s_{\ell(s)\dot{-} 1}&si $\ell(s)\geq 2$,} \)

o, equivalentemente,

\( G(x, s) = \chi_{z\leq y}(\ell(s), 1)+\chi_{z\leq y}(2, \ell(s))( s_{\ell(s)\dot{-} 2}+s_{\ell(s)\dot{-} 1}), \)

de modo que \( F(n) = G(n, F|_n) \).

Notemos en general cómo podemos usar funciones características de fórmulas para formalizar en ARP cualquier definición por casos de un funtor.

En el próximo mensaje formalizaremos en ARP la expresión decimal (o en cualquier base) de un número natural. Aparte de que esto es un hecho básico de la aritmética tal y como la manejamos normalmente, veremos que de ahí podemos extraer consecuencias nada triviales sobre la capacidad expresiva de ARP.

06 Julio, 2023, 03:36 pm
Respuesta #15

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Vamos a probar que todo número natural admite un único desarrollo decimal en cualquier base prefijada. Para ello primero tenemos que introducir las sumas finitas:

Sumas finitas Si \( t(x_1,\ldots, x_n) \) es un término cuyas variables estén entre las indicadas, definimos un funtor de rango \( n \) mediante las ecuaciones:

\( \begin{eqnarray*}
\sum\limits_{i<0}t(x_1,\ldots, x_{n-1},i)&=&0\\
\sum\limits_{i<x+1}t(x_1,\ldots, x_{n-1},i)&=&\sum\limits_{i<x}t(x_1,\ldots, x_{n-1},i)+t(x_1,\ldots, x_{n-1},x).
\end{eqnarray*}
 \)

Escribiremos también:

\( \sum\limits_{i\leq x}t(x_1,\ldots, x_{n-1},i)\equiv \sum\limits_{i< x+1}t(x_1,\ldots, x_{n-1},i). \)

Los hechos siguientes se demuestran fácilmente por inducción sobre \( x \) (por simplicidad omitimos los parámetros que no son relevantes en el enunciado de las propiedades):

  • \( \sum\limits_{i<x}t_1(i)+\sum\limits_{i<x}t_2(i)=\sum\limits_{i<x}(t_1(i)+t_2(i)) \),
  • \( \sum\limits_{i<x} y\cdot t(i)=y\sum\limits_{i<x}t(i) \),
  • \( \sum\limits_{i<y+x}\!\!t(i)=\sum\limits_{i<y}t(i)+\sum\limits_{i<x}t(y+i) \),
  • \( \forall i<x\ t_1(i)\leq t_2(i)\rightarrow \sum\limits_{i<x}t_1(i)\leq \sum\limits_{i<x}t_2(i) \),
  • \( \sum\limits_{i<x}t(i)=0\rightarrow \forall i<x\ t(i)=0 \).
Desarrollos decimales  Hasta ahora, cuando hemos escrito números como \( 184 \), teníamos que entender que \( 184 \) no era más que una forma de abreviar un numeral compuesto por \( 184 \) funtores \( S \) seguidos de un \( 0 \). Sin embargo ahora podemos formalizar en ARP el concepto de desarrollo decimal que nos permite interpretar \( 184 \) como lo que expresa realmente. Empezamos introduciendo las definiciones necesarias:

Consideremos el funtor dado por
\( s_{(d)}=\sum\limits_{i<\ell(s)}s_i d^i. \)

Un desarrollo decimal en base \( d \) de un número natural \( x \) es una sucesión finita \( s \) tal que \( \forall i<\ell(s)\, s_i<d \) y \( x=s_{(d)} \). Diremos que se trata de un desarrollo reducido si \( \ell(s)=0 \) (lo cual sólo puede suceder si \( x=0 \)) o bien \( \ell(s)>0 \) y \( s_{\ell(s)\dot{-} 1}\neq 0 \).

Vamos a demostrar que cada número natural admite un desarrollo decimal en cualquier base \( d\geq 2 \) y que éste es único si exigimos que sea reducido.

Empezamos considerando el funtor dado por las ecuaciones

\( \begin{eqnarray*}
F(x, d, 0)&=&\left<c(x, d), r(x, d)\right>_\infty,\\
F(x, d,i+1)&=&\left<c(F(x, d, i)_0,d),r(F(x, d, i)_0,d)\right>_\infty.
\end{eqnarray*} \)

donde \( c \) y \( r \) son los funtores que calculan el cociente y el resto de la división euclídea. Definimos

\( x^*_i[d]=F(x, d, i)_0 \),           \( x_i[d]=F(x, d, i)_1 \).

Así
\( x=x^*_0[d]\cdot d + x_0[d],\qquad x^*_i[d]=x^*_{i+1}[d]\cdot d+x_{i+1}[d], \)

con \( x_i[d]<d \), para todo \( i \). De aquí se sigue que

\( x=x^*_n[d]\cdot d^{n+1}+\sum\limits_{i\leq n}x_i[d]\cdot d^i. \)

Demostración
Razonamos por inducción sobre \( n \). Para \( n=0 \) es inmediato y, si vale para \( n \),

\( \begin{eqnarray*}
x&=&x^*_n[d]\cdot d^{n+1}+\sum\limits_{i\leq n}x_i[d]\cdot d^i\\
&=&(x^*_{n+1}[d]\cdot d+x_{n+1}[d])\cdot d^{n+1}+\sum\limits_{i\leq n}x_i[d]\cdot d^i\\
&=&x^*_{n+1}[d]\cdot d^{n+2}+x_{n+1}[d]\cdot d^{n+1}+\sum\limits_{i\leq n}x_i[d]\cdot d^i\\
&=&x^*_{n+1}[d]\cdot d^{n+2}+\sum\limits_{i\leq n+1}x_i[d]\cdot d^i.
\end{eqnarray*} \)
[cerrar]

Si \( d\geq 2 \) tenemos que \( x<d^{x+1} \), luego \( x^*_x[d]=0 \), pues de lo contrario la expresión que acabamos de probar nos daría que \( d^{x+1}\leq x \). Por consiguiente,

\( x=\sum\limits_{i\leq x}x_i[d]\cdot d^i. \)

Con esto ya hemos probado que todo número natural admite un desarrollo decimal en base \( d \). Vamos a afinar un poco la construcción para quedarnos con uno reducido. Definimos

\( N_d(x)=\mu u\leq x+1\ x=\sum\limits_{i<u}x_i[d]\cdot d^i, \)

de modo que

\( x=\sum\limits_{i< N_d(x)}\!\!\!x_i[d]\cdot d^i. \)

Claramente \( N_d(0)=0 \) y si \( x\neq 0 \), entonces \( N_d(x)>0 \) y \( n_d(x)=N_d(x)\dot{-} 1 \) cumple que \( x_{n_d(x)}[d]\neq 0 \), o de lo contrario sería

\( x=\sum\limits_{i< n_d(x)}x_i[d]\cdot d^i \)

con \( n_d(x)<N_d(x) \), en contra de la minimalidad de \( N_d(x) \).

Definimos las cifras decimales de \( x \) en base \( d \) como la sucesión dada por la restricción a \( N_d(x) \) del funtor \( x_i[d] \), es decir, \( x[d]= x|_{N_d(x)}[d] \). El teorema siguiente recoge lo que hemos demostrado y algunos hechos más:

Teorema Si \( d\geq 2 \), todo número natural \( x\neq 0 \) admite el desarrollo decimal reducido en base \( d \)

\( x=x[d]_{(d)}=\sum\limits_{i\leq n_d(x)}x_i[d]\cdot d^i \).

Además, si \( x=s_{(d)} \) es otro desarrollo decimal en base \( d \), entonces \( \ell(s)> n_d(x) \), y, para todo \( i<\ell(s) \), se cumple que

\( s_i=\cases{x_i[d]&si $i\leq n_d(x)$,\cr 0&si $i>n_d(x)$.} \)

En particular, \( x \) admite un único desarrollo decimal reducido.

Demostración
Ya hemos probado que \( x[d]_{(d)}=x \), que \( x_i[d]<d \) y que \( x_{n_d(x)}[d]\neq 0 \), por lo que \( x[d] \) es un desarrollo decimal reducido de \( x \).

Para probar la unicidad partimos de una sucesión \( s>0 \) arbitraria tal que \( \forall i<\ell(s)\, s_i<d \) y vamos a probar por inducción que, para todo \( k< \ell(s) \), se cumple

\( (s_{(d)})^*_k[d]= \sum\limits_{i<\ell(s)\dot{-} (k+1)}s_{i+(k+1)}d^i\land \forall i\leq k\,(s_{(d)})_i[d]=s_i. \)

Para \( k=0 \) tenemos que

\( s_{(d)}=\sum\limits_{i<\ell(s)}\!\!s_i\cdot d^i=\sum\limits_{i<\ell(s)\dot{-} 1}\!\!\!\!s_{i+1}\cdot d^{i+1}+s_0=d\cdot \sum\limits_{i<\ell(s)\dot{-} 1}\!\!\!s_{i+1}\cdot d^i+s_0,
 \)

luego por la unicidad de la división euclídea concluimos que \( (s_{(d)})_0[d]=s_0 \) y

\( (s_{(d)})^*_0[d]=\sum\limits_{i<\ell(s)\dot{-} 1}\!\!\!\!\!s_{i+1}\cdot d^i. \)

Supuesto cierto para \( k \) y que \( k+1<\ell(s) \), tenemos que

\( (s_{(d)})^*_k[d]=d\cdot (s_{(d)})^*_{k+1}[d]+(s_{(d)})_{k+1}[d],\qquad (s_{(d)})_{k+1}[d]<d, \)

\( (s_{(d)})^*_k[d]=\!\!\!\!\!\!\sum\limits_{i<\ell(s)\dot{-} (k+1)}\!\!\!\!\!\!s_{i+k+1}d^i=d\cdot \!\!\!\!\!\!\!\!\!\sum\limits_{i<\ell(s)\dot{-} (k+2)}\!\!\!\!\!\!\!\!s_{i+k+2}d^i+s_{k+1},\qquad s_{k+1}<d. \)

Por la unicidad de la división euclídea, tiene que ser

\( (s_{(d)})^*_{k+1}[d]=\!\!\!\!\!\!\!\!\!\sum\limits_{i<\ell(s)\dot{-} (k+2)}\!\!\!\!\!\!\!\!s_{i+k+2}d^i,\qquad (s_{(d)})_{k+1}[d]=s_{k+1},
 \)

lo que completa la inducción. En particular, para \( k=\ell(s)\dot{-} 1 \) tenemos que

\( \forall i< \ell(s)\,(s_{(d)})_i[d]=s_i. \)

Si suponemos que \( s_{(d)}=x \), entonces \( x=\sum\limits_{i<\ell(s)}x_i[d]\cdot d^i \), luego por la definición de \( N_d(x) \) tiene que ser \( n_d(x)<N_d(x)\leq \ell(s) \). Además,

\( x=\sum\limits_{i<\ell(s)}s_i\cdot d^i = \sum\limits_{i<N_d(x)}x_i[d]\cdot d^i +\sum\limits_{i<\ell(s)\dot{-} N_d(x)}s_{N_d(x)+i}\,d^{N_d(x)+i},
 \)
pero el primero de los últimos dos sumandos también vale \( x \), luego

\( \sum\limits_{i<\ell(s)\dot{-} N_d(x)}s_{N_d(x)+i}\,d^{N_d(x)+i}=0, \)

luego \( \forall i<\ell(s)\dot{-} N_d(x)\ s_{N_d(x)+i}=0 \), luego \( s_i=0 \) si \( N_d(x)\leq i<\ell(s) \).

De este modo, el desarrollo reducido \( x=\sum\limits_{i\leq n_d(x)}x_i[d]\cdot d^i \) es esencialmente único, en cuanto que cualquier otro desarrollo decimal de \( x \) resulta de prolongar éste con cifras nulas.
[cerrar]

Por otro lado, observemos que \( 0=0_{(d)} \) es por definición el único desarrollo decimal reducido de \( 0 \).

En particular, el teorema anterior implica que cada número está determinado por su desarrollo decimal:

Teorema \( d\geq 2\land \forall i<x+y\ x_i[d]=y_i[d]\rightarrow x=y \).

Así pues, ahora podemos definir las cifras decimales

\( 1 \equiv S0,\quad 2 \equiv S1, \quad 3 \equiv S2, \quad 4 \equiv S3, \quad 5 \equiv S4, \)

\( 6 \equiv S5,\quad 7 \equiv S6,\quad 8 \equiv S7,\quad 9 \equiv S8 \)

y convenir en que todo numeral, como \( 1\,314 \), ha de interpretarse como

\( \left<4, 1, 3, 1\right>_{(S9)}. \)

En particular, \( S9=10 \) y \( \left<4, 1, 3, 1\right>_{(10)}=1\cdot 10^3+3\cdot 10^2+1\cdot 10+4 \).

13 Julio, 2023, 11:16 pm
Respuesta #16

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahora estamos en condiciones de definir una relación muy interesante entre los números naturales:

\( x\in y\equiv y_x[2]=1 \)

(escribiremos también \( x\notin y\equiv \lnot x\in y \)).

Equivalentemente, diremos que un número natural \( x \) pertenece a otro \( y \) si la cifra de orden \( x \) del desarrollo binario de \( y \) vale \( 1 \).

En particular, si \( x\in y \), entonces \( x<2^x\leq y \). Esto hace que podamos considerar cuantificadores acotados en la forma

\( \exists u\in y\,\alpha(u)\equiv \exists u\leq y(u\in y\land \alpha(u)),\quad \forall u\in y\,\alpha(u)\equiv \forall  u\leq y(u\in y\rightarrow \alpha(u)),
 \)

\( \exists! u\in y\,\alpha(u)\equiv \exists! u\leq y(u\in y\land \alpha(u)). \)

Y también podemos definir \( \mu u\in x\,\alpha(u)\equiv \mu u <x(u\in x\land \alpha(u)) \).

El hecho de que cada número natural esté determinado por su desarrollo decimal en una base dada (en este caso por su desarrollo binario) implica claramente lo que en teoría de conjuntos se llama axioma de extensionalidad:

\( \forall u\in x\, u\in y\land \forall u\in y\, u\in x\rightarrow x=y. \)

Definimos la inclusión como
\( x\subset y\equiv \forall u\in x\, u\in y, \)
de modo que
  • \( x\subset x \),
  • \( x\subset y\land y\subset x\rightarrow x=y \),
  • \( x\subset y\land y\subset z\rightarrow x\subset z \).
Definimos \( \emptyset \equiv 0 \), y es inmediato que \( x\notin \emptyset \), así como que \( \emptyset\subset x \).

Para cada fórmula \( \alpha(u, x_1,\ldots, x_n) \), definimos

\( \textstyle\{u<k\mid \alpha(u, x_1,\ldots, x_n)\}\equiv \sum\limits_{u<k}\chi_\alpha(u, x_1,\ldots, x_n)2^u,
 \)

y así se cumple claramente lo que en teoría de conjuntos se conoce como axioma de especificación:

Teorema (especificación) Si \( \alpha(x, x_1,\ldots, x_n) \) es una fórmula cualquiera, en ARP se demuestra:

\( x\in \{u<k\mid \alpha(u,x_1,\ldots, x_n)\}\leftrightarrow x<k\land \alpha(x,x_1,\ldots, x_n). \)

Notemos que en el teorema anterior podemos cambiar \( u<k \) por \( u\in k \), entendiendo que

\( \{u\in k\mid \alpha(u,x_1,\ldots, x_n)\}\equiv \{u<k\mid u\in k\land \alpha(u, x_1,\ldots , x_n)\}. \)

A partir de aquí ya podemos definir fácilmente todos los conceptos conjuntistas básicos:

\( \begin{eqnarray*}
\{x_1,\ldots, x_n\}&\equiv&\{u<x_1+\cdots + x_n\mid u = x_1\lor \cdots \lor u = x_n\},\\
x\cup y &\equiv& \{u<x+y\mid u\in x\lor u\in y\},\\
x\cap y &\equiv& \{u<x+y\mid u\in x\land u\in y\},\\
x\setminus y &\equiv& \{u<x\mid u\in x\land u\notin y\},\\
\mathcal Px&\equiv&\{u<x+1\mid u\subset x\},\\
\textstyle \bigcup x&\equiv&\{u<x\mid \exists v\in x\, u\in v\},\\
\textstyle \bigcap x&\equiv&\{u<x\mid \forall  v\in x\, u\in v\},\\
x\times y&\equiv&\{w<\left<x,y\right>_\infty\mid \exists u\in x\exists v\in y\, w=\left<u, v\right>_\infty\}.
\end{eqnarray*} \)

En la definición de \( \mathcal Px \), notemos que \( y\subset x\rightarrow y_i[2]\leq x_i[2] \), de donde \( y\leq x \). Observemos también que

\( x\neq \emptyset\rightarrow (u\in \bigcap x\leftrightarrow \forall v\in x\, u\in v), \)

mientras que \( \bigcap\emptyset = \emptyset \) no cumple la equivalencia anterior.

Definimos también \( I_k \equiv \{u<k\mid u = u\} \), que es el conjunto de todos los números naturales menores que \( k \).



Nota: Pares ordenados Con la definición que hemos dado de producto cartesiano \( x\times y \) se cumple que

\( w\in x\times y\leftrightarrow \exists u\in x\exists v\in y\ w = \left<u, v\right>_\infty. \)

En teoría de conjuntos es habitual definir el par ordenado de dos conjuntos como

\( (x, y) \equiv \{\{x\},\{x, y\}\}. \)

Esta definición también es válida en ARP y se demuestra fácilmente que

\( (x, y) = (z, w)\leftrightarrow x = z\land y = w. \)

También se cumple que \( x<\{x\}<(x, y) \), \( y<\{x, y\}<(x, y) \). Por consiguiente podríamos haber definido

\( x\times y \equiv \{w<2^{2^x}+2^{2^x+2^y}\mid \exists u\in x\exists v\in y\ w = (u, v)\}. \)

y se cumpliría igualmente

\( w\in x\times y\leftrightarrow \exists u\in x\exists v\in y\ w = (u, v). \)

Esto hace que, en todo cuanto vamos a decir a continuación sobre aplicaciones (que las vamos a definir como subconjuntos de productos cartesianos) será irrelevante considerar pares ordenados de la forma \( \left<u, v\right>_\infty \) o \( (u, v) \).



Para definir subconjuntos de productos cartesianos es útil introducir la notación siguiente:

\( \{\left<u, v\right>\in x\times y\mid \alpha(u, v, x, y, x_1,\ldots, x_n)\}\equiv \)

\( \{w\in x\times y\mid \exists u\in x\exists v\in y(w = \left<u, v\right>\land \alpha(u, v, x, y, x_1,\ldots, x_n))\}. \)

El mínimo y el máximo de un conjunto pueden definirse así:

\( \min x=\mu u\leq x(u\in x),\qquad \max x = x\dot{-} \mu u\leq x(x\dot{-} u\in x), \)

de modo que
\( x\neq \emptyset\rightarrow (\min x\in x\land \forall  u\in x\, \min x\leq u), \)

\( x\neq \emptyset\rightarrow (\max x\in x\land \forall  u\in x\, u\leq \max x). \)

Veamos ahora que es posible definir conjuntos sin tener a priori una cota para sus elementos eludiendo la exigencia del teorema de especificación:

Si fijamos un término \( t(x, x_1,\ldots, x_n) \), podemos definir el funtor

\( \begin{eqnarray*}
F_t(x_1,\ldots, x_n, y,0)&=&0,\\
F_t(x_1,\ldots, x_n,y,x+1)&=&F_t(x_1,\ldots, x_n,y,x)\cup \{t(x, x_1,\ldots, x_n)\}\cdot\chi[x\in y],
\end{eqnarray*} \)
y a su vez

\( \{t(u, x_1,\ldots, x_n)\mid u\in y\} = F_t(x_1,\ldots, x_n, y,y). \)

Teorema (Reemplazo) Si \( t(x, x_1,\ldots, x_n) \) es un término cualquiera, en ARP se demuestra:

\( z\in \{t(u, x_1,\ldots, x_n)\mid u\in y\} \leftrightarrow \exists u\in y\, z = t(u,x_1,\ldots, x_n). \)

Demostración
Omitiendo los parámetros, supongamos que

\( z\in \{t(u)\mid u\in y\}=F_t(y, y). \)

Podemos tomar entonces

\( w\equiv \mu u\leq y\, z\in F_t(y, u) \)

No puede ser \( w=0 \), luego, llamando \( x=w\dot{-} 1 \), se cumple que \( w=x+1 \) y así

\( z\in F_t(y, x+1)=F_t(y, x)\cup\{t(x)\}\cdot \chi(x\in y). \)

Por la minimalidad de \( w \), tenemos que \( z\notin F_t(y, x) \), luego se tiene que cumplir que \( z=t(x) \) y \( \chi[x\in y]=1 \), que es lo mismo que \( x\in y \). Por lo tanto, \( \exists u\in y\, z=t(u) \).

Recíprocamente, supongamos que \( \exists u\in y\, z=t(u) \) y tomemos \( x\equiv\mu u\in y\, z=t(u). \)

Entonces \( x\in y \), luego \( x<y \), luego \( x+1\leq y \). Además \( z = t(x) \), luego

\( z\in F_t(y,x)\cup\{t(x)\}\cdot \chi[x\in y]=F_t(y,x+1). \)

Ahora bien, una simple inducción demuestra que

\( x_1\leq x_2\rightarrow F_t(y, x_1)\subset F_t(y, x_2), \)

luego podemos concluir que \( z\in F_t(y, y)=\{t(u)\mid u\in y\} \).
[cerrar]

En otras palabras, los valores que toma un término cuando una de sus variables recorre un conjunto, forman un conjunto.

Por ejemplo, ahora podemos definir

\( \textstyle \bigcup\limits_{u\in y}t(u, x_1, \ldots, x_n) = \bigcup\{t(u, x_1,\ldots, x_n)\mid u\in y\}, \)

\( \textstyle \bigcap\limits_{u\in y}t(u, x_1, \ldots, x_n) = \bigcap\{t(u, x_1,\ldots, x_n)\mid u\in y\}, \)

de modo que

\( \textstyle v\in \bigcup\limits_{u\in y}t(u, x_1, \ldots, x_n) \leftrightarrow \exists u\in y\, v\in t(u, x_1,\ldots, x_n),
 \)

\( \textstyle y\neq \emptyset\rightarrow ( v\in \bigcap\limits_{u\in y}t(u, x_1, \ldots, x_n) \leftrightarrow \forall  u\in y\, v\in t(u, x_1,\ldots, x_n)). \)

Aplicaciones Aunque las definiciones siguientes tienen sentido para cualquier conjunto \( f \) (es decir, para cualquier número natural \( f \)), sólo tienen interés cuando \( f \) es un conjunto de pares ordenados. En tal caso, el dominio de \( f \) es el conjunto de todas las primeras componentes de los pares ordenados de \( f \) y el rango es el conjunto de todas sus segundas componentes:

\( \mathcal D f \equiv \{u<f\mid \exists v< f\, \left<u, v\right>_\infty\in f\}, \)

\( \mathcal R f \equiv \{v<f\mid \exists u< f\, \left<u, v\right>_\infty\in f\}. \)

Diremos que \( f \) es una aplicación de un conjunto \( x \) en un conjunto \( y \) si cumple:

\( f: x\longrightarrow y\equiv f\subset x\times y\land \forall u\in x\exists! v\in y\,\left<u,v\right>_\infty\in f. \)

Así, si definimos
\( f(u)\equiv \mu v\in \mathcal Rf\ \left<u, v\right>_\infty\in f, \)

tenemos que
\( f:x\longrightarrow y\land u\in x\rightarrow f(u)\in y\land \left<u, f(u)\right>_\infty\in f, \)

y también que
\( f: x\longrightarrow y\land \left<u, v\right>_\infty\in f\rightarrow v = f(u). \)

A partir de aquí podemos introducir de forma natural todos los conceptos conjuntistas relacionados con aplicaciones: composición, restricción, aplicación inyectiva, suprayectiva, biyectiva, aplicación inversa, imagen y antiimagen de un conjunto, etc., y demostrar sus propiedades básicas con los mismos argumentos que se emplean habitualmente en la teoría de conjuntos, sin más precaución que acotar debidamente todos los cuantificadores involucrados. Teniendo en cuenta que

\( f:x\longrightarrow y\rightarrow f\in \mathcal P(x\times y), \)

podemos definir el conjunto potencia

\( y^x\equiv \{f\in \mathcal P(x\times y)\mid f: x\longrightarrow y\}, \)

de modo que
\( f\in y^x\leftrightarrow f: x\longrightarrow y. \)



En resumen, en ARP se pueden demostrar todos los axiomas de ZFC salvo el axioma de infinitud (al contrario, en el mensaje siguiente veremos que en ARP se demuestra que todo conjunto es finito). No hemos mencionado el axioma de elección pero es inmediato a partir del hecho de que hemos visto cómo asociar a cada conjunto no vacío su mínimo elemento (respecto al orden usual de los números naturales).

En la práctica esto supone que podemos razonar en ARP con la misma "comodidad" con que lo hacemos en ZFC, con la única precaución de no hablar nunca de conjuntos infinitos (o, más precisamente, de conjuntos que no tengamos garantizado desde el principio que son finitos).

No obstante, el lector familiarizado con ZFC debe tener en cuenta que el axioma de especificación o el axioma de reemplazo en ZFC son válidos para fórmulas cualesquiera del lenguaje de ZFC, y éstas admiten cuantificadores arbitrarios, mientras que la versión del axioma de especificación que hemos probado aquí vale para fórmulas de ARP, que sólo admiten cuantificadores acotados, y el teorema de reemplazo está enunciado en términos de términos de ARP, que tampoco son tan generales como las fórmulas de ZFC. Más aún, el propio lenguaje de ZFC permite considerar cuantificadores no acotados, lo que permite definir y estudiar en ZFC conceptos que en ARP no pueden siquiera definirse. Pero la diferencia es simplemente la necesaria para forzar a que todas las definiciones sean absolutamente finitistas.

15 Julio, 2023, 02:49 pm
Respuesta #17

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Como ilustración de cómo se puede trabajar con conjuntos en ARP voy a presentar el concepto de cardinal de un conjunto, que en realidad completa la formalización de la aritmética básica, ya que saber que la suma de dos números es el cardinal de la unión de dos conjuntos disjuntos con tantos elementos como indican los sumandos es algo esencial al concepto de suma, más que la relación recurrente que hemos tomado como definición formal.

Diremos que dos conjuntos son equipotentes si cumplen

\( x\sim y \equiv \exists f\in y^x\ f: x\longrightarrow y \) biyectiva.

Notemos que, para que esto tenga sentido en ARP, es esencial la acotación del cuantificador.

Es fácil comprobar que
\( x\sim x,\qquad x\sim y \rightarrow y\sim x,\qquad x\sim y\land y\sim z\rightarrow x\sim z. \)

Recordemos que \( I_k \) es el conjunto de los números menores que \( k \).

Teorema \( \exists k\leq x\exists f\in x^{I_k}\ f:I_k\longrightarrow x \) biyectiva.

Demostración
Lo probamos por inducción sobre \( x \). Si \( x = 0 \) es obvio que sirve \( k=0 \), pues \( \emptyset: \emptyset\longrightarrow \emptyset \) biyectiva. Si es cierto para todo \( y<x \) y \( x\neq 0 \), tomamos \( u\in x \) (técnicamente, hacemos, por ejemplo, \( u\equiv \min x \)), con lo que \( y = x\setminus\{u\}<x \). Por hipótesis de inducción existe un \( k\leq y \) y una biyección \( f: I_k\longrightarrow y \), que se extiende a \( g: I_{k+1}\longrightarrow x \) biyectiva sin más que tomar \( g = f\cup \{\left<k,u\right>_\infty\} \). Además \( k+1\leq y+1\leq x \).
[cerrar]

Ahora necesitamos probar que un mismo conjunto \( x \) no puede ser equipotente a dos conjuntos \( I_k, I_r \) con \( k\neq r \). Si así fuera, serían \( I_k\sim I_r \), luego basta ver que esto es imposible:

Teorema \( k\neq r\rightarrow I_k\not\sim I_r \).

Spoiler
Basta probar que \( k<r\rightarrow I_k\not\sim I_r \). Razonamos por inducción sobre \( r \). Si \( r = 0 \) es trivial. Si vale para \( r \) y \( k<r+1 \), pero existe \( f: I_k\longrightarrow I_{r+1} \) biyectiva, sea \( u<k \) tal que \( f(u)=r \). En particular, \( k\neq 0 \), luego, llamando \( k' = k\dot{-} 1<r \), tenemos que \( k=k'+1 \) y podemos construir \( g: I_{k'}\longrightarrow I_r \) biyectiva como sigue: si \( u=k' \) basta tomar \( g = f|_{I_{k'}} \), mientras que si \( u<k' \), entonces \( f(k')\neq f(u)=r \), luego podemos definir \( g(u) = f(k') \) y \( g(v)=f(v) \) para todo \( v<k' \), \( v\neq u \). Esto contradice la hipótesis de inducción.
[cerrar]

Con esto podemos definir el cardinal de un conjunto \( x \) como

\( |x| = \mu k\leq x\  I_k\sim x. \)

Por comodidad lo hemos definido como "el mínimo \( k \)", pero en realidad hemos demostrado que es el único. Así:

\( I_{|x|}\sim x,\qquad I_k\sim x\rightarrow |x| = k. \)

El segundo teorema expresa que si hemos logrado biyectar un conjunto \( x \) con un conjunto \( I_k \), entonces hemos contado \( x \) y podemos afirmar que su número de elementos es \( k \).

En efecto, si \( I_k\sim x \), entonces \( I_{|x|}\sim x\sim I_k \), y hemos probado que no puede ser \( |x|<k \) o \( k<|x| \), luego tiene que ser \( |x|=k \).

Ahora podemos expresar formalmente que dos conjuntos son equipotentes si y sólo si tienen el mismo número de elementos:

\( x\sim y\leftrightarrow |x|=|y|. \)

A partir de aquí ya es pura rutina comprobar los hechos siguientes:

  • \( x\cap y = \emptyset\rightarrow |x\cup y| = |x|+|y| \),
  • \( |x\times y| = |x|\cdot |y| \),
  • \( |y^x| = |y|^{|x|} \),
  • \( |\mathcal Px| = 2^{|x|} \).
Veamos, como ilustración, la demostración del primer teorema (como ilustración de cómo se puede trabajar en ARP, naturalmente).

Dejo este spoiler para que no se pierda la continuidad sobre esto en el hilo de comentarios, pero el spoiler siguiente contiene una demostración mucho más simple.

Demostración mala
Razonamos por inducción sobre \( |y| \). Técnicamente, esto significa que vamos a probar

Esto está mal:

\( |y| = n \land x\cap y =\emptyset \rightarrow |x\cup y| = |x|+|y|. \)

Luego basta sustituir \( n = |y| \).

Lo correcto es probar por inducción

\( \forall y'\in \mathcal P y(|y'| = n \land x\cap y' =\emptyset \rightarrow |x\cup y'| = |x|+|y'|. \)

y luego sustituir \( n = |y| \) y eliminar el cuantificador haciendo \( y' = y \). De este modo se puede aplicar la hipótesis de inducción a cualquier subconjunto de \( y' \) de cardinal \( n \). Lo que sigue es lo mismo que había antes, pero cambiando en todas partes \( y \) por \( y' \).

Si \( n = 0 \), es fácil ver que \( |y'|=0 \) implica \( y' = \emptyset \), luego
\( |x\cup y'| = |x| = |x|+0 = |x|+|y'|. \)

Si es cierto para \( n \) y \( |y'|=n+1 \), sea \( f: I_{n+1}\longrightarrow y' \) biyectiva.

Nota
Técnicamente, cuando sabemos que existe un conjunto \( f \) que cumple algo y tomamos uno en concreto, hay que entender que lo estamos definiendo, por ejemplo, tomando el mínimo \( f \) que cumple lo requerido así:
\( f \equiv \mu f\in y'^{I_{n+1}}\ f: I_{n+1}\longrightarrow y' \) biyectiva.
[cerrar]

Sea \( v = f(n)\in y' \) y sea \( y'' = y'\setminus\{v\} \), de modo que \( f|_{I_n}:I_n\longrightarrow y'' \) biyectiva, luego \( |y''| = n \). Además \( x\cup y' = (x\cup y'')\cup \{v\} \).

Por hipótesis de inducción \( |x\cup y''| = |x|+|y''| \), luego tenemos una biyección

\( g: I_{|x|+|y''|}\longrightarrow x\cup y'' \) biyecctiva.

Esta biyección se puede extender a

\( g':I_{|x|+|y'|}\longrightarrow x\cup y' \) biyectiva

sin más que definir \( g'(|x|+|y''|) = v \). Por lo tanto, \( |x\cup y'| = |x|+|y'| \).
[cerrar]

Demostración buena
Razonamos por inducción completa sobre \( y \), es decir, suponemos que la igualdad es cierta para todo \( y'<y \) y vamos a probarla para \( y \). Si \( y = 0 \) es trivial, pues
\( |x\cup y| = |x| = |x|+0 = |x|+|y| \).

Si \( y\neq 0 \), podemos tomar \( v\in y \) y definir \( y' = y\setminus\{v\} \), de modo que \( x\cap y' = \emptyset \), \( y'\subsetneq y \), luego \( y'< y \). Podemos aplicar la hipótesis de inducción, que nos da que \( |x\cup y'| = |x|+|y'| \).

Ahora observamos que una biyección \( f: I_{|y'|}\longrightarrow y' \) se extiende a otra biyección \( f':I_{|y'|+1}\longrightarrow y \) sin más que definir \( f'(|y'|) = v \), con lo que \( |y| = |y'|+1 \), y esto vale siempre que a un conjunto se le quita uno de sus elementos, luego, puesto que \( x\cup y' = (x\cup y)\setminus\{v\} \), también \( |x\cup y| = |x\cup y'|+1 = |x|+|y'|+1 = |x|+|y| \).
[cerrar]

El teorema anterior se refina fácilmente a la conocida relación
\( |x\cup y| = |x|+|y|\dot{-} |x\cap y|. \)

Ahora podemos interpretar en términos de aplicaciones las desigualdades entre cardinales:

Teorema Se cumple:
  • \( |x|\leq |y|\leftrightarrow \exists f\in y^x\ f: x\longrightarrow y \) inyectiva,
  • \( x\neq \emptyset\rightarrow (|x|\leq |y|\leftrightarrow \exists f\in x^y\ f: y\longrightarrow x \) suprayectiva).

Demostración
1) Si \( |x|\leq |y| \), es obvio que, a partir de dos biyecciones \( f: I_{|x|}\longrightarrow x \), \( g: I_{|y|}\longrightarrow y \), podemos construir una aplicación inyectiva \( h: x\longrightarrow y \) mediante \( h(u) = g(f^{-1}(u)) \).

Si \( f: x\longrightarrow y \) inyectiva, entonces \( y = f[x]\cup (y\setminus f[x]) \), luego \( |y| = |x|+|y\setminus f[x]| \), luego \( |x|\leq |y| \).

2) Si \( f: y\longrightarrow x \) suprayectiva, podemos definir

\( g \equiv \{\left<u, v\right>_\infty\in x\times y\mid v = \mu w\in y\ f(w)=u\}, \)

y es fácil ver que \( g: x\longrightarrow y \) inyectiva, luego \( |x|\leq |y| \).

Si \( |x|\leq |y| \), basta encontrar \( f: I_{|y|}\longrightarrow I_{|x|} \) suprayectiva, pues componiéndola con biyecciones obtendremos la aplicación requerida. Tenemos que \( |x|>0 \), luego \( 0\in I_{|x|} \) y basta definir
\( f(u) = \cases{u&si $u<|x|$,\cr 0& en otro caso.} \)
[cerrar]

A partir de aquí el lector debería convencerse de que cualquier hecho razonable relativo a aplicaciones y cardinales de conjuntos finitos es demostrable en ARP.

Aplicaciones y sucesiones Ahora tenemos dos formas distintas de expresar una sucesión \( x_0, \ldots, x_{n-1} \), bien como una sucesión \( s \) tal que \( \ell(s)= n \), bien como una aplicación \( f: I_n\longrightarrow x \), donde \( x \) es un conjunto que contiene a \( \{x_0, \ldots, x_n\} \). El conjunto \( x^{I_n} \) contiene a todas las aplicaciones \( f: I_n\longrightarrow x \), y vamos a ver ahora que también podemos definir un conjunto que contenga a todas las sucesiones de longitud \( n \) cuyos términos estén en un conjunto \( x \).

Para ello consideramos el funtor definido por

\( F(f, 0) = 0,\qquad F(f, i+1) = F(f,i)\frown \left<f(i)\right>_\infty. \)

Una simple inducción prueba que

\( f\in x^{I_n}\rightarrow \ell(F(f, m)) = m\land \forall i<m\ F(f, m)_i = f(i). \)

Esto nos permite definir
\( S_n(x) = \{F(f, n)\mid f\in x^{I_n}\}, \)
de modo que
\( s\in S_n(x)\leftrightarrow \ell(s) = n\land \forall i<n\ s_i\in x. \)

En efecto, si \( \ell(s) = n\land \forall i<n\ s_i\in x \), podemos definir

\( f \equiv \{z\in I_n\times x\mid \exists i<n\, z = \left<i, s_i\right>_\infty\}, \)

de modo que \( f\in x^{I_n} \) y \( \forall i<n\ f(i) = s_i \), y así \( s=F(f, n) \in S_n(x) \). El recíproco es más sencillo.

Más aún, tenemos una aplicación \( H(x, n): x^{I_n}\longrightarrow S_n(x) \) biyectiva dada por \( H(x,n)(f) = F(f, n) \).

Esto nos permite intercambiar aplicaciones por sucesiones siempre que sea necesario.

AÑADIDO:

Si \( F \) es un funtor de rango \( n+1 \), podemos definir otro funtor del mismo rango mediante

\( [F]|_x(x_1, \ldots, x_n)=\{\left<u, F(x_1,\ldots, x_n, u)\right>\mid u\in x\}, \)

de modo que

\( [F]|_x(x_1,\ldots, x_n): x\longrightarrow \mathcal R[F]|_x\land \forall u\in x\, [F]|_x(x_1, \ldots, x_n)(u) = F(x_1,\ldots, x_n, u).
 \)

Vamos a usar esto para formular un nuevo teorema de recursión. Definimos

\( \mbox{Sub}(s) = \{t\in \bigcup\limits_{i<\ell(s)}S_i(\{s_j\mid j<\ell(s)\})\mid \exists k<\ell(s)\exists r<\ell(s)(k+r\leq \ell(s)
 \)
\( \land \ell(t)= r\land \forall  j<r\  t_j = s_{k+j})\}. \)

Así \( \mbox{Sub}(s) \) está formado por las subsucesiones \( t\neq s \) de \( s \), en el sentido de que \( s = x\frown\ t\frown\ y \), para ciertos \( x, y \).

Teorema Si \( G \) es un funtor de rango \( n+2 \), existe un funtor \( F \) de rango \( n+1 \) tal que

\( F(x_1, \ldots, x_n, s) = G(x_1, \ldots, x_n, s, [F]|_{\rm Sub(s)}(x_1,\ldots, x_n)). \)

En otros términos: podemos definir un funtor especificando el valor de \( F(x_1, \ldots, x_n, s) \) supuesto definido \( F(x_1, \ldots, x_n, t) \) para todo \( t\in \mbox{Sub}(s) \).

Demostración
Sea \( L(s) = \sum\limits_{i<\ell(s)}(s_i+1) \). Así es claro que

\( t\in \mbox{Sub}(s)\rightarrow L(t)<L(s). \)

Sea
\( S_k = \{s\in \bigcup\limits_{i\leq k}S_i(I_k)\mid L(s)\leq k\}, \)

de modo que \( s\in S_k\leftrightarrow L(s)\leq k \). Notemos que
\( L(s)= k+1\rightarrow \mbox{Sub}(s)\subset S_k. \)

Definimos un funtor \( H \) de rango \( n+1 \) tal que

\( H_k(x_1,\ldots, x_n): S_k\longrightarrow  \mathcal RH_k(x_1,\ldots, x_n). \)

He simplificado ligeramente la construcción que sigue:

Como \( S_0 =\{0\} \), podemos definir

\( H_0(x_1,\ldots, x_n) = \{\left<0, G(x_1,\ldots, x_n, 0, 0)\right>_\infty\} \).

Ahora definimos \( H_{k+1}(x_1, \ldots, x_n) \) supuesto definido \( H_k(x_1, \ldots x_n) \). Dada \( s\in S_{k+1} \), distinguimos dos casos: si \( L(s)\leq k \), entonces \( s\in S_k \) y definimos

\( H_{k+1}(x_1,\ldots, x_n)(s) = H_k(x_1,\ldots, x_n)(s) \).

Esto garantiza que
\( H_k(x_1,\ldots, x_n)\subset H_{k+1}(x_1, \ldots, x_n) \),

de donde, a su vez,
\( k<r\rightarrow H_k(x_1,\ldots, x_n)\subset H_r(x_1, \ldots, x_n). \)

Si \( L(s) = k+1 \), tenemos que \( \mbox{Sub}(s)\subset S_k \), luego podemos considerar el conjunto
\( A\equiv \{\left<u, H_k(x_1,\ldots, x_n)(u))\right>\mid u\in \mbox{Sub}(s)\}, \)

y definimos \( H_{k+1}(x_1,\ldots, x_n)(s) = G(x_1, \ldots, x_n, s, A) \).

Esto completa la definición del funtor \( H \). A su vez podemos definir
\( F(x_1, \ldots, x_n, s) = H_{L(s)}(x_1, \ldots, x_n)(s), \)

y es fácil ver que \( F \) cumple lo requerido (pues en el caso \( k= 0 \) se cumple que \( [F]|_{\rm Sub(0)}(x_1, \ldots, x_n)= 0 \) y en el caso \( k>0 \) el conjunto \( A \) que hemos considerado no es sino \( [F]|_{\rm Sub(s)}(x_1, \ldots, x_n) \).
[cerrar]

Observemos además que si dos funtores \( F_1 \) y \( F_2 \) satisfacen el teorema anterior, entonces podemos probar que

\( F_1(x_1, \ldots, x_n, s) = F_2(x_1, \ldots, x_n, s). \)

Demostración
Si suponemos que \( F_1(x_1, \ldots, x_n, s) \neq F_2(x_1, \ldots, x_n, s) \), podemos considerar

\( m_0 \equiv \mu m\leq L(s)\exists t\in S_m\ F_1(x_1, \ldots, x_n, t) \neq F_2(x_1, \ldots, x_n, t) \)

A su vez, podemos tomar

\( t_0 \equiv \mu t\in S_{m_0}\ F_1(x_1, \ldots, x_n, t) \neq F_2(x_1, \ldots, x_n, t), \)

de modo que
\( F_1(x_1, \ldots, x_n, t_0) \neq F_2(x_1, \ldots, x_n, t_0) \),

pero si \( L(u)<L(t_0)=m_0 \), entonces \( F_1(x_1, \ldots, x_n, u) = F_2(x_1, \ldots, x_n, u) \). Como

\( u\in \mbox{Sub}(t_0)\rightarrow L(u)<L(t_0), \)

resulta que\( [F_1]|_{\rm Sub(t_0)}(x_1, \ldots, x_n)=[F_2]|_{\rm Sub(t_0)}(x_1, \ldots, x_n) \), y entonces la hipótesis sobre \( F_1 \) y \( F_2 \) nos da que \( F_1(x_1, \ldots, x_n, t_0) = F_2(x_1, \ldots x_n, t_0) \), con lo que tenemos una contradicción.
[cerrar]

18 Julio, 2023, 02:48 pm
Respuesta #18

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Para acabar de hacernos una idea lo más clara posible del alcance de ARP, creo que puede ser ilustrativo ver que en ella es posible demostrar las propiedades básicas de los números enteros. La forma usual de definir los números enteros en la teoría de conjuntos es considerar la relación de equivalencia en \( \mathbb N\times \mathbb N \) dada por

\( (a, b)\, R\, (c, d)\equiv a+d = b+c. \)

y definir \( \mathbb Z \) como el conjunto cociente \( (\mathbb N\times \mathbb N)/R \), de forma que cada número entero es un conjunto infinito de pares de números naturales.

Esto no es viable en ARP, porque no podemos definir conjuntos infinitos. Pero en lugar de definir la clase de equivalencia \( [a,b] \) de un par \( (a, b) \) como el conjunto de todos los pares relacionados con él, podemos definirla como un representante canónico de la clase, de modo que dos pares estén relacionados si y sólo si ambos están relacionados con el mismo representante canónico. Eso es lo que vamos a hacer:

Definición Consideramos la relación dada por:

\( (a, b)\, R\, (c, d)\equiv a+d = b+c. \)

A partir de las propiedades de la suma es fácil probar que

\( (a, b)\,R\, (a, b), \qquad (a, b)\,R\, (c, d)\rightarrow (c, d)\, R\, (a, b), \)

\( (a, b)\,R\,(c, d)\land (c, d)\,R\, (e, f)\rightarrow (a, b)\,R\,(e, f). \)

La primera propiedad nos permite definir

\( [a, b] \equiv \mu x\leq \left<a, b\right>_\infty\ \exists uv<x (x = \left<u, v\right>_\infty\land (u, v)\,R\,(a, b)). \)

Como \( x = \left<a, b\right>_\infty \) cumple la propiedad requerida, el mínimo así definido también la cumple y, de hecho,

\( [a, b] = [c, d]\leftrightarrow (a, b)\,R\,(c, d). \)

Esto hace que \( [a,b] \) se comporte exactamente igual que una clase de equivalencia en teoría de conjuntos.

Demostración
Si \( [a, b] = [c, d] \), llamamos \( u \equiv [a, b]_0 \), \( v \equiv [a, b]_1 \), de modo que \( [a, b] = \left<u, v\right>_\infty \) y \( (u, v)\,R\,(a, b) \). Pero también \( (u, v)\,R\,(c, d) \), luego \( (a, b)\,R\,(c, d) \).

Recíprocamente, si $(a, b)\,R\,(c, d)$, tenemos que

\( (u, v)\,R\,(a, b)\leftrightarrow (u, v)\,R\,(c, d), \)

Si aplicamos esto a \( u \equiv [a, b]_0 \), \( v = [a, b]_1 \), \( u' = [c, d]_0 \), \( v' = [c,d]_1 \), tenemos que \( (u', v')\,R\,(c, d) \), luego \( (u', v')\,R\,(a, b) \), luego \( [a, b]\leq [c, d] \), e igualmente se prueba la desigualdad contraria.
[cerrar]

Definición Llamaremos números enteros a los conjuntos (números naturales) de la forma \( [a, b] \). Explícitamente:

\( z\in \mathbb Z\equiv \exists ab< z\ z = [a, b]. \)

Notemos que el \( \in \) que aparece en \( z\in \mathbb Z \) no es la pertenencia entre conjuntos que habíamos definido, sino que \( z\in \mathbb Z \) debe entenderse como la fórmula de ARP con \( z \) como única variable indicada en el miembro derecho.

Definimos los funtores
\( z+z' = [z_0+z'_0, z_1+z'_1],\qquad zz' = [z_0z'_0+z_1z'_1,z_0z'_1+z_1z'_0], \)
y la fórmula
\( z\leq z'\equiv z_0+z'_1\leq z_1+z'_0. \)

Se cumple entonces que
\( [a, b]+ [c, d] = [a+c, b+d],\qquad [a, b]\cdot [c, d] = [ac+bd, ad+bc], \)

\( [a,b]\leq [c, d]\leftrightarrow a+d\leq b+c. \)

Demostración
Llamemos \( z \equiv [a, b] \), \( z' \equiv [c, d] \). Entonces
\( (z_0, z_1)\,R\,(a, b),\qquad (z'_0,z'_1)\,R\,(c, d), \)

luego \( z_0+b = z_1+a \), \( z'_0+d = z'_1+c \), de donde
\( z_0+z'_0+b+d = z_1+z'_1+a+c, \)

luego \( (z_0+z'_0, z_1+z'_1)\,R\,(a+c, b+d), \) luego
\( [a, b]+[c, d] = [z_0+z'_0, z_1+z'_1] = [a+c, b+d]. \)

Con el producto y la relación de orden se razona análogamente.
[cerrar]

Definimos
\( 0\equiv [0, 0],\qquad 1\equiv [1, 0], \qquad -z\equiv [z_1,z_0]. \)

Nota Los números enteros \( 0 \) y \( 1 \) que acabamos de definir no coinciden con los números naturales \( 0 \) y \( 1 \), pero en lo sucesivo el contexto dejará siempre claro si por \( 0,1 \) nos referimos a los números naturales \( 0, 1 \) o a los números enteros \( 0, 1 \), igual que podemos distinguir si hablamos de la suma, el producto y el orden de los números naturales o de los enteros.

Ahora podemos probar:

Teorema Si \( x, y, z\in \mathbb Z \), se cumple:
  • \( (x+y)+z = x+(y+z) \),
  • \( x+y = y+ x \),
  • \( x+0 = x \),
  • \( x+(-x) = 0 \),
  • \( (xy)z = x(yz) \),
  • \( xy = yx \),
  • \( x\cdot 1 = x \),
  • \( x(y+z)=xy+xz \),
  • \( x\leq x \),
  • \( x\leq y\land y\leq x\rightarrow x = y \),
  • \( x\leq y\land y\leq z\rightarrow x\leq z \),
  • \( x\leq y\lor y\leq x \),
  • \( x\leq y \rightarrow x+z\leq y+z \),
  • \( x\geq 0\land y\geq 0\rightarrow xy\geq 0 \).
Estas afirmaciones son lo que en álgebra se llaman axiomas de anillo ordenado conmutativo y unitario. Todas las comprobaciones son rutinarias. Veamos la primera igualdad, por ejemplo:

Demostración
\( (x+y)+z = [x_0+y_0, x_1+y_1]+[z_0, z_1] = [x_0+y_0+z_0, x_1+y_1+z_1] \)

y \( x+(y+z) \) lleva a la misma expresión.
[cerrar]

A cada número entero \( z\in \mathbb Z \) le podemos asignar un valor absoluto como sigue:

\( |z|= \cases{z_0\dot{-} z_1&si $z_0\geq z_1$,\cr z_1\dot{-} z_0&si $z_0\leq z_1$.} \)

Por otro lado, definimos \( +n = [n,0] \), de modo que \( +0 \) y \( +1 \) coinciden con los números enteros que hemos llamado \( 0 \) y \( 1 \), respectivamente. Escribiremos \( -n \equiv -(+n) \). En general, tenemos:

Teorema Se cumple:
  • \( +n\in \mathbb Z \),
  • \( +m = +n\leftrightarrow m=n \),
  • \( +(m+n) = +m+(+n) \),
  • \( +(mn) = (+m)(+n) \),
  • \( m\leq n\leftrightarrow +m\leq +n \),
  • \( z\in \mathbb Z\land z\geq 0\rightarrow z = +|z| \),
  • \( z\in \mathbb Z\land z\leq 0\rightarrow z = -|z| \).
Demostración
1) Es inmediato. Para probar 2) observamos que

\( +m = +n \leftrightarrow [m,0]= [n,0]\leftrightarrow m+0 = n+0 \leftrightarrow m = n. \)

3) \( +m + (+n) = [m, 0]+[n,0] = [m+n, 0+0]= +(m+n) \). La prueba de 4) y 5) es similar.

Para probar 6) observamos que \( z\geq 0 \) equivale a \( z_0\geq z_1 \), con lo que

\( z_0 = z_1+(z_0\dot{-} z_1) = z_1+|z|, \)

y esto equivale a \( z=[z_0, z_1] =[|z|,0]=+|z| \). El razonamiento para 7) es análogo.
[cerrar]

Observemos ahora que \( y\leq z\leftrightarrow -z\leq -y \), pues

\( y< z\leftrightarrow y+(-y)+(-z)< z+(-z)+(-y)\leftrightarrow 0-z< 0-y\leftrightarrow -z< -y. \)

Con todo esto ya podemos afirmar que los números enteros son:

\( \cdots\quad < -3< -2< -1< 0 < +1 < +2 < + 3 <\quad \cdots \)

y en la práctica escribiremos \( n \) en vez de \( +n \), con lo que los números enteros pueden expresarse así:

\( \cdots\quad < -3< -2< -1< 0< 1 < 2 < 3 <\quad \cdots \)

Por lo tanto, si llamamos números enteros positivos (resp. negativos) a los que cumplen

\( z\in \mathbb Z^+\equiv z\in \mathbb Z\land z >0,\qquad  z\in \mathbb Z^-\equiv z\in \mathbb Z\land z<0 \)
,
resulta que

\( z\in \mathbb Z\rightarrow z\in \mathbb Z^-\lor z = 0\lor z\in \mathbb Z^+ \)

y no pueden darse a la vez dos de estos tres casos, y podemos identificar los números naturales con el \( 0 \) y los números enteros positivos, en el sentido de que cualquier suma como \( 2+3 = 5 \), o cualquier producto como \( 2\cdot 3 = 6 \), o cualquier desigualdad como \( 2\leq 5 \) es correcta o no tanto si consideramos que los números son naturales o enteros no negativos.

Más precisamente, si estamos considerando números naturales y necesitamos verlos como enteros, sólo tenemos que cambiar cada \( n \) por \( +n \) y, si estamos considerando números enteros no negativos y necesitamos verlos como naturales, sólo tenemos que cambiar cada \( z \) por \( |z| \).

Ahora podemos caracterizar el valor absoluto de un número entero como

\( |z| = \cases{\phantom-z& si $z\geq 0$,\cr -z&si $z\leq 0$,} \)
y es fácil probar:

  • \( |z|\geq 0, \qquad |z|=0\leftrightarrow z = 0 \),
  • \( |w+z|\leq |w|+|z| \),
  • \( |wz| = |w||z| \).
Estas propiedades nos dan una prueba rápida de otro hecho relevante de la aritmética de los números enteros, y es que
\( wz = 0\leftrightarrow w = 0\lor z = 0. \)

A partir de los resultados que hemos enunciado aquí se pueden probar todos los hechos básicos sobre la aritmética de los números enteros de forma natural, es decir, sin necesidad de tecnicismos propios de ARP (más allá de la necesidad de que todas las pruebas de existencia sean constructivas).

Por ejemplo, para probar que es posible dividir euclídeamente números enteros definimos

\( c^*(D, d) = \cases{\phantom-c(|D|, |d|)&si $D\geq 0$, $d>0$ o $D<0$, $d<0$, $r(|D|, |d|)=0$,\cr
-c(|D|, |d|)&si $D\geq 0$, $d<0$ o $D<0$, $d>0$, $r(|D|, |d|)=0$,\cr -c(|D|,|d|)-1&si $D<0$, $d>0$, $r(|D|, |d|)>0$, \cr
\phantom- c(|D|, |d|)+1&si $D<0$, $d<0$, $r(|D|, |d|)>0$,}
 \)

\( r^*(D, d) = \cases{\phantom-r(|D|, |d|)&si $D\geq 0$ o $r(|D|, |d|)=0$,\cr \phantom-d-r(|D|, |d|)&si $D<0$, $d>0$, $r(|D|, |d|)>0$,\cr -d-r(|D|, |d|)&si $D<0$, $d<0$, $r(|D|, |d|)>0$,}
 \)
donde \( c \) y \( r \) son los funtores que dan el cociente y el resto de la división euclídea de números naturales. A partir de aquí escribiremos \( c \) y \( r \) en lugar de \( c^* \) y \( r^* \). Entonces

Teorema Se cumple:
\( D, d\in \mathbb Z\land d\neq 0\rightarrow D = d c(D, d)+r(D, d)\land 0\leq r(D, d)<|d|, \)

\( D, d, c, r\in \mathbb Z\land d\neq 0\land D=dc+r\land 0\leq r<|d|\rightarrow c = c(D, d)\land r = r(D, d). \)

Demostración
Sólo hay que distinguir los cuatro casos posibles para el signo de \( D \) y \( d \). Por ejemplo, si \( D<0 \), \( d>0 \), tenemos que

\( |D| = |d| c(|D|, |d|)+r(|D|, |d|)\land 0\leq r(|D|, |d|)<|d|, \)

luego, multiplicando por \( -1 \),
\( D =d(-c(|D|, |d|)) -r(|D|, |d|) \)

Si \( r(|D|, |d|)=0 \) esto ya es \( D = d c(D, d)+r(D, d) \). Si \( r(|D|, |d|)>0 \), entonces

\( D = d(-c(|D|, |d|)-1)+d-r(|D|, |d|) = d c(D, d)+r(D, d), \)

y además \( 0< r(|D|, |d|)< d \), luego \( 0\leq d-r(|D|, |d|)= r(D, d)<d = |d| \). Los otros casos se tratan análogamente.

Similarmente, si se cumple \( D = dc + r\land 0\leq r<|d| \), en el caso \( D<0 \), \( d>0 \), o bien \( r=0 \), en cuyo caso \( |D| = |d|(-c)+0 \), con lo que, por el teorema de división euclídea para números naturales, tiene que ser \( c = -c(|D|, |d|) = c(D, d) \) y \( r = r(|D|, |d|)=r(D, d) \), o bien \( 0<r<d \), en cuyo caso

\( |D| = |d|(-c)-r = |d|(-c-1)+d-r,\qquad 0\leq d-r<d, \)

con lo que nuevamente \( c(|D|, |d|) = -c-1 \), \( r(|D|, |d|) = d-r \), de donde se concluye igualmente que \( c = c(D, d) \), \( r = r(D, d) \).
[cerrar]



Ahora es evidente que la construcción conjuntista típica de \( \mathbb Q \) a partir de \( \mathbb Z \) puede formalizarse en ARP con el mismo truco de cambiar las clases de equivalencia por representantes canónicos, y así podemos probar las propiedades básicas de los números racionales, podemos definir, por ejemplo, los números combinatorios y demostrar el teorema del binomio de Newton, etc.

Más aún, igualmente podemos definir en ARP el anillo \( \mathbb Q[x] \) de los polinomios con una indeterminada (o con un número finito de ellas, si se quiere), pues, al fin y al cabo, un polinomio no es más que una sucesión finita de números racionales con la suma y el producto definidos adecuadamente.

Más aún, es posible definir cocientes \( \mathbb Q[x]/(p(x)) \) con el mismo truco de sustituir las clases de equivalencia por representantes, y en particular podemos definir el cuerpo \( \mathbb Q(i) \), que contiene al anillo \( \mathbb Z(i) \) de los enteros de Gauss, y demostrar que éste tiene factorización única, o se pueden definir los cuerpos ciclotómicos \( \mathbb Q(\omega) \), donde \( \omega \) es una raíz \( n \)-sima de la unidad.

Obviamente no me he puesto a comprobar los detalles, pero dudo mucho que haya algo en este hilo, por ejemplo, que no sea formalizable en ARP sin emplear técnicas más allá de las que hemos visto sin más que sustituir toda mención a los números complejos por números algebraicos construidos como elementos de cuerpos de cocientes de \( \mathbb Q[x] \) respecto de polinomios irreducibles.

20 Julio, 2023, 03:48 pm
Respuesta #19

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Dedico un mensaje breve a algo que pensaba incluir en el mensaje siguiente, pero así me aprovecha para responder a lo que se ha planteado en el hilo de comentarios sobre la construcción de anillos de polinomios en ARP.

Se trata simplemente de la generalización a sumas arbitrarias de las sumas finitas de números naturales. Para que los resultados sean aplicables en contextos diversos, partimos de las hipótesis siguientes:

Supongamos que hemos fijado una cierta fórmula \( \phi(x, x_1,\ldots, x_n) \) que abreviaremos \( x\in A  \)(sin mencionar explícitamente los parámetros \( x_1,\ldots, x_n \)) y que tenemos términos

\( 0\equiv 0(x_1,\ldots, x_n),\qquad x+y \equiv +(x, y, x_1,\ldots, x_n) \)

de modo que podemos demostrar:

  • \( +: A\times A\longrightarrow A\equiv u\in A\land v\in A\rightarrow u+v\in A \),
  • \( u\in A\land v\in A\land w\in A\rightarrow (u+v)+w = u+(v+w) \),
  • \( 0\in A \),
  • \( u\in A\rightarrow u+0 = u \).
Para cada término \( t(i) \) (tal vez con más variables), definimos:

\( \sum\limits_{i<0}t(i)= 0,\qquad \sum\limits_{i<n+1}t(i) = \sum\limits_{i<n}t(i)+t(n). \)

En estas condiciones, es fácil ver (por inducción sobre \( n \)) que

\( \forall i<n\ t(i)\in A\rightarrow \sum\limits_{i<n}t(i)\in A, \)

\( \forall i<n\ (t(i)\in A\land t(i) = t'(i))\rightarrow \sum\limits_{i<n}t(i) = \sum\limits_{i<n}t'(i). \)

\( \forall i<m+n\ t(i)\in A\rightarrow \sum\limits_{i<m+n}t(i) = \sum\limits_{i<m}t(i)+\sum\limits_{i<n}t(m+i). \)

En lo que falta de este hilo, sólo nos va a hacer falta un caso particular de esta situación, en la que \( x\in A\equiv x = x \) (es decir, no restringimos el dominio de la suma) y tomando como suma la concatenación de sucesiones, es decir, \( x+y \equiv x\frown y \) (y \( 0 \) es el número natural cero, que se identifica con la sucesión vacía de longitud \( 0 \)).

Es claro que en este caso podemos demostrar las cuatro fórmulas que hemos supuesto, por lo que tenemos definidas las sumas finitas (aunque en este caso las representaremos como productos): \( \prod\limits_{i\leq n}t(i) \) o, más cómodamente, como \( t_0\cdots t_n \) (donde aquí es crucial que \( n \) no es un numeral, sino una variable), de modo que se cumplen los hechos siguientes (el primero es por definición):

  • \( t_0\cdots t_{n+1} = (t_0\cdots t_n)\frown t_{n+1} \),
  • \( \forall i\leq n (t(i) = t'(i))\rightarrow t_0\cdots t_n = t'_0\cdots t'_n \),
  • \( t_0\cdots t_{m+n} = (t_0\cdots t_m)\frown (t_{m+1}\cdots t_{m+n}) \).



No vamos a necesitar nada más, pero menciono también que otro contexto en el que todo esto es aplicable es el que resulta de tomar \( x\in \mathbb Z \) como dominio de la suma y como funtor "suma" bien la suma o bien el producto de números enteros (con el \( 0 \) o el \( 1 \) como neutro en cada caso).

Y si uno va a manipular sumas o productos finitos de números enteros (o de números racionales, o de polinomios, etc.) tarde o temprano necesitará usar la propiedad conmutativa generalizada. En el contexto general consiste en probar que si suponemos una condición más, a saber:

\( u\in A\land v\in A\rightarrow u+v = v+u \)

entonces podemos demostrar

\( f: I_n\longrightarrow I_n\mbox{ biyectiva}\land \forall i<n\ t(i)\in A\rightarrow \sum\limits_{i<n}t(f(i))=\sum\limits_{i<n}t(i). \)