Autor Tema: La Aritmética Recursiva Primitiva

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

03 Junio, 2023, 04:25 pm
Leído 12762 veces

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
A raíz de lo que estábamos hablando en este hilo:

Comentarios a "Ordinales menores que \( \epsilon_0 \)"

se me ocurrió que podría ser interesante dedicar otro a describir la Aritmética Recursiva Primitiva (ARP, o PRA en inglés). Se trata de una teoría axiomática más débil que la Aritmética de Peano, pero que es suficiente para formalizar buena parte de la lógica matemática (esencialmente, la parte puramente sintáctica, la que no tiene que ver con modelos), y que se considera que captura la noción de finitismo más conservadora, que sólo admite pruebas constructivas que no requieran conjuntos o sucesiones infinitas de forma esencial.

Por una parte, voy a tratar de explicitar los hechos sobre números naturales que es necesario aceptar —aunque yo diría mejor "entender que son ciertos"— para construir ARP reduciéndolos a su mínima expresión y, por otra parte, voy a presentar la teoría en una versión lo más simple posible, para que la metamatemática indispensable se reduzca también a lo imprescindible. Esto pretende contribuir a un asunto sobre el que hemos discutido en este foro más de una vez, y es qué supuestos metamatemáticos son necesarios para fundamentar la matemática formal.

Me basaré en el artículo

Logic-Free formalisations of Recursive Arithmetic de R.L. Goodstein, Mathematica Scandinavica Vol. 2 No 2 (1954), pp 247-261,

pero me va a ocupar bastante más de las 14 páginas que ocupa el artículo.

Precisamente, otra de las razones por las que considero que puede ser interesante este hilo es que se trata de una teoría relativamente relevante en la lógica matemática, pero sobre la que es difícil leer algo detallado fuera de publicaciones muy especializadas.

Como en otros hilos de naturaleza similar a la de éste, he creado otro hilo paralelo para comentarios en el que cualquiera está invitado a intervenir, de modo que los comentarios sobre el hilo no se intercalen con la exposición y entorpezcan la lectura:

Comentarios a "La Aritmética Recursiva Primitiva"

03 Junio, 2023, 05:58 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Decía Raymond Smullyan que un formalista es un matemático que es incapaz de entender algo a menos que carezca de significado.

En principio, es posible razonar formal e informalmente: un razonamiento es informal cuando la comprobación de que es correcto consiste en asegurarse de que cada cosa que se afirma es verdad, mientras que un razonamiento es formal si su corrección consiste en que la inclusión en él de cada afirmación se justifica en que, o bien es un axioma que se acepta sin cuestionarlo, o bien se sigue de afirmaciones anteriores por reglas que atienden exclusivamente a la forma sintáctica de las afirmaciones. Por ejemplo, si ya se han incluido en el razonamiento una afirmación \( p \) y otra \( p\rightarrow q \), podemos incluir también \( q \), sin preocuparnos en ningún momento (ni en este ejemplo, ni en general) de lo que significan las afirmaciones consideradas, hasta el punto de que es irrelevante o no que signifiquen algo.

El sueño del formalista caricaturizado por Smullyan es reducir toda la matemática a razonamientos formales, y considerar que cualquier razonamiento informal es dudoso, sospechoso, poco riguroso y está sin duda implicado en el asesinato de JFK. Pero, a poco que se cuestione sus planteamientos, el formalista se ve obligado a despertar de su sueño y conceder que, para definir un lenguaje formal (en el que se puedan formular afirmaciones sin necesidad de tener en cuenta para nada su posible significado) y precisar unas reglas de razonamiento, es necesario razonar (sí, informalmente) sobre algunos conceptos básicos para hablar de signos, cadenas de signos, sucesiones de cadenas de signos, demostraciones, etc., y entonces su máxima preocupación es reducir al mínimo esta vergonzosa e innoble parte del pensamiento matemático para disponer lo antes posible de un sólido formalismo en el que refugiarse para siempre jamás.

Una queja frecuente entre los formalistas que desconfían de todo razonamiento intuitivo informal es que los libros de lógica razonan informalmente con toda alegría sin dejar constancia precisa de en qué principios se basan. En realidad no hay ninguna necesidad de reducir al mínimo el razonamiento intuitivo informal: el razonamiento formal sólo es indispensable cuando uno se propone hablar de conceptos muy abstractos, como la medida de Lebesgue en \( \mathbb R^n \) y cosas así, pero uno podría desarrollar perfectamente un curso entero de teoría de grupos finitos, o de teoría de grafos o incluso de teoría de números con todo rigor sin necesitar en ningún momento de ninguna teoría axiomática formal. No obstante, voy a aprovechar este hilo para tratar de contribuir al sueño del formalista despierto (el que ya ha asumido que algo de razonamiento informal va a necesitar) y tratar de construir ARP apoyándome en un conjunto de hechos intuitivamente ciertos sobre los números naturales lo más reducido posible.

En este mensaje describiré lo poco que necesita entender un lector sobre los números naturales para entender la construcción de ARP y en el mensaje siguiente describiré lo poco que necesita para entender ARP, es decir, para entender que las fórmulas de ARP no son cadenas de signos sin sentido, sino que se pueden interpretar como ciertas afirmaciones sobre los números naturales.

En otras palabras: este mensaje contendrá lo que un formalista necesita entender mal que le pese, y el siguiente lo que un formalista puede despreciar si se conforma con razonar formalmente en ARP sin preocuparse del significado de sus teoremas.

En realidad, los mensajes que vendrán están sin escribir, por lo que no puedo saber exactamente qué me va a hacer falta, pero de momento voy a apostar a que no me hará falta nada más que lo que voy a indicar a continuación y, si en algún momento hiciera falta algo más, ya lo añadiría.

El lector formalista radical está invitado a vigilar si hago uso de algo no declarado en la aduana y a denunciarlo inmediatamente en el hilo de comentarios. Su denuncia será debidamente investigada y debatida.



En resumen, lo que necesita el lector para entender la construcción de ARP es poco más que el hecho de que los números naturales son

0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   10,   11,   12,  13,   ...

pero, en realidad, esta modesta afirmación contiene ya más de lo que es necesario suponer que sabe el lector, pues en ella está implícito el sistema de numeración posicional decimal que nos permite entender que \( 13 \) es el número compuesto por una decena y tres unidades. Esto es mucho más de lo que necesitamos saber.

Puestos a apretarnos el cinturón, podemos reducir a esto el conocimiento requerido sobre los números naturales:

  • Existe un primer número natural, al que llamaremos cero.

    No tiene sentido preguntarse qué es el cero, de qué está hecho, quién lo ha creado, etc., porque el cero no es nada más que un nombre abstracto de nada en particular.

  • Todo número natural tiene un sucesor, que es un número natural "nuevo", distinto de todos los anteriores.

    Así, después del cero viene "el siguiente de cero", y luego "el siguiente del siguiente de cero", y luego "el siguiente del siguiente del siguiente de cero", etc., de forma que "el siguiente de cero" (que podemos abreviar con el nombre de "uno") no es nada en particular, sino que los números naturales son como piezas de un juego abstracto: a la primera la llamamos "cero", a la segunda "siguiente de cero (vulgo uno)", a la tercera "siguiente del siguiente de cero (vulgo dos)", etc. Son sólo nombres, como rey, dama, alfil, caballo, etc, con la peculidaridad de que la lista de los números naturales no termina nunca. De acuerdo con este segundo principio, podemos pensar en un número natural "siguiente del siguiente del siguiente..." en el que la palabra "siguiente" aparezca más veces que átomos hay en el universo o que nanosegundos tiene el universo desde el big bang. Sólo hay que entender que, dado un número natural, nada nos impide añadirle un "siguiente de" para tener otro nuevo.

  • No hay más números naturales que el cero, el siguiente de cero, el siguiente del siguiente de cero y, en general, todos los que se obtienen del cero aplicando repetidamente la operación "siguiente".
Nada de esto debe entenderse como "cosas que hay que creerse" sobre los números naturales, sino que son más bien la definición de "número natural". Nadie nace sabiendo el significado de las palabras "número natural", por lo que todos, en algún momento de su vida, tienen que asociarles un significado, y el significado de estas palabras es el determinado por las tres propiedades anteriores, ni más ni menos.

Por ejemplo, no tiene sentido plantearse si realmente "el siguiente del siguiente del siguiente de cero" (lo que podemos abreviar en un simple "tres") es realmente un número distinto de "el siguiente de cero" (es decir, del uno), o si, sin que nos diéramos cuenta, podría suceder que el uno y el tres fueran lo mismo. Eso es lo mismo que plantearse si no podría ocurrir que un caballo del juego del ajedrez fuera realmente un alfil que una bruja ha tansformado en cuadrúpedo, por lo que en realidad debería moverse en diagonal y todas las partidas de ajedrez jugadas hasta la fecha están mal. Del mismo modo que un caballo no es un alfil por definición, el tres no es el uno por definición. Lo contrario es tan imposible como que un cuadrado no tenga cuatro lados.

Una vez fijadas estas tres características que definen los números naturales (que si las cambiamos estamos dejando de hablar de los números naturales para hablar de otra cosa) todo lo demás que afirmemos sobre ellos habrá que justificarlo y cualquier concepto relacionado con ellos habrá que definirlo.

Por ejemplo, si \( m \) y \( n \) son dos números naturales, diremos que \( m< n \) (o que \( n>m \)) si \( m \) aparece antes que \( n \) en la sucesión:

cero,   siguiente de cero,   siguiente del siguiente de cero,   siguiente del siguiente del siguiente de cero,   ...

con lo cual, por la propiedad 3, que asegura que todos los números naturales tienen que salir en esa sucesión, es claro que, o bien \( m<n \), o bien \( n<m \), o bien \( m = n \), es decir, que en realidad \( m \) y \( n \) estén haciendo referencia al mismo número natural. Lo que dice la propiedad 2 es que esto no puede ocurrir más que cuando obviamente ocurre, es decir, que no puede haber igualdades entre números naturales que la humanidad no haya descubierto hasta la fecha (no digo entre expresiones aritméticas o de otra clase construidas a partir de números naturales, como \( 4+1 = 3+2 \), sino entre números puros y duros, expresados como siguientes de siguientes de cero). Por ejemplo:

El siguiente del siguiente de cero =  el siguiente del siguiente de cero,

El siguiente del siguiente de cero \( \neq \) el siguiente del siguiente del siguiente del siguiente de cero,

porque la propiedad 2 establece que "el siguiente del siguiente del siguiente del siguiente de cero" es distinto de todos los números anteriores, como "el siguiente del siguiente de cero".

Usaremos la notación \( m\leq n \) y \( m\geq n \) en el sentido usual de ser menor (o mayor) o igual.

Es fácil probar consecuencias obvias, como que si \( m<n \) y \( n<p \), entonces \( m<p \), pues si \( m \) aparece primero en la sucesión, luego aparece \( n \) y luego aparece \( p \), entonces \( m \) ha aparecido antes que \( p \).

Por último, mencionamos dos hechos fundamentales básicos sobre los números naturales, que son, por supuesto, consecuencia de las tres propiedades que los definen:

Principio de buena ordenación: Si un número natural cumple una determinada propiedad, existe un mínimo número natural con dicha propiedad, es decir, un número natural que tiene la propiedad y ninguno menor la cumple también.

Esto es inmediato: basta ir recorriendo la sucesión:

cero,   siguiente de cero,   siguiente del siguiente de cero,   siguiente del siguiente del siguiente de cero,   ...

hasta que aparezca un número natural con la propiedad en cuestión. El primero que aparezca será el mínimo buscado. Tiene que aparecer uno porque estamos suponiendo que hay un número natural que tiene la propiedad y, por la propiedad 3, todos los números naturales aparecen en la sucesión.

Principio de inducción Si probamos que el número cero tiene una propiedad y, suponiendo que un número arbitrario \( n \) la posee, podemos justificar que lo mismo le sucede a su siguiente, podemos concluir que todos los números naturales tienen dicha propiedad.

En efecto, si algún número natural no tuviera la propiedad, existiría un mínimo número natural sin ella. No podría ser el cero, porque hemos probado que la tiene, luego tendría que ser el siguiente de otro número \( n \), pero como el siguiente de \( n \) es el menor número natural que no tiene la propiedad y \( n \) es menor que el siguiente de \( n \) (porque aparece justo antes en la sucesión), el número \( n \) debería tenerla, pero estamos suponiendo que hemos razonado que en tal caso el siguiente de \( n \) también la tiene, con lo que tenemos una contradicción.

Naturalmente, estos argumentos suponen que hablamos de una propiedad objetiva, que tenga sentido asegurar que un número la tiene o no la tiene. Nosotros sólo necesitaremos usar estos principios respecto de propiedades que, más que eso, sabremos cómo comprobar explícitamente si un número dado la tiene o no.

En la práctica, porque la vida es breve y conviene aprovecharla, el lector deberá consentir en que escribamos cosas como \( 12 \) en lugar de

el siguiente del siguiente del siguiente del siguiente del siguiente del siguiente
del siguiente del siguiente del siguiente del siguiente del siguiente del siguiente de cero.

Esto no supone en teoría que el lector deba conocer el sistema de numeración decimal, pero, como de hecho lo conoce, así nos ahorramos retahílas monstruosas, pero de modo que cada vez que aparezca un 3 o un 12 o un 454 en el texto, siempre sea posible sustituir el nombre abreviado por el nombre completo del número en cuestión sin cambiar para nada el significado de lo que se afirme.

Aparte de esto, sólo necesitaremos que el lector sepa contar o, dicho de otro modo, que sepa numerar conjuntos finitos con los primeros números naturales, es decir, que entienda lo que decimos si decimos que \( n_0, n_1, \ldots, n_k \) son ciertos números naturales (podría haber escrito equivalentemente

\( n_{\rm cero}, n_{\rm siguiente\ de\ cero}, \ldots , n_k \)
pero la vida es breve y hay que aprovecharla).

Una consecuencia del principio de buena ordenación es que no puede haber sucesiones estrictamente decrecientes de números naturales. Si pudiéramos construir una sucesión de números naturales

\( n_0 >n_1> n_2 >\cdots \)

que no se acabara nunca, existirían sin duda números naturales con la propiedad de estar en esta sucesión (como \( n_0 \)), pero no existiría el mínimo de todos ellos, y tendríamos una contradicción.

Los lectores formalistas radicales críticos con la "informalidad" de los libros de metamatemática quedan invitados a exponer qué más necesitan para convencerse de que cualquiera de las cosas que he dicho aquí son ciertas (no asumibles, sino ciertas) y a vigilar si en el futuro me saco algún as de la manga, es decir, alguna propiedad más de los números naturales que no esté declarada en este mensaje.

Nótese en particular que, aunque seguro que el lector sabe sumar, y multiplicar, y esas cosas, no necesitaré apoyarme en esos conocimientos para construir ARP.

04 Junio, 2023, 01:05 am
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Tal y como he dicho en el mensaje anterior, aquí voy a contar lo poco que hay que entender para entender los teoremas de ARP en lugar de verlos como meras cadenas de signos sin sentido. En la Aritmética Recursiva Primitiva podemos hablar de los números naturales y de las funciones recursivas primitivas, de modo que lo único que necesitamos es la definición de "función recursiva primitiva".

Las funciones recursivas primitivas las introdujo Gödel para demostrar sus teoremas de incompletitud, aunque él las llamó simplemente "funciones recursivas". Más tarde, Herbrand introdujo una clase más extensa de funciones a las que llamó "funciones recursivas generales", pero posteriormente se pasó a llamar "funciones recursivas" a las funciones recursivas generales y así a las funciones recursivas de Gödel se las pasó a llamar "funciones recursivas primitivas".

En este mensaje entenderemos que una función \( n \)-ádica \( F \) (donde \( n \) es un número natural no nulo) es cualquier criterio que a \( n \) números naturales \( a_1,\ldots, a_n \), dados en un cierto orden con posibles repeticiones, les asigna un número natural que representaremos por \( F(a_1,\ldots, a_n) \).

Se podría filosofar mucho sobre cómo ha de ser el criterio para que se pueda considerar objetivo e inequívoco, pero eso no nos tiene que preocupar, porque sólo nos van a interesar unas funciones muy concretas en las que no va a caber duda de que están bien definidas.

Nota Aunque hemos prometido que no necesitaríamos que el lector sepa sumar, sólo a modo de abreviatura, para no desperdiciar la vida escribiendo cosas muy largas, si \( n \) es un número natural, escribiremos \( n+1 \) para referirnos al siguiente de \( n \) y \( n+2 \) para referirnos al siguiente del siguiente de \( n \).

Para empezar, definimos las funciones recursivas elementales como las funciones siguientes:

  • La función monádica \( S \) (o función sucesor) que a cada número natural \( n \) le hace corresponder \( S(n) = n+1 \).

    En estos términos, si representamos por \( 0 \) el número natural cero, los números naturales son

    \( 0, \quad  S(0),  \quad    S(S(0)),  \quad    S(S(S(0))),   \quad   S(S(S(S(0)))),    \quad  \ldots \)

  • La función monádica \( c_0 \) (función cero) que a cada número natural \( n \) le hace corresponder \( c_0(n) = 0 \).

  • Para cada par de números naturales \( 1\leq i\leq n \), la función \( n \)-ádica \( p^n_i \) (la \( i \)-ésima proyección \( n \)-ádica) dada por  \( p^n_i(a_1,\ldots, a_n) = a_i \).

El lector deberá reconocer que no hay ninguna ambigüedad posible en la definición de estas funciones, y que es posible programar a un ordenador para que nos calcule cualquiera de ellas para unos argumentos dados cualesquiera (haciendo abstracción de las posibles limitaciones de memoria del ordenador o del universo).

Ahora vamos a describir dos formas de definir nuevas funciones a partir de unas funciones dadas:

Composición de funciones Si \( G_1, \ldots, G_m \) son funciones \( n \)-ádicas y \( H \) es una función \( m \)-ádica, definimos la función definida por composición a partir de \( H \) y \( G_1,\ldots, G_m \) como la función dada por
\( F(a_1,\ldots, a_n) = H(G_1(a_1,\ldots, a_n), \ldots, G_m(a_1,\ldots, a_n)) \).

En otras palabras, dados los argumentos \( a_1,\ldots, a_n \), calculamos los números \( G_1(a_1,\ldots, a_n), \ldots, G_m(a_1,\ldots, a_n) \) y los usamos como argumentos para la función \( H \), y así obtenemos el valor de \( F \) sobre los números dados.

Está claro que si sabemos calcular en la práctica las funciones dadas sobre números cualesquiera, también podemos calcular su composición sobre números dados cualesquiera. Si podemos programar a un ordenador para que calcule las funciones \( \color{red}H \) y \( \color{red}G_i \), también podemos programarlo para que calcule \( \color{red}F \).

Funciones definidas por recursión Si \( G \) es una función \( n \)-ádica y \( H \) es una función \( n+2 \)-ádica, podemos definir como sigue una función \( n+1 \)-ádica \( F \) determinada por las condiciones siguientes:
\( \begin{eqnarray*}
F(m_1,\ldots, m_n, 0) &=& G(m_1,\ldots, m_n)\\
F(m_1,\ldots, m_n, k+1)&=&H(m_1,\ldots, m_n,k,F(m_1,\ldots, m_n, k)).
\end{eqnarray*}
 \)

Se dice que \( F \) es la función definida por recursión a partir de \( G \) y \( H \).

Por ejempo, si \( G \) es diádica y \( H \) es tetrádica, la función que definen por recursión se puede calcular como sigue. Si queremos calcular, por ejemplo, \( F(1, 2, 3) \), en primer lugar, calculamos

\( F(1, 2, 0) = G(1, 2) \).

Una vez conocemos \( F(1, 2, 0) \), calculamos

\( F(1, 2, 1) = H(1, 2, 0, F(1, 2, 0)) \).

Con este valor podemos calcular

\( F(1, 2, 2) = H(1, 2, 1, F(1, 2, 1)) \),

y a su vez, con este valor, obtenemos

\( F(1, 2, 3) = H(1, 2, 2, F(1, 2, 2)) \).

Es obvio que, de este modo, podemos calcular cualquier valor \( F(a, b, c) \), empezando con \( F(a, b, 0) \), luego \( F(a, b, 1) \), etc., hasta llegar a \( F(a, b, c) \).

Aquí sólo estamos usando que cada número natural \( c \) se puede obtener avanzando desde el \( 0 \) aplicando la operación "siguiente" las veces que sea preciso (es decir, \( c \) veces).

Es claro que si podemos programar a un ordenador para que calcule las funciones \( G \) y \( H \) sobre argumentos dados cualesquiera, también podemos programarlo para que calcule la función \( F \) sobre argumentos cualesquiera. Dicha función está unívocamente determinada.

Veamos algunos ejemplos concretos:
  • Al componer la función \( S \) con la función \( p^3_3 \) obtenemos la función \( H \) dada por \( H(m, n, r) = r+1. \)

  • La función \( F \) definida por recursión a partir de \( p^1_1 \) y \( H \) cumple

    \( \begin{eqnarray*}
    F(m, 0) &=&p_1^1(m) = m\\
    F(m, n+1) &=& H(m, n, F(m, n)) = S(F(m, n)) = F(m, n)+1.
    \end{eqnarray*} \)

    Estas condiciones determinan una única función que se puede calcular como hemos explicado. Si el lector sabe sumar (conocimiento al que sólo apelamos para que entienda este ejemplo, que podríamos omitir), sabrá que la función \( F(m, n) = m+n \) cumple estas dos propiedades, pues, en efecto:
    \( m+0 = m,\qquad m+(n+1) = (m+n)+1, \)

    luego \( F \) no es más que la suma usual de números naturales.

  • La composición de la función suma con las funciones \( p^3_3 \) y \( p^3_1 \) nos da una función \( H^* \) dada por:

    \( H^*(m, n, r) = F(p^3_3(m, n, r), p^3_1(m, n, r)) = r+m. \)

  • La función \( F^* \) definida por recursión a partir de la función \( c_0 \) y de la función \( H^* \) cumple:

    \( \begin{eqnarray*}
    F^*(m, 0) &=&c_0(m) = 0\\
    F^*(m, n+1) &=& H^*(m, n, F^*(m, n)) = F^*(m, n)+m.
    \end{eqnarray*} \)

    Si el lector sabe multiplicar (cosa que sólo necesitamos suponer para que entienda este ejemplo), sabrá que la función \( F^*(m, n) = mn \) cumple estas propiedades, pues
    \( m\cdot 0 = 0,\qquad m(n+1) = mn + m. \)

    luego la función que acabamos de definir no es sino el producto usual de números naturales.

Funciones recursivas primitivas Ahora podemos definir las funciones recursivas primitivas como las funciones que pueden obtenerse a partir de las funciones recursivas elementales mediante composiciones y recursiones sucesivas.

En estos términos, los ejemplos precedentes muestran que la suma y el producto usual de números naturales son dos ejemplos de funciones diádicas recursivas primitivas.

Si el lector considera poco preciso lo de "pueden obtenerse a partir de", podemos dar una definición de función recursiva más operativa:

Una función \( F \) es recursiva primitiva si existe una sucesión de funciones \( F_1, \ldots F_r \), donde \( F_r \) es la propia \( F \), de modo que cada función \( F_i \) es recursiva elemental o bien se obtiene por composición o recursión a partir de funciones precedentes de la sucesión.

Por ejemplo, en el caso de la función producto, una sucesión que atestigua su carácter recursivo primitivo es:

\( \begin{array}{ll}
F_1(m,n,r) = r&\text{Recursiva elemental } (p^3_3)\\
F_2(r) = Sr&\text{Recursiva elemental }(S)\\
F_3(m, n, r)=Sr&\text{Composición de }F_2 \text{ y } F_1\\
F_4(m)=m&\text{Recursiva elemental }(p^1_1)\\
F_5(m, n) = m+n&\text{Recursión con }F_4, F_3\\
F_6(m, n, r) = m&\text{Recursiva elemental }(p^3_1)\\
F_7(m, n, {\color{red}r})=r+m&\text{Composición de }F_5 \text{ con }F_1, F_6\\
F_8(m)=0&\text{Recursiva elemental }(c_0)\\
F_9(m, n) = mn&\text{Recursión con }F_8, F_7
\end{array} \)

Puesto que las funciones recursivas elementales pueden ser calculadas por un ordenador y las funciones definidas por composición o recursión a partir de funciones calculables por un ordenador son también calculables por un ordenador, concluimos claramente que todas las funciones recursivas primitivas son calculables por un ordenador, es decir, que para cada función recursiva primitiva existe un algoritmo que nos permite calcularla en un tiempo finito para números naturales cualesquiera (haciendo abstracción de las limitaciones de memoria que surgirían si los números fueran excesivamente grandes).

Y ya está. El lector no necesita entender nada más. Todas las propiedades de las funciones recursivas primitivas podremos demostrarlas en ARP. No necesitamos presuponer ninguna de ellas.

Con esto acaba el inventario de conocimientos que presuponemos al lector, salvo que algún formalista estricto encuentre (y denuncie) que estamos usando algún conocimiento no declarado.

En el próximo mensaje empezaremos a construir ARP.

04 Junio, 2023, 03:41 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Vamos a construir un lenguaje formal \( \mathcal L_{\rm arp} \) para hablar sobre los números naturales y sobre las funciones recursivas primitivas. Que el lenguaje sea formal significa que vamos a definirlo sin hacer referencia en ningún momento al posible significado de sus "palabras" o "frases". Mejor dicho, sí que explicaremos cuál es ese significado, pero lo haremos de modo que si un formalista radical —esto es una caricatura, que nadie se dé por aludido, pues los formalistas así de radicales no existen— quiere entender el lenguaje sin entender nada de lo que significan sus frases, siempre puede saltarse todos los párrafos en los que se hable de significados (y que he señalado en rojo) sin que ello le impida seguir la parte sintáctica de la exposición.

Signos de \( \mathcal L_{\rm arp} \) Llamaremos signos del lenguaje de la Aritmética Recursiva Primitiva a ocho signos distintos cualesquiera, a los que llamaremos

\( 0\qquad S \qquad p\qquad c\qquad \kappa\qquad \rho\qquad x\qquad = \)

Llamaremos cadenas de signos de \( \mathcal L_{\rm arp} \) a las sucesiones finitas de estos signos, con posibles repeticiones y en un orden dado, de modo que sólo consideraremos que dos cadenas de signos \( \zeta_1 \) y \( \zeta_2 \) son idénticas (y lo expresaremos así: \( \zeta_1\equiv \zeta_2 \)) cuando consten de los mismos signos en el mismo orden.

Por ejemplo, algunas cadenas de signos son:

\( 0 = 0,\qquad  00\kappa ==S,\qquad SSSS=x, \)         etc.

Si \( \zeta_1,\ldots, \zeta_n \) son cadenas de signos de \( \mathcal L_{\rm arp} \), podemos yuxtaponerlas, es decir, construir la cadena de signos \( \zeta_1\cdots \zeta_n \) que resulta de escribir primero los signos de \( \zeta_1 \), justo a continuación los de \( \zeta_2 \) y así hasta llegar a los de \( \zeta_n \).


En este punto conviene aclarar un matiz muy sutil:

Uso y mención
Observemos que no hay contradicción en decir que España es un país y que "España" no es un país. En efecto, España es un país y "España" es una palabra de ocho letras.

Cuando hablamos de un lenguaje, hay que tener cuidado en distinguir cuándo usamos una palabra para hacer referencia a su significado (como cuando usamos la palabra "España" para hacer referencia a España) y cuándo estamos hablando de la palabra en sí. Una forma inequívoca de mostrar la distinción es poner una palabra entre comillas cuando estamos hablando de ella y no de su significado, que es lo que estoy haciendo en todo este spoiler y lo que haré en todo momento, si no me despisto.

Observemos ahora que, en la definición anterior, he dicho que los signos de \( \mathcal L_{\rm arp} \) pueden ser cualesquiera (no importa cuáles sean), y que los llamaremos \( 0, S, c,  \) etc. Por eso, hay que entender que "\( 0 \)" no es (necesariamente) un signo de \( \mathcal L_{\rm arp} \), sino que \( \mathcal L_{\rm arp} \) tiene un signo, que puede ser J, o \( \triangle \) o lo que sea (no importa), y que a ese signo lo llamaremos \( 0 \), es decir, que nos referiremos a él (en el español en el que está escrito este hilo)  con el nombre "\( 0 \)".

Igual que, hablando en español puro, uno puede plantear un problema que empieza: "Tres personas A, B, y C acuden a un concurso, y a A le preguntan..." y ahí entendemos que A, B, C actúan como pronombres en lo que podemos considerar una extensión oportuna del español, para evitar decir en todo momento "el primero", "el segundo", etc., del mismo modo hay que entender que "\( 0 \)" es como esas A, B, C, es una extensión del español que usamos para referirnos a un cierto signo de \( \mathcal L_{\rm arp} \), cuya forma es irrelevante.

Otro ejemplo: "\( 0 \)" es como "alfil" al hablar del ajedrez. Es el nombre que damos a ciertas piezas del juego, las cuales pueden tener diseños de lo más variados. No importa si los alfiles de un juego de ajedrez son piezas esquemáticas, o esculturillas que muestran un caballero con armadura, etc. A efectos de jugar al ajedrez, lo que importa es que a ciertas cuatro piezas del juego las llamaremos alfiles.

Igualmente, no importa si el \( 0 \) de \( \mathcal L_{\rm arp} \) es un triángulo o una reproducción en miniatura de la Gioconda (¡o incluso el signo "\( 0 \)"!). Lo que importa es que a esa "pieza" de nuestro juego la llamaremos \( 0 \) en español.

Ojo, que con esto introducimos una polisemia, pues en español, se usa "\( 0 \)" para nombrar el número natural cero, pero el contexto permitirá evitar ambigüedades: a partir de ahora tenemos que tener presente que "\( 0 \)" puede ser el nombre en español del número cero o el nombre del signo de \( \mathcal L_{\rm arp} \) al que hemos acordado llamar \( 0 \), igual que hay ciertas piezas de un juego de ajedrez a las que acordamos llamar alfiles.

Otra cosa es —que los formalistas no lean esto— que \( 0 \) será el signo que en el lenguaje \( \mathcal L_{\rm arp} \) usaremos para nombrar al número natural cero, con lo que (en el sentido que le acabamos de dar al signo) podemos decir que "\( 0 \)" es el nombre del signo \( 0 \) que en \( \mathcal L_{\rm arp} \) será el nombre del número natural cero.

En resumen, el lector debería asimilar que (entendiendo "\( 0 \)" en el sentido que le hemos dado aquí y no en su sentido usual en español), las afirmaciones siguientes son ciertas:
  • "0" no es un número natural.
  • 0 no es un número natural.
  • 0 es un signo de \( \mathcal L_{\rm arp} \).
  • "0" no es un signo de \( \mathcal L_{\rm arp} \).
  • 0 es el nombre en \( \mathcal L_{\rm arp} \) del número natural cero.
Para nombrar una cadena de signos de \( \mathcal L_{\rm arp} \), el criterio más simple es yuxtaponer los nombres de los signos que la componen, de modo que \( 00\kappa == S \) es la cadena de signos cuyo primer signo es \( 0 \) (es decir, el signo nombrado por "\( 0 \)", sea éste el que sea, seguido de otro \( 0 \), seguido del signo que llamamos \( \kappa \) (que perfectamente podría ser una reproducción en miniatura de Las meninas), etc.

Más en general, en la definición precedente hemos establecido el convenio de nombrar una yuxtaposición de cadenas de signos yuxtaponiendo sus nombres.

No obstante, éste no será el criterio que seguiremos más a menudo, sino que tenemos la libertad de elegir los nombres que nos resulten más oportunos para las distintas cadenas de signos de \( \mathcal L_{\rm arp} \).

Por ejemplo, podemos establecer que \( 1\equiv S0 \), donde con esto no hay que entender que hemos introducido un nuevo signo en \( \mathcal L_{\rm arp} \) "de contrabando", sino que a la cadena de signos \( S0 \), es decir, la formada por el signo \( S \) (el signo nombrado por "\( S \)") seguido del signo \( 0 \) la podemos llamar más cómodamente \( 1 \). Igualmente, podemos convenir en que

\( 15\equiv SSSSSSSSSSSSSSS0 \)

de modo que "\( 15 \)" y "\( SSSSSSSSSSSSSSS0 \)" son dos formas alternativas de referirnos a la misma cadena de signos de \( \mathcal L_{\rm arp} \). Podemos llamar a cada cadena como queramos siempre y cuando no haya duda de a qué cadena nos referimos con cada nombre que se nos ocurra darle.

Esta "filosofía" se suele resumir diciendo que nunca vamos a usar los signos de \( \mathcal L_{\rm arp} \), sino que meramente los vamos a mencionar a través de los nombres que les hemos dado, igual que en un libro de ajedrez nunca se usan las piezas de ningún juego de ajedrez, sino que meramente se mencionan a través de sus nombres: rey, dama, torre, etc.
[cerrar]

Numerales Llamaremos numerales de \( \mathcal L_{\rm arp} \) a las cadenas de signos de la forma

\( 0,\quad S0, \quad SS0, \quad SSS0, \quad SSSS0, \quad \ldots \)

es decir, las formadas por cualquier cantidad de signos \( S \) y un \( 0 \).

De este modo, a cada numeral le podemos asignar un número natural (el número de signos \( S \) que lo componen) al que llamaremos su índice, de modo que, si llamamos \( N_i \) al numeral de índice \( i \), tenemos que

\( N_0\equiv 0,\qquad N_1\equiv S0,\qquad N_2\equiv SS0, \qquad N_3\equiv SSS0,\qquad \ldots \)

En la práctica, dado que el lector conoce sin duda la expresión decimal posicional de los números naturales, no habrá inconveniente en escribir, más fácilmente,

\( 15\equiv N_{15}\equiv SSSSSSSSSSSSSSS0 \)

en el mismo sentido en que indicábamos en un mensaje anterior, que en teoría no es necesario que el lector conozca la expresión decimal de los números naturales, pues siempre que vea escrito \( 15 \) podrá sustituirlo por \( SSSSSSSSSSSSSSS0 \) sin alterar el sentido de lo que esté leyendo.

El formalista radical tiene que admitir que sabe reconocer cuál es el índice de cada numeral, pero puede hacer caso omiso cuando decimos que este índice será precisamente el significado que el numeral tendrá en \( \mathcal L_{\rm arp} \), de modo que con los numerales hemos asignado un nombre en \( \mathcal L_{\rm arp} \) a todos y cada uno de los números naturales.

Ahora bien, desde un punto de vista puramente formal, lo único relevante de todo lo dicho es que podemos programar a un ordenador para que, si le damos una cadena de signos de \( \mathcal L_{\rm arp} \), éste identifique si es o no un numeral y, en caso afirmativo, calcule su índice. Que ese índice vaya a ser el significado del numeral es algo formalmente irrelevante. Un poco más en general, un ordenador puede reconocer si una cadena de signos empieza por un numeral y, en caso afirmativo, puede determinar donde termina y cuál es su índice.

Proyecciones Llamaremos proyecciones a las cadenas de signos de la forma

\( p^n_k\equiv pN_kN_n \),

donde \( p \) es el signo de \( \mathcal L_{\rm arp} \) al que hemos dado este nombre y \( N_k, N_n \) son numerales de índices \( 1\leq k\leq n \). Diremos, concretamente, que \( p^n_k \) es la proyección \( n \)-ádica \( k \)-ésima o la proyección de rango \( n \) e índice \( k \).

Por ejemplo, \( p_2^4\equiv pSS0SSSS0 \) es una proyección, mientras que \( p0SSS0 \) o \( pSSSS0S0 \) no lo son.

En general, es fácil programar un ordenador para que, si le damos una cadena de signos, determine si empieza por una proyección y, en caso afirmativo, determina dónde acaba y cual es su rango \( n \) y su índice \( k \).

Funtores Ahora vamos a darle un nombre en \( \mathcal L_{\rm arp} \) a cada función recursiva primitiva. En realidad será más que un nombre. Por ejemplo, en español se llama alcohol a una cierta sustancia química, pero nadie puede saber cuál es sin más que mirar la palabra "alcohol". En cambio, los químicos llaman a esta misma sustancia \( CH_3-CH_2-OH \), y esto no es un "nombre" cualquiera, sino un nombre que explica su propio significado. Alguien que conozca la nomenclatura química puede ver una fórmula que nunca haya visto antes y saber a qué compuesto hace referencia sin necesidad de consultar ningún "diccionario químico". Aquí vamos a hacer lo mismo: vamos a darle a cada función recursiva primitiva, no un nombre sin más, sino una "fórmula química" que permite saber qué función es sin más que analizar su nombre. A los nombres de las funciones las llamaremos funtores.

Diremos que una cadena de signos \( f \) de \( \mathcal L_{\rm arp} \) es un funtor de rango \( n \) (o un  funtor \( n \)-ádico) si existen una sucesión \( f_1,\ldots, f_r \) de cadenas de signos y una sucesión \( n_1,\ldots, n_r \) de números naturales de modo que \( f\equiv f_r \), \( n = n_r \) y, para cada índice \( i \), se da uno de los casos siguientes:

  • \( f_i\equiv S \) y \( n_i = 1 \),
  • \( f_i\equiv c \) y \( n_i = 1 \),
  • Existe \( 1\leq k\leq n_i \) tal que \( f_i\equiv p^{n_i}_k \),
  • Existen índices \( j, j_1,\ldots, j_m<i \) tales que \( n_j=m \), \( n_{j_k}= n_i \), para todo \( k \) y
    \( f_i \equiv \kappa(f_j,f_{j_1},\ldots, f_{j_m})\equiv \kappa f_jf_{j_1}\cdots f_{j_m} \),

  • Existen \( j, k<i \) tales que \( n_i = n_j+1 \), \( n_k = n_j+2 \) y
    \( f_i \equiv \rho(f_j, f_k)\equiv \rho f_jf_k \).

Aquí \( n_i = n_j+1 \) sólo significa que \( n_i \) es el siguiente de \( n_j \), mientras que \( n_k = n_j+2 \) sólo significa que \( n_k \) es el siguiente del siguiente de \( n_j \), y todo esto lo puede entender un lector que no sepa sumar.

Observemos que todas las cadenas de signos \( f_i \) que aparecen en la sucesión son funtores, pues cumplen la definición con las sucesiones que terminan en \( f_i \) y \( n_i \).

Ejemplo Veamos que
\( +\quad \equiv\quad  \rho(p_1^1, \kappa(S, p_3^3))\equiv \rho pS0S0\kappa S pSSS0SSS0,
 \)

es un funtor diádico. Para ello observamos que lo podemos construir en los pasos siguientes:

\(
\begin{array}{rll}
f_1&S&\text{funtor monádico}\\
f_2&p_3^3\equiv pSSS0SSS0&\text{funtor triádico}\\
f_3&\kappa(f_1, f_2)\equiv \kappa SpSSS0SSS0&\text{funtor triádico}\\
f_4&p_1^1\equiv pS0S0&\text{funtor monádico}\\
f_5&\rho(f_4,f_3)\equiv \rho pS0S0\kappa SpSSS0SSS0&\text{funtor diádico}
\end{array}
 \)

Observemos que los paréntesis y las comas son signos que hemos introducido como parte de una notación para nombrar funtores para facilitar su lectura, pero que no forman parte de los signos de \( \mathcal L_{\rm arp} \), sino que las cadenas de signos correspondientes a dichos nombres son las cadenas "ilegibles" que mostramos a la derecha en cada término de la sucesión.

En particular, de la definición de funtor se sigue que todo funtor \( f \) está necesariamente en uno de los casos siguientes:

  • \( f\equiv S \), y es un funtor monádico.
  • \( f\equiv c \),  y es un funtor monádico.
  • \( f\equiv p^n_k \), y es un funtor \( n \)-ádico.

  • \( f\equiv \kappa(h, g_1,\ldots, g_m) \), donde \( h \) es un funtor \( m \)-ádico y \( g_1,\ldots, g_m \) son funtores \( n \)-ádicos, y entonces \( f \) es \( n \)-ádico. Diremos que \( f \) está definido por composición a partir de \( h, g_1,\ldots, g_m \)

  • \( f\equiv \rho(g, h) \), donde \( g \) es un funtor \( n \)-ádico y \( h \) es un funtor \( n+2 \)-ádico, y entonces \( f \) es \( n+1 \)-ádico. Diremos entonces que \( f \) está definido por recursión a partir de \( g, h \).

La unicidad de la estructura de un funtor
En principio, un mismo funtor podría definirse a partir de sucesiones distintas, por lo que podría ocurrir, por ejemplo, que tuviera dos rangos distintos, pero sucede que no es así. Más aún, se puede programar a un ordenador para que determine la estructura de un funtor (en particular su rango) sin más que leerlo mecánicamente de izquierda a derecha. Lo ilustraré con un ejemplo, pero es fácil convencerse de que el procedimiento es general.

Consideremos la cadena de signos
\( f\equiv \rho c\kappa \rho pS0S0\kappa SpSSS0SSS0pSSS0SSS0pS0SSS0 \)

y vamos a ver cómo podemos determinar de forma algorítmica que es un funtor.

  • Como \( f \) empieza por \( \rho \), si es un funtor, tiene que estar definido por recursión. Por lo tanto, tras el signo \( \rho \) tienen que estar yuxtapuestos los nombres de dos funtores. El segundo signo es ya el funtor \( c \) (ningún otro funtor puede empezar por \( c \)), luego tiene que ser

    \( f\equiv \rho(c,\kappa \rho pS0S0\kappa SpSSS0SSS0pSSS0SSS0pS0SSS0 \)

    Más aún, como el primer funtor de la recursión es monádico, el segundo debe ser triádico.

  • Como el segundo funtor empieza por \( \kappa \), debe ser una composición.
    • El primero de los funtores de la composición empieza por \( \rho \), luego tiene que ser un funtor definido por recursión.
      • El signo siguiente es \( p \), luego el primer funtor de la recursión tiene que ser una proyección. Para que pueda serlo, tras la \( p \) deben venir dos numerales adecuados, y vemos que así es, que determinan la proyección \( p^1_1 \). Por lo tanto, la recursión debe completarse con un funtor triádico para formar un funtor diádico.

        \( f\equiv \rho(c,\kappa (\rho(p^1_1,\kappa SpSSS0SSS0pSSS0SSS0pS0SSS0 \)
      • Tras \( p^1_1 \) viene una \( \kappa \), luego el segundo funtor de la recursión tiene que ser una composición. Luego viene \( S \), que es, pues, el primer funtor de la composición. Como es un funtor monádico, la composición deberá completarse con un único funtor.

        \( f\equiv \rho(c,\kappa (\rho(p^1_1,\kappa(S,pSSS0SSS0pSSS0SSS0pS0SSS0 \)
      • A continuación de \( S \) viene una \( p \), luego el segundo funtor de la composición tiene que ser una proyección. Vemos que se trata de \( p^3_3 \), y ahí tiene que acabar la composición y también la recursión que es, como debía ser, un funtor diádico:

        \( f\equiv \rho(c,\kappa (\rho(p^1_1,\kappa(S,p^3_3)),pSSS0SSS0pS0SSS0 \)

    • Puesto que el primer funtor de la composición es diádico, ahora deben venir dos funtores más. El primero empieza por \( p \), luego tiene que ser una proyección, y vemos que es \( p^3_3 \). A continuación tenemos otra \( p \), que es el principio de \( p_1^3 \). Esto completa la composición:

      \( f\equiv \rho(c,\kappa (\rho(p^1_1,\kappa(S,p^3_3)),p^3_3, p_1^3))\equiv \rho(c, \kappa(+, p_3^3, p_1^3)). \)
Si en algún momento no se hubiera cumplido algo de lo que hemos dicho que debía cumplirse, habríamos concluido que la cadena de signos dada no sería un funtor, pero, como todo ha cuadrado, concluimos que, en efecto, \( f \) es un funtor diádico (y no podría ser otro), que podemos construir mediante la sucesión:

\( \begin{array}{ll}
f_1&S\\
f_2&p_3^3\\
f_3&\kappa(f_1, f_2)\\
f_3&p_1^1\\
f_5&\rho(f_4, f_3)\\
f_6&p_1^3\\
f_7&\kappa(f_5, f_2, f_6)\\
f_8&c\\
f_9&\rho(f_8, f_7)
\end{array} \)
[cerrar]

Ahora pasamos a asignarle a cada funtor \( n \)-ádico una función \( n \)-ádica, que será su significado en  \( \mathcal L_{\rm arp} \):

Diremos que un funtor \( n \)-ádico \( f \) denota una función \( n \)-ádica \( F \) si existe una sucesión de funtores \( f_1,\ldots, f_r \) en las condiciones de la definición de funtor y una sucesión de funciones \( F_1,\ldots, F_r \) de modo que, para cada \( i \), la función \( F_i \) es \( n_i \)-ádica y se cumple una de las condiciones siguientes:


  • Si \( f_i\equiv S \), entonces \( F_i \) es la función sucesor.
  • Si \( f_i\equiv c \), entonces \( F_i \) es la función \( c_0 \) que vale siempre cero.
  • Si \( f_i\equiv p^n_k \), entonces \( F_i \) es la proyección correspondiente.
  • Si \( f\equiv \kappa(f_j, f_{j_1},\ldots, f_{j_m}) \), entonces \( F_i \) es la composición de las funciones \( F_j, F_{j_1},\ldots, F_{j_m} \)
  • Si \( f\equiv \rho(f_j, f_k) \), entonces \( F_i \) es la función definida por recursión a partir de \( F_j \) y \( F_k \).

Es fácil concluir que cada funtor \( n \)-ádico \( f \) denota una única función \( F \), que además es \( n \)-ádica y recursiva primitiva.

Demostración
Es obvio que toda sucesión en las condiciones de la definición de funtor se puede completar con una sucesión de funciones en las condiciones de la definición anterior, por lo que todo funtor denota al menos una función, que claramente es recursiva primitiva. Para probar la unicidad suponemos que hay un funtor que denota dos funciones distintas (es decir, que toman valores distintos sobre unos mismos números naturales). Distinguimos varios casos:

  • Es imposible que\(  f\equiv S \), \( f\equiv c \) o \( f\equiv p^n_k \), pues la definición de denotación sólo asigna una función posible a cada uno de estos funtores.
  • Si \( f\equiv \kappa(h, g_1,\ldots, g_n) \), alguno de los funtores \( h \) o \( g_i \) debe denotar dos funciones distintas, porque si cada uno de ellos sólo denotara una función, entonces la función denotada por \( f \) sería la composición de estas funciones, y también sería única.
  • Si \( f\equiv \rho(g, h) \), concluimos del mismo modo que alguna de las funciones \( g \) o \( h \) debe denotar al menos dos funciones distintas.
Así pues, si \( f \) denota dos funciones distintas, tiene que haber un funtor \( f_1 \) de menor longitud que también denote dos funciones distintas, y por la misma razón debería haber otro funtor \( f_2 \) de menor longitud que también denotara dos funciones distintas, y en definitiva tendríamos una sucesión infinita estrictamente decreciente de números naturales (las longitudes de los funtores que estamos obteniendo) y eso es imposible (ya que en tal caso no existiría el mínimo de las longitudes de los funtores de la sucesión, en contra del principio del mínimo).
[cerrar]

Por consiguiente, dado un funtor \( n \)-ádico \( f \), podemos definir la función denotada por \( f \) como la única función \( F(f) \) denotada por \( f \), que es una función \( n \)-ádica recursiva primitiva. Las afirmaciones siguientes son inmediatas:

  • \( F(S) \) es la función sucesor.
  • \( F(c) \) es la función \( c_0 \) que toma siempre el valor \( 0 \).
  • \( F(p^n_k) \) es la proyección \( n \)-ádica \( k \)-ésima.
  • \( F(\kappa(h, g_1,\ldots, g_m)) \) es la composición de \( F(h) \) y \( F(g_1),\ldots, F(g_m) \).
  • \( F(\rho(g, h)) \) es la función definida por recursión a partir de \( F(g) \) y \( F(h) \).

Ejemplos: Los ejemplos del mensaje anterior muestran que si llamamos \( +\equiv \rho(p_1^1, \kappa(S, p_3^3)) \) entonces \( F(+) \) es la suma usual de números naturales, y si llamamos \( \cdot \equiv  \rho(c, \kappa(+, p_3^3, p_1^3)) \) entonces \( F(\cdot) \) es el producto usual de números naturales.

Ejercicio: Definir un funtor \( f \) tal que \( F(f)(m, n) = m^n \). (Enunciado alternativo para formalistas radicales: definir un funtor que, por razones inconfesables, estaría dispuesto a tomar como definición de exponencial de números naturales).

06 Junio, 2023, 12:18 am
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En el mensaje anterior hemos definido los numerales y los funtores de \( \mathcal L_{\rm arp} \), que nombran, respectivamente, a los números naturales y a las funciones recursivas primitivas. Ahora queremos definir cadenas de signos del estilo de

\( x+y=y+x \),

es decir, que afirmen cosas sobre los números naturales, pero no necesariamente sobre números concretos, sino sobre números arbitrarios como en el ejemplo precedente. Para ello necesitamos introducir variables.

Variables Metemos ahora en juego el penúltimo signo de \( \mathcal L_{\rm arp} \):

Llamaremos variables de \( \mathcal L_{\rm arp} \) a las cadenas de signos de la forma \( x_i \equiv xN_i \), es decir, formadas por el signo \( x \) seguido de un numeral:

\( x_0\equiv x0, \quad x_1\equiv xS0,\quad x_2\equiv xSS0, \quad x_3\equiv xSSS0, \quad \ldots \)

Diremos que \( x_i \) es la variable de índice \( i \), pero, a diferencia de lo que sucede con los numerales, para los que \( SS0 \) es algo muy distinto de \( SSSSS0 \), el uso que vamos a hacer de las variables hace que siempre vaya a ser irrelevante cuáles son los índices de las variables que consideremos, por lo que habitualmente usaremos letras arbitrarias \( x, y, z, \ldots \) para hacer referencia a variables de \( \mathcal L_{\rm arp} \) sin que importen sus índices.

Notemos que, en principio, si decimos que \( x, y \) son dos variables de \( \mathcal L_{\rm arp} \), podría darse el caso de que \( x\equiv y \), pero, para evitar constantes aclaraciones, convendremos en que siempre que hablemos de variables con nombres distintos, se sobreentenderá que son variables distintas, salvo que indiquemos explícitamente que podrían coincidir.

Términos Los términos serán las cadenas de signos de \( \mathcal L_{\rm arp} \) que nombrarán números naturales, concretos o genéricos (si contienen variables). Formalmente:

Un término de \( \mathcal L_{\rm arp} \) es una cadena de signos \( t \) tal que exista una sucesión \( t_1,\ldots, t_r \) de cadenas de signos de modo que \( t_r\equiv t \) y, para cada \( i \), se cumpla uno de los casos siguientes:

  • \( t_i\equiv 0 \),
  • \( t_i \) es una variable,
  • \( t_i \equiv f(t_{j_1},\ldots, t_{j_n})\equiv  ft_{j_1}\cdots t_{j_n} \), donde \( f \) es un funtor \( n \)-ádico y \( j_1,\ldots, j_n<i \).
Es claro que cada cadena \( t_i \) es, de hecho, un término, pues satisface la definición con la sucesión \( t_1,\ldots, t_i \).

En particular, todo término \( t \) de \( \mathcal L_{\rm arp} \) se encuentra en uno de los casos siguientes:

  • \( t\equiv 0 \),
  • \( t \) es una variable,
  • \( t\equiv f(t_1,\ldots, t_n)\equiv ft_1\cdots t_n \), donde \( f \) es un funtor \( n \)-ádico y \( t_1,\ldots, t_n \) son otros términos.

En otras palabras, los términos son las cadenas que se obtienen aplicando funtores al \( 0 \) y a las variables. En particular, todos los numerales —que resultan de aplicar el funtor \( S \) al \( 0 \)— son términos.

En la práctica introduciremos todos los convenios de notación que nos resulten convenientes para facilitar la lectura de los términos. Por ejemplo, ya hemos definido los funtores diádicos \( +\equiv \rho(p^1_1, \kappa(S, p^3_3)) \) y \( \cdot \equiv \rho(c,\kappa(+, p^3_3, p^3_1)) \), y en la práctica escribiremos

\( t_1+t_2 \equiv +(t_1, t_2),\qquad t_1\cdot t_2 \equiv \cdot(t_1, t_2). \)

Similarmente, si llamamos \( f\equiv \rho(\kappa(S, c), \kappa(\cdot, p_3^3, p_1^3)) \), usaremos la notación

\( t_1^{t_2}\equiv f(t_1, t_2) \).

Nota Estas notaciones alternativas obligan a usar paréntesis que no son necesarios si escribimos todo en el orden correcto. Por ejemplo:

\( x(y+z) = \cdot(x, +(y, z)) \equiv \cdot x+yz,\qquad x+yz \equiv +(x, \cdot(y, z))\equiv +x\cdot yz \).

En general, el lector debería convencerse de que es posible programar un ordenador para que, si le damos una cadena de signos, determine si empieza por un término y, en tal caso, determine dónde acaba y cuál es su estructura, exactamente igual que vimos con los funtores.


Veamos ahora que cada término nombra un número natural si asignamos una interpretación a sus variables.

Una valoración es cualquier criterio \( v \) que asigne un número natural \( v(x) \) a cada variable \( x \) de \( \mathcal L_{\rm arp} \).

Diremos que un término \( t \) denota un número natural \( N \) respecto de una valoración \( v \) si, existen una sucesión \( t_1,\ldots, t_r \) de términos en las condiciones de la definición y otra \( N_1,\ldots, N_r \) de números naturales de modo que \( N=N_r \) y, para cada \( i \), se cumpla:


  • Si \( t_i\equiv 0 \), entonces \( N_i = 0 \),
  • Si \( t_i \) es una variable, entonces \( N_i = v(t_i) \),
  • Si \( t_i\equiv f(t_{j_1},\ldots, t_{j_n}) \), entonces \( N_i = F(f)(N_{j_1},\ldots, N_{j_n}) \).
Es fácil ver entonces, como en el caso de la función denotada por un funtor, que, para cada término \( t \) y cada valoración \( v \), existe un único número natural denotado por \( t \), y lo representaremos por \( N(t)[v] \).

La definición del número denotado por un término implica claramente los hechos siguientes:

  • \( N(0)[v] = 0 \)
  • Si \( x \) es una variable, \( N(x)[v] = v(x) \),
  • \( N(f(t_1,\ldots, t_n))[v] = F(f)(N(t_1)[v], \ldots, N(t_n)[v]) \).
También es fácil concluir que \( N(t)[v] \) depende a lo sumo de los valores que \( v \) asigna a las variables que aparecen en \( t \). En particular, si \( t \) no tiene variables, no es necesaria ninguna valoración y escribiremos simplemente \( N(t) \).

Uniendo que \( N(0) = 0 \) con que \( N(St)[v] \) es el siguiente del número natural \( N(t)[v] \), una simple inducción prueba que \( N(N_i) = i \), es decir, que cada numeral denota precisamente a su índice. Explícitamente:


\( N(0) = 0,\qquad N(S0) = 1, \qquad N(SS0) = 2, \qquad N(SSS0) = 3, \qquad \ldots \)

Ejemplo Si \( v \) es una valoración, tenemos que

\( N(x^2+y^2)[v] = N(x^2)[v]+ N(y^2)[v] \),

donde hemos usado que \( F(+) \) es la suma de números naturales. A su vez,

\( N(x^2+y^2)[v] = (N(x)[v])^{N(2)}+(N(y)[v])^{N(2)} \),

donde hemos usado que \( F(()^{()}) \) es la exponenciación de números naturales. A su vez:

\( N(x^2+y^2)[v] =v(x)^2+v(y)^2 \).

En definitiva, vemos que el número denotado por \( x^2+y^2 \) es la suma de los cuadrados de los números denotados por las variables \( x, y \). En la práctica, nunca necesitaremos aplicar la definición de denotación para interpretar términos concretos, ya que el resultado es simplemente lo que uno entiende al "leer" el término normalmente.


Fórmulas Ponemos en juego ahora el último signo de \( \mathcal L_{\rm arp} \):

Una fórmula del lenguaje \( \mathcal L_{\rm arp} \) es una cadena de signos de la forma

\( t_1 = t_2 \equiv =t_1t_2 \).

Los términos \( t_1,t_2 \) se llaman miembros de la fórmula. Llamaremos expresiones de \( \mathcal L_{\rm arp} \) a las cadenas de signos que son términos o fórmulas.

Notemos que "técnicamente", todas las fórmulas empiezan por el igualador \( = \), aunque en la práctica las nombraremos poniendo el igualador entre sus miembros.

Si \( \alpha \equiv t_1 = t_2 \) es una fórmula y \( v \) es una valoración, diremos que \( \alpha \) es satisfecha por \( v \), y lo representaremos por \( \vDash \alpha[v] \), si se cumple

\( N(t_1)[v] = N(t_2)[v] \),

es decir, si los dos miembros denotan el mismo número natural cuando sus variables se interpretan según \( v \).

Por la observación análoga para términos, que una fórmula \( \alpha \) sea satisfecha o no por una valoración \( v \) depende únicamente de los números que \( v \) asigna a las variables que aparecen en \( \alpha \), que son un número finito.

Por ejemplo, si \( \alpha \equiv Sx = 5 \), es claro que \( \vDash (Sx = 5)[v] \) equivale a que \( v(x)+1 = 5 \), luego también a que \( v(x) = 4 \).

Ahora introducimos un convenio crucial al que debemos prestar mucha atención, porque no coincide con lo que un matemático entiende normalmente:

Diremos que una fórmula \( \alpha \) es verdadera si es satisfecha respecto de todas las valoraciones de sus variables, y es falsa si no es satisfecha respecto de ninguna valoración.

Aquí es esencial observar que que el "es satisfecha respecto de todas las valoraciones" tiene un sentido claro gracias a que, en realidad, sólo tenemos que asignar valores a las variables que aparecen en \( \alpha \), que son un número finito, luego las asignaciones posibles son numerables (si \( \alpha \) tiene \( n \) variables, hay tantas como \( n \)-tuplas de números naturales), luego podemos decir que \( \alpha \) es verdadera si es satisfecha con la primera asignación posible de valores, y con la segunda, y con la tercera, etc.

Notemos, por otra parte, el punto delicado respecto al uso habitual en matemáticas: normalmente, un matemático dirá que la fórmula \( Sx = 5 \) es verdadera si \( x=4 \) y falsa en caso contrario, pero según las definiciones que acabamos de adoptar esa fórmula no es ni verdadera ni falsa.

En general, una fórmula es verdadera cuando lo que se entiende al leerla normalmente es verdad (para cualquier interpretación de sus variables). Por ejemplo, la fórmula

\( (x+y)^2 = (x^2+y^2)+2(xy) \)

es verdadera, pero para comprobarlo no hace falta recurrir a las definiciones de denotación y satisfacción. Si lo hacemos, veremos que lo que nos dicen es que la fórmula anterior es verdadera si el cuadrado de la suma de los números denotados por \( x, y \) es igual a la suma de los cuadrados más el doble de su producto, cosa que es cierta.

Con esto hemos completado la construcción del lenguaje \( \mathcal L_{\rm arp} \), pero necesitamos un último concepto sintáctico:

Sustitución Necesitamos describir una manipulación elemental que podemos llevar a cabo con las expresiones de \( \mathcal L_{\rm arp} \). Por ejemplo, si tenemos una fórmula como
\( (x+y)^2 = (x^2+y^2)+2(xy) \),

a partir de ella podemos construir la fórmula que resulta de sustituir una de sus variables, por ejemplo, la \( y \), por un término cualquiera, como \( t\equiv 3z \). El resultado es:
\( S_y^{3z}\bigl((x+y)^2 = (x^2+y^2)+2(xy)\bigr) \equiv (x+3z)^2 = (x^2+(3z)^2)+2(x(3z)) \).

En general:

Definición Si \( \theta \) es una expresión de \( \mathcal L_{\rm arp} \), \( x \) es una variable y \( t \) es un término, llamaremos sustitución de \( x \) por \( t \) en \( \theta \), y la representaremos por \( S_x^t\theta \), a la expresión que resulta de sustituir cada aparición de la variable \( x \) en \( \theta \) por el término \( t \). Explícitamente:

  • \( S_x^t0 \equiv 0 \),

  • \( S_x^ty\equiv \begin{cases}{t}&\text{si}& x\equiv y,\\ y & \text{si}& x\not\equiv y,\end{cases} \)

  • \( S_x^tf(t_1,\ldots, t_n)\equiv f(S_x^tt_1,\ldots, S_x^tt_n) \),

  • \( S_x^t(t_1=t_2) \equiv S_x^tt_1 = S_x^tt_2 \).
La sustitución tiene una interpretación que vamos a necesitar. Para enunciarla, si \( v \) es una valoración, \( x \) es una variable y \( n \) es un número natural, representaremos por \( v_x^n \) a la valoración que coincide con \( v \) salvo por que asigna a \( x \) el número natural \( n \).

Teorema El término \( S_x^tt' \) denota, respecto de una valoración \( v \), el mismo número natural que \( t' \) denota respecto de la valoración \( v_x^{N(t)[v]} \). Equivalentemente:

\( N(S_x^tt')[v] = N(t')[v_x^{N(t)[v]}] \).

Si \( \alpha \) es una fórmula, se cumple
\( \vDash S_x^t\alpha[v] \)     si y sólo si    \( \vDash \alpha[v_x^{N(t)[v]}] \).

Demostración
Si \( t'\equiv 0 \) se cumple la igualdad:

\( N(S_x^t 0)[v] = N(0)[v] = 0,\qquad N(0)[v_x^{N(t)[v]}] = 0. \)

Si \( t' \) es una variable distinta de \( x \) también:

\( N(S_x^t t')[v] = N(t')[v],\qquad N(t')[v_x^{N(t)[v]}] = N(t')[v]. \)

Si \( t'\equiv x \) entonces

\( N(S_x^t x)[v] = N(t)[v],\qquad N(x)[v_x^{N(t)[v]}] = N(t)[v]. \)

Si el resultado fuera falso, podríamos tomar un término \( t' \) que lo incumpla de longitud mínima. Según acabamos de ver, no puede ser que \( t' \) sea \( 0 \) o una variable, luego \( t'\equiv f(t_1,\ldots, t_n) \), para ciertos términos \( t_i \), que cumplen la conclusión por la minimalidad de \( t' \). Entonces

\( N(S_x^tf(t_1,\ldots, t_n))[v] = N(f(S_x^tt_1,\ldots, S_x^tt_n))[v] = \)

\( F(f)(N(S^t_xt_1)[v],\ldots N(S^t_xt_n)[v]) = F(f)(N(t_1)[v_x^{N(t)[v]}],\ldots, N(t_n)[v_x^{N(t)[v]}] ) =  \)

\( N(f(t_1,\ldots, t_n))[v_x^{N(t)[v]}], \)


con lo que \( t' \) también cumple el resultado y tenemos una contradicción.

Si \( \alpha \equiv t'=t'' \), entonces \( \vDash S_x^t\alpha[v] \) equivale a


\( N(S_x^tt')[v] = N(S_x^tt'')[v], \)

que a su vez equivale a \( N(t')[v_x^{N(t)[v]}] = N(t'')[v_x^{N(t)[v]}] \), y esto a su vez equivale a que \( \vDash \alpha[v_x^{N(t)[v]}] \).
[cerrar]

Una notación muy práctica (habitual en matemáticas) consiste en escribir \( \theta(x_1,\ldots, x_n) \) para referirnos a una expresión \( \theta \), donde \( x_1,\ldots, x_n \) son variables cualesquiera, que pueden estar o no en \( \theta \), y luego entender que \( \theta(t_1,\ldots, t_n) \) es la expresión que resulta de sustituir cada variable \( x_i \) por el término \( t_i \). Pero aquí hay un problema técnico que obliga a adoptar la definición siguiente:

\( \theta(t_1,\ldots, t_n) \equiv S_{y_1}^{t_1}\cdots S_{y_n}^{t_n}S_{x_1}^{y_1}\cdots S_{x_n}^{y_n}\theta,
 \)
donde \( y_1,\ldots, y_n \) son variables cualesquiera que no estén en \( t_1,\ldots, t_n \) ni en \( \theta \).

Para entender por qué es necesario introducir las variables \( y_1,\ldots, y_n \) consideremos \( \theta(x, y) \equiv x = y \). Por ejemplo, queremos que

\( \theta(S0, x+y) \equiv S0 = x+y, \)

pero si hubiéramos definido

\( \theta(S0, x+y) \equiv S_x^{S0}S_y^{x+y}\theta, \)

tendríamos que

\( \theta(S0, x+y) \equiv S_x^{S0}(x = x+y)\equiv S0 = S0+y, \)

que no es lo que queremos. En cambio, con la definición que hemos dado:

\( \theta(S0, x+y)\equiv S_{y_1}^{S0}S_{y_2}^{x+y}S_x^{y_1}S_y^{y_2}(x=y)\equiv S_{y_1}^{S0}S_{y_2}^{x+y}S_x^{y_1}(x=y_2)
 \)

\( \equiv  S_{y_1}^{S0}S_{y_2}^{x+y}(y_1=y_2)\equiv S_{y_1}^{S0}(y_1=x+y)\equiv S0 = x+y, \)

como debe ser. Vemos así que al introducir las variables auxiliares \( y_1,\ldots, y_n \) (que luego se eliminan) evitamos que algún \( t_i \) pase a ocupar el lugar que \( x_i \) ocupa en algún término \( t_j \) sustituido previamente.

En el mensaje siguiente veremos cómo razonar formalmente en \( \mathcal L_{\rm arp}. \)

07 Junio, 2023, 04:06 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ya tenemos construido el lenguaje formal de la Aritmética Recursiva Primitiva. Ahora necesitamos fijar unos axiomas y unas reglas de inferencia que nos permitan demostrar teoremas. Un formalista radical dirá que le da igual qué axiomas tomemos con tal de que esté bien claro cuáles son, pero nosotros vamos a exigir que los axiomas que tomemos sean verdaderos. Ahora bien, ¿qué afirmaciones sobre los números naturales podemos asegurar que son verdaderos si hemos prometido que no exigiríamos al lector ni que sepa sumar? Muy simple:

Definiciones de funtores A cada funtor de \( \mathcal L_{\rm arp} \) distinto de \( S \) le vamos a asociar una o dos fórmulas de \( \mathcal L_{\rm arp} \) a las que llamaremos su definición. Concretamente:

  • La definición del funtor \( c \) es la fórmula: \( c(x)=0 \).
  • La definición del funtor \( p^n_k \) es la fórmula \( p^n_k(x_1,\ldots, x_n)=x_k \).
  • La definición de un funtor \( f\equiv \kappa(h, g_1,\ldots, g_m) \), donde \( h \) es \( m \)-ádico y los \( g_i \) son \( n \)-ádicos es

    \( f(x_1,\ldots, x_n) = h(g_1(x_1, \ldots, x_n), \ldots, g_m(x_1,\ldots, x_n)) \)

  • La definición de un funtor \( f\equiv \rho(g, h) \) son las fórmulas

    \( f(x_1,\ldots, x_n, 0) = g(x_1,\ldots, x_n) \),

    \( f(x_1,\ldots, x_n, Sx_{n+1}) = h(x_1, \ldots, x_n, x_{n+1}, f(x_1,\ldots, x_n, x_{n+1})). \)
(Podríamos precisar qué variables concretas son las que aparecen en las definiciones, pero enseguida veremos que eso es irrelevante.)

No cuesta nada demostrar que todas las definiciones de los funtores son fórmulas verdaderas, porque si aplicamos la definición de \( \vDash \) a cada una de ellas vemos inmediatamente que lo que tiene que cumplirse para que sean verdaderas se cumple precisamente por la definición de la función asociada a cada funtor. De este modo, aunque técnicamente estas definiciones van a ser los axiomas de ARP, en realidad son más bien lo que cualquier matemático llama "definiciones" y, podemos decir que son verdaderas "por definición". Veamos, por ejemplo, la comprobación de uno de los axiomas:

Ejemplo
Si \( f\equiv \rho(g, h) \), para probar que

\( \vDash f(x_1,\ldots, x_n, Sx_{n+1}) = h(x_1, \ldots, x_n, x_{n+1}, f(x_1,\ldots, x_n, x_{n+1})) \)

tenemos que fijar una valoración \( v \) arbitraria y probar

\( \vDash f(x_1,\ldots, x_n, Sx_{n+1}) = h(x_1, \ldots, x_n, x_{n+1}, f(x_1,\ldots, x_n, x_{n+1}))[v] \).

Pero, aplicando la definición de satisfacción, esto equivale a que
\( F(f)(v(x_1),\ldots, v(x_n), v(x_{n+1})+1) = F(h)(v(x_1), \ldots, v(x_{n+1}), F(f)(v(x_1),\ldots, v(x_{n+1}))) \),

y esto se cumple porque, por definición \( F(f) \) es la función definida por recursión a partir de \( F(g) \) y \( F(h) \).
[cerrar]
La demostración de los demás axiomas es igualmente trivial.

En la práctica, nunca introduciremos nuevos funtores en términos de \( \kappa \) y \( \rho \), sino que lo haremos a través de sus definiciones en este sentido. Por ejemplo, en lugar de presentar la suma como \( +\equiv \rho(p_1^1, \kappa(S, p^3_3)) \), diremos simplemente que \( + \) es el funtor diádico definido por las ecuaciones

\( \begin{eqnarray*}
m+0&=&m\\
m+Sn&=&S(m+n).
\end{eqnarray*} \)

A la vista de estas ecuaciones, es claro que estamos definiendo un funtor de la forma \( \rho(g, h) \), donde necesariamente \( g(x) = x \), luego tiene que ser \( g\equiv p^1_1 \), y \( h(x, y, z)= Sz \), luego tiene que ser \( h\equiv \kappa(S, p_3^3) \).

Similarmente, el producto y la exponenciación pueden definirse como los funtores que cumplen:

\( \begin{eqnarray*}
m\cdot 0&=&0\\
m\cdot Sn&=&m\cdot n + m.
\end{eqnarray*} \)               \( \begin{eqnarray*}
m^0&=&1\\
m^{Sn}&=&m^n\cdot m.
\end{eqnarray*} \)

Estas fórmulas bastarán para determinar el comportamiento de los funtores distintos de \( S \), pero vamos a necesitar reglas de inferencia que determinen el comportamiento de las variables y los signos \( 0, S, = \). Hasta ahora sabemos lo que queremos que signifiquen, pero, así como las definiciones anteriores expresan en \( \mathcal L_{\rm arp} \) el significado de los funtores distintos de \( S \), no disponemos de fórmulas de \( \mathcal L_{\rm arp} \) que expresen el significado de estos signos.

Respecto a las variables, lo que necesitamos expresar es que, en fórmulas como \( x+y = y+x \), hay que entender que \( x, y \) representan números arbitrarios, que lo que dice esa fórmula no es que hay ciertos números en los que la suma conmuta, sino que la suma conmuta para todos los números \( x, y \). Esto nos lleva a considerar la primera regla de sustitución:


\( (S_1)\ \ \ \ \begin{array}{c}
\alpha\\
\hline
S_x^t\alpha
\end{array} \)

Donde \( \alpha \) es una fórmula, \( x \) una variable y \( t \) un término.

Vamos a comprobar que se trata de una regla de inferencia válida, es decir, que si la fórmula que está sobre la raya es verdadera, también lo es la que está debajo de la raya. En otras palabras, lo que dice la regla de inferencia es que lo que una fórmula \( \alpha \) afirma para una variable \( x \) vale "para todo \( x \)", luego sigue valiendo si cambiamos \( x \) por cualquier término \( t \).


Demostración
Más explícitamente, si \( \alpha\equiv s_1=s_2 \), podemos expresar la regla así:

\( (S_1)\ \begin{array}{c}
s_1=s_2\\
\hline
S_x^ts_1=S_x^ts_2
\end{array} \)

Supongamos que la premisa es verdadera, es decir, que \( \vDash s_1 = s_2 \) y veamos que lo es la conclusión. Para ello fijamos una valoración \( v \) y usamos que \( s_1=s_2 \) es satisfecha por cualquier valoración, en particular por \( v_x^{N(t)[v]} \). Por lo tanto:

\( \vDash (s_1=s_2)[v_x^{N(t)[v]}]. \)

Pero, por el último teorema del mensaje anterior, esto equivale a

\( \vDash (S_x^ts_1=S_x^ts_2)[v]. \)

Y, como esto vale para toda valoración \( v \), la conclusión de la regla de inferencia es verdadera.
[cerrar]

El significado del igualador se plasma en las dos reglas de inferencia siguientes: la segunda regla de sustitución y la regla de transitividad:

\( (S_2)\
\begin{array}{c}
t_1=t_2\\
\hline
S_x^{t_1}s=S_x^{t_2}s
\end{array}\qquad
(T)\ \begin{array}{ccc}
t_1=t_2&&t_1=t_3\\
\hline
&t_2=t_3
\end{array} \)

La segunda regla de sustitución expresa que si \( t_1 = t_2 \), cualquier cálculo \( s(x) \) que hagamos a partir de \( t_1 \) dará lo mismo que si lo hacemos con \( t_2 \). El significado de la regla de transitividad es obvio. Vamos a demostrar la validez de \( S_2 \), porque la de \( T \) es inmediata:

Demostración
Suponemos que su premisa es verdadera, es decir, que \( \vDash t_1 = t_2 \). Entonces, para toda valoración \( v \), tenemos que \( N(t_1)[v] = N(t_2)[v] \), luego

\( N(s)[v_x^{N(t_1)[v]}]=N(s)[v_x^{N(t_2)[v]}], \)

pues ambas valoraciones son la misma. Aplicando de nuevo el teorema sobre la sustitución, vemos que esto equivale a que

\( N(S_x^{t_1}s)[v]=N(S_x^{t_2}s)[v], \)

luego a

\( \vDash(S_x^{t_1}s=S_x^{t_2}s)[v] \)

y, como esto vale para toda valoración, la conclusión es verdadera.
[cerrar]

Para expresar formalmente el significado de los signos \( 0 \) y \( S \) formulamos un caso particular del principio de inducción:

\( (I_0)\ \begin{array}{ccc}
s_1(0)=s_2(0)&s_1(Sx)=h(x, s_1(x))&s_2(Sx)=h(x,s_2(x))\\
\hline
&s_1(x)=s_2(x)
\end{array}
 \)

Las premisas afirman que dos términos \( s_1(x) \) y \( s_2(x) \) toman el mismo valor para \( x=0 \) y que el valor que toman en \( Sx \) puede obtenerse en ambos casos a partir de \( x \) y del valor que toman en \( x \) mediante un mismo cálculo, expresado en el término \( h(x, y) \). La conclusión es que los dos términos coinciden para todo valor de \( x \). Es obvio entonces que si las premisas son verdaderas la conclusión también tiene que serlo, pero vamos a probarlo explícitamente:

Demostración
Como siempre, vamos a aplicar el teorema sobre sustituciones, por lo que es mejor expresar la regla de inducción explicitando las sustituciones, así:

\( (I_0)\ \begin{array}{ccc}
S_x^0s_1=S_x^0s_2&S_x^{Sx}s_1=S_y^{s_1}h&S_x^{Sx}s_2=S_y^{s_2}h\\
\hline
&s_1=s_2
\end{array}
 \)

Suponemos que las premisas son verdaderas y tenemos que probar que lo es la conclusión. Fijamos una valoración \( v \), de modo que tenemos que probar que:

\( N(s_1)[v] = N(s_2)[v] \).

Para ello demostraremos, por inducción sobre \( n \), que se cumple

\( N(s_1)[v_x^n] = N(s_2)[v_x^n] \).

En particular, para \( n = v(x) \) tenemos que \( v_x^n \) es la propia valoración \( v \), y tenemos la conclusión deseada. La primera premisa nos da que

\( N(S_x^0s_1)[v]=N(S_x^0s_2)[v], \)

que por el teorema de la sustitución equivale a

\( N(s_1)[v_x^0] = N(s_2)[v_x^0]. \)

Ahora supongamos que la conclusión es correcta para \( v_x^n \), es decir, que

\( N(s_1)[v_x^n] = N(s_2)[v_x^n] \).

La segunda premisa nos da que

\( N(S_x^{Sx}s_1)[v_x^n] = N(S_y^{s_1}h)[v_x^n], \)

lo que equivale a

\( N(s_1)[v_x^{N(Sx)[v_x^n]}] = N(h)[v_{x,y}^{n,N(s_1)[v_x^n]}], \)

pero \( N(Sx)[v_x^n] = N(x)[v_x^n]+1 = v_x^n(x)+1 = n+1 \), luego tenemos que

\( N(s_1)[v_x^{n+1}] = N(h)[v_{x,y}^{n,N(s_1)[v_x^n]}]. \)

Igualmente, partiendo de la tercera premisa llegamos a que

\( N(s_2)[v_x^{n+1}] = N(h)[v_{x,y}^{n,N(s_2)[v_x^n]}]. \)

Teniendo en cuenta la hipótesis de inducción, resulta que

\( N(s_1)[v_x^{n+1}] = N(s_2)[v_x^{n+1}] \),

lo que termina la prueba.
[cerrar]
Con esto ya hemos demostrado todo lo que el formalista radical no quiere saber y ya podemos presentar ARP como un sistema deductivo formal con la tranquilidad de que lo estamos haciendo bien (es decir, con la tranquilidad de haber demostrado que los axiomas no son arbitrarios, sino verdaderos, y que las reglas de inferencia tampoco son arbitrarias, sino que dan conclusiones verdaderas cuando parten de premisas verdaderas):

Definición: Llamaremos axiomas de la Aritmética Recursiva Primitiva a las definiciones de los funtores distintos de \( S \), y llamaremos reglas de inferencia de la Aritmética Recursiva Primitiva a las cuatro reglas de inferencia siguientes, a las que llamaremos primera y segunda regla de sustitución, regla de transitividad y regla de inducción:

\( (S_1)\ \ \ \ \begin{array}{c}
s_1(x)=s_2(x)\\
\hline
s_1(t)=s_2(t)
\end{array}\qquad (S_2)\ \ \ \
\begin{array}{c}
t_1=t_2\\
\hline
s(t_1)=s(t_2)
\end{array}\qquad
(T)\ \ \ \ \begin{array}{ccc}
t_1=t_2&&t_1=t_3\\
\hline
&t_2=t_3
\end{array} \)

\( (I_0)\ \ \ \ \begin{array}{ccc}
s_1(0)=s_2(0)&s_1(Sx)=h(x, s_1(x))&s_2(Sx)=h(x,s_2(x))\\
\hline
&s_1(x)=s_2(x)
\end{array} \)

Desde un punto de vista puramente formal, estas cuatro reglas de inferencia sólo deben entenderse como parte de la definición siguiente:

Una deducción en ARP a partir de unas premisas \( \alpha_1, \ldots, \alpha_n \) (fórmulas de \( \mathcal L_{\rm arp} \)) es una sucesión \( \delta_1,\ldots, \delta_r \) de fórmulas de \( \mathcal L_{\rm arp} \) tales que cada \( \delta_i \) sea, o bien un axioma, o bien una premisa, o bien una consecuencia de fórmulas anteriores por una de las cuatro reglas de inferencia fijadas (es decir, que \( \alpha_i \) es la fórmula de la parte de abajo de la raya de una de las reglas y las fórmulas que están sobre la raya figuran antes en la deducción).

Diremos que una fórmula \( \alpha \) es una consecuencia en ARP de unas premisas \( \alpha_1, \ldots, \alpha_n \) si existe una deducción con dichas premisas cuya última línea es \( \alpha \). Lo expresaremos así:
\( \alpha_1,\ldots, \alpha_n\mathop{\vdash}\limits_{\rm ARP}\alpha \)

o también así:
\( \begin{array}{c}
\alpha_1,\ldots, \alpha_n\\
\hline
\alpha
\end{array} \)

A cualquier resultado de este tipo lo llamaremos regla de inferencia derivada en ARP con las premisas y la conclusión indicadas.

Una demostración en ARP es una deducción sin premisas. Una fórmula \( \alpha \) es un teorema de ARP si existe una demostración en ARP cuya última línea sea \( \alpha \). Lo expresaremos así: \( \mathop{\vdash}\limits_{\rm ARP}\alpha \).

Es claro que en una deducción en ARP podemos incluir cualquier fórmula \( \alpha \) que sea consecuencia en ARP de fórmulas anteriores de la deducción, aunque no sea una consecuencia inmediata, pues siempre podríamos extender la deducción intercalando las fórmulas que justifican que \( \alpha \) se deduce de tales fórmulas anteriores. En particular, en toda deducción (o demostración) en ARP se pueden incluir teoremas ya demostrados sin necesidad de repetir cada vez su demostración.

Esto completa la definición de la Aritmética Recursiva Primitiva. En los mensajes siguientes mostraremos cómo trabajar en ella en la práctica, pero de momento terminamos éste con la consecuencia fundamental de lo que hemos demostrado en este mensaje:

Teorema de corrección  La conclusión de una deducción en ARP es necesariamente una fórmula verdadera si sus premisas lo son. En particular, todos los teoremas de ARP son fórmulas verdaderas.


Demostración
Si \( \delta_1,\ldots, \delta_n \) es una deducción en ARP, podemos razonar que cada \( \delta_i \) es una fórmula verdadera, luego en particular lo será su conclusión \( \delta_n \). En efecto, en caso contrario podríamos considerar el menor índice \( i \) tal que \( \delta_i \) no fuera verdadera, pero entonces \( \delta_i \) no puede ser una premisa (porque estamos suponiendo que las premisas son verdaderas), ni tampoco un axioma (porque hemos razonado que todos los axiomas son verdaderos), luego \( \delta_i \) tiene que ser consecuencia inmediata de fórmulas anteriores de la deducción. Pero, por la minimalidad de \( i \), dichas fórmulas tienen que ser verdaderas, y hemos demostrado que las conclusiones de las reglas de inferencia son verdaderas cuando sus premisas lo son, por lo que \( \delta_i \) también tiene que ser verdadera, y así tenemos una contradicción.
[cerrar]

Conviene enfatizar que, no es que los axiomas de ARP sean verdaderos, sino que son trivialmente verdaderos porque no son más que los matemáticos llaman normalmente definiciones, y que, de las cuatro reglas de inferencia, la primera sólo expresa que lo que es verdad para todo \( x \) tiene que ser verdad en particular para cualquier \( t \), la segunda sólo expresa que si \( t_1 = t_2 \), lo que digamos de \( t_1 \) vale igual para \( t_2 \), la tercera sólo expresa la transitividad de la igualdad y la cuarta es un caso particular del principio de inducción restringido a propiedades expresables en términos de funciones recursivas primitivas.

09 Junio, 2023, 03:55 pm
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Teóricamente, ya hemos cumplido el propósito de este hilo, que es presentar la Aritmética Recursiva Primitiva, pero en la práctica queda mucho por hacer. La mayor parte de las teorías axiomáticas son inmanejables si pretendemos razonar en ellas sin hacer uso de nada más que sus axiomas y sus reglas de inferencia, pues entonces la demostración más elemental se vuelve larga y artificiosa. La ventaja de reducir una teoría axiomática a unos pocos axiomas y reglas de inferencia es que así es fácil evaluar lo que estamos aceptando al trabajar en ella, pero el inconveniente es que necesitamos probar (a menudo penosamente) muchos resultados básicos hasta contar con una "caja de herramientas" con la que demostrar formalmente cualquier cosa tiene aproximadamente la misma dificultad que tiene el matemático a la hora de descubrir por qué lo que quiere probar es necesariamente cierto, de modo que la formalización del argumento es más o menos mecánico y rutinario. En este mensaje empezamos a dotarnos de esa "caja de herramientas", pero todavía quedará bastante camino por recorrer.

Recordemos que, en principio, sólo contamos con las definiciones de las funciones recursivas primitivas y con estas cuatro "míseras" reglas de inferencia:

\( (S_1)\ \ \ \ \begin{array}{c}
s_1(x)=s_2(x)\\
\hline
s_1(t)=s_2(t)
\end{array}\qquad (S_2)\ \ \ \
\begin{array}{c}
t_1=t_2\\
\hline
s(t_1)=s(t_2)
\end{array}\qquad
(T)\ \ \ \ \begin{array}{ccc}
t_1=t_2&&t_1=t_3\\
\hline
&t_2=t_3
\end{array} \)

\( (I_0)\ \ \ \ \begin{array}{ccc}
s_1(0)=s_2(0)&s_1(Sx)=h(x, s_1(x))&s_2(Sx)=h(x,s_2(x))\\
\hline
&s_1(x)=s_2(x)
\end{array} \)

Empezamos justificando que en ARP podemos hacer cualquier manipulación razonable con el igualador. En primar lugar:

Teorema Si \( t \) es un término cualquiera, la fórmula siguiente es un teorema de ARP:

\( t=t \).

Demostración
\( \begin{array}{rll}
(1)&p_1^1(x)=x&\text{Definición de }p^1_1\\[1mm]
(2)&p_1^1(t)=t&S_1, 1\\
(3)&t=t&T, 2, 2
\end{array} \)

Notemos que hemos aplicado la regla de inferencia de transitividad T tomando como sus dos premisas la misma línea 2 de la demostración (alternativamente, podríamos haber deducido (2) dos veces a partir de (1)).
[cerrar]

En segundo lugar probamos una regla de inferencia derivada, a la que llamaremos regla de simetría (del igualador):

\( (S)\ \ \ \begin{array}{c}
t_1=t_2\\
\hline
t_2=t_1
\end{array} \)

La prueba de \( t=t \) tenía "truco", pero ésta no, así que el lector podría plantearse como ejercicio encontrar la prueba por sí mismo antes de abrir el spoiler (recordemos que es lícito emplear en una demostración teoremas ya demostrados):

Demostración
\( \begin{array}{rll}
(1)&t_1=t_2&\text{Premisa}\\
(2)&t_1=t_1&\text{Teorema}\\
(3)&t_2=t_1&T, 1, 2
\end{array} \)
[cerrar]

También es fácil demostrar esta variante de la regla de transitividad, a la que también llamaremos T:

\( (T)\ \ \ \ \begin{array}{ccc}
t_1=t_2&&t_2=t_3\\
\hline
&t_1=t_3
\end{array} \)

Demostración
\( \begin{array}{rll}
(1)&t_1=t_2&\text{Premisa}\\
(2)&t_2=t_1&S, 1\\
(3)&t_2=t_3&\text{Premisa}\\
(4)&t_1=t_3&T, 2, 3
\end{array} \)
[cerrar]

Con esto vemos que en ARP podemos encadenar igualdades sin preocuparnos de si un término está a la izquierda o a la derecha de cada igualdad.

Ahora podemos probar una variante de \( S_2 \) que muestra más claramente que dos términos iguales cumplen lo mismo:

\( \begin{array}{ccc}
\alpha(t_1)&&t_1=t_2\\
\hline
&\alpha(t_2)
\end{array} \)

Demostración
Pongamos que \( \alpha(x)\equiv s_1(x) = s_2(x) \). Entonces
\( \begin{array}{rll}
(1)&s_1(t_1)=s_2(t_1)&\text{Premisa } \alpha(t_1)\\
(2)&t_1=t_2&\text{Premisa}\\
(3)&s_1(t_1)=s_1(t_2)&S_2, 2\\
(4)&s_2(t_1)=s_2(t_2)&S_2, 2\\
(5)&s_1(t_2)=s_2(t_2)&S, T, 1, 3, 4
\end{array} \)
[cerrar]

Definición de funtores por términos Veamos ahora que todo término puede usarse para definir un funtor:

Teorema Si \( t(x_1,\ldots, x_n) \) es un término cuyas variables están todas entre \( x_1,\ldots, x_n \), entonces existe un funtor \( n \)-ádico \( f_t \) tal que

\( \mathop{\vdash}\limits_{\rm ARP} f_t(x_1,\ldots, x_n)=t(x_1,\ldots, x_n). \)

Demostración
Razonamos por inducción sobre la longitud de \( t \). Si \( t\equiv 0 \), basta tomar\(  f_0 \equiv \kappa(c, p^n_1) \), pues la definición de \( f_0 \) es:

\( f_0(x_1,\ldots, x_n) = c(p_1^n(x_1,\ldots, x_n)), \)

y por otro lado, la definición de \( c \) es \( c(x) = 0 \), luego aplicando \( S_1 \) obtenemos

\( c(p_1^n(x_1,\ldots, x_n))=0, \)

y, finalmente, la regla \( T \) nos da la igualdad

\( f_0(x_1,\ldots, x_n) = 0. \)

Si \( t\equiv x_i \), basta tomar \( f_t\equiv p^n_i \). La alternativa es que \( t \equiv f(t_1,\ldots, t_m) \), para cierto funtor \( f \) y ciertos términos \( t_i \) para los que, por hipótesis de inducción, existen funtores \( f_{t_i} \) tales que

\( \mathop{\vdash}\limits_{\rm ARP}f_{t_i}(x_1,\ldots, x_n) = t_i(x_1,\ldots, x_n). \)

Basta tomar \( f_t \equiv \kappa(f, f_{t_1},\ldots, f_{t_m}) \), pues la definición de \( f_t \) es

\( f_t(x_1,\ldots, x_n) = f(f_{t_1}(x_1,\ldots, x_n), \ldots, f_{t_m}(x_1,\ldots, x_n)). \)

Si llamamos \( \bar t_i \equiv f_{t_i}(x_1, \ldots, x_n) \), tenemos \( f_t(x_1,\ldots, x_n) = f(\bar t_1,\ldots, \bar t_n) \), así como \( \bar t_i = t_i \), luego aplicando \( S_2 \) sucesivamente obtenemos

\( f(\bar t_1,\ldots, \bar t_n) = f(t_1,\bar t_2,\ldots, \bar t_n), \)

\( f(t_1,\bar t_2,\ldots, \bar t_n) = f(t_1, t_2, \bar t_3, \ldots, \bar t_n), \)

etc., y la regla \( T \) nos da

\( f_t(x_1,\ldots, x_n) = f(t_1, \ldots, t_n) \equiv t. \)
[cerrar]

Este teorema vuelve innecesario recurrir directamente a las definiciones de los funtores \( c \) o \( p^n_k \) o a las de los funtores definidos por composición, pues todas ellas son casos particulares de lo que acabamos de probar. Los únicos axiomas no triviales son a partir de ahora los que definen funciones por recursión.

Como primera aplicación del teorema anterior mostramos que también podemos definir funciones monádicas por recursión:

Teorema Si \( t \) es un término sin variables y \( h(x, y) \) es un término con a lo sumo las variables indicadas, existe un funtor monádico \( f \) que cumple

\( f(0)=t,\qquad f(Sx)=h(x, f(x)). \)

Demostración
Por el teorema anterior existe un funtor para el que se cumple \( g(y)=t \), y otro que cumple \( \bar h(x, y) = h(x, y) \). Consideramos el funtor diádico con axiomas

\( \bar f(y,0)=g(y),\qquad \bar f(y, Sx)=\bar h(x, \bar f(y,x)), \)

y a su vez definimos \( f\equiv\kappa(\bar f,c,p^1_1) \). Así \( f(x)=\bar f(0, x) \), luego

\( f(0)=\bar f(0, 0)=g(0)=t,\quad f(Sx)=\bar f(0, Sx)=\bar h(x, \bar f(0,x))=h(x, f(x)). \)
[cerrar]

Por ejemplo, en virtud de este teorema, en ARP podemos definir el funtor factorial:

\( 0! = 1, \qquad (Sx)! = Sx\cdot x! \),

mientras que esta definición no encaja con la definición de funtores por recursión que habíamos dado.

Recogemos en el teorema siguiente los resultados que acabamos de demostrar, y que son la forma más natural de trabajar con los funtores de ARP:

Teorema Se cumple:

  • Si \( t(x_1,\ldots, x_n) \) es un término cuyas variables están todas entre \( x_1,\ldots, x_n \), entonces existe un funtor \( n \)-ádico \( f_t \) tal que

    \( f_t(x_1,\ldots, x_n)=t(x_1,\ldots, x_n). \)

  • Si \( g(x_1,\ldots, x_n) \), \( h(x_1,\ldots, x_n, x, y) \) son términos con a lo sumo las variables indicadas, existe un funtor \( n+1 \)-ádico \( f \) que cumple:

    \( f(x_1,\ldots, x_n, 0)=g(x_1,\ldots, x_n), \)

    \( f(x_1,\ldots, x_n, Sx)=h(x_1,\ldots, x_n, x, f(x_1,\ldots, x_n,x)). \)

  • Si \( t \) es un término sin variables y \( h(x,y) \) es un término con a lo sumo las variables indicadas, existe un funtor monádico \( f \) que cumple

    \( f(0)=t,\qquad f(Sx)=h(x, f(x)). \)

La única variante en 2) y 3) es que en los miembros derechos ponemos términos arbitrarios en vez de funtores, lo cual es lícito gracias a 1), y ello nos evita toda preocupación sobre que el número de variables sea el exigido por el esquema de recursión.

Notemos también que, en 2), el hecho de que la recursión se haga sobre el último argumento de \( f \) es anecdótico. Por ejemplo, si queremos que la recursión se haga sobre el primero basta considerar el funtor:

\( f^*(x_1,\ldots, x_{n+1})=f(p^{n+1}_2(x_1,\ldots, x_{n+1}), \ldots, p^{n+1}_{n+1}(x_1,\ldots, x_{n+1}), p^{n+1}_1(x_1,\ldots, x_{n+1})), \)
que cumple

\( f^*(0,x_1,\ldots, x_n)=g(x_1,\ldots, x_n), \)

\( f^*(Sx,x_1,\ldots, x_n)=h(x_1,\ldots, x_n, x, f^*(x,x_1,\ldots, x_n)). \)

Inducción Ahora enunciamos dos casos particulares de la regla de inducción que nos serán útiles más adelante:

\( (I_1)\ \ \ \begin{array}{c}
t(Sx)=t(x)\\
\hline
t(x)=t(0)
\end{array}\qquad
(I_2)\ \ \ \begin{array}{ccc}
s_1(0)=s_2(0)&&s_1(Sx)=s_2(Sx)\\
\hline
&s_1(x)=s_2(x)
\end{array} \)

La regla \( I_1 \) afirma que si un término toma el mismo valor en cada número natural y en su siguiente, entonces tiene que ser constante.

Demostración
Aplicamos la regla de inducción a los términos \( s_1(x)\equiv t(x) \), \( s_2(x)\equiv t(0) \), \( h(x, y) \equiv y \), con lo que se reduce a:

\( \begin{array}{ccc}
t(0)=t(0)&t(Sx)=t(x)&t(0)=t(0)\\
\hline
&t(x)=t(0)
\end{array} \)

Vemos que las premisas primera y tercera son un mismo teorema y la segunda es la premisa de \( I_1 \), luego, en efecto, la conclusión se deduce de dicha premisa.
[cerrar]

La regla \( I_2 \) afirma que si dos términos coinciden en \( 0 \) y en todos los números naturales que son el sguiente de otro, entonces coinciden en todos los números naturales.

Demostración
Esta regla se sigue inmediatamente de \( I_0 \) usando \( h(x, y)\equiv s_2(Sx) \), pues así \( I_0 \) se reduce a:

\( \begin{array}{ccc}
s_1(0)=s_2(0)&s_1(Sx)=s_2(Sx)&s_2(Sx)=s_2(Sx)\\
\hline
&s_1(x)=s_2(x)
\end{array} \)

de modo que las dos primeras premisas son las premisas de \( I_2 \) y la tercera es un teorema.
[cerrar]

Sustitución de variables En varias ocasiones hemos señalado que, en general, será irrelevante qué variables concretas consideramos en cada momento. Ahora podemos precisar este hecho. Consideremos, por ejemplo, este axioma de ARP:

\( p_1^2(x_0, x_1) = x_0, \)

donde suponemos que las variables son precisamente las de índices \( 0 \) y \( 1 \). Consideremos ahora dos variables cualesquiera \( x, y \) y otras dos variables \( y_0, y_1 \) distintas de \( x_0, x_1, x, y \). Aplicando sucesivamente la regla \( S_1 \) podemos ir deduciendo:

\( \begin{array}{rl}
(1)&p_1^2(x_0, x_1) = x_0\\
(2)&p_1^2(y_0, x_1) = y_0\\
(3)&p_1^2(y_0, y_1) = y_0\\
(4)&p_1^2(x, x_1) = x\\
(5)&p_1^2(x, y) = x
\end{array}
 \)

Así pues, o bien consideramos que todas las fórmulas \( p^2_1(x, y) = x \) son axiomas, o bien especificamos unas variables en concreto para los axiomas, pero en este segundo caso las fórmulas con otras elecciones de variables son teoremas y en la práctica es lo mismo.

10 Junio, 2023, 11:49 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Veamos ahora algunos resultados que ilustren cómo podemos trabajar en ARP con los pocos medios de que disponemos de momento.

La suma Empezamos recordando la definición del funtor suma. Según hemos explicado, para definir un funtor, en la práctica, basta presentar los axiomas que lo definen, que en el caso de la suma son las ecuaciones:

\( x+0 = x,\qquad x+Sy = S(x+y). \)


Por el teorema sobre definición de funtores que hemos visto en el mensaje anterior, es inmediato que estas ecuaciones determinan, en efecto, un funtor diádico \( + \). He aquí algunos teoremas de ARP relativos a la suma:

  • \( Sx=x+1 \)
  • \[ (x+y)+z=x+(y+z) \]
  • \[ x+y=y+x \]

Demostración: En la práctica no es necesario que escribamos explícitamente cada demostración en ARP como una sucesión de fórmulas. Por ejemplo, para justificar que 1) es un teorema de ARP al lector le debería bastar esto:

\( x+1 = x+S0 = S(x+0) = Sx. \)

Una demostración explícita (teniendo en cuenta que \( x+1 \equiv x+S0 \)) sería así:

\( \begin{array}{rll}
(1)&x+Sy = S(x+y)&\text{Definición de suma}\\
(2)&x+1 = S(x+0)&S_1, 1\\
(3)&x+0 = x&\text{Definición de suma}\\
(4)&S(x+0)=Sx&S_2, 3\\
(5)&x+1=Sx&T, 2, 4\\
(6)&Sx = x+1&S,5
\end{array}
 \)

La fórmula 2) la demostramos por inducción sobre \( z \), es decir, considerando los términos \( s_1(z)\equiv (x+y)+z \), \( s_2(z)\equiv x+(y+z) \). La regla \( I_0 \) requiere probar en primer lugar que

\( s_1(0) \equiv  (x+y)+0 = x+y = x+(y+0) \equiv s_2(0). \)

En segundo lugar tenemos que calcular

\( s_1(Sz) \equiv (x+y)+Sz = S((x+y)+z) \equiv S(s_1(z)), \)

\( s_2(Sz) \equiv x+(y+Sz) = x+S(y+z) = S(x+(y+z))\equiv S(s_2(z)). \)

Vemos así que \( s_1(Sz) \) y \( s_2(Sz) \) se obtienen, respectivamente, de \( s_1(z) \) y \( s_2(z) \) aplicando un mismo funtor (en este caso \( S \)), y con esto ya podemos aplicar \( I_0 \) para concluir la igualdad.

De nuevo doy la prueba detallada para que el lector vea cómo se pueden completar fácilmente estos argumentos con sustituciones y las propiedades del igualador:

\( \begin{array}{rll}
(1)&x+0 = x&\text{Definición de suma}\\
(2)&(x+y)+0 = x+y&S_1,1\\
(3)&y+0 = y&\text{Definición de suma}\\
(4)&x+(y+0) = x+y&S_2,3\\
(5)&(x+y)+0 = x+(y+0)&T, 2, 4\\
(6)&x+Sz = S(x+z)&\text{Definición de suma}\\
(7)&(x+y)+Sz = S((x+y)+z)&S_1,6\\
(8)&y+Sz = S(y+z)&\text{Definición de suma}\\
(9)&x+(y+Sz)= x+S(y+z)&S_2,8\\
(10)&x+S(y+z) = S(x+(y+z))&S_1,6\\
(11)&x+(y+Sz) = S(x+(y+z))&T, 9, 10\\
(12)&(x+y)+z = x+(y+z)&I_0, 5, 7, 11
\end{array}
 \)

Para probar 3) probamos primero un caso particular: \( 0 + x = x \). Razonamos por inducción con \( s_1(x) = 0+x \), \( s_2(x) = x \). Un esbozo de la prueba consiste en observar que, por definición de suma \( s_1(0)\equiv 0+0 = 0\equiv  s_2(0) \) y, por otra parte,

\( s_1(Sx) \equiv 0+ Sx = S(0+x) \equiv S(s_1(x)), \quad s_2(Sx) \equiv Sx  \equiv S(s_2(x)), \)

de modo que \( s_1(Sx) \) y \( s_2(Sx) \) se obtienen de \( s_1(x) \) y \( s_2(x) \) respectivamente mediante el mismo cálculo (aplicar el funtor \( S \)), luego la regla \( I_0 \) nos da la conclusión.

En segundo lugar probamos que \( Sy +x = y+ Sx \), ahora por inducción con \( s_1(x) \equiv Sy+x \), \( s_2(x) \equiv y+Sx \). En primer lugar:

\( s_2(0) \equiv y+S0 = S(y+0) = Sy = Sy+0 \equiv s_1(0). \)

Por otra parte,

\( s_1(Sx)\equiv Sy+Sx = S(Sy+x) \equiv S(s_1(x)), \)

\( s_2(Sx)\equiv y+SSx = S(y+Sx) \equiv S(s_2(x)), \)

y podemos aplicar la regla \( I_0 \).

Por último razonamos por inducción con \( s_1(y) \equiv x+y \), \( s_2(y)\equiv y+x \). Por la primera igualdad que hemos probado:

\( s_1(0)\equiv x+0 = x = 0+x \equiv s_2(0). \)

Y usando la segunda igualdad:

\( s_1(Sy)\equiv  x+Sy = S(x+y) \equiv S(s_1(y)), \)

\( s_2(Sy)\equiv Sy+ x = y+ Sx = S(y+x)\equiv S(s_2(y)), \)

y también podemos aplicar la regla \( I_0 \). Dejamos a cargo del lector dar una prueba explícita.

El producto Ahora recordamos la definición del producto de números naturales, que está determinado por los axiomas:

\( x\cdot 0 = 0,\qquad x\cdot Sy = x\cdot y+ x. \)

De nuevo el teorema sobre definición de funtores garantiza que esta definición es correcta. Los teoremas básicos sobre el producto son:

  • \( x\cdot 1 = x \)
  • \( x\cdot y = y\cdot x \)
  • \( x\cdot (y+z)=x\cdot y+x\cdot z \)
  • \( x(yz)=(xy)z \)

Dejo las demostraciones como ejercicio, pero doy algunas indicaciones:

Spoiler
1) Inmediato a partir de las definiciones.

2) En primer lugar, probar por inducción \( 0\cdot x = 0 \).

En segundo lugar, por inducción sobre \( y \), probar \( (Sx)\cdot y = x\cdot y+y \).

Finalmente, probar el teorema por inducción sobre \( x \).

3), 4) Directamente por inducción sobre \( z \).
[cerrar]

Cálculos explícitos El lector sabrá sin duda que \( 2\cdot 3 = 6 \), pero una cosa es que una afirmación aritmética sea verdadera y otra muy distinta que pueda demostrarse en ARP. Para que suceda lo segundo es necesario que la afirmación se pueda expresar mediante una fórmula de \( \mathcal L_{\rm arp} \) (lo cual es cierto en este caso, pues podemos considerar a \( 2\cdot 3 = 6 \) como una fórmula de \( \mathcal L_{\rm arp} \) que significa precisamente que ``dos por tres son seis'') y además que dicha fórmula pueda demostrarse a partir de los axiomas de ARP usando las reglas de inferencia de ARP, y esto no sucede con todas las afirmaciones verdaderas formalizables en ARP. No obstante, en el caso de esta fórmula en particular es fácil encontrar una demostración:

\( \begin{eqnarray*}
2\cdot 3 &=&2\cdot 2+2=(2\cdot 1+2)+2=((2\cdot 0+2)+2)+2=((0+2)+2)+2\\
&=&S(((0+2)+2)+1)=SS(((0+2)+2)+0)=SS((0+2)+2)\\
&=&SS(S((0+2)+1))=SS(SS((0+2)+0))=SSSS(0+2)\\
&=&SSSSS(0+1)=SSSSSS(0+0)=SSSSSS0=6.
\end{eqnarray*}
 \)

Podríamos haber abreviado la demostración usando algunos de los teoremas que hemos demostrado sobre la suma y el producto, pero hemos dado una demostración basada exclusivamente en las definiciones de la suma y del producto (y de los numerales). Como el producto se define a partir de la suma y la suma a partir del funtor \( S \), lo que hemos hecho ha sido reducir el cálculo de un producto al cálculo de varias sumas, y el cálculo de las sumas a aplicar varias veces el operador \( S \).

Es fácil convencerse de que en ARP se puede calcular cualquier suma y cualquier producto, pero en realidad sucede algo mucho más general: todas las funciones expresables mediante funtores de ARP se pueden calcular en la práctica, en el sentido de que el resultado se puede reducir a un numeral (no en vano son las funciones recursivas primitivas). Esto es lo que prueba el teorema siguiente:

Teorema Si \( t \) es un término sin variables y \( d = N(t) \) es el número natural denotado por \( t \), entonces

\( \mathop{\vdash}\limits_{\rm ARP} t=N_d, \)

donde \( N_d \) es el numeral de índice \( d \).

Demostración
En primer lugar demostramos el teorema en el caso en que \( t\equiv f(N_{d_1},\ldots, N_{d_n}) \), donde \( f \) es un funtor y cada \( d_i \) es un número natural, de modo que \( d = F(f)(d_1,\ldots, d_n) \). Razonamos por inducción sobre la longitud de \( f \).

  • Si \( f \equiv S \), entonces \( t \equiv Sd_1 \equiv N_{d_1+1}\equiv N_d \) y, ciertamente, \( \mathop{\vdash}\limits_{\rm ARP}N_d = N_d \).

  • Si \( f\equiv c \), entonces \( t\equiv c(N_{d_1}) \), luego \( d = F(c)(d_1) =0 \) y, como \( c(x)=0 \) es un axioma de ARP, la regla \( S_1 \) nos da \( \mathop{\vdash}\limits_{\rm ARP} t= N_0 \).

  • Si \( f\equiv p_k^n \), entonces \( t\equiv p_k^n(N_{d_1},\ldots, N_{d_n}) \), luego \( d = F(p^n_k)(d_1,\ldots, d_n)=d_k \). Como \( p^n_k(x_1,\ldots, x_n)=x_k \) es un axioma de ARP, aplicando \( n \) veces la regla \( S_1 \) obtenemos que \( \mathop{\vdash}\limits_{\rm ARP}t = N_d \).

  • Si \( f\equiv \kappa(h, g_1,\ldots, g_m) \), tenemos entonces que \( d = F(h)(e_1,\ldots, e_m) \), donde \( e_i = F(g_i)(d_1,\ldots, d_n) \). Por hipótesis de inducción tenemos que

    \( \mathop{\vdash}\limits_{\rm ARP}g_i(N_{d_1},\ldots, N_{d_n}) = N_{e_i},\qquad \mathop{\vdash}\limits_{\rm ARP} h(N_{e_1},\ldots, N_{e_m}) = N_d. \)

    Aplicando \( m \) veces la regla \( S_2 \), de aquí obtenemos

    \( \mathop{\vdash}\limits_{\rm ARP}h(g_1(N_{d_1},\ldots, N_{d_n}),\ldots,g_m(N_{d_1},\ldots N_{d_n})) = N_d, \)

    y aplicando \( S_1 \) a la definición de \( f \) y la regla \( T \) concluimos \( \mathop{\vdash}\limits_{\rm ARP}t = N_d. \)

  • Si \( f\equiv \rho(g, h) \), entonces \( d \) viene determinado por las relaciones

    \( e_0 = N(g)(d_1,\ldots, d_{n-1}),\quad e_{i+1} = N(h)(d_1,\ldots, d_{n-1}, i, e_i), \)

    de modo que \( d = e_{d_n} \). Por hipótesis de inducción

    \( \mathop{\vdash}\limits_{\rm ARP}g(N_{d_1}, \ldots, N_{d_{n-1}}) = N_{e_0}, \)

    y teniendo en cuenta que

    \( f(x_1,\ldots, x_{n-1},0) = g(x_1,\ldots, x_{n-1}) \)

    es un axioma de ARP (parte de la definición de \( f \)), aplicando \( S_1 \) llegamos a que

    \( \mathop{\vdash}\limits_{\rm ARP} f(N_{d_1},\ldots, N_{d_{n-1}}, 0) = g(N_{d_1}, \ldots, N_{d_{n-1}}) \)

    y por \( T \) concluimos que \( \mathop{\vdash}\limits_{\rm ARP}f(N_{d_1},\ldots, N_{d_{n-1}}, N_0) =N_{e_0} \). Veamos que, en general,

    \( \mathop{\vdash}\limits_{\rm ARP}f(N_{d_1}, \ldots,N_{d_{n-1}}, N_i) =N_{e_i}. \)

    Lo tenemos probado para i\(  = 0 \). Razonando por inducción sobre \( i \), lo suponemos cierto para \( i \) y usamos que, por la hipótesis de inducción sobre la longitud de \( f \) (aplicada al funtor \( h \)):

    \( \mathop{\vdash}\limits_{\rm ARP} h(N_{d_1}, \ldots, N_{d_{n-1}}, N_i, N_{e_i}) = N_{e_{i+1}}. \)

    Usando la definición de \( f \), según la cual

    \( f(x_1,\ldots, x_{n-1}, Sx) = h(x_1,\ldots, x_{n-1}, x, f(x_1,\ldots, x_{n-1}, x)), \)

    aplicando \( S_1 \) obtenemos

    \( \mathop{\vdash}\limits_{\rm ARP} f(N_{d_1},\ldots, N_{d_{n-1}},N_{i+1})= h(N_{d_1},\ldots, N_{d_{n-1}}, N_i, f(N_{d_1},\ldots,N_{d_{n-1}},N_i)). \)

    La hipótesis de inducción sobre \( i \) junto con las reglas \( S_2 \) y \( T \) nos dan

    \(  \mathop{\vdash}\limits_{\rm ARP}f(N_{d_1},\ldots, N_{d_{n-1}}, N_{i+1})= h(N_{d_1},\ldots, N_{d_{n-1}}, N_i, N_{e_i}), \)

    y la hipótesis de inducción sobre \( h \), junto con \( T \), nos permite concluir que

    \( \mathop{\vdash}\limits_{\rm ARP} f(N_{d_1},\ldots, N_{d_{n-1}}, N_{i+1})= N_{e_{i+1}}. \)

    Esto completa la inducción sobre \( i \), con lo que, en particular, para \( i = d_n \), tenemos que

    \( \mathop{\vdash}\limits_{\rm ARP}f(N_{d_1},\ldots, N_{d_n})= N_d. \)

Esto termina la prueba del caso particular. Para probar el caso general razonamos por inducción sobre la longitud de \( t \). Si \( t\equiv N_0 \), entonces \( d = 0 \) y ciertamente \( \mathop{\vdash}\limits_{\rm ARP}N_0 = N_0 \).

La alternativa es que \( f \equiv f(t_1,\ldots, t_n) \), para cierto funtor \( f \) y ciertos términos sin variables \( t_i \) que, por hipótesis de inducción, llamando \( d_i = N(t_i) \), cumplirán

\( \mathop{\vdash}\limits_{\rm ARP}t_i = N_{d_i} \)

Además, \( d = N(t) = F(f)(d_1,\ldots, d_n) \). Por la parte ya probada,

\( \mathop{\vdash}\limits_{\rm ARP} f(N_{d_1},\ldots, N_{d_n}) = N_d, \)

luego aplicando \( n \) veces la regla \( S_2 \) seguida de \( n \) aplicaciones de la regla \( T \) llegamos a que \( \mathop{\vdash}\limits_{\rm ARP} t = N_d \).
[cerrar]

Así pues, si comprobamos que una función recursiva primitiva, sobre unos valores dados, toma un cierto valor, independientemente de cómo hayamos llegado a esa conclusión, podemos asegurar que ese hecho puede probarse razonando formalmente en ARP (simplemente, aplicando las definiciones de la función considerada y las que se usan para definirla).

En el próximo mensaje prepararemos el camino para extraer toda la potencia de ARP.

13 Junio, 2023, 03:06 pm
Respuesta #8

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En este mensaje estudiaremos tres funtores o, equivalentemente, tres funciones recursivas primitivas. Empezamos con las dos primeras:

La resta truncada Consideramos los funtores definidos así:

\( \text{pre}(0)=0,\quad \text{pre}(Sx)=x, \)

\( x\dot{-} 0 = x,\qquad x\dot{-} Sy=\text{pre}(x\dot{-} y). \)


Es fácil entender cuáles son las funciones denotadas por estos funtores:

\( N(\text{pre})(n) = \cases{0&si $n=0$,\cr n-1&si $n>0$,}\qquad N(\dot{-})(m,n)=\cases{m-n&si $m\geq n$,\cr 0& si $m\leq n$.} \)

En otras palabras, la resta truncada \( x\dot{-}y \) es la resta \( x-y \) salvo que ésta no pueda efectuarse, en cuyo caso el resultado es \( 0 \).

Todo esto es evidente y, sin embargo, no es fácil expresar estos hechos en el lenguaje de ARP. ¿Qué fórmula expresa que \( x\dot{-} y = 0 \) cuando \( x\leq y \)? Incluso, restringiéndonos a lo que sabemos expresar en ARP, de las premisas \( x\dot{-} y = 0 \), \( y\dot{-} x = 0 \), tendría que poder deducirse que \( x= y \) y, en efecto, se puede, pero ¿cómo? Veremos que la prueba es complicada, y el hecho de que algo tan evidente sea difícil de probar da una idea de que ARP no es, tal y como la conocemos, una teoría muy "amigable".

Empezamos probando algunos resultados sencillos (que el lector puede tratar de probar por su cuenta para ir familiarizándose con la ARP "dura"):

Propiedades de la resta truncada

  •   \( x\dot{-} 1=\text{pre}\, x \)

    Demostración
    Ésta es inmediata:
    \( x\dot{-}1 = \text{pre}\,(x\dot{-}0)=\text{pre}\, x \)
    [cerrar]
  •   \( Sx \dot{-} Sy=x \dot{-} y \)

    (Ayuda: Razonar por inducción sobre \( y \).)
    Demostración

    \( Sx\dot{-} S0 = \text{pre}\, (Sx\dot{-} 0)=\text{pre}\, Sx = x=x\dot{-} 0, \)

    \( Sx\dot{-} SSy = \text{pre}\,(Sx\dot{-} Sy),\qquad x\dot{-} Sy=\text{pre}\,(x\dot{-} y). \)

    Con esto hemos probado que \( Sx\dot{-} SSy \) se obtiene de \( Sx\dot{-} Sy \) con el mismo funtor que nos da \( x\dot{-} Sy \) a partir de \( x\dot{-} y \), luego la regla de inducción nos da la igualdad.
    [cerrar]
  •   \( x\dot{-}x=0 \)

    (Ayuda: Aplicar la regla de inducción \( I_1 \) a \( t(x)\equiv x\dot{-}x \).
    Demostración

    Como \( Sx\dot{-}Sx = x\dot{-} x \), la regla \( I_1 \) nos da que \( x\dot{-}x = 0\dot{-} 0 = 0 \).
    [cerrar]
  •   \( 0\dot{-}x=0 \)

    (Ayuda: Inducción con \( s_1(x)\equiv 0\dot{-}x \), \( s_2(x)\equiv 0 \).)
    Demostración

    \( s_1(0)=0\dot{-}0 = 0=s_2(0), \)

    \( s_1(Sx)=0\dot{-}Sx=\text{pre}\,(0\dot{-} x)=\text{pre}\,s_1(x), \)

    \( s_2(Sx)=0=\text{pre}\,0=\text{pre}\,s_2(x). \)
    [cerrar]
  •   \( (x+y)\dot{-} y=x \)

    (Ayuda: Aplicar la regla \( I_1 \) a \( t(y)\equiv (x+y)\dot{-} y \).)
    Demostración

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

    luego la conclusión es \( (x+y)\dot{-} y=(x+0)\dot{-} 0 = x \).
    [cerrar]
  •   \( (x+y)\dot{-} x=y \)

    Esto es consecuencia del punto anterior y de la conmutatividad de la suma.

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

    (Ayuda: Aplicar la regla \( I_1 \) a \( t(z)\equiv (x+z)\dot{-} (y+z) \).)
    Demostración

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

    luego \( (x+z)\dot{-}(y+z)=(x+0)\dot{-}(y+0)=x\dot{-} y \).
    [cerrar]
  •   \( y\dot{-}  (x+y)=0 \)

    (Ayuda: Aplicar el punto anterior.)
    Demostración

    \( y\dot{-} (x+y) =(0+y)\dot{-} (x+y)=0\dot{-} x=0. \)
    [cerrar]
  •   \( x\cdot (1\dot{-} x)=0 \)

    (Ayuda: Aplicar la regla \( I_2 \).)
    Demostración

    \( 0\cdot (1\dot{-} 0)=0,\qquad  (Sx)(1\dot{-} Sx)=(Sx)(0\dot{-} x)=(Sx)\cdot 0 = 0. \)
    [cerrar]
  •   \( (1\dot{-} x)y = y\dot{-} (xy) \)

    (Ayuda: Inducción sobre \( x \))
    Demostración

    \( (1\dot{-} 0)y =y = y\dot{-} 0 = y\dot{-} (0\cdot y), \)

    \( (1\dot{-} Sx)y = (0-x)y=0\cdot y  = 0, \)

    \( y\dot{-} (Sx)\cdot y = y\dot{-} (y+xy)=0, \)

    donde en el último paso hemos usado el punto 8.
    [cerrar]

Ahora abordamos el problema de deducir \( x=y \) de las premisas \( x\dot{-} y = 0, y\dot{-} x = 0 \). No tenemos —de momento— una forma de llevar a cabo una inducción que tenga en cuenta unas premisas. En su lugar, vamos a probar una igualdad válida sin premisas, pero que, al suponer \( x\dot{-} y = 0, y\dot{-} x = 0 \), se reduce a \( x=y \). El teorema siguiente es una de las piezas clave para sacar a la luz la auténtica potencia de ARP:

Teorema \( x+(y\dot{-}x)=y+(x\dot{-} y) \).

Demostración: Sea \( t_1(x, y)\equiv x+(y\dot{-}  x) \), de modo que

\( t_1(x,0)=x,\quad t_1(0, y)=y,\qquad t_1(Sx,Sy)=St_1(x, y). \)

Igualmente, sea \( t_2(x, y)\equiv y+(x\dot{-}  y) \), de modo que

\( t_2(x, 0)=x,\quad t_2(0, y)=y,\quad t_2(Sx,Sy)=St_2(x, y). \)

En primer lugar, usando \( I_2 \), demostramos que

\( (x\dot{-}1)+(1\dot{-}(1\dot{-} x))=x. \)

Demostración
Para \( x=0 \) se cumple la igualdad, pues

\( (0\dot{-} 1)+(1\dot{-} (1\dot{-} 0))= 0+(1\dot{-} 1)=0. \)

Por otro lado, usando la propiedad 2 de la resta truncada,

\( (Sx\dot{-} 1)+(1\dot{-} (1\dot{-} Sx)) = x+(1\dot{-} (0\dot{-} x))=x+1=Sx, \)

luego \( I_2 \) nos permite concluir.
[cerrar]

De aquí deducimos a su vez que

(*)        \( t_1(x, y)=t_1(x\dot{-} 1, y\dot{-} 1)+(1\dot{-} (1\dot{-} (x+y))). \)

Aplicamos de nuevo la regla de inducción \( I_2 \) respecto de \( y \). El miembro derecho en \( y=0 \) es

\( t_1(x\dot{-} 1, 0)+(1\dot{-} (1\dot{-} x))=x\dot{-} 1+(1\dot{-} (1\dot{-} x))=x=t_1(x, 0), \)

por la igualdad que hemos demostrado previamente. Esto completa el primer paso de la inducción. Por otra parte, el miembro derecho para \( Sy \) es:

\( t_1(x\dot{-} 1, Sy\dot{-} 1)+(1\dot{-} (1\dot{-} (x+Sy)))= \)

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

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

\( t_1(x\dot{-} 1, y)+1=St_1(x\dot{-} 1, y). \)

Por lo tanto, para aplicar \( I_2 \) basta demostrar que el miembro izquierdo en \( Sy \) es también:

\( t_1(x, Sy)=St_1(x\dot{-}  1, y). \)

Esto lo probamos a su vez aplicando \( I_2 \) respecto de \( x \).

Demostración
Para \( x=0 \) se reduce a \( Sy=Sy \). Además,

\( t_1(Sx, Sy)=St_1(x, y)=St_1(\text{pre}\, Sx,y)=St_1(Sx\dot{-} 1, y). \)
[cerrar]

Esto termina la prueba de (*). Ahora consideramos el funtor dado por las ecuaciones

\( F(x, y, 0)=0,\quad F(x, y, Sz)=F(x, y, z)+(1\dot{-}(1\dot{-}((x\dot{-}z)+(y\dot{-}z)))). \)

Vamos a demostrar que
(**)     \( t_1(x\dot{-} z,y\dot{-} z)+F(x, y, z)= t_1(x\dot{-}Sz,y\dot{-}Sz)+F(x, y, Sz). \)

En efecto, por (*) tenemos que
\( t_1(x\dot{-} z,y\dot{-} z)+F(x, y, z)= \)

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

\( t_1(x\dot{-} Sz,y\dot{-} Sz)+F(x, y, Sz). \)

Notemos que el miembro derecho de (**) resulta de sustituir \( z \) por \( Sz \) en el miembro izquierdo, luego la regla \( I_1 \) nos da que

\( t_1(x\dot{-} z,y\dot{-} z)+F(x, y, z)=t_1(x\dot{-} 0,y\dot{-} 0)+F(x, y, 0)=t_1(x, y). \)

Ahora bien, intercambiando los papeles de \( x \) e \( y \), el mismo razonamiento vale para \( t_2 \), y nos lleva hasta

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

(Notemos que la definición de \( F \) es simétrica.)

Sustituyendo \( z \) por \( y \) queda

\( t_1(x\dot{-} y,0)+F(x, y, y)=t_1(x, y),\qquad t_2(x\dot{-}y,0)+F(x, y, y)=t_2(x, y) \)

o también:

\( t_1(x, y)=x\dot{-} y+F(x, y, y),\qquad t_2(x, y)=x\dot{-} y+F(x, y, y), \)

luego \( t_1(x, y)=t_2(x, y) \), que es lo que queríamos probar.



Ahora ya es inmediato que de \( x\dot{-} y = 0, y\dot{-} x = 0 \) se deduce \( x=y \), pero vamos a enunciarlo en términos más convenientes:

El valor absoluto Consideramos el funtor dado por

\( |x-y|=(x\dot{-} y)+(y\dot{-} x). \)

El hecho fundamental que vamos a necesitar es que se cumplen estas dos reglas de inferencia:

\( \begin{array}{c}
s=t\\
\hline
|s-t|=0
\end{array}\qquad
\begin{array}{c}
|s-t|=0\\
\hline
s=t
\end{array} \)

donde \( s, t \) son términos cualesquiera.

La primera es inmediata, mientras que la segunda es consecuencia del teorema anterior. En efecto, si suponemos \( |s-t|=0 \), tenemos que

\( |s-t|\dot{-} (t\dot{-} s)=0 \)

(porque \( 0\dot{-}  x=0 \)), pero esto es

\( ((s\dot{-} t)+(t\dot{-}  s))-(t\dot{-} s)=0 \)

y la propiedad 5 de la resta truncada nos da que \( s\dot{-} t=0 \). Análogamente (usando la propiedad 6) concluimos que \( t\dot{-} s = 0 \), y el teorema nos da entonces que \( s=t \).

Propiedades del valor absoluto

  •   \( |x-y|=|y-x| \)

  •   \( |x-0|=x \)

  •   \( |(x+z)-(y+z)|=|x-y| \)

  •   \( (1\dot{-} z)|x-y|= |(1\dot{-} z)x-(1\dot{-} z)y| \)

Las dejo como ejercicio. La última se prueba con la regla de inducción \( I_2 \) sobre \( z \).

La importancia de lo que hemos probado aquí se debe a lo siguiente: hasta ahora teníamos que toda fórmula de ARP es de la forma \( s = t \), para ciertos términos \( s, t \), y ahora tenemos que, en virtud de las reglas del valor absoluto, toda fórmula de ARP es equivalente a una de la forma \( u = 0 \), para cierto término \( u \). No parece un avance fascinante, pero en el mensaje siguiente le sacaremos un partido espectacular.

18 Junio, 2023, 07:58 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Toda fórmula de \( \mathcal L_{\rm arp} \) es de la forma \( \alpha \equiv s_1 = s_2 \), para ciertos términos \( s_1, s_2 \). Definimos \( t_\alpha \equiv |s_1-s_2| \), de modo que las dos reglas de inferencia del valor absoluto nos dan en particular las reglas:

\( \begin{array}{c}
\alpha\\
\hline
t_\alpha=0
\end{array}\qquad
\begin{array}{c}
t_\alpha=0\\
\hline
\alpha
\end{array} \)

Esto significa que, en realidad, toda fórmula de \( \mathcal L_{\rm arp} \) puede expresarse como un término igualado a cero. Puede parecer una curiosidad irrelevante, pero es todo lo contrario, pues esto nos permite dar las definiciones siguientes:

Si \( \alpha \) y \( \beta \) son fórmulas, definimos:

\( \lnot\alpha\equiv 1\dot{-} t_\alpha =0,\qquad \alpha\rightarrow \beta\equiv (1\dot{-} t_\alpha)\cdot t_\beta=0. \)

\( \alpha\lor\beta \equiv t_\alpha\cdot t_\beta = 0,\qquad \alpha\land \beta \equiv t_\alpha+t_\beta=0,\qquad \alpha\leftrightarrow\beta\equiv (\alpha\rightarrow\beta)\land (\beta\rightarrow\alpha).
 \)

Escribiremos también \( s\neq t\equiv \lnot(s=t) \).

El significado de estas fórmulas es claro. Observemos que, en general, fijada una valoración \( v \), se cumple \( \vDash \alpha[v] \) si y sólo si \( \vDash (t_\alpha = 0)[v] \), si y sólo si \( N(t_\alpha)[v] = 0 \).

En efecto, si  \( \alpha\equiv s_1 = s_2 \), entonces, \( \vDash (t_\alpha = 0)[v] \) significa que \( |N(s_1)[v]-N(s_2)[v]| = 0 \), y esto equivale a \( N(s_1)[v] = N(s_2)[v] \), que a su vez equivale a \( \vDash \alpha [v] \).

Por lo tanto:


  • \( \vDash \lnot\alpha[v] \) si y sólo si \( 1\dot{-} N(t_\alpha)[v] =0 \), si y sólo si \( N(t_\alpha)[v]\neq 0 \), si y sólo si no se cumple \( \vDash \alpha[v] \).

  • \( \vDash(\alpha\lor \beta)[v] \) si y sólo si \( N(t_\alpha)[v]\cdot N(t_\beta)[v] =0 \), si y sólo si \( N(t_\alpha)[v] =0 \) o \( N(t_\beta)[v] =0 \), si y sólo si \( \vDash \alpha[v] \) o \( \vDash \beta[v] \).

  • \( \vDash(\alpha\land \beta)[v] \) si y sólo si \( N(t_\alpha)[v]+ N(t_\beta)[v] =0 \), si y sólo si \( N(t_\alpha)[v] =0 \) y \( N(t_\beta)[v] =0 \), si y sólo si \( \vDash \alpha[v] \) y \( \vDash \beta[v] \).

  • \( \vDash(\alpha\rightarrow \beta)[v] \) si y sólo si \( (1\dot{-} N(t_\alpha)[v])\cdot N(t_\beta)[v]=0 \), lo cual equivale a que \( 1\dot{-} N(t_\alpha)[v]=0 \) o \( N(t_\beta)[v]=0 \), que a su vez equivale a que \( N(t_\alpha)\neq 0 \) o \( N(t_\beta)[v]=0 \), que a su vez equivale a que, o bien no \( \vDash \alpha[v] \), o bien \( \vDash \beta[v] \).

  • Claramente \( \vDash (\alpha\leftrightarrow \beta)[v] \) si y sólo \( \alpha \) y \( \beta \) son equivalentes, en el sentido de que se cumple \( \vDash \alpha[v] \) si y sólo si se cumple \( \vDash \beta[v] \).

Vamos a probar que estos conectores se comportan exactamente como requiere el cálculo proposicional. De momento hemos probado que su significado es el correcto, pero necesitamos probar que sus propiedades son demostrables en ARP, lo cual nos pone en la curiosa situación de que vamos a demostrar los resultados lógicos básicos a partir de la aritmética básica. Antes, no obstante, probaremos algunos resultados sencillos que no podríamos enunciar sin los conectores:

Los axiomas de Peano Las fórmulas siguientes se conocen habitualmente como axiomas de Peano. Las últimas ya las conocíamos, pues no son más que las definiciones de la suma y del producto:

Teorema (Axiomas de Peano) Se cumple:
  • \( Sx\neq 0 \),
  • \( Sx = Sy\rightarrow x = y \),
  • \( x+0=x \),
  • \( x+Sy = S(x+y) \),
  • \( x\cdot 0= 0 \),
  • \( x\cdot Sy = x\cdot y+x \).

Demostración
La fórmula \( Sx\neq 0 \) es \( 1\dot{-} |Sx-0| = 0 \), pero

\( |Sx- 0| = (Sx\dot{-} 0)+(0\dot{-} Sx)=Sx, \)

luego tenemos que probar \( 1\dot{-} Sx = 0 \) y, por las propiedades 2 y 4 de la resta truncada,  es \( S0\dot{-} Sx = 0\dot{-} x  = 0 \).

La segunda fórmula es \( (1\dot{-} |Sx-Sy|)|x-y|=0 \), pero, usando de nuevo la propiedad 2 de la resta truncada, equivale a \( (1\dot{-} |x-y|)|x-y|=0 \), lo cual se sigue de la propiedad 9.
[cerrar]

La regla de inducción Hay un último axioma de Peano que no es sino el principio de inducción usual. Éste no puede ser expresado mediante una fórmula de \( \mathcal L_{\rm arp} \), pero sí como una regla de inferencia:

\( (I)\ \begin{array}{ccc}
\alpha(0)&&\alpha(x)\rightarrow \alpha(Sx)\\
\hline
&\alpha(x)
\end{array}.
 \)

Demostración
Pongamos que \( \alpha(x)\equiv s(x)=t(x) \) y consideremos el funtor dado por \( f(x)=t_\alpha\equiv |s(x)-t(x)| \). Claramente, basta probar la validez de la regla

\( \begin{array}{ccc}
f(0)=0&&(1\dot{-} f(x))\cdot f(Sx)=0\\
\hline
&f(x)=0
\end{array}.
 \)
Para ello consideramos el funtor dado por las ecuaciones

\( g(0)=1,\qquad g(Sx)=g(x)(1\dot{-} f(x)). \)

Notemos que la función \( F(g)(n) \) toma el valor \( 1 \) mientras \( F(f)(n) \) valga \( 0 \), y pasa a valer \( 0 \) a partir del primer natural en el que \( F(f)(n) \neq  0 \). Por lo tanto, hay que probar de \( g(x)=1 \).

Usando la propiedad 10 de la resta truncada:

\( g(SSx)=g(Sx)(1\dot{-} f(Sx))=g(x)(1\dot{-}  f(x))(1\dot{-}  f(Sx)) \)

\( =g(x)((1\dot{-}  f(x))\dot{-} ((1\dot{-} f(x))f(Sx)))=g(Sx), \)

donde hemos usado la premisa \( (1\dot{-} f(x))f(Sx)=0 \). Por \( I_1 \) aplicada al término \( g(Sx) \) concluimos que \( g(Sx)=g(S0)=g(0)(1\dot{-} f(0))=1 \), donde hemos usado la premisa \( f(0)=0 \).

Explícitamente, tenemos que \( g(Sx)=g(x)(1\dot{-} f(x))=1 \), luego, multiplicando por \( f(x) \), queda

\( f(x)=g(x)(1\dot{-} f(x))f(x)=0, \)

donde hemos usado que \( x(1\dot{-} x)=0 \).
[cerrar]

Por supuesto, nadie debería pensar en la demostración anterior como un argumento para convencer a alguien de que el principio de inducción es correcto (lo cual es evidente), sino que se trata de la demostración de que el principio de inducción, formulado como regla de inferencia, es válido en ARP, lo cual no era evidente en absoluto.

De momento, poco partido le podemos sacar a esta regla, ya que no es fácil demostrar implicaciones. Por ejemplo, todos los teoremas siguientes son trivialmente verdaderos, pero sus demostraciones no son obvias:

  • \( ((\alpha\rightarrow\beta)\land (\beta\rightarrow\gamma))\rightarrow (\alpha\rightarrow \gamma) \).

    Demostración
    De momento, una estrategia que podemos emplear para probar este tipo de fórmulas con los escasos medios de que disponemos es empezar eliminando las definiciones de los conectores y luego tratar de probar (normalmente por inducción) la fórmula resultante. Por ejemplo, la fórmula 1 es

    \( (1\dot{-} t_{(\alpha\rightarrow \beta)\land (\beta\rightarrow \gamma)})\cdot t_{\alpha\rightarrow \gamma} = 0,
     \)
    pero a su vez tenemos que  \( t_{(\alpha\rightarrow \beta)\land (\beta\rightarrow \gamma)} =  t_{\alpha\rightarrow \beta}+ t_{\beta\rightarrow \gamma} \) y, si vamos sustituyendo las definiciones sucesivamente, llegamos a la fórmula

    \( (1\dot{-}  ((1\dot{-}  t_\alpha)\cdot t_\beta+(1\dot{-}  t_\beta)\cdot t_\gamma))\cdot (1\dot{-}  t_\alpha)\cdot t_\gamma=0.
     \)

    Recíprocamente, si demostramos esta fórmula, realizando las sustituciones de términos que proporcionan las definiciones de los conectores, llegamos a la fórmula 1). Para probar esta fórmula demostraremos, más en general, la fórmula

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

    pues sustituyendo en ella las variables por los términos adecuados se llega a la fórmula que queremos probar. Aplicamos \( I_2 \) a la variable \( x \).

    • Para \( x=0 \) tenemos que probar

      \( (1\dot{-}  (y+(1\dot{-}  y)\cdot z))\cdot  z=0. \)

      Demostraremos esto mediante \( I_2 \) aplicado a la variable \( y \):
      • Para \( y=0 \) tenemos que probar

        \( (1\dot{-}  z)\cdot  z=0, \)

        lo cual es la propiedad 9 de la resta truncada.

      • Para \( Sy \) tenemos que probar

        \( (1\dot{-}  (Sy+(1\dot{-}  Sy)\cdot z))\cdot  z=0, \)

        pero el miembro izquierdo es \( (1\dot{-}  Sy)\cdot  z=0\cdot z = 0 \).

    • Para \( Sx \) tenemos que probar

      \( (1\dot{-}  ((1\dot{-}  Sx)\cdot y+(1\dot{-}  y)\cdot z))\cdot (1\dot{-}  Sx)\cdot z=0, \)

      lo cual se cumple porque \( 1\dot{-}  Sx =0 \).
    [cerrar]
  • \( \lnot\lnot\alpha\rightarrow \alpha, \qquad \alpha\rightarrow \lnot\lnot\alpha \).

    Demostración
    Sustituyendo \( t_\alpha \) por una variable arbitraria, tenemos que probar las fórmulas

    \( (1\dot{-}  (1\dot{-}  (1\dot{-}  x)))\cdot x=0,\qquad (1\dot{-}  x)\cdot(1\dot{-} (1\dot{-}  x)))=0. \)

    Las dos se prueban trivialmente mediante \( I_2 \).
    [cerrar]

  • \( ((\alpha\rightarrow \beta)\land\lnot\beta)\rightarrow \lnot\alpha \).

    Demostración
    Basta probar la fórmula

    \( (1\dot{-}  ((1\dot{-}  x)\cdot y+(1\dot{-}  y)))\cdot (1\dot{-}  x)=0. \)

    Es inmediato que al sustituir \( x \) por \( Sx \) en el miembro izquierdo queda \( 0 \), luego, por \( I_2 \), basta probar que

    \( 1\dot{-}  (y+(1\dot{-}  y))=0, \)

    lo cual se prueba trivialmente mediante \( I_2 \).
    [cerrar]
  • \( \alpha\land\lnot\alpha\rightarrow \beta \).

    Demostración
    Basta probar la fórmula

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

    pero el primer factor es nulo, como ya hemos señalado en el punto precedente.
    [cerrar]
  • \( \alpha\lor\lnot\alpha \).

    Demostración
    Es consecuencia de la igualdad \( x\cdot(1\dot{-}  x)=0 \), que es la propiedad 4 de la resta truncada.
    [cerrar]

  • \( \alpha\rightarrow (\alpha\lor\beta),\qquad \beta\rightarrow (\alpha\lor\beta) \).

    Demostración
    Basta probar \( (1\dot{-}  x)\cdot x\cdot y=0 \), pero esto se cumple porque \( (1\dot{-}  x)\cdot x=0 \).
    [cerrar]
  • \( (\alpha\lor\alpha)\rightarrow \alpha \).

    Demostración
    Basta probar \( (1\dot{-}  (x\cdot x))\cdot x=0 \), lo cual se obtiene fácilmente mediante la regla \( I_2 \).
    [cerrar]
  • \( ((\alpha\rightarrow \gamma)\land (\beta\rightarrow \gamma))\rightarrow ((\alpha\lor\beta)\rightarrow \gamma) \).

    Demostración
    Basta probar
    \( (1\dot{-}  ((1\dot{-}  x)\cdot z+(1\dot{-}  y)\cdot z))\cdot(1\dot{-}  xy)\cdot z=0. \)

    Aplicamos \( I_2 \) respecto de la variable \( x \):

    • Para \( x=0 \) tenemos que probar:

      \( (1\dot{-}  (z+(1\dot{-}  y)\cdot z))\cdot z=0. \)

      Aplicamos para ello \( I_2 \) respecto de la variable \( y \):

      • Para \( y=0 \) tenemos que probar:

        \( (1\dot{-}  (z+z))\cdot z=0. \)

        Aplicamos \( I_2 \) respecto de la variable \( z \):

        • Es inmediato que el miembro izquierdo vale \( 0 \) en \( z=0 \).

        • Para \( Sz \) queda:

          \( (1\dot{-}  (Sz+Sz))\cdot Sz=0, \)

          lo cual se cumple porque \( Sz+Sz=S(Sz+z) \).

      • Para \( Sy \) queda:

        \( (1\dot{-}  z)\cdot z=0 \),

        y esto ya lo tenemos demostrado.

    • Para \( Sx \) queda:

      \( (1\dot{-}  (1\dot{-}  y)\cdot z)\cdot(1\dot{-}  (Sx)\cdot y)\cdot z=0. \)

      Lo probamos mediante \( I_2 \) respecto de la variable \( y \):

      • Para \( y=0 \) la ecuación se reduce a \( (1\dot{-}  z)\cdot z=0 \).
      • Para \( Sy \) queda:

        \( (1\dot{-}  (Sx)\cdot Sy)\cdot z=0, \)

        y esto se cumple porque \( (Sx)\cdot(Sy)=(x+1)\cdot(y+1)=S(xy+x+y) \).
    [cerrar]
  • \( (\alpha\land\beta)\rightarrow \alpha,\qquad (\alpha\land\beta)\rightarrow \beta \).

    Demostración
    Basta probar \( (1\dot{-}  (x+y))\cdot x=0 \), lo cual se obtiene inmediatamente mediante \( I_2 \).
    [cerrar]
  • \( \lnot(\alpha\land\lnot\alpha) \).

    Demostración
    Basta probar \( 1\dot{-} (x+(1\dot{-}  x))=0 \), pero ésta se obtiene inmediatamente con \( I_2 \).
    [cerrar]
  • \( ((\alpha\land\beta)\rightarrow\gamma)\rightarrow (\alpha\rightarrow (\beta\rightarrow\gamma)) \).

    Demostración
    Basta probar

    \( (1\dot{-}  ((1\dot{-}  (x+y))\cdot z))\cdot (1-x)\cdot (1-y)\cdot z=0. \)

    Vamos a aplicar la regla \( I_2 \). Es claro que al sustituir \( x \) por \( Sx \) el miembro izquierdo da \( 0 \), luego basta probar:

    \( (1\dot{-}  ((1\dot{-}  y)\cdot z))\cdot (1-y)\cdot z=0. \)

    Probamos esto mediante \( I_2 \), y de nuevo es claro que el miembro izquierdo vale \( 0 \) si cambiamos \( y \) por \( Sy \), y en \( y=0 \) se reduce a \( (1\dot{-}  z)\cdot z=0 \).
    [cerrar]

El teorema siguiente es también obviamente verdadero (no es sino una reformulación de la regla \( S_2 \)), pero su prueba es aún menos trivial que las anteriores:

Teorema \( x=y\rightarrow s(x)=s(y). \)

Demostración
De la regla \( I_2 \) (respecto de \( z \)) se sigue inmediatamente la fórmula

\( (1\dot{-} z)s(y+z)=(1\dot{-}  z)s(y). \)

En particular

\( (1\dot{-} (x\dot{-}  y))s(y+(x\dot{-}  y))=(1\dot{-}  (x\dot{-}  y))s(y). \)

Multiplicamos ambos miembros por \( 1\dot{-}  |x-y| \):

\( (1\dot{-}  |x-y|)(1\dot{-}  (x\dot{-}  y))s(y+(x\dot{-}  y))=(1\dot{-}  |x-y|)(1\dot{-}  (x\dot{-}  y))s(y). \)

Ahora observamos que

\( (1\dot{-} |x-y|)(1\dot{-}  (x\dot{-}  y))=1\dot{-}  |x-y|. \)

En efecto, por la propiedad 10 de la resta truncada:

\( (1\dot{-}  |x-y|)(1\dot{-}  (x\dot{-}  y))=(1\dot{-}  |x-y|)\dot{-}  (1\dot{-}  |x-y|)(x\dot{-}  y). \)

La fórmula \( (1\dot{-}  w)w=0 \) nos da \( (1\dot{-}  |x-y|)|x-y|=0 \), y por la definición del valor absoluto:

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

pero la propiedad 5, es decir, \( (x+y)\dot{-}  y = x \), implica que si una suma es \( 0 \), el primer sumando es \( 0 \), luego

\( (1\dot{-} |x-y|)(x\dot{-}  y)=0, \)

lo que prueba la fórmula que he puesto en azul (pues el trozo que le sobra a la fórmula que le sigue vale \( 0 \)), y a su vez esto reduce la fórmula anterior a la fórmula azul hasta

\( (1\dot{-}  |x-y|)s(y+(x\dot{-}  y))=(1\dot{-}  |x-y|)s(y). \)

Por simetría, también podemos demostrar

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

y el teorema previo a la definición del valor absoluto nos da que ambos miembros izquierdos son iguales, luego

\( (1\dot{-}  |x-y|)s(x)=(1\dot{-}  |x-y|)s(y). \)

Por consiguiente:

\( |(1\dot{-}  |x-y|)s(x)-(1\dot{-}  |x-y|)s(y)|=0, \)

Pero la propiedad 4 del valor absoluto nos da ahora que

\( (1\dot{-}  |x-y|)|s(x)-s(y)|=0, \)

y esto es, por definición, \( x=y\rightarrow s(x)=s(y) \).
[cerrar]

Los teoremas precedentes muestran que es mucho más fácil convencerse de que una fórmula de ARP es verdadera que demostrarla en ARP. Nuestro propósito es dotarnos de las herramientas suficientes para que esto deje de ser así. En el mensaje siguiente completaremos esta tarea, pero de momento obtenemos algunas consecuencias importantes del esfuerzo que hemos hecho:

Reglas de inferencia lógicas En primer lugar probamos en ARP la validez de algunas reglas de inferencia del cálculo proposicional (Modus ponens, Silogismo hipotético, Modus tollens, Introducción y Eliminación del conjuntor, Introducción del disyuntor y Dilema):

\( {\rm (MP)}\ \begin{array}{ccc}
\alpha&&\alpha\rightarrow\beta\\
\hline
&\beta
\end{array},\qquad {\rm (SH)}\ \begin{array}{ccc}
\alpha\rightarrow \beta&&\beta\rightarrow \gamma\\
\hline
&\alpha\rightarrow \gamma
\end{array},\ \
{\rm (MT)}\ \begin{array}{ccc}
\alpha\rightarrow \beta&&\lnot\beta\\
\hline
&\lnot\alpha
\end{array}, \)

\( {\rm (IC)}\ \begin{array}{ccc}
\alpha&&\beta\\
\hline
&\alpha\land \beta
\end{array},\qquad {\rm (EC)}\ \begin{array}{c}
\alpha\land\beta\\
\hline
\alpha
\end{array},\qquad \begin{array}{c}
\alpha\land\beta\\
\hline
\beta
\end{array}, \)

\( {\rm (ID)}\ \begin{array}{c}
\alpha\\
\hline
\alpha\lor\beta
\end{array},\qquad \begin{array}{c}
\beta\\
\hline
\alpha\lor \beta
\end{array},\qquad {\rm (Dil)}\ \begin{array}{ccc}
\alpha\rightarrow \gamma&&\beta\rightarrow \gamma\\
\hline
&\alpha\lor\beta\rightarrow \gamma
\end{array}. \)


Para probar la validez del modus ponens observamos que, por las reglas de inferencia enunciadas al principio de este mensaje, de las premisas se deduce \( t_\alpha = 0 \) y \( (1\dot{-} t_\alpha)\cdot t_\beta = 0 \), pero entonces

\( t_\beta =  1\cdot t_\beta = (1\dot{-}  0)\cdot t_\beta = (1\dot{-}  t_\alpha)\cdot t_\beta = 0, \)

luego, de nuevo por las reglas de inferencia iniciales, concluimos \( \beta \).

Ahora probamos la regla de introducción del conjuntor: si suponemos \( \alpha, \beta \), tenemos \( t_\alpha = 0 \) y \( t_\beta = 0 \), luego también \( t_\alpha+t_\beta = 0 \), y esto es \( \alpha\land \beta \).

Las reglas restantes se obtienen fácilmente de éstas dos y de las propiedades de los conectores que hemos demostrado.