[Carlos Ivorra]

En este mensaje presentamos algunas reflexiones sobre el concepto de deducción lógica, para lo cual pondremos un ejemplo que nos sirva de referencia. Vamos a demostrar que, para cualquier fórmula \( \alpha \) se cumple

\( \vdash \alpha\rightarrow \alpha \).

Una deducción posible es la siguiente:

\( \begin{array}{lll}
(1)&(\alpha\rightarrow((\alpha\rightarrow\alpha)\rightarrow\alpha))\rightarrow
((\alpha\rightarrow(\alpha\rightarrow\alpha))\rightarrow(\alpha\rightarrow\alpha))
&\mbox{(K2)}\\
(2)&\alpha\rightarrow((\alpha\rightarrow\alpha)\rightarrow\alpha)&\mbox{(Axioma K1)}\\
(3)&(\alpha\rightarrow(\alpha\rightarrow\alpha))
\rightarrow(\alpha\rightarrow\alpha)&\mbox{(MP 1,2)}\\
(4)&\alpha\rightarrow(\alpha\rightarrow\alpha)&\mbox{(Axioma K1)}\\
(5)&\alpha\rightarrow\alpha&\mbox{(MP 3,4)}
\end{array} \)

Lo primero que observa cualquiera a la vista de esto es que la prueba es horripilante. A nadie se le habría ocurrido recurrir a un "argumento" así para probar que  \( \alpha\rightarrow \alpha \).

Si tratamos de precisar esta primera impresión tratando de expresarla de forma más objetiva, lo que podemos decir es que la conclusión es mucho más evidente que los axiomas que presuntamente la demuestran. Más concretamente, lo que a uno le convence de que \( \alpha\rightarrow \alpha \) "es verdad" (más técnicamente, que es una fórmula lógicamente válida, verdadera en todo modelo) es considerar esta modesta tabla de verdad:

\( \begin{array}{c|c}
\alpha&\alpha\rightarrow \alpha\\
\hline
V&V\\
F&V
\end{array} \)

En cambio, para probar que el primer axioma de la prueba es lógicamente válido, y por lo tanto un axioma legítimo, hay que construir esta tabla de verdad:

\( \begin{array}{c|c|c|c|c|c|c}
\alpha&\alpha\rightarrow\alpha&(\alpha\rightarrow\alpha)\rightarrow\alpha&(\alpha\rightarrow((\alpha\rightarrow\alpha)\rightarrow\alpha))&\alpha\rightarrow(\alpha\rightarrow\alpha)&((\alpha\rightarrow(\alpha\rightarrow\alpha))\rightarrow(\alpha\rightarrow\alpha))&\alpha\rightarrow((\alpha\rightarrow\alpha)\rightarrow\alpha))\rightarrow
((\alpha\rightarrow(\alpha\rightarrow\alpha))\rightarrow(\alpha\rightarrow\alpha))\\
\hline
V&V&V&V&V&V&V\\
F&V&F&V&V&V&V
\end{array} \)

En este sentido podemos decir objetivamente que los axiomas de esta deducción son mucho más complicados que la conclusión. Y la idea que inevitablemente debería venirnos a la mente es si no estaremos haciendo el ridículo con \( K_{\mathcal L} \). La respuesta es negativa, pero conviene entender por qué.

Una axiomática "tradicional" (por ejemplo una axiomática para la geometría euclídea) pretende reducir lógicamente afirmaciones complejas a otras lo más simples posibles que se toman como axiomas. De este modo, una deducción a partir de unos axiomas resulta explicativa. Por ejemplo, si demostramos el teorema de Pitágoras a partir de los axiomas de la geometría euclídea estamos reduciendo una afirmación que no puede tenerse por evidente (nadie puede ver un triángulo rectángulo y decir "se ve claramente que el cuadrado de la hipotenusa es igual a ...") a otras que sí lo son (como "por dos puntos pasa una única recta", etc.) Cuando decimos que los axiomas de la geometría euclídea son intuitivamente evidentes queremos decir que cualquiera que los examine se da cuenta de que se corresponden con hechos intuitivamente verdaderos y que, por consiguiente, todas sus consecuencias serán intuitivamente verdaderas (aunque no sean intuitivamente evidentes).

De todos modos, el carácter intuitivo de los axiomas de la geometría euclídea es aquí secundario. Lo que importa es que (normalmente) los axiomas de una teoría axiomática se toman lo más simples posibles para que alguien que los vea pueda formarse una idea clara de lo que supone admitirlos como tales axiomas. Ya que los axiomas no se pueden demostrar, se procura al menos que se puedan juzgar fácilmente y sea igualmente fácil determinar bajo qué condiciones podemos esperar que se cumplan.

En cambio, los criterios para definir \( K_{\mathcal L} \) se han fijado siguiendo unos criterios que no tienen nada que ver con éstos. No hay necesidad de tomar axiomas simples porque los axiomas SÍ se demuestran (ya hemos demostrado que son lógicamente válidos), es decir, nadie necesita sopesarlos para decidir si "se los cree" o "no se los cree". (A lo sumo uno tendrá que decidir si quiere razonar como todo el mundo —clásicamente— o si quiere adherirse a alguna secta de razonamiento, pero si opta por lo primero puede razonar que los axiomas elegidos son lógicamente válidos, y eso los hace automáticamente aceptables como axiomas). Por ello, en lugar de la simplicidad, lo que se ha buscado en ellos es la potencia: que contengan la máxima información en el mínimo esfuerzo.

Podríamos haber elegido otra colección de axiomas para \( K_{\mathcal L} \) que fueran mucho más simples y "naturales", como \( \alpha\rightarrow \alpha\lor \beta \), \( \alpha\land \beta\rightarrow \alpha \), etc., pero el precio sería que en lugar de bastarnos con seis esquemas de axioma habríamos necesitado unas dos docenas de ellos, más o menos. ¿Merece la pena comprimir el número de axiomas necesarios (de esquemas de axioma, en realidad) a costa de hacerlos "poco naturales"? La respuesta es afirmativa. Como ya hemos comentado, la naturalidad es poco importante, pues al fin y al cabo podemos demostrar que son lógicamente válidos, y eso los legitima como axiomas, y como contrapartida hay varios resultados de la lógica matemática (del tipo "si se puede demostrar tal cosa también se puede demostrar tal otra cosa") que requieren razonar sobre los esquemas de axioma de \( K_{\mathcal L} \) uno por uno, y entonces es muy de agradecer que esa parte de la prueba pueda despacharse distinguiendo sólo seis casos en lugar de veintiocho.

Con este criterio para elegir los axiomas no podemos ver las deducciones en \( K_{\mathcal L} \) como explicativas, es decir, la prueba anterior no es una explicación de por qué es cierto (es lógicamente válido) que \( \alpha\rightarrow\alpha \), sino que es una deducción a partir de axiomas lógicamente válidos (pero no obviamente lógicamente válidos) de una conclusión obviamente lógicamente válida. ¿Qué aporta entonces? De la deducción anterior podemos aprender algo interesante y no trivial, que no es que alfa implica alfa (eso es trivial y, por eso mismo, de interés dudoso) sino que alfa implica alfa es deducible en \( K_{\mathcal L} \). Prueba de que esto no es trivial es que a pocos se les habría ocurrido cómo hacer la deducción. Y este hecho no trivial es sólo el primer paso en la prueba de otro hecho menos trivial aún, y es que todas las fórmulas lógicamente válidas son deducibles en \( K_{\mathcal L} \).

Hemos presentado un conjunto extraño (pero comprimido) de axiomas, y queremos demostrar que esos "bichos raros" que hemos tomado como axiomas de entre todas las fórmulas lógicamente válidas son suficientes para deducir de ellas todas las demás.

Pero esto no significa que todas las deducciones en \( K_{\mathcal L} \) vayan a ser "monstruos" como el ejemplo anterior. Por el contrario, un uso "sensato" de \( K_{\mathcal L} \) pasa por dos fases:

1) En una primera fase, lo que procede es "desembalar" la lógica que está ingeniosamente "embalada" en los axiomas de \( K_{\mathcal L} \). Es como si alguien hubiera logrado embalar una mesa desmontada en piezas en un espacio tan pequeño y tan bien aprovechado que no deja un hueco libre y parece mentira que toda una mesa de ese tamaño quepa en una caja tan diminuta. Lo primero que procede hacer es abrir la caja, sacar las piezas y ensamblarlas para tener la mesa lista para ser usada (aunque luego nadie sabría volver a meterla en la caja sin dejar cuarenta piezas fuera). En la práctica, esto significa demostrar las dos docenas (o más) de resultados que habríamos tomado como axiomas o reglas de inferencia de \( K_{\mathcal L} \) si no nos hubiera obsesionado reducir los axiomas a la mínima expresión. Tales demostraciones serán tremendamente "monstruosas" o, si se prefiere, tremendamente ingeniosas, pues son parte de la demostración de un teorema nada trivial, el que dice "toda la lógica cabe en esta reducidísima caja".

2) En segundo lugar, una vez demostrados esos resultados básicos que bien podrían haberse tomado como axiomas y reglas de inferencia de un sistema deductivo formal, lo que procede es olvidarse de los axiomas de \( K_{\mathcal L} \) y de todas las demostraciones monstruosas, y no usarlos nunca más salvo para propósitos teóricos (es como tirar el embalaje de la mesa), y a partir de ese momento realizar las deducciones prácticas en \( K_{\mathcal L} \) apoyándonos, no en los axiomas, sino en los resultados básicos deducidos de ellos que habrían sido axiomas si hubiéramos apostado por la naturalidad en vez de por la compacidad.

Insisto en esto porque no es raro encontrar libros y profesores de lógica que presentan sistemas deductivos formales como \( K_{\mathcal L} \) y no sólo no se molestan en "desembalar la lógica", como aquí haremos, sino que plantean ejercicios a sus lectores / alumnos en los que tratan de entrenarlos para hacer deducciones "monstruosas" del tipo necesario en la fase 1), como si eso fuera "lo normal" en \( K_{\mathcal L} \), y el efecto es que el lector / alumno se forma la imagen distorsionada de que razonar en lógica es algo que poco tiene que ver con razonar en matemáticas, porque en matemáticas uno hace cosas "naturales": si quiero probar que \( x\in A\rightarrow x\in B \), supongo que \( x\in A \) y argumento que tiene que estar en \( B \), mientras que demostrar esto mismo "en lógica" es buscar la combinación adecuada de axiomas esotéricos que, debida e ingeniosamente combinados, añadiendo un poco de MP, otro poco de IG y un algo de "vendo mi alma y salvación a Satán a cambio del don de la lógica formal", lleven a la implicación deseada.

Es como si un profesor de análisis, en lugar de reservar la definición de derivada para probar las reglas de derivación y otros resultados teóricos y enseñar a sus alumnos a usar las reglas de derivación para calcular derivadas en la práctica, ocultara a sus alumnos que existen las reglas de derivación (o las presentara aisladamente en ejercicios sin darles importancia) y exigiera a sus alumnos que calcularan cualquier derivada "normal" aplicando la definición de derivada cada vez.

Aquí trataremos de distinguir cuidadosamente la fase 1) de la fase 2), es decir, primero demostraremos (mediante pruebas "diabólicas") que en \( K_{\mathcal L} \) pueden probarse los principios elementales de argumentación que los matemáticos utilizan de forma natural sin pretender deducirlos de nada más elemental, y después mostraremos que, contando con tales principios elementales trabajar en \( K_{\mathcal L} \) es hacer exactamente lo mismo que hace un matemático que jamás haya oído hablar de \( K_{\mathcal L} \).

Es en los razonamientos de la fase 2) en los que un profesor de lógica debería ejercitar a sus alumnos (reservando los axiomas de \( K_{\mathcal L} \) para los razonamientos teóricos, como hacen los analistas con la definición de derivada), y son esos razonamientos los que los alumnos deben considerar como "típicos". Los razonamientos de la fase 1) son simplemente parte de la prueba de un teorema no trivial, y es que bastan los axiomas de  \( K_{\mathcal L} \) para fundamentar los principios en los que se apoyan los razonamientos de la fase 2. Es bueno que los alumnos conozcan la demostración de ese teorema, pero eso es una cosa, y otra muy distinta es tomar las técnicas ingeniosas que requiere la demostración del teorema y usarlas "cotidianamente", cuando es tonto usar tales técnicas para otra cosa que no sea demostrar ese teorema.

[Carlos Ivorra]

Vamos a presentar y analizar brevemente un ejemplo de deducción "natural" en \( K_{\mathcal L} \), no de las correspondientes a lo que hemos llamado "fase 1", sino de las correspondientes a la "fase 2". Como aún no hemos desarrollado la "fase 1" no estamos en condiciones de justificar que lo que vamos a escribir es realmente una deducción en \( K_{\mathcal L} \) (mejor dicho, es evidente que NO es una deducción en \( K_{\mathcal L} \), pero más adelante será también evidente que se puede desarrollar hasta una deducción en \( K_{\mathcal L} \)).

Consideramos el lenguaje de la aritmética, que ya hemos tratado otras veces, introducimos la abreviatura siguiente (que leeremos "x divide a y"):

\( x\mid y\equiv \exists u\ y=xz \).

y vamos a probar lo siguiente:

\( \forall xyz((xy)z=x(yz))\vdash \forall xyz(x\mid y\land y\mid z\rightarrow x\mid z) \).

Expresamos la deducción en tres columnas. A la izquierda ponemos lo que diría un matemático, en el centro la deducción propiamente dicha y a la derecha las indicaciones que bastan para justificar que la deducción es correcta (supuesto que hubiéramos desarrollado ya la fase 1) sin necesidad de la columna de la izquierda:

Como decíamos, las dos primeras columnas constituyen lo que un matemático reconocería como una demostración válida (muy detallada) de la conclusión a partir de la premisa. Aunque parece que sus explicaciones son suficientes para justificar la validez del razonamiento, lo cierto es que hay una serie de reglas que el matemático respeta implícitamente, incluso subconscientemente, y que, aunque no estén indicadas de forma explícita, son indispensables para que la prueba sea correcta.

Por ejemplo, el matemático distingue entre las variables \( x, y, z \), que en la línea (2) usa para referirse a tres números arbitrarios, y las variables \( u \) y \( v \), que introduce en (5) y (8) para referirse a dos números particulares. El matemático usa subconscientemente que no puede hacer lo mismo con una variable que represente a un objeto arbitrario que con otra que represente a un objeto particular. Por ejemplo, en la línea (12) escribe \( \exists u \) y jamás habría pensado en escribir \( \forall u \), porque esa \( u \) representa al número particular \( uv \), que es particular porque \( u \) y \( v \) lo eran. En cierto sentido, la posibilidad de escribir \( \forall u \) o sólo \( \exists u \) depende de "la historia" de las variables, y no sólo de la línea (11), a partir de la cual se introduce el cuantificador.

Sin embargo, aunque, según decimos, el hecho de que  \( u \) y \( v \) sean variables particulares prohíbe al matemático ligarlas con un generalizador, el hecho de que \( x, y, z \) sean variables generales no significa que pueda ligarlas en cualquier momento por un generalizador. Por ejemplo, al matemático jamás se le habría pasado por la cabeza escrbir (3)  \( \forall xyz(x\mid y\land y\mid z) \). Él lo razonaría así: \( x, y, z \) son tres números arbitrarios de los que supongo que \( x\mid y\land y\mid z \), pero eso no significa que tres números cualesquiera deban cumplir esto, por lo que sería absurdo introducir ahí un generalizador. Sólo cuando llego a la línea (14) y tengo que si \( x\mid y\land y\mid z \) también se cumple que \( x\mid z \), sólo entonces puedo decir que esto vale para tres números arbitrarios, y eso justifica el paso a (15).

Más en general: cuando queremos probar que todo \( x \) que cumple A también cumple B, puedo tomar un \( x \) genérico que cumpla A, pero dicha generalidad no me permite afirmar que todo x cumple A. Sólo cuando pruebo la implicación \( A\rightarrow B \) es cuando puedo decir que dicha implicación vale para todo \( x \). Puedo generalizar respecto de \( x \) después, pero no antes de llegar a la implicación.

Otro hecho que el matemático tiene en cuenta instintivamente es que, aunque en la línea (7) tiene un \( \exists u \), al eliminar el cuantificador está obligado a sustituir la variable \( u \) por otra variable nueva \( v \), porque ya está usando la variable \( u \) para referirse al número que cumple (5) y no tiene por qué ser el mismo que cumpla (8). En cambio, cuando elimina los cuantificadores de (1) para escribir (10), no le importa que ya esté usando la variable \( x \) ni tampoco tiene inconveniente en sustituir las variables \( y, z \) por las variables \( u, v \) que ya está usando para nombrar otros objetos. La diferencia la marca que los cuantificadores de (1) son universales, por lo que las variables ligadas por ellos pueden sustituirse por cualquier objeto, aunque sea uno del que ya estemos hablando.

En general, podemos decir que el matemático aplica reglas "locales", es decir, reglas que dependen del punto de la demostración en el que estemos: no es lo mismo generalizar antes de haber probado la implicación que después, no es lo mismo quitar un \( \exists u \) si antes ya hemos hablado de una \( u \) que si no, etc. Por el contrario, las reglas de inferencia de \( K_{\mathcal L} \) son globales: dadas una o dos fórmulas, o de ellas se deduce algo o no se deduce, no importa qué otras líneas haya en la deducción. Otro ejemplo de "localidad" es que el matemático tiene claro que, en caso de prolongar la deducción, no podría usar ya que \( x\mid y \), porque esto no es una premisa de la deducción, sino una hipótesis local que ha usado para probar la implicación (15), en caso de seguir usando la línea (3) estaría convirtiendo en premisa de su deducción lo que no era más que una premisa local, y no sería cierto que sus consecuencias fueran realmente consecuencias de la línea (1), que es la única premisa declarada.

Esto podría hacernos sospechar que \( K_{\mathcal L} \) no es suficientemente potente como para formalizar razonamientos como el anterior, puesto que le falta la "sensibilidad al contexto" en la que constante y casi inconscientemente se apoya el matemático. Pese a las apariencias, veremos que no es así. Eso sí, para formalizar este tipo de razonamientos en  \( K_{\mathcal L} \) tendremos que explicitar todos los detalles como los que hemos comentado y que un matemático tiene en cuenta casi sin decirlo explícitamente, pues para que algo sea una auténtica deducción en \( K_{\mathcal L} \) tiene que cumplir una serie de requisitos muy concretos totalmente explícitos, y eso es incompatibles con asumir condiciones tácitas que el "sentido común" dicte en cada momento improvisadamente.

En los próximos mensajes nos dedicaremos a mostrar que (una vez hecho el "trabajo sucio") en \( K_{\mathcal L} \) es posible razonar siempre al estilo de la deducción anterior y que nunca será necesario deprimirse con deducciones como la que consideramos en el mensaje anterior.

[Carlos Ivorra]

El teorema de deducción afirma que (pese a las apariencias) en \( K_{\mathcal L} \) es válida una técnica de razonamiento que usan constantemente los matemáticos. La hemos usado en la deducción que hemos puesto como ejemplo en el mensaje anterior. Allí la única premisa era (1), y queríamos demostrar la implicación \( x\mid y\land y\mid z\rightarrow x\mid z \) que constituye la línea (14). Para ello hemos supuesto la hipótesis (2), contraviniendo la definición de deducción, pues (2) no es una premisa, ni un axioma, ni se deduce de líneas anteriores, y hemos llegado hasta (13).

Lo que dice el teorema de deducción es que esto es correcto, que si suponiendo (2) (aunque no sea una premisa de la deducción) llegamos a (13), podemos afirmar la implicación (14). El enunciado general es el siguiente:

Teorema de deducción Sea \( \mathcal L \) un lenguaje formal y consideremos fórmulas de \( \mathcal L \) tales que \( \alpha_1,\ldots, \alpha_n,\alpha\vdash \beta \). Si es posible deducir \( \beta \) sin aplicar la regla de introducción del generalizador a variables libres en \( \alpha \), entonces \( \alpha_1,\ldots, \alpha_n\vdash \alpha\rightarrow \beta \).

En pocas palabras, lo que dice el teorema de deducción es que para deducir \( \alpha\rightarrow\beta \) a partir de unas premisas, podemos añadir \( \alpha \) como premisa y deducir \( \beta \). Lo que obtendremos así no será una deducción de \( \alpha\rightarrow\beta \) en \( K_{\mathcal L} \), pero la demostración del teorema de deducción muestra cómo a partir de esta deducción es posible obtener una auténtica deducción de \( \alpha\rightarrow\beta \) a partir de las premisas indicadas.

Notemos la restricción (que no puede ser pasada por alto) de que en la deducción de \( \beta \) no puede generalizarse respecto de variables libres en \( \alpha \). Esta limitación puede parecer extraña a un matemático, pero, como explicábamos en el mensaje anterior, en realidad es una limitación que todos los matemáticos se autoimponen inconscientemente cuando se ven en una situación concreta de las descritas por el teorema anterior.

Por ejemplo, en la deducción que poníamos como ejemplo, desde el momento en que suponemos \( x\mid y\land y\mid z \) queda prohibido generalizar respecto de \( x, y, z \), porque al hacerlo estaríamos afirmando que todos los números cumplen \( x\mid y\land y\mid z \) y esto es falso. Desde el momento en que introducimos esta hipótesis, debemos romper nuestro convenio semántico de que una variable libre representa a un objeto arbitrario, y a partir de aquí \( x, y, z \) representan números arbitrarios de entre los que cumplan la hipótesis (y si generalizáramos como si fueran números totalmente arbitrarios estaríamos afirmando que todos los números cumplen la hipótesis, lo cual no tiene por qué ser cierto). Una vez hemos aplicado el teorema de deducción para escribir (14) el teorema nos asegura que esta línea es consecuencia de la premisa (1), y a partir de aquí podemos "olvidarnos" de que hemos usado el teorema de deducción para probarlo (pues ya sabemos que existe una deducción "normal" de (14) a partir de (1), y podemos generalizar para pasar a (15).

Demostración

Por hipótesis existe una deducción \( \gamma_1,\ldots, \gamma_m \) con premisas entre \( \alpha_1,\ldots, \alpha_n,\alpha \) tal que \( \gamma_m\equiv\beta \) y en la que no se generaliza respecto de variables libres en \( \alpha \).

Vamos a construir una deducción con premisas \( \alpha_1,\ldots, \alpha_n \) (pero no \( \alpha \)) que contenga las fórmulas \( \alpha\rightarrow \gamma_1,\ldots, \alpha\rightarrow\gamma_m \) (con otras posibles fórmulas intercaladas). Como la última fórmula es \( \alpha\rightarrow\beta \), con esto tendremos probado que la implicación es consecuencia de las premisas.

Si \( \gamma_i \) es un axioma lógico o una premisa \( \alpha_1,\ldots, \alpha_n \), la forma de incorporar \( \alpha\rightarrow \gamma_i \) a la deducción es la siguiente:

\( \begin{array}{lll}
(1)& \gamma_i&\mbox{Axioma o premisa}\\
(2)&\gamma_i\rightarrow (\alpha\rightarrow \gamma_i)&\mbox{K1}\\
(3)&\alpha\rightarrow \gamma_i&\mbox{MP 1, 2.}
\end{array} \)

Si \( \gamma_i\equiv \alpha \), entonces debemos incorporar a la deducción que estamos construyendo la fórmula \( \alpha\rightarrow\alpha \), y esto es correcto porque ya hemos visto anteriormente cómo deducir esta fórmula en \( K_{\mathcal L} \).

Si \( \gamma_i \) se deduce por MP, entonces hay dos fórmulas anteriores de la forma \( \gamma_j \) y \( \gamma_j\rightarrow \gamma_i \). Puesto que en nuestra deducción vamos incorporando las implicaciones de forma sucesiva, cuando lleguemos a \( \gamma_i \) ya habremos incorporado las fórmulas \( \alpha\rightarrow \gamma_j \) y \( \alpha\rightarrow (\gamma_j\rightarrow \gamma_i) \). Éstas son, pues, líneas anteriores de nuestra deducción y podemos usarlas para deducir \( \alpha\rightarrow \gamma_i \). Lo hacemos de este modo:

\( \begin{array}{lll}
(1)&\alpha\rightarrow \gamma_j&\mbox{fórmula anterior de la deducción}\\
(2)&\alpha\rightarrow(\gamma_j\rightarrow\gamma_i)&\mbox{fórmula anterior de la deducción}\\
(3)&(\alpha\rightarrow(\gamma_j\rightarrow\gamma_i))\rightarrow((\alpha\rightarrow \gamma_j)\rightarrow(\alpha\rightarrow\gamma_i))&\mbox{K2}\\
(4)&(\alpha\rightarrow \gamma_j)\rightarrow(\alpha\rightarrow\gamma_i)&\mbox{MP 2, 3}\\
(5)&\alpha\rightarrow\gamma_i&\mbox{MP 1, 4}
\end{array} \)

Supongamos, por último que \( \gamma_i \) se deduce por generalización de otra fórmula anterior \( \gamma_j \). Esto significa que \( \gamma_i\equiv \forall x\gamma_j \), y por la hipótesis del teorema sabemos que \( x \) no está libre en \( \alpha \).

Entonces incorporamos \( \alpha\rightarrow \forall x\gamma_j \) de este modo:

\( \begin{array}{lll}
(1)&\alpha\rightarrow \gamma_j&\mbox{fórmula anterior de la deducción}\\
(2)&\forall x(\alpha\rightarrow \gamma_j)&\mbox{IG 1}\\
(3)&\forall x(\alpha\rightarrow \gamma_j)\rightarrow (\alpha\rightarrow \forall x\gamma_j)&\mbox{K5 (porque $x$ no está libre en $\alpha$)}\\
(4)&\alpha\rightarrow \forall x\gamma_j&\mbox{MP2, 3}
\end{array}
 \)

Esto completa la prueba.

[cerrar]

De la demostración del teorema de deducción se sigue que en la deducción que se construye de \( \alpha_1,\ldots, \alpha_n\vdash \alpha\rightarrow \beta \) se generaliza exactamente respecto de las mismas variables que en la deducción dada de  \( \alpha_1,\ldots, \alpha_n,\alpha\vdash \beta \).

En la práctica podemos usar el teorema de deducción en una versión ligeramente más general. Imaginemos que estamos construyendo una deducción a partir de unas premisas \( \alpha_1,\ldots, \alpha_n \), digamos \( \gamma_1,\ldots, \gamma_m \), y a continuación queremos deducir una fórmula de tipo \( \alpha\rightarrow \beta \). Entonces escribimos \( \alpha \) y la usamos como una premisa más hasta obtener \( \beta \) (sin generalizar respecto de variables libres en \( \alpha \)). Al llegar a \( \beta \), lo que hemos probado es que \( \gamma_1,\ldots, \gamma_m,\alpha\vdash \beta \) con una deducción en la que no se generalizan variables libres en \( \alpha \), luego el teorema de deducción nos da que \( \gamma_1,\ldots, \gamma_n\vdash \alpha\rightarrow \beta \), es decir, que existe una deducción de \( \alpha\rightarrow \beta \) con premisas en \( \gamma_1,\ldots, \gamma_m \). Pero por otra parte sabemos que \( \gamma_1,\ldots, \gamma_m \) se deducen de \( \alpha_1,\ldots, \alpha_n \), luego también \( \alpha_1,\ldots, \alpha_n\vdash \alpha\rightarrow \beta \). (Para tener una deducción que prueba esto deducimos cada \( \gamma_i \) de las premisas y luego deducimos \( \alpha\rightarrow \beta \) de las \( \gamma_i \)).

En la práctica marcaremos todas las líneas desde que suponemos \( \alpha \) hasta que llegamos a \( \beta \) con una línea vertical (tal y como se ve en el ejemplo del hilo anterior). Esta línea advierte de que las fórmulas abarcadas por ella no son consecuencia de las premisas de la deducción principal, sino de las premisas más una hipótesis auxiliar (la fórmula \( \alpha \)) que sólo hemos aceptado provisionalmente para aplicar el teorema de deducción. Si una vez hemos añadido \( \alpha\rightarrow \beta \) a la deducción la prosiguiéramos haciendo uso de las líneas marcadas, la deducción sería inválida, pues estaríamos haciendo uso de una premisa \( \alpha \) que no forma parte de las premisas de la deducción.

La observación de que para obtener la deducción cuya existencia afirma el teorema de deducción sólo se generaliza respecto de variables generalizadas en la prueba dada es esencial para que estemos seguros de que no estamos generalizando en un momento dado respecto de una variable "prohibida". El uso del teorema de deducción oculta el uso de algunos axiomas y reglas de inferencia (las que aparecen en la demostración al construir la deducción de \( \alpha\rightarrow \beta \)), pero no oculta ningún uso de IG.

Ejemplo Hemos explicado que la restricción sobre el uso de IG en el teorema de deducción es "razonable", pero ahora vamos a demostrar que es necesaria. Para ello veamos un ejemplo de falsa deducción en la que se usa el teorema de deducción sin respetar la restricción sobre el uso de IG. Concretamente, en la línea (2) generalizamos respecto de una variable libre en la hipótesis:



La línea (7) es deducible en \( K_{\mathcal L} \) (sin premisas), aunque posponemos la prueba hasta más adelante (cuando "desenlatemos" la lógica del igualador). Aceptando este hecho, podemos incorporarla en nuestra deducción.

Si el teorema de deducción fuera válido sin la restricción sobre el uso de IG, la deducción anterior sería correcta y podríamos concluir que \( \vdash \forall xy\ x=y \), luego, por el teorema de corrección, \( \vDash \forall xy\ x=y \), pero esta fórmula no es lógicamente válida. Al contrario, es falsa en todos los modelos del lenguaje formal considerado cuyo universo tenga más de un objeto. Esta contradicción prueba que la hipótesis sobre IG es necesaria en el teorema de deducción.

Observemos que el teorema de deducción tiene un recíproco trivial:

Recíproco del teorema de deducción: Si \( \alpha_1,\ldots, \alpha_n\vdash\alpha\rightarrow\beta \) entonces \( \alpha_1,\ldots, \alpha_n,\alpha\vdash \beta \).

En efecto, para deducir \( \beta \) deducimos primero \( \alpha\rightarrow \beta \) y luego aplicamos MP.

Aclaración

Aunque en realidad es una obviedad, tal vez no esté de más recalcar que el teorema de deducción es un teorema sobre \( K_{\mathcal L} \), no una modificación o rectificación de \( K_{\mathcal L} \), es decir, en ningún momento hemos dicho "aunque en la definición de \( K_{\mathcal L} \) no está contemplado hacer esto, a partir de ahora admitiremos que para probar \( \alpha\rightarrow \beta \) podremos suponer \( \alpha \) y demostrar \( \beta \). En absoluto. Lo que dice el teorema de deducción es que, si hacemos esto (respetando la restricción sobre IG) la deducción que obtenemos NO es una deducción en \( K_{\mathcal L} \) de \( \alpha\rightarrow \beta \), pero a partir de dicha deducción podemos obtener mecánicamente una deducción de \( \alpha\rightarrow \beta \) que respeta exactamente la definición de deducción en \( K_{\mathcal L} \), sin ningún retoque.

Esto significa que cuando estemos analizando una deducción arbitraria en un contexto teórico no tendremos que preocuparnos por la posibilidad de que en ella se use el teorema de deducción. Si así fuera, siempre podríamos reemplazarla por otra deducción en la que no se use. Por lo tanto, siempre podremos suponer que toda fórmula que aparezca en la deducción es una premisa, un axioma lógico o una consecuencia de las líneas anteriores por MP o IG, tal y como estipula la definición de deducción en \( K_{\mathcal L} \). El uso del teorema de deducción no es un caso más a considerar en un contexto teórico.

[cerrar]

[Carlos Ivorra]

Llamaremos reglas de inferencia derivadas a cualquier resultado de la forma

\( \alpha_1,\ldots, \alpha_n\vdash \alpha \)

y las llamamos así porque una vez hemos comprobado que esto es cierto (es decir, hemos encontrado una deducción de \( \alpha \) a partir de las premisas correspondientes) podemos usarlas en las deducciones como reglas de inferencia en pie de igualdad con las dos reglas primitivas MP e IG. En efecto, si en una deducción hemos escrito ya (entre otras) las líneas \( \alpha_1,\ldots, \alpha_n \), podemos escribir \( \alpha \) en cualquier momento que nos interese, aunque no se deduzca ni por MP ni por IG. Con esto nuestra deducción tendrá un "agujero", pero sabemos que ese agujero se puede "llenar" intercalando las líneas de la deducción de \( \alpha \) a partir de \( \alpha_1,\ldots, \alpha_n \) que ya conocemos.

Por ejemplo, en la deducción sobre divisibilidad de números naturales que vimos dos mensajes atrás, para pasar de la línea (2) a la (3) usamos la regla de inferencia derivada de eliminación del conjuntor, que en realidad son dos reglas de inferencia a las que no merece la pena dar nombres distintos:

\( \alpha\land \beta\vdash \alpha \)    y    \( \alpha\land\beta\vdash\beta \).

Para que la deducción indicada estuviera completa haría falta (entre otras cosas) insertar la deducción en \( K_{\mathcal L} \) de \( x\mid y \) a partir de \( x\mid y\land y\mid z \), pero si demostramos que las reglas anteriores valen en general para todas las fórmulas \( \alpha \) y \( \beta \) podemos omitir las líneas necesarias para ello en nuestras deducciones con la garantía de que si quisiéramos una deducción completa, sin que falte una sola línea, sabríamos cómo añadir lo que hemos omitido.

Esto es lo que hacen los matemáticos cada vez que citan un teorema ya demostrado. Una demostración que en un momento dado diga "por el teorema del valor medio podemos afirmar que..." está incompleta, y sólo estaría completa si antes de decir "por el teorema del valor medio" insertáramos una demostración del teorema del valor medio, pero no ganaríamos nada con ello, al contrario, sólo volveríamos ilegibles todas las demostraciones.

El teorema de completitud semántica (que todavía no hemos demostrado) garantizará que para toda regla de inferencia semática \( \alpha_1,\ldots, \alpha_n\vDash\alpha \), es decir, que siempre que el hecho de que \( \alpha_1,\ldots, \alpha_n \) sean verdaderas en un modelo es necesario (no necesario según ciertos convenios arbitrarios prefijados, sino necesario a secas) que \( \alpha \) sea verdadera, entonces \( \alpha_1,\ldots, \alpha_n\vdash \alpha \), es decir, existe una deducción de \( \alpha \) a partir de los axiomas lógicos que hemos seleccionado en principio arbitrariamente y de las dos reglas de inferencia que hemos elegido en principio arbitrariamente.

Como aún no estamos en condiciones de probar esto, no podemos justificar una regla de inferencia constatando simplemente que es semánticamente válida, pues eso no nos garantiza que sea deducible en \( K_{\mathcal L} \) y a menudo sucederá que la validez semántica es inmediata, mientras que la validez sintáctica, es decir, la existencia de una deducción, requiera utilizar los escasos recursos que proporciona \( K_{\mathcal L} \) de forma retorcida y antinatural. Ya hemos explicado cómo debe entenderse esto y no entraremos aquí de nuevo en ello.

Una regla de inferencia muy tonta pero, pese a ello, muy útil, es la regla de repetición (R):

\( \alpha\vdash \alpha \)

Es útil porque a menudo conviene cambiar el nombre con el que nos estamos refiriendo a una misma fórmula. Así lo hemos hecho, por ejemplo en la prueba sobre divisibilidad al pasar de la línea (3) a la (4) que son la misma fórmula, pues (3) es por definición una abreviatura taquigráfica de (4).

Nota

Una peculiaridad de la regla de repetición es que el hecho de que \( \alpha\vdash \alpha \) se justifica sin más que observar que \( \alpha \) es ya de por sí una deducción de \( \alpha \) a partir de \( \alpha \), pero lo cierto es que este argumento no justifica la repetición de \( \alpha \) en una deducción, pues \( \alpha \) no se deduce de \( \alpha \) ni por MP ni por IP.

Una forma de justificar que, intercalando las líneas oportunas en una deducción, podemos acabar escribiendo de nuevo \( \alpha \) es demostrar \( \alpha\rightarrow \alpha \) (que ya hemos visto que se puede) y luego aplicar MP a \( \alpha \) y \( \alpha\rightarrow \alpha \).

Por supuesto, una forma más elegante de justificar la legitimidad de repetir líneas es darse cuenta de que podemos extraer las mismas consecuencias tanto si repetimos una línea como si no, pues la línea en cuestión estará igualmente disponible para ser usada luego si aparece una vez o si aparece dos veces.

[cerrar]

Una regla de inferencia que admite una deducción "natural" gracias a que contamos ya con el teorema de deducción es la siguiente:

Modus Barbara (MB)  \( \alpha\rightarrow \beta,\beta\rightarrow\gamma\vdash\alpha\rightarrow\gamma \)

La deducción sería la siguiente (llamamos hipótesis a las premisas adicionales que añadimos para emplear el teorema de deducción):

Reglas relacionadas con el negador y el implicador

Una regla muy especial es la siguiente:

Regla de la contradicción (C)   \( \alpha,\lnot\alpha\vdash \beta \)

En palabras: a partir de una contradicción (es decir si contamos con una fórmula y su negación como premisas) podemos deducir cualquier otra fórmula. La versión semántica de esta regla es peculiar, pues se reduce a que si en un modelo \( M \) son verdaderas a la vez \( \alpha \) y \( \lnot\alpha \) entonces en \( M \) es verdadera cualquier fórmula, y esto es trivialmente cierto porque es imposible que en un modelo sean verdaderas a la vez \( \alpha \) y \( \lnot\alpha \).

Demostración

\(
\begin{array}{lll}
(1)&\alpha&\mbox{Premisa}\\
(2)&\lnot\alpha&\mbox{Premisa}\\
(3)&\lnot\alpha\rightarrow(\lnot\beta\rightarrow\lnot\alpha)&\mbox{K1}\\
(4)&\lnot\beta\rightarrow \lnot\alpha&\mbox{MP 2, 3}\\
(5)&(\lnot\beta\rightarrow\lnot\alpha)\rightarrow (\alpha\rightarrow\beta)&\mbox{K3}\\
(6)&\alpha\rightarrow\beta&\mbox{MP 4, 5}\\
(7)&\beta&\mbox{MP 1, 6}
\end{array}
 \)

[cerrar]

La deducción de la regla en \( K_{\mathcal L} \) sugiere un argumento semántico algo más sofisticado: si en un modelo \( M \) se cumple \( M\vDash \lnot\alpha \), entonces se cumple claramente \( \vDash \alpha\rightarrow\beta \) (porque una implicación con hipótesis falsa es verdadera), luego si se cumpliera \( \alpha \) también tendría que cumplirse \( \beta \).

Regla de la doble negación (DN)   \( \lnot\lnot\alpha\vdash \alpha \),      \( \alpha\vdash\lnot\lnot\alpha \)

Notemos que aplicando el teorema de deducción a estas reglas (lo cual es válido porque en su prueba no se usa para nada IG) obtenemos que \( \vdash \lnot\lnot\alpha\rightarrow \alpha \) y \( \vdash\alpha\rightarrow \lnot\lnot\alpha \). También llamaremos DN a estos dos hechos, es decir, al insertar fórmulas de cualquiera de estos dos tipos en una deducción.

Notemos que \( \lnot\lnot\alpha\vDash \alpha \) es inmediato. Si un modelo cumple \( M\vDash \lnot\lnot\alpha \) eso es exactamente lo mismo que cumplir \( M\vDash \alpha \). Sin embargo, el hecho de que la regla sea semánticamente trivial no nos exime de justificar que \( K_{\mathcal L} \) es lo suficientemente potente para demostrarla, y la prueba es horripilante:

Demostración

\(
\begin{array}{lll}
(1)&\lnot\lnot\alpha&\mbox{Premisa}\\
(2)&\lnot\lnot\alpha\rightarrow(\lnot\lnot\lnot\lnot\alpha\rightarrow \lnot\lnot\alpha)&\mbox{K1}\\
(3)&\lnot\lnot\lnot\lnot\alpha\rightarrow\lnot\lnot\alpha&\mbox{MP 1,2}\\
(4)&(\lnot\lnot\lnot\lnot\alpha\rightarrow \lnot\lnot\alpha)\rightarrow(\lnot\alpha\rightarrow\lnot\lnot\lnot\alpha)&\mbox{K3}\\
(5)&\lnot\alpha\rightarrow\lnot\lnot\lnot\alpha&\mbox{MP 3,4}\\
(6)&(\lnot\alpha\rightarrow\lnot\lnot\lnot\alpha)\rightarrow (\lnot\lnot\alpha\rightarrow\alpha)&\mbox{K3}\\
(7)&\lnot\lnot\alpha\rightarrow \alpha&\mbox{MP 5,6}\\
(8)&\alpha&\mbox{MP 1,7}
\end{array}
 \)

Por el teorema de deducción \( \vdash \lnot\lnot\alpha\rightarrow\alpha \). Esto vale para toda fórmula \( \alpha \). Si lo aplicamos a \( \lnot\alpha \) obtenemos \( \vdash \lnot\lnot\lnot\alpha\rightarrow\lnot\alpha \). Usamos esto en la deducción siguiente:

\(
\begin{array}{lll}
(1)&\alpha&\mbox{Premisa}\\
(2)&\lnot\lnot\lnot\alpha\rightarrow\lnot\alpha&\mbox{por la observación precedente}\\
(3)&(\lnot\lnot\lnot\alpha\rightarrow\lnot\alpha)\rightarrow(\alpha\rightarrow\lnot\lnot\alpha)&\mbox{K3}\\
(4)&\alpha\rightarrow \lnot\lnot\alpha&\mbox{MP 2,3}\\
(5)&\lnot\lnot\alpha&\mbox{MP 1,4}
\end{array}
 \)

Aun a riesgo de resultar pesados insistiremos en que esto no es "la lógica", esto no son ejemplos representativos de lo que es "razonar lógicamente", sino todo lo contrario, son ejemplos absolutamente atípicos y nada representativos de lo que es un razonamiento lógico. Esto es una prueba técnica de un teorema técnico que sólo tiene interés para los especialistas en lógica, a saber, que toda la lógica es formalizable en \( K_{\mathcal L} \). Alguien interesado en usar la lógica para razonar en matemáticas puede simplemente aceptar las reglas de doble negación por el mero hecho de que son semánticamente válidas. Eso sí, si más adelante se interesa, por ejemplo, por entender los teoremas de incompletitud de Gödel, o quiere entender por qué no se puede demostrar la hipótesis del continuo, necesitará saber que todas esas reglas que ha aceptado por su validez semántica pueden deducirse de \( K_{\mathcal L} \), de modo que estudiar las posibilidades de demostración en \( K_{\mathcal L} \) es equivalente a estudiar las posibilidades de demostración en matemáticas.

[cerrar]

Reglas de la negación de la implicación (NI)  \( \alpha\rightarrow\beta\vdash \lnot\beta\rightarrow\lnot\alpha \),   \( \lnot\beta\rightarrow\lnot\alpha\vdash\alpha\rightarrow \beta \),   \( \alpha\rightarrow\lnot\beta\vdash\beta\rightarrow\lnot\alpha \),   \( \lnot\alpha\rightarrow \beta\vdash\lnot\beta\rightarrow\alpha \)

Para la prueba remito al lector a mi libro de lógica (página 47). La prueba de las reglas NI es "menos horripilante" que la de las reglas DN, pero no por ello dejan de ser "antinaturales" en el sentido de que no pueden ser entendidas como una justificación de por qué son semánticamente válidas. (Pero esto no ha de entenderse como ninguna clase de crítica a la teoría, la teoría es exactamente la que tiene que ser y las pruebas son antinaturales porque así tienen que ser, no hay nada de erróneo en el planteamiento).

Modus tollendo tollens (MT)     \( \alpha\rightarrow\beta,\lnot\beta\vdash \lnot\alpha \),    \( \alpha\rightarrow\lnot\beta, \beta\vdash \lnot\alpha \).

Para deducir estas reglas basta aplicar el recíproco del teorema de deducción a NI.

Reglas relacionadas con el disyuntor

Reglas de equivalecia entre disyunción e implicación (EDI)   \( \alpha\lor\beta\vdash \lnot\alpha\rightarrow\beta \),   \( \lnot\alpha\rightarrow \beta\vdash \alpha\lor \beta \).

Estas reglas son un caso particular de la regla de repetición, pues las dos fórmulas que relacionan son de hecho la misma, por la definición que hemos dado del disyuntor.

Notemos que nos proporcionan una técnica que es útil a menudo para demostrar una disyunción: suponemos que no se cumple una de las fórmulas y usamos eso para demostrar la otra. El teorema de deducción nos da entonces \( \lnot\alpha\rightarrow \beta \) y esto equivale a \( \alpha\lor\beta \).

Recíprocamente, una forma de "aprovechar" una premisa que sea una disyunción (no es la única posible) consiste en llegar a que no se cumple una de las fórmulas y concluir que se tiene que cumplir la otra. Esto lo expresa de forma más explícita la regla siguiente:

Modus tollendo ponens (MTP)  \( \alpha\lor \beta,\lnot\alpha\vdash \beta \),   \( \alpha\lor\beta,\lnot\beta\vdash \alpha \).

La primera se deduce inmediatamente de EDI: si suponemos \( \alpha\lor\beta \) y \( \lnot\alpha \), tenemos que \( \lnot\alpha\rightarrow \beta \) y basta aplicar MP. Para la segunda:

\(
\begin{array}{lll}
(1)&\alpha\lor\beta&\mbox{Premisa}\\
(2)&\lnot\beta&Premisa\\
(3)&\lnot\alpha\rightarrow\beta&\mbox{EDI 1}\\
(4)&\lnot\lnot\alpha&\mbox{MT 2, 3}\\
(5)&\alpha&\mbox{DN 4.}
\end{array}
 \)

Una regla con demostración inmediata es:

Regla del tercio excluso o tertium non datur (TND)  \( \vdash \alpha\lor\lnot\alpha \)

Basta tener en cuenta que esta fórmula es la misma que \( \lnot\alpha\rightarrow\lnot\alpha \), que ya sabemos que es deducible en \( K_{\mathcal L} \).

En cambio, la regla siguiente es algo más complicada de probar:

Regla de eliminación del disyuntor (ED)   \( \alpha\lor\alpha\vdash\alpha \)

Una prueba directa a partir de los axiomas de \( K_{\mathcal L} \) es especialmente monstruosa. En cambio, se simplifica muchísimo si se demuestran primero las reglas relacionadas con el conjuntor, de las que hablaremos luego. Remito a mi libro de lógica para la prueba (página 49).

Con esta regla podemos probar otra técnica útil para sacarle partido a una disyunción en una deducción: si contamos con que \( \alpha\lor \beta \), una forma de concluir de ahí que se cumple una fórmula \( \gamma \) es probar que cada una de las dos fórmulas por separado implica \( \gamma \), esto es lo que se suele llamar "distinguir casos":

Regla del dilema (Dil)  \( \alpha\rightarrow \gamma, \beta\rightarrow\gamma\vdash(\alpha\lor\beta)\rightarrow\gamma \)

Demostración

[cerrar]

Un caso particular de argumento "distinguiendo casos" consiste en tomar cualquier fórmula \( \alpha \) que sea relevante en la discusión y probar que tanto \( \alpha\rightarrow \beta \) como \( \lnot\alpha\rightarrow\beta \). Así, como tenemos \( \alpha\lor\lnot\alpha \) por TND, podemos concluir \( \beta \) por la regla anterior.

Regla de introducción del disyuntor (ID) \( \alpha\vdash \alpha\lor\beta \),   \( \beta\vdash\alpha\lor\beta \)

Una es trivial: aplicando el teorema de deducción a la regla de la contradicción obtenemos \( \alpha\vdash \lnot\alpha\rightarrow\beta \), pero esto es exactamente lo mismo que \( \alpha\vdash \alpha\lor\beta \), por la definición del disyuntor. Para la segunda usamos K1: \( \beta\rightarrow(\lnot\alpha\rightarrow\beta) \), que con la premisa nos da \( \lnot\alpha\rightarrow\beta \), que es lo mismo que \( \alpha\lor\beta \).

Reglas relacionadas con el conjuntor

Las relaciones fundamentales entre el conjuntor y el disyuntor son las llamadas leyes de De Morgan, una de las cuales la hemos tomado como definición del conjuntor y, por consiguiente, su prueba es trivial (ya que se reduce a la regla de repetición):

Leyes de De Morgan (DM)

\(
\begin{array}{ll}
\phantom\lnot\alpha\land\beta\vdash\lnot(\lnot\alpha\lor\lnot\beta)&\lnot(\lnot\alpha\lor\lnot\beta)\vdash\alpha\land \beta\\
\phantom\lnot\alpha\lor\beta\vdash\lnot(\alpha\land\lnot\beta)&\lnot(\alpha\land\lnot\beta)\vdash\alpha\lor\beta\\
\lnot(\alpha\land\beta)\vdash \lnot\alpha\lor\lnot\beta&\lnot\alpha\lor\lnot\beta\vdash\lnot(\alpha\land\beta)\\
\lnot(\alpha\land\beta)\vdash \lnot\alpha\lor\lnot\beta&\lnot\alpha\lor\lnot\beta\vdash\lnot(\alpha\land\beta)
\end{array} \)

Según ya hemos dicho, las dos primeras son casos particulares de la regla de repetición, pues las dos fórmulas involucradas son la misma por definición. Para la prueba de las restantes remito a mi libro de lógica (página 48).

Una consecuencia inmediata de las leyes de De Morgan es la regla de no contradicción:

Regla de no contradicción \( \vdash\lnot(\alpha\land\lnot\alpha) \)

En efecto, un caso particular de TND es \( \lnot\alpha\lor\lnot\lnot\alpha \), y de aquí se pasa a la fórmula que indica la regla por DM.

Regla de introducción del conjuntor (IC)  \( \alpha,\beta\vdash \alpha\land \beta \)

La prueba es bastante artificial. Remito a mi libro de lógica (página 48).

Reglas de eliminación del conjuntor (EC) \( \alpha\land\beta\vdash\alpha \),   \( \alpha\land \beta\vdash \beta \)

También llamaremos (EC) a los resultados \( \vdash (\alpha\land\beta)\rightarrow \alpha \),  \( \vdash(\alpha\land \beta)\rightarrow \beta \), que resultan de aplicar el teorema de deducción.

Para la prueba de estas reglas remito a mi libro de lógica (página 49).

Reglas relacionadas con el bicondicionador

Para razonar de forma natural con el coimplicador o bicondicionador basta considerar las dos reglas que resultan de combinar su definición (que es una conjunción) con las reglas de introducción y eliminación del conjuntor:

Regla de introducción del bicondicionador (IB) \( \alpha\rightarrow\beta, \beta\rightarrow\alpha\vdash \alpha\leftrightarrow\beta \)

Reglas de eliminación del bicondicionador (EB) \( \alpha\leftrightarrow\beta\vdash \alpha\rightarrow\beta \),   \( \alpha\leftrightarrow\beta\vdash \beta\rightarrow\alpha \)


Las reglas que hemos dado son suficientes para que, contando con ellas, cualquier deducción en \( K_{\mathcal L} \) que no requiera tratar con cuantificadores o el igualador pueda realizarse de forma natural, es decir, sin tener que recurrir a combinar de forma "inspirada" axiomas lógicos aplicados a fórmulas elegidas "inspiradamente". En el mensaje siguiente introduciremos las reglas necesarias para poder trabajar del mismo modo con los cuantificadores y el igualador.

Conviene observar que en la deducción de todas las reglas derivadas que hemos visto hasta aquí sólo han intervenido los axiomas K1, K2 y K3 y la regla MP. En particular, como nunca hemos usado IG, todas las reglas pueden usarse libremente aunque estemos trabajando bajo hipótesis adicionales para aplicar el teorema de deducción, pues la aplicación de estas reglas nunca supondrá una generalización inadvertida sobre una variable libre en alguna hipótesis (ni sobre ninguna otra variable).

Las reglas de inferencia que hemos presentado bastan para justificar que una técnica de razonamiento muy habitual en matemáticas es formalizable en \( K_{\mathcal L} \):

Razonamiento por reducción al absurdo

Si en una deducción tomamos \( \lnot\alpha \) como premisa adicional y, sin generalizar respecto de variables libres en \( \alpha \), llegamos a una contradicción \( \beta\land\lnot\beta \), podemos concluir \( \alpha \).

Más precisamente, lo que estamos afirmando es que en esta situación:

si a partir del momento en que suponemos \( \lnot\alpha \) no generalizamos respecto a variables libres en \( \alpha \), la fórmula \( \alpha \) escrita en la línea \( (k+1) \) es deducible en \( K_{\mathcal L} \) a partir de las premisas, pero las líneas marcadas con la raya vertical a la izquierda no lo son, porque suponen la hipótesis adicional \( \lnot\alpha \).

En efecto, lo que nos dice el teorema de deducción al llegar a la línea \( (k) \) es que \( \lnot\alpha\rightarrow (\beta\land\lnot\beta) \) es deducible de las premisas, luego podríamos haber escrito esta fórmula en la línea \( (k+1) \), y la deducción podría haber continuado así:

\( \begin{array}{lll}
(k+1)&\lnot\alpha\rightarrow (\beta\land\lnot\beta)\\
(k+2)&\lnot (\beta\land\lnot\beta)&\mbox{NC}\\
(k+3)&\lnot\lnot\alpha&\mbox{MT $k+1, k+2$}\\
(k+4)&\alpha&\mbox{DN $k+3$}
\end{array} \)

En la práctica suprimiremos estas líneas y escribiremos directamente \( \alpha \) tras haber llegado a una contradicción. En suma:

Una forma válida de concluir \( \alpha \) es suponer \( \lnot\alpha \) como hipótesis adicional y llegar a una contradicción, con la condición de que a partir de ese momento no se generalice respecto de variables libres en \( \alpha \).

Nuevamente, la restricción sobre la generalización es algo que todo matemático respetará de forma instintiva en cada caso concreto. Por ejemplo, supongamos que, en el curso de una prueba, un matematico quiere probar que un cierto \( p \) que está considerando es un número primo y se propone hacerlo por reducción al absurdo. Jamás razonaría así:

(1) Supongamos (por reducción al absurdo) \( \lnot (p \) es primo)

(2) \( \forall p\lnot (p \) es primo) (generalización que viola la restricción sobre el uso de IG)

(3) \( \exists p\ (p \) es primo) (resultado probado anteriormente)

(4) \( \lnot\forall p\ \lnot (p \) es primo) (equivalencia lógica con 3 que veremos en el mensaje siguiente)

(5)  \( \forall p\lnot (p \) es primo) \( \land \lnot\forall p\ \lnot(p \) es primo) contradicción

(6) \( p \) es primo, por reducción al absurdo.

Esto en realidad no prueba nada. Podemos suponer para llegar a un absurdo que \( p \) no es primo, pero no podemos pasar de ahí a que ningún p es primo (que es lo que obtenemos si generalizamos ilegalmente respecto de p).

[Carlos Ivorra]

Aunque todavía nos falta por dar reglas que nos permitan trabajar de forma natural con los cuantificadores y con el igualador, podemos decir que en este punto "ya hemos desempaquetado la lógica", porque los únicos axiomas "pensados con ingenio" para contener mucha lógica en poco espacio son los axiomas K1, K2, K3 que ya hemos desarrollado, y el axioma K5, que hemos usado únicamente en la prueba del teorema de deducción y no volveremos a usarlo nunca más.

Más concretamente, K5 se usa para probar que el teorema de deducción es aplicable a deducciones que usen IG, pero como en el mensaje anterior sólo lo hemos usado para deducciones que no usaban IG, todo lo dicho hasta aquí es válido incluso sin K5, y ahora sólo lo vamos a usar indirectamente, cuando apliquemos el teorema de deducción a deducciones que usan IG.

Ahora sólo nos falta desarrollar los axiomas K4 y K6, que hasta ahora no hemos usado para nada, y ambos son bastante "naturales", así que ya nunca más vamos a necesitar demostrar nada mediante argumentos "retorcidos".

Reglas relacionadas con los cuantificadores

Las propiedades de los cuantificadores (sin tener en cuenta el uso indirecto de K5 que acabamos de explicar) se siguen todas del axioma K4, que recordamos aquí:

\( \forall x\alpha\rightarrow S_x^t\alpha \)

Lo que afirma es muy natural y podemos expresarlo equivalentemente en forma de regla de inferencia:

Regla de eliminación del generalizador (EC) \( \forall x\alpha\vdash S_x^t\alpha \)

Lo que afirma esta regla es que si contamos con que todo \( x \) cumple lo que dice \( \alpha \), entonces podemos afirmar que un término \( t \) cualquiera cumple lo que dice \( \alpha \).

No damos una regla de introducción del generalizador porque ésta es una de las dos reglas primitivas que hemos usado para definir \( K_{\mathcal L} \).

La relación entre el cuantificador universal y el existencial son consecuencia esencialmente de la definición del segundo y de la regla de doble negación:

Reglas de negación del generalizador (NG) \( \lnot\forall x\lnot\alpha\vdash \exists x\alpha \),   \( \exists x\alpha\vdash \lnot\forall x\lnot\alpha \),     \( \lnot\forall x\alpha\vdash \exists x\lnot\alpha \),   \( \exists x\lnot\alpha\vdash \lnot\forall x\alpha \)

Las dos primeras son casos particulares de la regla de repetición, pues hemos definido \( \exists x\alpha \) precisamente como \( \lnot\forall x\lnot\alpha \), luego las dos fórmulas que involucran las reglas son la misma.

Las otras dos sólo requieren aplicar oportunamente la regla de doble negación, lo cual exige eliminar primero el cuantificador para luego volverlo a introducir:

Demostración

Observemos que desde el momento en que suponemos (2) está prohibido generalizar respecto de variables libres en (2), pero luego sólo generalizamos respecto de \( x \), que no está libre en (2).

Notemos que aquí hemos usado una variante de la reducción al absurdo: en vez de suponer \( \lnot\alpha \) para llegar a una contradicción y deducir \( \alpha \), hemos supuesto \( \alpha \) para deducir \( \lnot\alpha \). Esto es válido en general, pues podríamos haber supuesto \( \lnot\lnot\alpha \), aplicar DN y luego seguir como hemos hecho. Notemos también que el uso de IG no viola la restricción que exige la hipótesis (2) por reducción al absurdo.

[cerrar]

Reglas de negación del particularizador (NP) \( \lnot\exists x\alpha\vdash \forall x\lnot\alpha \),    \( \forall x\lnot\alpha\vdash \lnot\exists x\alpha \),    \( \lnot\exists x\lnot\alpha\vdash \forall x\alpha \),     \( \forall x\alpha\vdash \lnot\exists x\lnot\alpha \).

Éstas se prueban más fácilmente incluso que las anteriores, porque al anteponer un negador al particularizador y aplicar la definición de éste, se juntan dos negadores que pueden ponerse o quitarse por DN, y no hacen falta reducciones al absurdo. Dejamos las pruebas al lector y, en todo caso, remito a mi libro de lógica (página 51).

Regla de introducción del particularizador (IP) \( S_x^t\alpha\vdash \exists x\alpha \)

Esta regla afirma que si hemos probado que un cierto término \( t \) cumple lo que dice \( \alpha \), entonces podemos afirmar que existe un \( x \) que cumple \( \alpha \). Tenemos un ejemplo de  su uso en la línea 12 de la deducción sobre divisibilidad que pusimos como ejemplo más arriba.

Demostración

[cerrar]

Por último nos falta una "regla de eliminación del particularizador", que es la que aplica un matemático cuando tiene que \( \exists x\alpha \) y dice "tomemos un \( x \) que cumpla \( \alpha \)". Tenemos dos ejemplos en las líneas 5 y 8 de la deducción sobre divisibilidad que pusimos como ejemplo. Ahora bien, esta "regla" no es realmente una regla derivada de inferencia, sino un (meta)teorema análogo al teorema de deducción. Para probarlo necesitamos un hecho previo que tiene interés en sí mismo:

Teorema: Si la variable \( y \) no está en la fórmula \( \forall x\alpha \), entonces

\( \vdash\forall x\alpha\leftrightarrow \forall yS_x^y\alpha,\qquad \vdash \exists x\alpha\leftrightarrow \exists y S_x^y\alpha \)

Demostración

Notemos que podemos generalizar sobre \( y \) porque suponemos que la variable no está libre en la hipótesis.

Ahora observamos que la variable \( x \) no está libre en \( \forall y S_x^y\alpha \) (porque todas sus apariciones libres han sido sustituidas por \( y \)), luego podemos aplicar lo que acabamos de probar a la variable \( x \) y la fórmula \( \forall yS_x^y\alpha \), con lo que obtenemos \( \vdash \forall y S_x^y\alpha\rightarrow \forall x S_y^xS_x^y\alpha \), pero es fácil ver que la doble sustitución es simplemente \( \alpha \). Así hemos probado:

\( \vdash \forall x\alpha\rightarrow \forall yS_x^y\alpha\qquad \vdash \forall y S_x^y\alpha\rightarrow\forall x\alpha \)

Aplicando la regla IB obtenemos la primera parte del enunciado. Para la segunda parte aplicamos lo que hemos visto a la fórmula \( \lnot\alpha \) y tenemos:

\( \vdash \forall x\lnot \alpha\rightarrow \forall y\lnot S_x^y\alpha\qquad \vdash \forall y\lnot S_x^y\alpha\rightarrow\forall x\lnot\alpha \)

Prolongando ambas deducciones con una aplicación de NI obtenemos

\( \vdash \lnot\forall y\lnot S_x^y\alpha\rightarrow\lnot\forall x\lnot\alpha\qquad \vdash \lnot\forall x\lnot \alpha\rightarrow \lnot\forall y\lnot S_x^y\alpha \)

Y esto es exactamente lo mismo que

\( \vdash\exists y S_x^y\alpha\rightarrow\exists x\alpha\qquad \vdash\exists x\alpha\rightarrow \exists y S_x^y\alpha \),

de donde se sigue la segunda parte del enunciado.

[cerrar]

Regla de eliminación del particularizador (EP):

En esta situación:

\( \begin{array}{lll}
(1)&\gamma_1\\
\ \ \vdots&&\mbox{deducción a partir de unas premisas $\alpha_1,\ldots, \alpha_n$}\\
(k)& \exists x\alpha&\\
\ \ \vdots\\
(m)&\gamma_m\\
(m+1)&S_x^y\alpha&\mbox{EP k}\\
\ \ \vdots&&\mbox{deducción a partir de las premisas, las líneas precedentes y $S_x^y\alpha$}\\
\end{array} \)

Si la variable \( y \) no está en \( \alpha \) o bien \( y\equiv x \) (en cuyo caso \( S_x^x\alpha\equiv \alpha \)) y a partir de la línea \( m+1 \) no se generaliza respecto de variables libres en \( S_x^y\alpha \), entonces toda línea posterior \( \beta \) que no tenga libre la variable \( y \) es una consecuencia de las premisas.

Demostración

En principio, en la situación descrita tenemos que

\( \alpha_1,\ldots, \alpha_n,S_x^y\alpha\vdash \beta \).

Ahora bien,  como para obtener \( \beta \) no se ha generalizado respecto de ninguna variable libre en \( S_x^y\alpha \), podemos aplicar el teorema de deducción y concluir que

\( \alpha_1,\ldots, \alpha_n\vdash S_x^y\alpha\rightarrow \beta \).

Pero también sabemos que \( \alpha_1,\ldots, \alpha_n\vdash \exists x\alpha \) y por el teorema anterior también

\( \alpha_1,\ldots, \alpha_n\vdash \exists yS_x^y\alpha \)

Por lo tanto, sólo necesitamos probar que \( S_x^y\alpha\rightarrow \beta,  \exists yS_x^y\alpha\vdash\beta \). En efecto:

[cerrar]

Es muy importante observar que en la deducción de \( \beta \) a partir de las premisas se generaliza respecto de la variable \( y \). Esto significa que si aplicamos EP en un contexto en el que tenemos prohibido generalizar respecto de ciertas variables, debemos elegir la variable \( y \) como una nueva variable sobre la que no exista prohibición de generalizar. Una vez más, esto es algo que el matemático hace instintivamente. Consideremos por ejemplo la deducción sobre divisibilidad que presentamos unos mensajes atrás:

Desde la línea 2, tenemos prohibido generalizar respecto de \( x, y, z \). En la línea 5 eliminamos un particularizador \( \exists u \), y no cambiamos de variable porque no hay problema en generalizar respecto de \( u \). A partir de esa línea tenemos prohibido generalizar respecto de \( u \), por lo que, cuando queremos eliminar el \( \exists u \) de la línea 7 nos vemos obligados a sustituir la variable \( u \) por una nueva variable \( v \) que tiene que ser distinta de \( x, y, z, u \), que son las variables respecto a las que tenemos prohibido generalizar. El matemático hace esto instintivamente cuando piensa que no puede tomar \( u \) tal que \( z=yu \) porque ya está llamando \( u \) a otro número, y mucho menos se le ocurriría llamarlo \( x, y, z \) por el mismo motivo, porque sabe que el \( u \) que existe por 7 no tiene por qué ser el mismo que cualquiera de los números que está considerando hasta entonces.

Al introducir el particularizador en 12 dejamos de tener libres las variables \( u, v \), por lo que todas las fórmulas que siguen son ya auténticas consecuencias de las premisas (y de la hipótesis 2), y podemos aplicar el teorema de deducción para pasar a 14 (hubiera sido incorrecto hacerlo con una fórmula que tuviera libre la variable \( u \) o la variable \( v \).

Nótese la sutileza: a partir del momento en que suponemos \( y=xu \) queda prohibido generalizar respecto de \( u \), pero la deducción de \( x\mid z \) a partir de las premisas y la hipótesis (2) usa la regla IG respecto de \( u \), es decir, tenemos prohibido generalizar, pero a la vez la prueba completa que elimina la premisa adicional \( y=xu \) generaliza respecto de \( u \). En general:

Cuando aplicamos EP, debemos reemplazar la variable afectada por el particularizador por una variable respecto a la que sea lícito generalizar hasta ese momento, pero a partir de ese momento tenemos prohibido generalizar respecto de ella.

Como al eliminar un particularizador dejamos libre una variable que no puede quedar libre en la conclusión, la única forma de volver a ligarla es mediante la regla de introducción del particularizador (IP), porque la regla de introducción del generalizador la tenemos prohibida. Aquí es fundamental observar que en la demostración de IP no se generaliza respecto a la variable que particularizamos.

Notemos que es "de sentido común": si una variable procede de eliminar un \( \exists u \), luego no podemos ligarla con un \( \forall u \), sino que tendremos que volver a introducir un particularizador.

Reglas relacionadas con el igualador

Finalmente vamos a "desempaquetar" la lógica del igualador, que la tenemos toda "empaquetada" en el axioma K6. Si queremos expresar este axioma como reglas de inferencia tenemos trivialmente las dos reglas siguientes:

Reglas de introducción y eliminación del igualador (II, EI)

\( S_x^t\alpha\vdash \forall x(x=t\rightarrow \alpha)\qquad \forall x(x=t\rightarrow \alpha)\vdash S_x^t\alpha \)

Estas reglas sólo son aplicables si la variable \( x \) no está (libre) en \( t \).

Lo que dice aquí es que es equivalente que \( t \) cumpla \( \alpha \) que cuando \( x=t \) entonces \( x \) cumple \( \alpha \).

De aquí se deducen todas las propiedades que cabe esperar del igualador:

Regla de la identidad (I) \( \vdash t=t \)

Demostración

Sea \( x \) una variable que no esté en \( t \). La primera línea de la deducción siguiente la incluimos porque ya hemos probado que es deducible en \( K_{\mathcal L} \).

\( \begin{array}{lll}
(1)&x=t\rightarrow x=t\\
(2)&\forall x(x=t\rightarrow x=t)&\mbox~{IG 1}\\
(3)&S_x^t(x=t)&\mbox{EI 2}\\
(4)&t=t&\mbox{R3}
\end{array} \)

Notemos que en la prueba usamos IG, pero respecto de una variable que podemos elegir arbitrariamente, por lo que no hay problema en usar la regla I en contextos donde no se pueda generalizar respecto de ciertas variables, pues para llenar el "agujero" que supone usar I siempre podemos elegir \( x \) distinta de tales variables prohibidas. Lo mismo se aplica a las reglas siguientes.

[cerrar]

Regla se la simetría de la identidad (SI) \( t_1=t_2\vdash t_2=t_1 \)

Regla se la transitividad de la identidad (TI) \( t_1=t_2,t_2=t_3\vdash t_1=t_3 \)

Para la prueba de las dos reglas precedentes remito a mi libro de lógica (página 52). Veamos la prueba de la propiedad más importante y la que se usa en todo momento cuando se trabaja con igualdades:

Regla de equivalencia entre términos idénticos (ETI) \( t_1=t_2, S_x^{t_2}\alpha\vdash S_x^{t_1}\alpha \)

Lo que afirma esta regla es que si tenemos que \( t_1=t_2 \) y que \( t_2 \) cumple lo que afirma \( \alpha \), entonces lo mismo vale para \( t_1 \) o, más en general, que si tenemos \( t_1=t_2 \) entonces todo lo que sepamos de \( t_2 \) vale también para \( t_1 \).

Demostración

Sea \( y \) una variable que no esté en \( \alpha \), \( t_1 \) o \( t_2 \) (tomamos esta variable en previsión de que \( x \) pudiera estar libre en alguno de los términos). Es fácil ver entonces que \( S_y^{t_2}S_x^y\alpha\equiv S_x^{t_2}\alpha \) y \( S_y^{t_1}S_x^y\alpha\equiv S_x^{t_1}\alpha \).

\( \begin{array}{lll}
(1)&S_y^{t_2}S_x^y\alpha&\mbox{Premisa}\\
(2)&t_1=t_2&\mbox{Premisa}\\
(3)&\forall y(y=t_2\rightarrow S_x^y\alpha)&\mbox{II 1}\\
(4)&t_1=t_2\rightarrow S_y^{t_1}S_x^y\alpha&\mbox{EG 3}\\
(5)&S_x^{t_1}\alpha&\mbox{MP 2,4}
\end{array} \)

[cerrar]

[Carlos Ivorra]

Ahora estamos en condiciones de usar de forma natural el cálculo deductivo que hemos construido. Conviene enriquecer un poco el lenguaje que estamos empleando:

Definición Una teoría axiomática de primer orden \( T \) sobre un lenguaje formal \( \mathcal L \) es un sistema deductivo formal cuyos axiomas son los de \( K_{\mathcal L} \) más quizá otros axiomas adicionales, a los que se les llama axiomas propios de la teoría, y cuyas reglas de inferencia son las de  \( K_{\mathcal L} \).

Pese a lo que acabamos de decir, en la práctica es costumbre llamar axiomas de \( T \) a sus axiomas propios, y axiomas lógicos de \( T \) a los axiomas de \( K_{\mathcal L} \).

Una demostración en una teoría axiomática \( T \) es una deducción sin premisas (que es lo mismo que una deducción en \( K_{\mathcal L} \) que tiene por premisas los axiomas (propios) de \( T \)).

Esto hace que todos los resultados que hemos obtenido para deducciones en \( K_{\mathcal L} \) son aplicables a toda teoría axiomática \( T \), pues las deducciones en \( T \) son también deducciones en \( K_{\mathcal L} \), sólo que cuentan con premisas adicionales, a saber, los axiomas de \( T \).

Las fórmulas demostrables en \( T \) (es decir, deducibles sin premisas o deducibles en \( K_{\mathcal L} \) tomando como premisas los axiomas de \( T \))  se llaman teoremas de \( T \).

Si \( \lnot\alpha \) es demostrable en \( T \) se dice que \( \alpha \) es refutable en \( T \), y una demostración de \( \lnot\alpha \) se llama también una refutación de \( \alpha \).

Así \( K_{\mathcal L} \) es la teoría axiomática de primer orden más simple posible (la única que no tiene axiomas propios) y sus teoremas se llaman teoremas lógicos. El teorema de completitud semántica (que aún no hemos demostrado) implica que los teoremas lógicos son precisamente las fórmulas lógicamente válidas, es decir, las verdaderas en todos los modelos.

Una teoría axiomática de primer orden \( T \) es contradictoria si en ella se puede demostrar una contradicción, es decir, si existe una fórmula \( \alpha \) tal que \( \vdash_T\alpha\land\lnot\alpha \). En caso contrario se dice consistente.

Notemos que, por la regla de contradicción, en una teoría contradictoria se pueden demostrar todas las fórmulas, luego sus demostraciones no tienen valor alguno. Recíprocamente, una teoría es consistente si y sólo si hay al menos una fórmula que no sea un teorema.

Una teoría \( T \) es completa si para toda sentencia \( \alpha \) se cumple \( \vdash_T\alpha  \) o bien \( \vdash_T\lnot \alpha \), es decir, si toda sentencia es demostrable o refutable en \( T \).

Nota

Es importante que en la definición de teoría completa hablamos sólo de sentencias (fórmulas sin variables libres) y no de fórmulas arbitrarias. Por ejemplo, consideremos la fórmula \( x=y \). Esta fórmula no es refutable en ninguna teoría consistente, pues si \( \vdash_T x\neq y \) entonces, usando IG,  \( \vdash_T\forall xy(x\neq y) \), pero esto es contradictorio, ya que usando EG se obtiene también \( \vdash_T x\neq x \). Como también tenemos \( \vdash_Tx=x \), resulta que \( T \) es contradictoria.

Por otro lado, si una teoría cumple \( \vdash_Tx=y \) entonces también \( \vdash_T\forall xy(x=y) \), y resulta que los únicos modelos que admite \( T \) tienen un único elemento en su universo. Así pues, la fórmula \( x=y \) no es demostrable ni refutable en ninguna teoría que admita modelos con más de un elemento. Hemos definido la completitud de modo que esto no sea obstáculo para que una teoría pueda ser completa.

[cerrar]

Ejemplo Una teoría axiomática de primer orden es la aritmética de Peano (de primer orden) AP, que es la teoría axiomática cuyo lenguaje formal es el lenguaje de la aritmética que ya hemos descrito (el que tiene una constante \( 0 \), un funtor monádico \( S \) y dos funtores diádicos \( + \) y \( \cdot \)) y cuyos axiomas (propios) son:

\( \forall x\ Sx\neq 0 \)

\( \forall xy(Sx=Sy\rightarrow x=y) \)

\( \forall x(x+0=x) \)

\( \forall xy(x+Sy=S(x+y)) \)

\( \forall x(x\cdot 0=0) \)

\( \forall xy(x\cdot Sy = (x\cdot y)+x) \)

\( \alpha(0)\land \forall x(\alpha(x)\rightarrow \alpha(Sx))\rightarrow \forall x\alpha(x) \), para toda fórmula \( \alpha \).

Notemos que usamos la notación \( \alpha(0)\equiv S_x^0\alpha \),      \( \alpha(Sx)\equiv S_x^{Sx}\alpha \).


Introducidos estos conceptos, nos centramos ahora en ilustrar el concepto de deducción formal. Tomemos este ejemplo:

\( \alpha\rightarrow \alpha',\beta\rightarrow \beta'\vdash (\alpha\lor \beta)\rightarrow (\alpha'\lor\beta') \)

Lo importante es que estamos en condiciones de probar esto (y cualquier otra cosa) razonando exactamente como razonaría un matemático. Un matemático razonaría así:

Tenemos como premisas que \( \alpha\rightarrow \alpha' \) y \( \beta\rightarrow \beta' \). Para probar \( (\alpha\lor \beta)\rightarrow (\alpha'\lor\beta') \) suponemos \( \alpha\lor\beta \) y queremos probar \( \alpha'\lor\beta' \). Para probar una disyunción suponemos que no se cumple una de las partes y demostramos la otra. Suponemos, pues, \( \lnot\alpha' \). Entonces, por la primera premisa, \( \lnot\alpha \) y como suponemos \( \alpha\lor \beta \), tiene que ser \( \beta \), luego por la segunda premisa \( \beta' \), como queríamos probar.

Si ponemos esto en orden nos queda:

Si alguien lee esto y el razonamiento le parece artificial o enrevesado, significa que no está bien familiarizado con la lógica formal, y es con esto con lo que necesita familiarizarse, tiene que aprender a hacer deducciones formales como ésta y llegar a verlas naturales, no tiene que esforzarse por entender e imaginar deducciones kafkianas a partir de axiomas kafkianos, como las que hemos considerado en los mensajes anteriores para "desempaquetar" la lógica. El razonamiento formal es razonar así y no razonar como hemos tenido que hacer antes de poder llegar hasta aquí.

Por supuesto, las reglas de inferencia que hemos presentado en los mensajes precedentes no son las únicas posibles, ni forman ninguna especie de club selecto al que no se puede añadir nada más. Por el contrario, todos los resultados que demostremos y que puedan considerarse lo suficientemente generales como para que puedan ser de utilidad en diferentes contextos pueden y deben ser incorporados a la lista de resultados "utilizables" siempre que sea conveniente.

Por ejemplo, si tenemos \( \alpha\leftrightarrow \beta \) y \( \alpha \), podemos concluir \( \beta \), esto no es exactamente MP porque tenemos una coimplicación, pero está claro que de la coimplicación podemos deducir la implicación (EB) y a ésta le podemos aplicar MP. En la práctica no hay ningún inconveniente en dar los dos pasos en uno si sabemos lo que estamos haciendo.

Vamos a enumerar aquí algunos resultados de utilidad general:

Resultados sobre coimplicaciones

\( \vdash \alpha\leftrightarrow \alpha \)

\( \alpha\leftrightarrow\beta\vdash \beta\leftrightarrow \alpha \)

\( \alpha\leftrightarrow \beta, \beta\leftrightarrow \gamma\vdash\alpha\leftrightarrow\gamma \)

\( \alpha\leftrightarrow\beta\vdash \lnot\alpha\leftrightarrow \lnot\beta \)

\( \alpha\leftrightarrow \alpha', \beta\leftrightarrow \beta'\vdash (\alpha\land\beta)\leftrightarrow (\alpha'\land \beta') \)

\( \alpha\leftrightarrow \alpha', \beta\leftrightarrow \beta'\vdash (\alpha\lor\beta)\leftrightarrow (\alpha'\lor \beta') \)

\( \alpha\leftrightarrow \alpha', \beta\leftrightarrow \beta'\vdash (\alpha\rightarrow \beta)\leftrightarrow (\alpha'\rightarrow \beta') \)

\( \alpha\leftrightarrow \alpha', \beta\leftrightarrow \beta'\vdash (\alpha\leftrightarrow \beta)\leftrightarrow (\alpha'\leftrightarrow \beta') \)

\( \alpha\leftrightarrow \alpha'\vdash \forall x\alpha\leftrightarrow \forall x\alpha' \)

\( \alpha\leftrightarrow \alpha'\vdash \exists x\alpha\leftrightarrow \exists x\alpha' \)

Demostración

Las pruebas son sencillas: las cuatro primeras se demuestran desdoblando las coimplicaciones de las premisas en implicaciones, aplicando las propiedades correspondientes para implicaciones (que ya las tenemos probadas) y agrupando de nuevo las implicaciones en coimplicaciones.

La sexta se obtiene desdoblando igualmente las premisas y aplicando el resultado que hemos probado más arriba como ejemplo. La quinta, séptima y octava son similares, pero más fáciles. Veamos la penúltima:

Un matemático diría: suponemos la premisa (1). Para probar la equivalencia empezamos suponiendo (2). Tomemos ahora un \( x \) arbitrario. Por (2) sabemos que cumple \( \alpha \), es decir, (3), por la premisa nuestro \( x \) cumple también \( \alpha' \), es decir, (4), y como \( x \) era arbitrario podemos generalizar y escribir (5). Esto prueba la implicación (6) y análogamente se prueba (7), luego tenemos (8).

El último resultado se prueba exactamente igual cambiando EG, IG por EP, IP. En la versión del matemático, los únicos cambios son que ahora diría "tomemos un \( x \) que cumple \( \alpha \), es decir, (3) (sabemos que existe por (2)), entonces \( x \) cumple también \( \alpha' \), es decir, (4), luego existe un \( x \) que cumple \( \alpha' \), es decir, (6)..."

[cerrar]

El álgebra del cálculo proposicional

A menudo es útil sustituir una fórmula por otra lógicamente equivalente con otra estructura, normalmente con intención de llegar a expresiones más simples o más manejables. Para ello ayudan las propiedades siguientes (donde usamos la notación \( \top \) para nombrar cualquier fórmula que sea un teorema lógico y \( \bot \) para representar cualquier fórmula cuya negación sea un teorema lógico:

\( \vdash (\alpha\land \beta)\land \gamma\leftrightarrow \alpha\land (\beta\land \gamma) \)

\( \vdash (\alpha\lor \beta)\lor \gamma\leftrightarrow \alpha\lor (\beta\lor \gamma) \)

\( \vdash (\alpha\land \beta)\leftrightarrow (\beta\land \alpha) \)

\( \vdash (\alpha\lor \beta)\leftrightarrow (\beta\lor \alpha) \)

\( \vdash \alpha\land (\beta\lor\gamma)\leftrightarrow (\alpha\land\beta)\lor (\alpha\land \gamma) \)

\( \vdash \alpha\lor (\beta\land\gamma)\leftrightarrow (\alpha\lor\beta)\land (\alpha\lor \gamma) \)

\( \vdash \alpha\lor \bot\leftrightarrow \alpha \)

\( \vdash \alpha\land \top\leftrightarrow \alpha \)

\( \vdash\alpha\lor\lnot\alpha\leftrightarrow \top \)

\( \vdash\alpha\land\lnot\alpha\leftrightarrow \bot \)

Los dos primeros resultados justifican que escribamos \( \alpha_1\land \cdots \land \alpha_n \) y \( \alpha_1\lor \cdots \lor \alpha_n \) sin paréntesis, porque las fórmulas resultantes son equivalentes sin que importe cómo se disponen los paréntesis.

Demostración

Dejamos la primera al lector porque es más fácil que la segunda.

La otra implicación es análoga.

Dejamos al lector las propiedades conmutativas y probamos la primera distributiva:

¿Y no sería más fácil probar esta equivalencia demostrando que la tabla de verdad de la coimplicación es siempre verdadera? Si hacemos eso habremos probado que la fórmula es lógicamente válida, pero en principio eso no es lo mismo que ser deducible en \( K_{\mathcal L} \), que es lo que acabamos de probar. Ahora bien, aceptando el teorema de completitud semántica ambos métodos son equivalentes, eso sí, con las tablas de verdad probamos que la equivalencia se puede demostrar, pero no obtenemos una demostración.

Veamos la primera de las cuatro últimas y dejamos las demás al lector:

[cerrar]

El spoiler siguiente contiene una observación marginal:

El álgebra de Lindenbaum-Tarski

Aunque esto tendría sentido metamatemáticamente, no hay razón para plantearlo fuera de una teoría de conjuntos, así que en esta nota consideramos que estamos desarrollando la lógica formalizada en ZF.

Dada una teoría axiomática \( T \) consideramos el conjunto de todas sus sentencias (fórmulas sin variables libres) y definimos en él la relación de equivalencia dada por

\( \alpha\sim \beta \) si y sólo si \( \vdash_T\alpha\leftrightarrow \beta \)

Los teoremas precedentes muestran que, en efecto, se trata de una relación de equivalencia. Por ejemplo, si \( \alpha\sim \beta \), entonces \( \vdash_T\alpha\leftrightarrow \beta \), y como \( \alpha\leftrightarrow \beta\vdash \beta\leftrightarrow\alpha \), también \( \vdash_T\beta\leftrightarrow\alpha \), luego \( \beta\sim \alpha \).

Se define el álgebra de Lindenbaum-Tarski de \( T \) como el conjunto cociente \( \mathbb B(T) \) respecto de esta relación de equivalencia. Así, los elementos de \( \mathbb B(T) \) son clases de equivalencia \( [\alpha] \) de sentencias del lenguaje de \( T \).

Los teoremas anteriores prueban que las operaciones dadas por \( \lnot[\alpha]=[\lnot\alpha] \), \( [\alpha]\land [\beta]=[\alpha\land \beta] \), \( [\alpha]\lor [\beta]=[\alpha\lor\beta] \) están bien definidas, en el sentido de que no dependen de los representantes con los que se calculan.

Todos los teoremas de \( T \) forman una misma clase de equivalencia, a la que llamaremos \( 1=[\top] \). En efecto, es claro que \( \alpha,\beta\vdash \alpha\leftrightarrow \beta \), por lo que dos teoremas cualesquiera de \( T \) son equivalentes. A su vez, la clase \( 0=\lnot 1 \) está formada por las negaciones de los teoremas de \( T \).

Las propiedades que hemos demostrado implican claramente que \( \mathbb B(T) \) con estas operaciones es un álgebra de Boole. La teoría \( T \) es contradictoria si y sólo si \( \mathbb B(T)=\{0\} \) (y se dice que el álgebra es degenerada). Si es consistente, será completa si y sólo si \( \mathbb B(T)=\{0,1\} \) (y se dice que el álgebra es trivial). Cuanto mayor sea el álgebra de Lindenbaum-Tarski, "más incompleta" es la teoría.

[cerrar]

Ejemplos de deducciones con cuantificadores

Para terminar veamos algunos ejemplos que involucren las reglas sobre cuantificadores:

\( \forall xy(Bxy\rightarrow Sy), \exists x(\lnot Bxa\rightarrow Cx), \forall x\lnot Cx\vdash \exists ySy \)

(Aquí se entiende que \( B, S, C, \) son relatores y que \( a \) es una constante.)

Solución

Añadimos una primera columna con "lo que diría un matemático":

\( \begin{array}{llll}
&(1)&\forall xy(Bxy\rightarrow Sy)&\mbox{Premisa}\\
&(2)&\exists x(\lnot Bxa\rightarrow Cx)&\mbox{Premisa}\\
&(3)&\forall x\lnot Cx&\mbox{Premisa}\\
\mbox{Tomemos un $x$ que cumpla (2)}&(4)&\lnot Bxa\rightarrow Cx&\mbox{EP 2}\\
\mbox{Por (3), dicho $x$ cumple}&(5)&\lnot Cx&\mbox{EG 3}\\
\mbox{luego}&(6)&Bxa&\mbox{MT 4, 5}\\
\mbox{Aplicamos (1) a $x$ y $a$}&(7)&Bxa\rightarrow Sa&\mbox{EG 1}\\
\mbox{de donde}&(8)&Sa&\mbox{MP 6, 7}\\
\mbox{Como $a$ cumple $S$ tenemos que}&(9)&\exists y\ Sy&\mbox{IP 8}
\end{array} \)

Notemos que a partir de (4) no se podía generalizar respecto de \( x \) y que (8) puede verse como \( S_y^aSy \) para aplicar IP. La conclusión es correcta porque no tiene a \( x \) como variable libre.

[cerrar]

\( \exists y\forall x(Pxy\rightarrow Rxy), \forall yz\ Pyz\vdash \forall y\exists z\ Ryz \)

Solución

\( \begin{array}{lrll}
&(1)&\exists y\forall x(Pxy\rightarrow Rxy)&\mbox{Premisa}\\
&(2)&\forall yz\ Pyz&\mbox{Premisa}\\
\mbox{Tomamos un $y$ arbitrario}\\
\mbox{Llamemos $z$ a alguien que cumpla (1)}&(3)&\forall x(Pxz\rightarrow Rxz)&\mbox{EP 1}\\
\mbox{Aplicamos esto al $y$ que hemos fijado}&(4)&Pyz\rightarrow Ryz&\mbox{EG 3}\\
\mbox{Aplicamos (2) a nuestros $y$, $z$}&(5)&Pyz&\mbox{EG 2}\\
\mbox{Entonces}&(6)&Ryz&\mbox{MP 4, 5}\\
\mbox{Esto prueba que}&(7)&\exists z\ Ryz&\mbox{IP 6}\\
\mbox{Como $y$ era arbitrario}&(8)&\forall y\exists z Ryz&IG 7
\end{array} \)

A partir de (3) no se podía generalizar respecto de \( z \), pero no hay problema en ligar \( z \) en (7) mediante IP, ni en generalizar luego respecto de \( y \). La conclusión es correcta porque no tiene libre la variable \( z \).

[cerrar]

\( \exists x(Pxa\rightarrow Qx), \forall y\lnot Qy,\forall xy(\lnot Rxy\lor Pxy)\vdash \exists xy\lnot Rxy \)

Solución

\( \begin{array}{lrll}
&(1)&\exists x(Pxa\rightarrow Qx)&\mbox{Premisa}\\
&(2)&\forall y\lnot Qy&\mbox{Premisa}\\
&(3)&\forall xy(\lnot Rxy\lor Pxy)&\mbox{Premisa}\\
\mbox{Tomemos un $x$ que cumpla (1)}&(4)&Pxa\rightarrow Qx&\mbox{EP 1}\\
\mbox{Por (2) dicho $x$ cumple&(5)}&\lnot Qx&\mbox{EG 2}\\
\mbox{luego}&(6)&\lnot Pxa&\mbox{MT 4, 5}\\
\mbox{Aplicamos (3) a $x$ y $a$}&(7)&\lnot Rxa\lor Pxa&\mbox{EG 3 (dos veces)}\\
\mbox{Entonces}&(8)&\lnot Rxa&\mbox{MTP 6, 7}\\
\mbox{Por lo tanto}&(9)&\exists y \lnot Rxy&\mbox{IP 8}\\
&(10)&\exists xy\lnot Rxy&\mbox{IP 9}
\end{array} \)

A partir de (4) no se podía generalizar respecto de \( x \). Podemos ver (8) como \( S_y^a\lnot Rxy \) para aplicar IP. La conclusión es válida porque \( x \) no está libre en ella.

[cerrar]

[Carlos Ivorra]

En este mensaje demostraremos finalmente que el cálculo deductivo que hemos definido es justo lo que tiene que ser, es decir, que permite deducir de unas premisas todas las consecuencias que cabe esperar que puedan deducirse. Aunque en este artículo pretendo centrarme en los aspectos prácticos de lo que supone realizar deducciones en el cálculo deductivo de primer orden, demostrar el teorema de completitud es obligado para terminar de justificar que lo que estamos haciendo es correcto. Por ello este mensaje tendrá un nivel mucho más técnico que los anteriores y que los siguientes, y en realidad nada de lo que veremos aquí será necesario para lo que diremos después, por lo que el lector puede pasar directamente al mensaje siguiente si así lo prefiere.

Aunque la tarea que pretendemos realizar aquí ya ha sido perfilada en los mensajes anteriores, no está de más acabar de centrarla:

Si nos fijamos en cómo razonan en la práctica los matemáticos, veremos que en realidad nunca se cuidan de comprobar si, en efecto, todo cuanto dicen puede justificarse paso a paso aplicando oportunamente las reglas de inferencia de \( K_{\mathcal L} \), de si en tal paso tienen permitido aplicar o no IG, etc. Esto puede interpretarse de dos modos distintos: La interpretación más formal es que sus demostraciones son en realidad esbozos de demostración, lo suficientemente detallados como para que cualquiera que se lo proponga pueda desarrollarlos hasta convertirlos en auténticas demostraciones, paso a paso, en \( K_{\mathcal L} \). Pero la realidad es que cuando un matemático razona y valora si sus razonamientos son correctos o no, no tiene en cuenta para nada si tal o cual cosa se podrá justificar con EDI o con MB, sino que da por bueno un argumento si se convence de que si sus hipótesis son ciertas sus conclusiones también tienen que serlo. Pero ¿ciertas en qué sentido? El matemático no se plantea eso, pero no es difícil responder: se da por satisfecho cuando se convence de que si unos objetos (los que sean) cumplen sus hipótesis, necesariamente tienen que cumplir también sus conclusiones. Se puede decir que el matemático en la práctica razona semánticamente (es decir, preocupado de no pasar nunca de afirmaciones verdaderas a falsas) y no formalmente (preocupado de aplicar sólo unas reglas de razonamiento prefijadas).

El problema de razonar semánticamente (si uno quiere a la vez ser riguroso) es que en principio nos pone en la obligación de explicar de qué estamos hablando (es decir, de explicar qué objetos se supone que cumplen nuestras afirmaciones para que podamos decir con sentido ``si nuestras hipótesis son verdaderas\ldots") Lo que suele hacer el matemático si le piden este tipo de explicaciones es dar la respuesta fácil (y válida) de que, en realidad, se podría comprobar que todo cuanto razona puede ser formalizado en \( K_{\mathcal L} \), y eso basta para que sus razonamientos sean rigurosos. En efecto, esto resuelve el problema de fundamentar su trabajo ``sin agujeros", porque razonar formalmente en \( K_{\mathcal L} \) es un proceso objetivo y bien definido, pero, ¿de verdad hace falta recurrir al ``se podría comprobar"? ¿Es casualidad que todo lo que un matemático razona sin preocuparse de\( K_{\mathcal L} \) al final resulta que, en efecto, puede formalizarse en \( K_{\mathcal L} \)? ¿No puede justificarse que razonar semánticamente tiene sentido sin refugiarse en \( K_{\mathcal L} \)?

En este mensaje responderemos afirmativamente a las dos últimas preguntas. De hecho, veremos que la respuesta a la segunda lleva fácilmente a la respuesta a la primera. Notemos en primer lugar que para que tenga sentido razonar formalmente no es necesario dar un modelo explícito de los axiomas aceptados, porque el argumento no es: ``tales objetos concretos cumplen lo que digo", sino ``si unos objetos (los que sean) cumplen mis axiomas, también tienen que cumplir mis teoremas", por lo que sólo necesitamos justificar que existen unos objetos (los que sean) que cumplan mis axiomas.

Eso es precisamente lo que afirma el teorema siguiente, debido a Gödel (aunque la prueba que daremos se debe a Henkin):

Teorema: Una teoría axiomática es consistente si y sólo si tiene un modelo.

(Un modelo de una teoría axiomática es un modelo en el que sus axiomas, y por consiguiente sus teoremas, son verdaderos.) Por lo tanto, el único requisito para que el razonamiento semántico tenga sentido es garantizar que sus axiomas son consistentes (requisito obviamente necesario, por otra parte). Ahora bien, una cosa es que tenga sentido y otra distinta que razonar semánticamente sea lo mismo que razonar formalmente. El teorema que garantiza esto es el que se conoce propiamente como teorema de completitud semántica de Gödel:

Teorema de completitud semántica Si \( \Gamma \) es una colección de fórmulas de un lenguaje formal y \( \alpha \) es una fórmula tal que \( \Gamma\vDash \alpha \), es decir, tal que podemos razonar que \( \alpha \) es necesariamente verdadera en todo modelo en el que las fórmulas de \( \Gamma \) son verdaderas, entonces \( \Gamma\vdash \alpha \).

Esto significa que todo razonamiento semántico (de tipo: si las premisas son verdad entonces la conclusión es verdad) es formalizable en \( K_{\mathcal L} \).

Como el segundo teorema es una consecuencia sencilla del primero y el primero se usa bastante más que el segundo, es frecuente llamar también "teorema de completitud" al primero, aunque el nombre no le corresponde propiamente. Pasemos a demostrarlos.

Ante todo, es inmediato que si una teoría axiomática tiene un modelo entonces es consistente, pues en tal caso todos sus teoremas tienen que ser verdaderos en el modelo, luego hay sentencias que no pueden ser demostradas (las que son falsas en el modelo, recordemos que una sentencia y su negación no pueden ser ambas verdaderas en un modelo). El problema es demostrar el recíproco. Si llamamos \( \Gamma \) a la colección de los axiomas de una teoría formal, se trata de probar que si \( \Gamma \) es consistente (es decir, si de \( \Gamma \) no se deducen contradicciones), entonces \( \Gamma \) tiene un modelo.

En principio no hay inconveniente en que las fórmulas de \( \Gamma \) tengan variables libres, pero en primer lugar observamos que no perdemos generalidad si suponemos que no las tienen, es decir, que son sentencias.

Demostración

Para cada fórmula \( \alpha \), llamamos \( \alpha^c \) a su clausura universal, es decir, a la sentencia que resulta de añadir cuantificadores \( \forall x \) para todas sus variables libres.
Llamamos \( \Gamma^c \) a la colección de las clausuras universales de todas las fórmulas de \( \Gamma \). Observamos que si \( \Gamma \) es consistente, entonces \( \Gamma^c \) también lo es. En efecto, si \( \Gamma^c\vdash \alpha\land\lnot\alpha \), existirá un número finito de sentencias en \( \Gamma^c \), digamos \( \gamma_1^c,\ldots, \gamma_n^c \), tales que \( \gamma_1^c,\ldots, \gamma_n^c\vdash \alpha\land\lnot\alpha \) (porque en una deducción sólo puede aparecer una cantidad finita de premisas).

Pero \( \gamma_i\vdash \gamma_i^c \), sin más que aplicar IG las veces que haga falta, luego \( \Gamma\vdash \alpha\land\lnot\alpha \) (primero deducimos las sentencias \( \gamma_i^c \) a partir de las fórmulas \( \gamma_i \) y luego deducimos de éstas la contradicción). Pero esto es imposible porque estamos suponiendo a \( \Gamma \) consistente.

Así pues, \( \Gamma^c \) es consistente. Supongamos que podemos demostrar que \( \Gamma^c \) tiene un modelo \( M \). Entonces cada sentencia \( \gamma^c \) es verdadera en \( M \), pero esto implica que cada fórmula \( \Gamma \) es verdadera en \( M \), si más que aplicar un número finito de veces el hecho que sabemos, según el cual \( M\vDash \alpha \) si y sólo si \( M\vDash \forall x\alpha \) (por la definición de verdad que hemos dado).

[cerrar]

Así pues, basta probar que si \( \Gamma \) es una colección consistente de sentencias de un lenguaje formal, entonces \( \Gamma \) tiene un modelo.

Vamos a necesitar un hecho elemental sobre consistencia:

Teorema: Sea \( \Gamma \) una colección de fórmulas y \( \alpha \) una sentencia. Entonces \( \Gamma\cup\{\alpha\} \) es consistente si y sólo si no \( \Gamma\vdash \lnot\alpha \).

Demostración

Si \( \Gamma\vdash \lnot\alpha \), entonces \( \Gamma\cup\{\alpha\} \) es obviamente contradictoria, porque permite probar \( \alpha \) y \( \lnot\alpha \).

Si \( \Gamma\cup\{\alpha\} \) es contradictoria entonces a partir de sus premisas se puede demostrar cualquier cosa, en particular \( \Gamma\cup\{\alpha\}\vdash \lnot\alpha \). Como \( \alpha \) es una sentencia, en la deducción no se generaliza respecto de variables libres en \( \alpha \) (no las hay), luego podemos aplicar el teorema de deducción y concluir que \( \Gamma\vdash \alpha\rightarrow\lnot\alpha \), pero esto equivale a \( \lnot\alpha\lor\lnot\alpha \) (por EDI) y a su vez a \( \lnot\alpha \) (por ED).

[cerrar]

Notemos que este resultado se usa de forma habitual casi sin nombrarlo. Por ejemplo, es lo mismo decir que la hipótesis del continuo es consistente con ZFC que decir que no puede demostrarse que es falsa.

Definición Diremos que una colección de sentencias \( \Gamma \) es maximalmente consistente si es consistente y para toda sentencia \( \alpha \) se cumple que \( \Gamma\cup\{\alpha\} \) es contradictoria.

Notemos que si una colección de sentencias \( \Gamma \) tiene un modelo \( M \), entonces \( \Gamma \) se extiende a una colección maximalmente consistente de sentencias. Basta tomar la colección de todas las sentencias verdaderas en \( M \). Dicha colección contiene a toda sentencia \( \alpha \) o bien a su negación, luego si intentamos añadirle una sentencia más, pasamos a una teoría contradictoria, pues contendrá la sentencia añadida y su negación.

De lo que se trata es de probar que toda colección consistente de sentencias puede extenderse a una colección maximalmente consistente (sin suponer que tiene un modelo) y usar esta extensión para construir el modelo.

Antes de ello observamos algunas consecuencias sencillas de la definición:

Teorema Sean \( \Gamma \) una colección maximalmente consistente de sentencias de un lenguaje formal y sean \( \alpha,\beta \) dos sentencias de dicho lenguaje. Entonces:

a) \( \Gamma\vdash \alpha \) si y sólo si \( \alpha \) está en \( \Gamma \).

b) \( \Gamma \) contiene a todos los teoremas lógicos (sin variables libres).

c) \( \lnot\alpha \) está en \( \Gamma \) si y sólo si \( \alpha \) no está en \( \Gamma \).

d) \( \alpha\rightarrow\beta \) está en \( \Gamma \) si y sólo si \( \alpha \) no está en \( \Gamma \) o \( \beta \) está en \( \Gamma \).

e) \( \alpha\lor\beta \) está en \( \Gamma \) si y sólo si \( \alpha \) está en \( \Gamma \) o \( \beta \) está en \( \Gamma \).

f) \( \alpha\land\beta \) está en \( \Gamma \) si y sólo si \( \alpha \) y \( \beta \) están en \( \Gamma \).

g) \( \alpha\leftrightarrow \beta \) está en \( \Gamma \) si y sólo si \( \alpha \) y \( \beta \) están ambas en \( \Gamma \) o ninguna lo está.

Notemos que este teorema es puramente sintáctico, pero tiene ya un "sabor" semántico, en el sentido de que está poniendo de manifiesto la interpretación de los conectores lógicos.

Demostración

a) Si \( \Gamma\vdash \alpha \), entonces no \( \Gamma\vdash \lnot\alpha \) (porque \( \Gamma \) es consistente), luego \( \Gamma\cup\{\alpha\} \) es consistente (por el teorema anterior), luego \( \alpha \) está en \( \Gamma \) (por ser maximalmente consistente). El recíproco es obvio.

b) es un caso particular de a)

c) Si \( \lnot\alpha \) está en \( \Gamma \) entonces \( \alpha \) no puede estar en \( \Gamma \) (por la consistencia)

Si \( \alpha \) no está en \( \Gamma \), entonces \( \Gamma\cup\{\alpha\} \) es contradictorio (por la consistencia maximal), luego \( \Gamma\vdash\lnot\alpha \) (por el teorema anterior), luego \( \lnot\alpha \) está en \( \Gamma \) por a).

d) Si \( \alpha\rightarrow\beta \) está en \( \Gamma \) y \( \alpha \) está en \( \Gamma \), entonces \( \Gamma\vdash \beta \), luego \( \beta \) está en \( \Gamma \).

Si \( \alpha \) no está en \( \Gamma \) o \( \beta \) está en \( \Gamma \), por c) tenemos que \( \lnot\alpha \) está en \( \Gamma \) o \( \beta \) está en \( \Gamma \). Por consiguiente \( \Gamma\vdash \lnot\alpha \) o \( \Gamma\vdash \lnot\alpha \). En ambos casos \( \Gamma\vdash (\alpha\rightarrow\beta) \), luego \( \alpha\rightarrow\beta \) está en \( \Gamma \).

Los apartados siguientes se deducen de los dos anteriores por las definiciones de los conectores.

[cerrar]

Necesitamos resultados análogos a los anteriores para los cuantificadores, pero para ello no basta la consistencia maximal:

Definición: Una colección \( \Gamma \) de sentencias de un lenguaje formal es ejemplificada si cuando \( \exists x\alpha \) está en \( \Gamma \) existe un designador \( t \) (un término sin variables libres) tal que \( S_x^t\alpha \) está en \( \Gamma \).

Es decir, si siempre que \( \Gamma \) afirma la existencia de un \( x \) que cumple algo, también pone un ejemplo de un \( t \) concreto que cumple ese algo.

Teorema Sea \( \Gamma \) una colección de sentencias maximalmente consistente y ejemplificada y sea \( \alpha \) una fórmula en la que a lo sumo esté libre la variable \( x \)

a) \( \exists x\alpha \) está en \( \Gamma \) si y sólo si existe un designador \( t \) del lenguaje formal considerado tal que \( S_x^t\alpha \) está en \( \Gamma \).

b) \( \forall x\alpha \) está en \( \Gamma \) si y sólo si para todo designador \( t \) del lenguaje formal se cumple que \( S_x^t\alpha \) está en \( \Gamma \).

Demostración

a) Si \( \exists x\alpha \) está en \( \Gamma \) hay un designador \( t \) tal que \( S_x^t\alpha \) está en \( \Gamma \) por definición de ejemplificación.

Si \( S_x^t\alpha \) está en \( \Gamma \), entonces por IP se cumple que \( \Gamma\vdash \exists x\alpha \), luego \( \exists x\alpha \) está en \( \Gamma \) por el teorema anterior.

b) Si \( \forall x\alpha \) está en \( \Gamma \) y \( t \) es un designador, por EG se cumple que \( \Gamma\vdash S_x^t\alpha \), luego \( S_x^t\alpha \) está en \( \Gamma \) por el teorema anterior.

Si \( S_x^t\alpha \) está en \( \Gamma \) para todo designador \( t \), entonces el teorema anterior nos da que \( \lnot S_x^t\alpha\equiv S_x^t\lnot\alpha \) no está en \( \Gamma \), para todo \( t \), luego por a) \( \exists x\lnot\alpha \) no está en \( \Gamma \), luego \( \lnot\exists\lnot\alpha \) está en \( \Gamma \) por el teorema anterior, luego \( \Gamma\vdash \forall x\alpha \) por NP, luego \( \forall x\alpha \) está en \( \Gamma \) por el teorema anterior.

[cerrar]

Nuestro objetivo es obtener una colección maximalmente consistente y ejemplificada de sentencias a partir de una colección consistente. Para ello necesitamos el siguiente resultado técnico:

Teorema Si una constante \( c \) no está en una fórmula \( \alpha \), la variable \( x \) no está ligada en \( \alpha \) y \( \vdash S_x^c\alpha \), entonces \( \vdash\alpha \).

La demostración de este teorema es una rutinaria inducción sobre la longitud de una demostración de \( S_x^c\alpha \) como muchas otras que hemos visto. Remito a mi libro de lógica para la prueba (teorema 4.10). La idea de fondo es que en una demostración da igual referirse a un objeto con una constante o con una variable que no se use para nada más, de modo que si en la demostración con la constante se sustituye sistemáticamente ésta por una variable "nueva", que no aparezca en la prueba para nada, lo que sale sigue siendo una demostración.

A partir de aquí demostramos el resultado que nos permite ejemplificar una sentencia:

Teorema Si \( \Gamma\cup\{\exists x\alpha\} \) es una colección consistente de sentencias de un lenguaje formal y \( c \) es una constante que no esté en ninguna de sus sentencias, entonces \( \Gamma\cup\{\exists x\alpha,S_x^c\alpha\} \) es consistente.

Demostración

Si \( \Gamma\cup\{\exists x\alpha,S_x^c\alpha\} \) es contradictoria, por el teorema elemental probado más arriba \( \Gamma\cup\{\exists x\alpha\}\vdash \lnot S_x^c\alpha \). Entonces existen \( \gamma_1,\ldots, \gamma_n \) en \( \Gamma \) tales que

\( \gamma_1\land\cdots \land \gamma_n\land\exists x\alpha\vdash \lnot S_x^c\alpha \).

Sea \( y \) una variable que no esté en ninguna de las sentencias consideradas. Entonces

\( \gamma_1\land\cdots \land \gamma_n\land\exists x\alpha\vdash S_y^cS_x^y\lnot\alpha \),

luego por el teorema de deducción

\( \vdash \gamma_1\land\cdots\land \gamma_n\land \exists x\alpha\rightarrow S_y^cS_x^y\lnot\alpha \),

y esto equivale a

\( \vdash S_y^c(\gamma_1\land\cdots\land \gamma_n\land \exists x\alpha\rightarrow S_x^y\lnot\alpha) \),

ya que \( y \) no aparece en \( \gamma_1\land\cdots\land \gamma_n\land \exists x\alpha \). Por el teorema anterior

\( \vdash \gamma_1\land\cdots\land \gamma_n\land \exists x\alpha\rightarrow S_x^y\lnot\alpha \),

luego \( \Gamma\cup\{\exists x\alpha\}\vdash \lnot S_x^y\alpha \). Aplicando IG y NP obtenemos que \( \Gamma\cup\{\exists x\alpha\}\vdash \lnot \exists y S_x^y\alpha \), pero esto es equivalente a \( \Gamma\cup\{\exists x\alpha\}\vdash \lnot \exists x\alpha \), con lo que \( \Gamma\cup\{\exists x\alpha\} \) resulta ser contradictoria.

[cerrar]

Ahora viene el teorema fundamental, el núcleo del argumento que prueba el teorema de completitud. Si alguien se pregunta qué necesitamos suponer sobre las colecciones metamatemáticas que estamos usando, la respuesta es muy simple: ni más ni menos que lo necesario para reconocer que el argumento del teorema siguiente tiene sentido y es concluyente. En este teorema aparecen las colecciones de objetos más generales que hemos necesitado o vamos a necesitar.

Teorema Sea \( \mathcal L \) un lenguaje formal, sea \( \mathcal L' \) el lenguaje formal que resulta de añadir a \( \mathcal L \) una sucesión de constantes \( d_0,d_1,d_2,\ldots \), sea \( \Gamma \) una colección consistente de sentencias de \( \mathcal L \). Entonces existe una colección \( \Gamma_\infty \) maximalmente consistente y ejemplificada de sentencias de \( \mathcal L \) que contiene a \( \Gamma \).

Demostración

Fijamos una enumeración \( \alpha_0,\alpha_1,\alpha_2,\ldots \) de todas las sentencias de \( \mathcal L' \). Dicha enumeración puede definirse explícitamente, de modo que la pueda calcular incluso un ordenador, pero no servirá de mucho, porque el argumento que nos ocupa pronto se volverá no constructivo.

Llamemos \( \Gamma_0 \) a la colección de sentencias dada, que por hipótesis es consistente y vamos a definir recurrentemente una sucesión de colecciones consistentes de sentencias \( \Gamma_n \). Supuesto que hayamos definido ya \( \Gamma_n \) y sea consistente, definimos \( \Gamma_{n+1} \) distinguiendo tres casos:

1) Si \( \Gamma_n\cup\{\alpha_n\} \) es contradictoria, entonces \( \Gamma_{n+1}=\Gamma_n \), que obviamente será consistente.

2) Si \( \Gamma_n\cup\{\alpha_n\} \) es consistente y \( \alpha_n \) no es de la forma \( \exists x\beta \), entonces \( \Gamma_{n+1}=\Gamma_n\cup\{\alpha_n\} \), que obviamente será consistente.

3) Si \( \Gamma_n\cup\{\alpha_n\} \) es consistente y \( \alpha_n\equiv \exists x\beta \), entonces observamos que en  \( \Gamma_n\cup\{\alpha_n\} \) sólo puede haber un número finito de constantes \( d_k \), ya que en \( \Gamma \) no hay ninguna y en cada paso de la construcción añadimos sólo una o dos sentencias nuevas (en los casos anteriores una, en éste añadiremos dos), luego en \( \Gamma_n \) sólo hay un número finito de fórmulas que pueden contener constantes \( d_k \). Por ello, podemos tomar el mínimo \( k \) tal que la constante \( d_k \) no aparece en ninguna fórmula de \( \Gamma_n\cup\{\alpha_n\} \). Definimos \( \Gamma_{n+1}=\Gamma_n\cup\{\exists x\beta, S_x^{d_k}\beta\} \), que es consistente por el teorema anterior.

Así tenemos definidas todas las colecciones \( \Gamma_n \), cada una de las cuales extiende a la anterior, y todas son consistentes.

Definimos \( \Gamma_\infty \) como la unión de todas las colecciones \( \Gamma_n \). Claramente contiene a \( \Gamma \) y es consistente, pues si de \( \Gamma_\infty \) se dedujera una contradicción se deduciría de un número finito de premisas, que estarían todas contenidas en un \( \Gamma_n \), con \( n \) suficientemente grande, y entonces \( \Gamma_n \) sería contradictorio.

Más aún, \( \Gamma_\infty \) es maximalmente consistente, pues si una sentencia \( \alpha \) de \( \mathcal L' \) no está en \( \Gamma_\infty \), será de la forma \( \alpha\equiv\alpha_n \), para algún \( n \), y si no está en \( \Gamma_{n+1} \) es porque \( \Gamma_n\cup\{\alpha\} \) es contradictoria, luego \( \Gamma_\infty\cup\{\alpha\} \) también lo es.

Por último veamos que \( \Gamma_\infty \) es ejemplificada. Si \( \exists x\alpha \) está en \( \Gamma_\infty \), entonces \( \exists x\alpha\equiv \alpha_n \), para cierto \( n \). Como \( \Gamma_n\cup\{\exists x\alpha\} \) está contenida en \( \Gamma_\infty \), tiene que ser consistente, luego por construcción \( \Gamma_{n+1} \) contiene a \( S_x^{d_k}\alpha \), y la constante \( d_k \) es un designador que cumple la definición de ejemplificación.

[cerrar]

Observaciones El lector no debe dejarse confundir por la notación conjuntista que hemos empleado (hemos hablado de uniones infinitas y otras cosas) que sólo sirve para simplificar la exposición. El argumento de la prueba es, en cierto sentido, elemental: tenemos numeradas las sentencias de \( \mathcal L' \) y lo que hacemos es ir recorriéndolas todas una por una y decidiendo si la añadimos o no a la extensión de \( \Gamma \) que vamos construyendo: si cada sentencia es consistente con las que ya tenemos, la añadimos (y si es existencial la ejemplificamos de paso) y si es contradictoria con las que ya tenemos la rechazamos. Eso es todo, sin necesidad de considerar uniones ni historias.

El punto delicado es que puede probarse que no existe un algoritmo para decidir si una colección de fórmulas es consistente o no, aunque sea finita. Por lo tanto, en cada paso tenemos un criterio muy concreto y definido que determina si cada sentencia \( \alpha_n \) tiene que ser añadida o no a la colección que estamos definiendo, pero no sabemos comprobar en la práctica si \( \alpha_n \) lo satisface o no. Esto hace que \( \Gamma_\infty \) esté perfectamente definida y que sus elementos dependan únicamente de la ordenación que hemos dado  a las fórmulas (si \( \alpha \) y \( \lnot\alpha \) son consistentes con \( \Gamma \), añadiremos una o la otra según cuál aparezca antes en la enumeración), pero en general no podemos decir cuáles son sus elementos.

Ahora ya podemos probar que toda colección consistente de sentencias tiene un modelo.

Demostración

Sea \( \Gamma \) una colección consistente de sentencias de un lenguaje \( \mathcal L \). Sea \( \mathcal L' \) el lenguaje que resulta de añadir la sucesión de constantes del teorema anterior. Basta probar que la colección \( \Gamma_\infty \) dada por el teorema tiene un modelo \( M \), pues entonces \( M \) también es un modelo de \( \Gamma \) (en principio sobre el lenguaje \( \mathcal L' \), pero si "nos olvidamos" de las nuevas constantes, podemos ver a \( M \) como un modelo de \( \mathcal L \) en el que las fórmulas de \( \Gamma \) siguen siendo verdaderas, pues en ellas no están las constantes nuevas y su interpretación en \( M \) es irrelevante para que sean o no verdaderas.

Por consiguiente, podemos suponer que \( \Gamma \) es  maximalmente consistente y ejemplificada.

Sea \( T \) la colección de todos los designadores de \( \mathcal L \) y definimos en \( T \) la relación dada por \( t_1\sim t_2 \) si y sólo si \( t_1=t_2 \) está en \( \Gamma \). Veamos que se trata de una relación de equivalencia.

Por ejemplo, si \( t_1\sim t_2 \) y \( t_2\sim t_3 \), entonces \( t_1\sim t_3 \). En efecto, lo que tenemos es que \( t_1=t_2, t_2=t_3 \) están en \( \Gamma \), luego por TI \( \Gamma\vdash t_1=t_3 \), luego \( t_1=t_3 \) está en \( \Gamma \) por la consistencia maximal. La reflexividad y la simetría se prueban exactamente igual.

Llamaremos \( U \) a la colección de todas las clases de equivalencia de designadores de \( \mathcal L \) respecto a la relación de equivalencia que acabamos de definir y vamos a definir un modelo \( M \) de universo \( U \) (notemos que podemos definir explícitamente una enumeración de \( T \), de donde se deduce que \( U \) es numerable, aunque no podemos encontrar una enumeración explícita de sus elementos porque eso supondría conocer de forma efectiva qué sentencias están en \( \Gamma \), y en general eso no es posible).

El modelo \( M \) (de universo \( U \)) se define como sigue:

1) Si \( c \) es una constante de \( \mathcal L \) su interpretación es su clase de equivalencia: \( M(c)=[c] \).

2) Si \( R \) es un relator \( n \)-ádico en \( \mathcal L \), su interpretación es la relación \( \bar R \) dada por

\( \bar r([t_1],\ldots, [t_n]) \) si y sólo si \( Rt_1\cdots t_n \) está en \( \Gamma \).

3) Si \( f \) es un funtor \( n \)-adico en \( \mathcal L \), su interpretación es la función \( \bar f \) dada por \( \bar f([t_1],\ldots, [t_n])\equiv [ft_1\cdots t_n] \).

Hay que comprobar que \( \bar R \) y \( \bar f \) están bien definidas, en el sentido de que, en el caso de \( \bar R \), si \( [t_1]\equiv [t'_1],\ldots [t_n]\equiv [t'_n] \), entonces \( Rt_1\cdots t_n \) está en \( \Gamma \) si y sólo si \( Rt'_1\cdots t'_n \) está en \( \Gamma \).

En efecto, tenemos que las sentencias \( t_i=t'_i \) están en \( \Gamma \), luego claramente

\( \Gamma\vdash Rt_1\cdots t_n\leftrightarrow Rt'_1\cdots t'_n \),

luego, por las propiedades de las colecciones maximalmente consistentes, la coimplicación está en \( \Gamma \) y a su vez esto implica que una parte está en \( \Gamma \) si y sólo si lo está la otra, que era lo que teníamos que probar.

Más aún, cuando el relator \( R \) es la igualdad, la relación \( \bar R \) es la dada por \( \bar R([t_1],[t_2]) \) si y sólo si \( t_1=t_2 \) está en \( \Gamma \) si y sólo si \( [t_1]\equiv [t_2] \), luego la igualdad se interpreta como la relación de identidad, tal y como exige la definición de modelo.

La prueba de que las funciones están bien definidas es análoga.

Ahora es fácil ver, por inducción sobre la longitud de un designador \( t \), que \( M(t)=[t] \), es decir, que cada designador denota a su propia clase de equivalencia. En efecto, para las constantes se cumple por la definición del modelo, y sólo falta ver que si vale para unos términos \( t_1,\ldots, t_n \) vale para \( ft_1\cdots t_n \), lo cual se cumple por la definición de \( \bar f \).

Por último, basta probar que si \( \alpha \) es una sentencia de \( \mathcal L \), entonces \( M\vDash \alpha \) si y sólo si \( \alpha \) está en \( \Gamma \), con lo que \( M\vDash \Gamma \).

Esto se demuestra por inducción sobre el número de signos lógicos (\( \lnot, \rightarrow, \forall \)) que contiene \( \alpha \). Si \( \alpha \) no tiene signos lógicos debe ser de la forma \( Rt_1\cdots t_n \), y entonces el resultado es cierto por definición de \( \bar R \).

Si vale para \( \alpha \), es trivial que vale para \( \lnot\alpha \):

\( M\vDash \not\alpha \) si y sólo si no \( M\vDash \alpha \) si y sólo si \( \alpha \) no está en \( \Gamma \) si y sólo si \( \lnot\alpha \) está en \( \Gamma \).

Análogamente se razona el caso de \( \alpha\rightarrow \beta \).

Supongamos por último que \( \alpha\equiv \forall x\beta \), y aquí hemos de tener cuidado porque \( \beta \) puede tener libre la variable \( x \), luego no es una sentencia y no podemos aplicarle la hipótesis de inducción.

\( M\vDash \forall x\alpha \) si y sólo si para toda valoración \( v \) y todo [t] de \( M \) se cumple \( M\vDash \beta[v_x^{[t]}] \), pero sabemos que \( [t]=M(t)[v] \), luego por el teorema sobre satisfacción de sustituciones que probamos al definir la sustitución esto equivale a que \( M\vDash S_x^t\beta[v] \) (para toda \( v \) y todo \( t \)), luego esto equivale a que \( M\vDash S_x^t \) para todo \( t \). Pero \( S_x^t \) es una sentencia con un signo lógico menos que \( \alpha \) (un cuantificador menos, porque los designadores no contienen signos lógicos). Por lo tanto podemos aplicarle la hipótesis de inducción, y esto equivale a que \( S_x^t\beta \) esté en \( \Gamma \) para todo designador \( t \) y por el teorema sobre colecciones ejemplificadas maximalmente consistentes, esto equivale a que \( \forall x\beta \) esté en \( \Gamma \).

[cerrar]

Notemos que hemos demostrado algo un poco más fuerte:

Teorema: Si una colección \( \Gamma \) de fórmulas es consistente, entonces tiene un modelo (de universo) numerable.

La numerabilidad tiene consecuencias notables a la hora de entender la lógica de la teoría de conjuntos, pero no vamos a entrar en ello. De momento lo que nos interesa es que ya hemos probado que, si tenemos una teoría axiomática consistente, tiene sentido razonar semánticamente en ella, pues existen unos objetos (con las relaciones y funciones adecuadas) para los cuales los axiomas son verdaderos, luego tiene sentido plantearse qué fórmulas son necesariamente verdaderas en un modelo en el que los axiomas sean verdaderos, y eso es razonar semánticamente (razonar informalmente con afirmaciones expresadas como fórmulas de un lenguaje formal).

Ahora nos falta probar que razonar semánticamente es equivalente a razonar formalmente, es decir, vamos a demostrar el teorema de completitud. La prueba es elemental:

Spoiler

Si tenemos \( \Gamma\vDash \alpha \), es decir, si tenemos un argumento que nos convence de que \( \alpha \) tiene que ser necesariamente verdadera sobre todo modelo de \( \Gamma \), veamos qué pasaría si no \( \Gamma\vdash \alpha \). Entonces tampoco \( \Gamma\vdash \alpha^c \) (porque de \( \alpha \) se deduce su clausura universal aplicando IG tantas veces como variables libres tenga), y tampoco \( \Gamma\vdash \lnot\lnot\alpha^c \), luego por el teorema elemental sobre consistencia tenemos que \( \Gamma\cup\{\lnot\alpha^c\} \) es consistente, luego tiene un modelo \( M \), es decir, tenemos un modelo en el que las fórmulas de \( \Gamma \) son verdaderas, pero no \( M\vdash \alpha^c \), luego tampoco \( M\vDash \alpha \), que es equivalente. Esto contradice la hipótesis.

[cerrar]

Terminamos con un par de observaciones. La primera es que hemos demostrado lo siguiente:

Teorema de Löwenheim-Skolem Si una teoría axiomática tiene un modelo, entonces tiene un modelo numerable.

La segunda es que cuando definimos el concepto de fórmula lógicamente válida advertimos de que debíamos entenderlo como que una fórmula \( \alpha \) es lógicamente válida, no si es verdadera en todo modelo, sino si tenemos un argumento que nos convence de que tiene que ser verdadera en todo modelo. Ahora podemos simplificar esto. Hay dos posibilidades: o bien \( \vdash \alpha \) o bien no \( \vdash\alpha \). En el primer caso existe un razonamiento que nos convence de que \( \alpha \) tiene que ser verdadera en todo modelo (el razonamiento informal codificado por una demostración formal de \( \alpha \)). En el segundo caso sabemos que \( \lnot\alpha \) es consistente, luego tiene un modelo, de modo que existe un modelo en el que \( \alpha \) no es verdadera.

En definitiva, el concepto de fórmula lógicamente válida ya no depende de si sabemos o no encontrar un argumento. Podemos decir que una fórmula es lógicamente válida si es verdadera en todo modelo, pues, o bien existe un argumento que lo justifique (lo conozcamos o no) o bien existe un modelo que lo refuta (lo conozcamos o no).

[Carlos Ivorra]

Nadie puede tener una idea clara de la razón de ser de toda la teoría que hemos presentado hasta aquí sin comprender el papel que desempeña en la fundamentación de la teoría de conjuntos. Como no se trata aquí de entrar en los detalles de las teorías axiomáticas de conjuntos, vamos a plantear una muy simple, que es suficiente para ilustrar las ideas que queremos discutir aquí:

Definición El lenguaje de la teoría de conjuntos \( \mathcal L_{\rm tc} \) es el  lenguaje formal cuyo único signo eventual es un relator diádico que representaremos por \( \in \) y lo llamaremos {\it relator de pertenencia.} Escribiremos \( t_1\notin t_2\equiv \lnot t_1\in t_2 \). También es frecuente abreviar \(
\forall u\in x\,\alpha\equiv \forall u(u\in x\rightarrow \alpha),\ \  \exists u\in x\, \alpha\equiv \exists u(u\in x\land \alpha).
 \)

La teoría básica de conjuntos es la teoría axiomática T cuyos axiomas son las sentencias siguientes:

\( \begin{array}{ll}
\mbox{Extensionalidad}&\forall xy(\forall u(u\in x\leftrightarrow u\in y)\rightarrow x=y)\\[1mm]
\mbox{Vacío}&\exists x\forall u\ u\notin x\\[1mm]
\mbox{Par}&\forall xy\exists z\forall u(u\in z\leftrightarrow u=x\lor u=y)\\[1mm]
\mbox{Unión}&\forall x\exists y\forall u(u\in y\leftrightarrow \exists v(u\in v\land v\in x))\\[1mm]
\mbox{Diferencia}&\forall xy\exists z\forall u(u\in z\leftrightarrow u\in x\land u\notin y)
\end{array}
 \)

Vamos a analizar esta definición. Ante todo observemos que todo lo dicho tiene sentido. La definición anterior determina exactamente qué es una fórmula del lenguaje \( \mathcal L_{\rm tc} \), qué es lo que significa "ser un axioma" de \( \mathcal L_{\rm tc} \) y, por consiguiente, está perfectamente determinado qué significa "ser un teorema" de \( \mathcal L_{\rm tc} \). Podemos ponernos ya mismo a demostrar formalmente teoremas de \( \mathcal L_{\rm tc} \) y todo esto podemos hacerlo sin responder en ningún momento a la pregunta de "qué significa \( \in \)".

Más aún, vamos a establecer, no sin cierta dosis de cinismo, que cuando leamos sentencias de \( \mathcal L_{\rm tc} \), cada vez que nos encontremos con un \( \forall x \) leeremos "para todo conjunto \( x \)", cada vez que nos encontremos con un \( \exists x \) leeremos "existe un conjunto \( x \) tal que", y cuando nos encontremos con una fórmula \( x\in y \) leeremos que "el conjunto \( x \) pertenece a (o es un elemento de) el conjunto \( y \)", y si alguien nos pregunta qué queremos decir cuando hablamos de "conjuntos" y de "pertenencia", le responderemos que nada, que es sólo una forma cómoda de leer las fórmulas de \( \mathcal L_{\rm tc} \). Y lo bueno es que nadie podrá acusarnos de falta de rigor.

Más concretamente, podemos leer el axioma de extensionalidad diciendo que "si dos conjuntos \( x \) e \( y \) tienen los mismos elementos, entonces son iguales", y podemos trabajar con esta afirmación, y deducir consecuencias lógicas de ella y los demás axiomas, sin necesidad de dar explicaciones sobre qué son esos conjuntos y esa relación de pertenencia de la que se supone que estamos hablando.

Si nos cansamos de ser cínicos y preferimos ser algo más conciliadores, podemos decir que suponemos que existen unos objetos llamados conjuntos, entre los cuales está definida una relación de pertenencia, y de forma que, cuando consideramos el modelo de \( \mathcal L_{\rm tc} \) cuyo universo es la colección de todos esos conjuntos e interpretamos el relator \( \in \) como la relación de pertenencia, todos los axiomas de T resultan ser verdaderos.

Pero si nos preguntan si tenemos garantías de que existen realmente tales objetos y tal relación, o si podemos poner algún ejemplo de objetos que realmente cumplan esos axiomas, podemos responder sin vacilar que no necesitamos responder a ninguna de esas preguntas para trabajar rigurosamente con la teoría~ T, porque para razonar formalmente no es necesario conocer los objetos sobre los que presuntamente estamos razonando, sino que basta con respetar las reglas sintácticas de \( \mathcal L_{\rm tc} \) y las reglas deductivas de \( K_{\mathcal L_{\rm tc}} \).

En resumen: todo el aparato lógico que hemos montado hasta aquí nos sirve ahora para que podamos hablar de conjuntos y de pertenencia sin necesidad de responder a ninguna pregunta embarazosa sobre qué son los conjuntos y qué es la pertenencia. Nos basta con suponer que los conjuntos y la pertenencia cumplen los axiomas de T y respetar en todo momento las reglas de deducción formal que hemos establecido.

En la práctica, cuando uno ya está habituado a estas situaciones y no necesita dar tantas vueltas a estos hechos, abrevia diciendo simplemente que los conceptos de "conjunto" y "pertenencia" son los conceptos primitivos (o no definidos) de la teoría T.

La lógica formal tendrá mil virtudes, pero si hoy tiene el grado de desarrollo que tiene, es porque sirve precisamente para esto: para justificar que uno se ponga a hablar de cosas sin decir de qué cosas está hablando y sin que nadie le pueda reprochar falta de rigor por ello. La fundamentación de las matemáticas consiste esencialmente en eso: en poder hablar de conjuntos y de pertenencia sin verse en la necesidad (o en el aprieto) de explicar qué significan exactamente estas palabras. De ahí el énfasis que hemos puesto en todo momento en la posibilidad de definir formalmente con rigor todos los conceptos sintácticos (fórmulas, axiomas, teoremas, etc.) sin hacer referencia en ningún momento a modelos, porque cuando llega el momento de introducir una teoría de conjuntos no sabríamos cómo justificar que nuestros axiomas tienen un modelo (en el caso de T es relativamente fácil hacerlo, pero en las teorías de conjuntos "para adultos" es práctica y teóricamente imposible). Lo bueno, lo que valdría su peso en oro si no fuera porque las buenas ideas no pesan, es que podemos decir con toda la autosuficiencia del mundo: "ni sé decirte nada sobre qué es un conjunto o qué cosas pueden formar un modelo de la teoría de conjuntos, ni tengo necesidad alguna de hacerlo para desarrollar con perfecto rigor formal toda la matemática".

Una vez eximidos de la necesidad de explicar qué es un conjunto o qué es la relación de pertenencia, nada nos impide tratar de formarnos una idea sobre qué características tendrían que tener unos objetos para cumplir los axiomas de~T. Si \( x \) es un conjunto, entonces podemos hablar de la colección (en el sentido intuitivo de la palabra) de todos los conjuntos que cumplen \( u\in x \). En principio, esa colección recibe el nombre de la extensión de \( x \), y lo que dice el axioma de extensionalidad es que si dos conjuntos tienen la misma extensión, entonces son iguales.

De aquí obtenemos dos cosas: por una parte, cada conjunto (en el sentido técnico, no definido de la palabra) tiene asociada una colección de objetos (su extensión) y en segundo lugar está completamente determinado por ella, de modo que lo único que diferencia a un conjunto de otro es que haya otros conjuntos que pertenezcan a uno y no al otro. Por lo tanto, podemos identificar a un conjunto con su extensión. Podemos considerar que, cuando hablamos de un conjunto, en realidad estamos hablando de su extensión. Según esto, los conjuntos son colecciones de objetos (colecciones de conjuntos). Eso sí, sería ingenuo y catastrófico identificar "conjunto" y "colección de conjuntos". Si \( M \) es un modelo de T y consideramos unos cuantos objetos de \( M \), nadie nos asegura que exista un conjunto (es decir, un elemento de \( M \)) cuya extensión sea precisamente la colección de objetos de \( M \) que hemos tomado, ni tampoco hay ninguna condición sencilla que nos permita decir: "de entre las colecciones de objetos de \( M \), son conjuntos las que cumplen tal cosa". El concepto de "conjunto" es un concepto técnico: son conjuntos las colecciones de conjuntos que conviene que lo sean para que se cumplan los axiomas, y no lo son las que no conviene que lo sean. Y punto. De hecho, sucede que que en todo modelo de T hay colecciones de conjuntos que no son (extensiones de) conjuntos.

En el mensaje siguiente desarrollaremos un poco la teoría T para tratar de describir el papel de la lógica que hemos estudiado (y de algún concepto que tenemos pendiente de introducir) en el razonamiento matemático. La teoría T parece poca cosa, pero sus axiomas bastan para definir los números naturales (aunque no la suma de números naturales).

[Carlos Ivorra]

Hasta ahora hemos analizado lo que hay de fondo en las demostraciones formales que hacen los matemáticos, pero los matemáticos no sólo demuestran, sino que también definen. La teoría de conjuntos que usan habitualmente los matemáticos (al igual que le sucede a la teoría T que hemos expuesto en el mensaje anterior) no tiene más conceptos primitivos que los de "conjunto" y "pertenencia". Sin embargo, los matemáticos tratan con un rico abanicos de conceptos. ¿De dónde salen? ¿Cómo se interpreta formalmente la introducción de un nuevo concepto?

Por poner un caso muy simple, si trabajamos en la teoría T un matemático podría empezar diciendo:

Definición Diremos que un conjunto \( x \) es un subconjunto de otro conjunto \( y \) (y lo representaremos por \( x\subset y \)) si todo elemento de \( x \) es también un elemento de \( y \).

¿Cómo se formaliza esto, que no es un teorema?

Hay esencialmente dos formas distintas de concebir una definición. Una es considerar que estamos añadiendo un nuevo signo al lenguaje formal de la teoría, en este caso un relator diádico \( x\subset y \), y el nuevo relator se acompaña de un nuevo axioma que regula su uso:

\( \forall xy(x\subset y\leftrightarrow \forall u(u\in x\rightarrow u\in y)) \)

Según esta concepción, las definiciones son axiomas. Ahora bien, está claro que no pueden considerarse axiomas "normales", en el sentido de que no es lo mismo añadir como axioma la definición de inclusión que añadir como axioma la hipótesis del continuo. Las definiciones, así entendidas, son lo que los lógicos llaman "axiomas inesenciales", lo cual viene a decir que no añaden información a la teoría, y con precisión significa que todo modelo de la teoría puede dotarse de una nueva relación que hace verdadero al nuevo axioma. De este modo, los axiomas inesenciales no restringen las interpretaciones posibles de la teoría (al contrario que los axiomas esenciales, como la hipótesis del continuo: si un modelo no la cumple, no se puede hacer nada para que la cumpla, y es un modelo que se descarta al añadir el axioma adicional).

Sin embargo, hay una forma conceptualmente mucho más simple de concebir una definición, y es considerar que es una mera abreviatura. Vista así, la definición se reduce a

\( x\subset y\equiv \forall u(u\in x\rightarrow u\in y), \)

donde ahora hay que entender que el término de la izquierda es otro nombre para la misma fórmula que nombra el término de la derecha. Deshaciendo todos los convenios de notación que venimos adoptando, la fórmula en cuestión es la sucesión de signos

\( \forall x\rightarrow \in ux\in uy \)

Incluso podríamos considerar que esto no es más que una sucesión de números naturales. Puestos a referirnos a esta sucesión de signos o números con el nombre más cómodo de \(  \forall u(u\in x\rightarrow u\in y) \), nada nos impide usar un nombre más cómodo y llamarla \( x\subset y \). Así, aquí no hemos de ver una fórmula con tres signos, sino una fórmula con nueve signos, el primero de los cuales no es la variable \( x \) sino el cuantificador universal.

Con esta forma de concebir las demostraciones el lenguaje de la teoría formal es siempre el mismo, y lo único que cambia es nuestra forma de referirnos a sus fórmulas. Así, en un razonamiento teórico sobre fórmulas arbitrarias no tenemos que preocuparnos para nada por los signos añadidos, ya que en realidad no hemos añadido ninguno. Podemos asegurar sin comprobación alguna que toda fórmula de la teoría (por muchas definiciones sucesivas que acumule) puede escribirse en términos de los signos primitivos de la teoría porque en realidad es una sucesión de signos primitivos del lenguaje de la teoría, porque nunca hemos añadido ninguno más.

Por el contrario, cuando se conciben las definiciones como axiomas que introducen un nuevo signo a la teoría, es necesario demostrar teoremas que justifiquen la inesencialidad en términos formales y no semánticos, estableciendo concretamente que toda fórmula que incluya signos "definidos" es equivalente a otra que no los contiene, pues para razonar con fórmulas "en abstracto" no podemos tener en cuenta todos los signos que podrían haberse introducido en la teoría mediante las definiciones oportunas. Con la segunda concepción todo esto es inmediato.

Sin embargo, hay dos clases muy distintas de definiciones, y todo lo que hemos dicho sólo vale para una de ellas. Imaginemos que un matemático sigue razonando en la teoría T y dice lo siguiente:

El axioma del par dice que, dados dos conjuntos \( x \) e \( y \), existe otro conjunto \( z \) cuyos elementos son exactamente \( x \) e \( y \). Dicho conjunto es único por el axioma de extensionalidad. En efecto, si hubiera dos conjuntos \( z \) y \( z' \) cuyos elementos fueran precisamente \( x \) e \( y \), ambos tendrían los mismos elementos, y lo que dice el axioma de extensionalidad es que dos conjuntos con los mismos elementos son iguales. A este único conjunto \( z \) cuyos elementos son \( x \) e \( y \) lo llamaremos par desordenado de \( x \) e \( y \) y lo representaremos por \( \{x,y\} \).

¿Cómo se ha de entender esto? Cuando escribimos \( x\in \{x,y\} \), ¿qué hay que entender que es \( \{x,y\} \)?

Al igual que antes, tenemos la opción de considerar que la definición consiste en añadir un nuevo signo al lenguaje formal, en este caso un funtor diádico, que podríamos representar en principio por \( P \), junto con el axioma

\( \forall xy(\forall u(u\in Pxy\leftrightarrow u=x\lor u=y)), \)

y además convenir en escribir \( \{x,y\}\equiv Pxy \).

Con este convenio, la respuesta a la pregunta que habíamos planteado es que \( \{x,y\} \) es un término del lenguaje formal de la teoría extendido con un nuevo funtor \( P \), concretamente el término que consta del nuevo funtor seguido de las dos variables \( x, y \).

De nuevo, esto exige justificar qué condiciones deben darse para que un axioma de este tipo sea inesencial, lo que formalmente supone demostrar que toda fórmula escrita con el nuevo signo \( \{x,y\} \) es equivalente a otra que no lo contiene.

Si intentamos concebir una definición de este tipo como una abreviatura, nos encontramos con un problema: el lenguaje \( \mathcal L_{\rm tc} \) no tiene más términos que las variables, y \( \{x,y\} \) debería ser un término, pero no una variable. Entonces, ¿qué término es?

Una solución en esta línea consiste en considerar que en realidad no definimos \( \{x,y\} \), sino más bien la fórmula

\( z=\{x,y\}\equiv \forall u(u\in z\leftrightarrow u\in y). \)

Aquí se entiende que la parte izquierda es sólo una forma abreviada de escribir la fórmula de la derecha, que es una fórmula de \( \mathcal L_{\rm tc} \), sin ningún signo añadido.

Toda fórmula en la que aparezca \( \{x,y\} \) debe entenderse como una abreviatura de otra fórmula en la que \( \{x,y\} \) aparece en la forma \( z=\{x,y\} \). Por ejemplo,

\( x\in \{x,y\}\equiv \exists z(z=\{x,y\}\land x\in z) \).

Concretando algunos detalles, ésta es una forma viable de concebir las definiciones de términos sin implicar la adición de nuevos funtores o constantes al lenguaje de la teoría. Sin embargo, hay una tercera opción más "concreta" que vamos a discutir seguidamente:

Lenguajes con descriptor

Una forma de tratar las definiciones de términos de forma clara y sistemática es añadir un nuevo signo lógico a los lenguajes formales, llamado el descriptor "\( | \)".

Ello nos obliga a modificar las definiciones que hemos dado en los mensajes anteriores para cubrir también este signo adicional.

En primer lugar, las definiciones de término y fórmula deben unirse a una definición conjunta de "expresión", pues igual que los relatores nos pasan de términos a fórmulas, el descriptor nos pasa de fórmulas a términos. En efecto, la definición de expresión queda ahora como sigue:

Toda variable \( x \) es un término.

Toda constante \( c \) es un término.

Si \( f \) es un funtor \( n \)-ádico y \( t_1,\ldots, t_n \) son términos, entonces \( ft_1\cdots t_n \) es una término.

Si \( R \) es un relator \( n \)-ádico y \( t_1,\ldots, t_n \) son términos, entonces \( Rt_1\cdots t_n \) es una fórmula.

Si \( \alpha \) es una fórmula \( \lnot\alpha \) es una fórmula.

Si \( \alpha \) y \( \beta \) son fórmulas, entonces \( \alpha\rightarrow \beta \) es una fórmula.

Si \( \alpha \) es una fórmula y \( x \) es una variable, entonces \( \forall x\alpha \) es una fórmula.

Si  \( \alpha \) es una fórmula y \( x \) es una variable, entonces \( |x\alpha\equiv (x|\alpha) \) es un término.

Como siempre, el orden "real de los signos" es \( |x\alpha \), con el nuevo signo delante, para marcar inequívocamente el tipo de expresión, pero en la práctica escribiremos \( x|\alpha \), añadiendo paréntesis si es necesario. Los términos de la forma \( x|\alpha \) se llaman descripciones.

Con ayuda del descriptor, la definición de par desordenado es:

\( \{x,y\}\equiv z|\forall u(u\in z\leftrightarrow u=x\lor u=y). \)

Esto se lee: "\( \{x, y\} \) es el conjunto \( z \) tal que sus elementos son exactamente \( x \) e \( y \)".

Para poder manipular formalmente las descripciones necesitamos incorporar a \( _{\mathcal L} \) un axioma que diga qué podemos decir de ellas. Es el axioma K7:

\( \exists !x\alpha\rightarrow S_x^{x|\alpha}\alpha \)

Naturalmente, esto supone extender la definición de la sustitución para incluir el caso de las descripciones. La definición sigue exactamente el mismo criterio seguido para definir la sustitución en una fórmula de tipo \( \forall x\alpha \). Dejando de lado esos detalles, lo que dice el axioma K7, (que también puede presentarse en forma de regla derivada de inferencia (DP descripciones propias):

\( \exists !x\alpha\vdash S_x^{x|\alpha}\alpha \))

es que si existe un único \( x \) que cumple la descripción, entonces el \( x|\alpha \) cumple la descripción (y por lo tanto es ese único objeto que la cumple).

En nuestro caso: como hemos demostrado que \( \exists! z(\forall u(u\in z\leftrightarrow u=x\lor u)y)) \), la regla de las descripciones propias nos permite sustituir \( z \) por \( z|\forall u(u\in z\leftrightarrow u=x\lor u=y) \) es decir, por \( \{x,y\} \) en la definición, y nos queda

\( \forall u(u\in \{x,y\}\leftrightarrow u=x\lor u=y) \),

es decir, el par \( \{x,y\} \) cumple la propiedad que lo define.

Antes de presentar con más detalle el uso del descriptor, vamos a ver más ejemplos de su funcionamiento. Todos ellos siguen el mismo esquema:


Razonamos en la teoría T: el axioma del conjunto vacío afirma que \( \exists x\forall u\ u\notin x \). Este \( x \) es único, porque si hubiera dos conjuntos sin elementos, ambos tendrían los mismos elementos (ninguno) y el axioma de extensionalidad afirma que dos conjuntos con los mismos elementos son iguales.

Por lo tanto, en T se demuestra: \( \exists ! x\forall u\ u\notin x \).

Esta unicidad nos permite aplicar la regla de las descripciones propias. Si definimos

\( \emptyset\equiv x|\forall u\ u\notin x \),

la regla DP nos permite pasar de la existencia con unicidad a la sustitución de la descripción \( \emptyset \) en la fórmula que lo define, es decir: \( \forall u\ u\notin \emptyset \), y a partir de ahí ya podemos usar el conjunto vacío sabiendo que cumple lo que dice su definición.

Similarmente, el axioma de la unión dice que, para todo conjunto \( x \), existe un conjunto \( y \) cuyos elementos son los elementos de los elementos de \( x \), y dicho \( y \) tiene que ser único por el axioma de extensionalidad. Por lo tanto, tenemos:

\( \forall x\exists !y\forall u(u\in y\leftrightarrow \exists v(u\in v\land v\in x)) \)

Si definimos

\( \bigcup x\equiv y|\forall u(u\in y\leftrightarrow \exists v(u\in v\land v\in x)) \)

La unicidad nos permite aplicar la regla DP para concluir que podemos sustituir \( \bigcup x \) en la fórmula que la define, es decir:

\( \forall u(u\in \bigcup x\leftrightarrow \exists v(u\in v\land v\in x)) \)

Notemos que la regla DP sigue el "espíritu" de \( K_{\mathcal L} \), es decir, es una regla que el matemático puede usar "instintivamente", sin siquiera ser consciente del paso lógico concreto que está dando. En la práctica, un matemático razona simplemente así:

El axioma de la diferencia afirma que, para todo par de conjuntos \( x \) e \( y \) existe un conjunto \( z \) cuyos elementos son los elementos de \( x \) que no pertenecen a \( y \). Claramente, dicho \( z \) es único por el axioma de extensionalidad, luego podemos llamarmo \( x\setminus y \)

Por debajo de esto hay dos cosas:

1) Que cuando el matemático dice ``podemos llamar \( x\setminus y \) al conjunto cuyos elementos son los elementos de \( x \) que no están en \( y \)" eso se formaliza como

\( x\setminus y\equiv z|\forall u(u\in z\leftrightarrow u\in x\land u\notin y) \)

2) Que el matemático tiene conciencia de que no puede dar nombre a algo salvo que haya demostrado que la definición lo caracteriza, es decir, que existe un único \( z \) que cumple la definición. Esto se formaliza como que es la condición necesaria para que sea aplicable la regla DP, que nos permite afirmar que

\( \forall xyu(u\in x\setminus y\leftrightarrow u\in x\land u\notin y). \)

Los ejemplos que hemos visto son los usos típicos del descriptor y, en realidad, todo uso del descriptor es un uso típico como los que acabamos de ver. Vemos así que la finalidad del descriptor no es ni más ni menos que (junto con la regla DP) formalizar de forma el concepto de definición matemática sin necesidad de recurrir a añadir signos al lenguaje formal.


Como comentábamos, la incorporación del descriptor a los lenguajes formales requiere retocar todas las definiciones para tenerlo en consideración. El cambio más drástico es el que ya hemos indicado: que ya no es posible definir los conceptos de término y fórmula por separado, sino que es necesario definirlos simultáneamente porque se puede construir fórmulas a partir de términos y términos a partir de fórmulas.

En segundo lugar, las definiciones de variable libre y ligada se han de extender para tener en cuenta que en un término como \( z|\forall u(u\in z\leftrightarrow u\in x\land u\notin y) \) la variable \( z \) está ligada por el descriptor, igual que la variable \( u \) está ligada por el cuantificador, mientras que las variables \( x, y \) están libres. La idea es que el descriptor liga variables exactamente igual que lo hacen los cuantificadores.

Por último, hay que definir el concepto de sustitución de una variable por un término en una expresión (término o fórmula) considerando a la vez los dos casos, pues ahora están relacionados, y sólo hay que añadir la definición de sustitución \( S_x^t y|\alpha \), que se define exactamente igual que \( S_x^t\forall y\alpha \), sin más que cambiar \( \forall y \) por \( y| \).

Remito para los detalles a mi libro de lógica (capítulo I).

Desde el punto de vista semántico, hay que definir qué es el objeto denotado en un modelo \( M \) por una descripción \( x|\alpha \) respecto de una valoración \( v \).

Para ello necesitamos hacerle un pequeño añadido a la definición de modelo. En un modelo \( M \) de un lenguaje con descriptor debe fijarse (además de una interpretación para cada constante, relator y funtor del lenguaje) un objeto \( d \) de su universo al que llamaremos "descripción impropia" en el modelo \( M \) y que será el objeto asignado a cada descripción impropia, en el sentido siguiente:

\( M(x|\alpha)[v] \) se define como el único objeto \( a \) que cumple \( M\vDash \alpha[v_x^a] \), si es que existe tal único \( a \), o bien \( M(x|\alpha)[v]\equiv d \)  en caso contrario (tanto si no existe ningún \( a \) como si existen varios).

De este modo el objeto denotado por \( x|\alpha \) es lo que cabe esperar que sea (el único objeto que cumple \( \alpha \)) cuando existe tal objeto, pero sucede que el término \( x|\alpha \) está ahí, es un término que requiere interpretación, aunque no se dé la unicidad, y en tal caso le asignamos un significado convencional, el objeto al que llamamos \( d \), y que podemos elegirlo en cada modelo.

Por ejemplo, un matemático nunca diría "definimos \( A \) como el conjunto que tiene entre sus elementos al conjunto vacío", porque sabe que eso no define un conjunto (no hay un único conjunto que cumpla eso), pero nada nos impide considerar el término \( A\equiv x|\emptyset\in x \).

Aunque un matemático nunca definiría esta \( A \), no hay ningún problema en definirla a condición de que tengamos claro que no podemos aplicar la regla DP y, por consiguiente, no podemos afirmar que \( \emptyset \in A \) (y, por consiguiente, no podemos decir nada de \( A \) a partir de su "definición", podemos dar la definición, pero no usarla, y ahí se ataja formalmente el sinsentido).

Pero como \( A \) es un término (si no "bien definido" en el sentido que los matemáticos usan la definición, sí al menos correctamente definido), tiene que tener una interpretación en todo modelo, y hemos convenido que se interpreta como un objeto \( d \) fijado arbitrariamente en el modelo de antemano, y que no tiene nada que ver con la definición. Si da la casualidad de que dicho objeto contiene al conjunto vacío, entonces \( A \) denotará un objeto que casualmente cumplirá la definición de \( A \), pero no tiene por qué ser así.

Con la definición que hemos dado de "objeto denotado por una descripción" se comprueba inmediatamente que el axioma K7 es verdadero en todo modelo, por lo que \( K_{\mathcal L} \) sigue siendo correcto.

En cambio, con dicha definición ha dejado de ser semánticamente completo. Hay sentencias verdaderas en todo modelo de T que no son demostrables a partir de los axiomas de T. Por ejemplo:

\( (x|\emptyset\in x)=(x|\emptyset\notin x) \)

Esta sentencia es verdadera en todo modelo de T, porque ambos miembros son descripciones impropias: ni hay un único conjunto que contenga al conjunto vacío, ni hay un único conjunto que no contenga al conjunto vacío. Por ejemplo, \( \{\emptyset\}, \{\emptyset, \{\emptyset\}\} \) son dos conjuntos que cumplen lo primero y \( \emptyset, \{\{\emptyset\}\} \) son dos conjuntos que cumplen lo segundo. Esto hace que en cualquier modelo de T ambos términos denoten la descripción impropia \( d \) y, por consiguiente, la sentencia resulta verdadera. Pero no tenemos ninguna regla de inferencia que nos permita tratar con descripciones impropias para que podamos demostrar esa igualdad.

La completitud semántica de \( K_{\mathcal L} \) se recupera añadiendo un octavo y último axioma que recoja el convenio que hemos adoptado con las descripciones impropias:

\( \lnot\exists !x\alpha\rightarrow (x|\alpha)=(x|x=x) \)

Notemos que \( x|x=x \) siempre denota en un modelo a la descripción impropia (porque sólo es una descripción propia si en el modelo hay un único objeto que es idéntico a sí mismo, lo cual sólo puede suceder si el modelo tiene un único objeto, y entonces dicho objeto tiene que ser \( d \) necesariamente, porque no hay otra posibilidad para \( d \)). Por lo tanto, lo que afirma K8 es que cuando no hay un único objeto que cumple \( \alpha \), la descripción \( x|\alpha \) (es decir, cualquier descripción impropia) es igual a una descripción impropia concreta (luego todas las descripciones impropias son iguales entre sí, todas denotan al mismo objeto en un modelo).

Este axioma K8 no se usa para nada en la práctica, pues explica cómo tratar el caso que nunca plantea un matemático, pues un matemático nunca usa descripciones impropias. Sin embargo, es todo lo que hace falta para demostrar igualdades "tontas" como la anterior que, queramos o no, tienen que poder demostrarse para que podamos decir que nuestro cálculo deductivo es semánticamente completo. En efecto, con este último axioma, la demostración del teorema de completitud sigue siendo válida aunque el lenguaje tenga descriptor.

Pese a todo, es posible dar al axioma K8 una utilidad práctica que un matemático considerará, si no especialmente útil, al menos razonable. Podemos añadir un axioma a T que diga:

\( (x|x=x)=\emptyset \)

Esto significa "la descripción impropia es el conjunto vacío". Dicho así puede que lo le diga mucho a un matemático, pero se puede explicar en términos más simples: "Cualquier cosa que esté mal definida se entenderá por convenio que es igual al conjunto vacío". Eso sí lo entiende el matemático y, aunque no le preocupe mucho, porque no tiene por costumbre definir cosas mal, sí puede serle útil a veces, para no tener que precisar qué sucede en los casos que no le interesan.

Por ejemplo, si la Aritmética de Peano adoptamos como axioma \( (x|x=x)=0 \), entonces podemos definir

\( x-y\equiv z|(x=y+z) \),

y con esta definición puede demostrarse que \( 0''''-0'''=0' \), mientras que \( 0''-0'''' \) es una descripción impropia, porque puede probarse que no existe ningún número \( z \) tal que \( 0''''+z=0'' \), pero entonces, por K8 y el axioma específico sobre las descripciones impropias, podemos afirmar que \( 0''-0''''=(x|x=x)=0 \). Así estamos conviniendo en que todas las restas que no se pueden calcular valen cero.

Similarmente, volviendo a la teoría de conjuntos, podemos convenir que las integrales de las funciones no integrables son el conjunto vacío, que los límites de las sucesiones que no tienen límite son el conjunto vacío, etc. No es imprescindible, pero no queda mal. Evita que podamos escribir cosas que no tengan interpretación.

Lo dicho es suficiente para manejar descripciones en la práctica (y manejarlas inconscientemente, como hace el matemático), así que nos limitaremos a citar un último resultado: si en una teoría podemos caracterizar la descripción impropia sin usar descriptores (por ejemplo, como el único \( x \) que cumple \( \forall u\ u\notin x \) en T, o como \( x=0 \) en AP), entonces toda fórmula con descriptores es equivalente en dicha teoría a otra sin descriptores. Por lo tanto, al estudiar la teoría a nivel teórico siempre podemos decir "consideramos únicamente fórmulas sin descriptores", y con ello (si lo que vamos a decir sobre fórmulas se conserva por equivalencia lógica) no perdemos generalidad. Por ello, una vez demostrado este teorema, el considerar descriptores no es un lastre con el que estemos obligados a cargar para siempre, sino que en cualquier momento podemos desprendernos de él a efectos teóricos, y usar los descriptores únicamente a efectos prácticos, para formalizar definiciones de forma económica y precisa.

[Carlos Ivorra]

Para terminar esta exposición de la lógica que subyace al razonamiento matemático quiero destacar algo que ya ha quedado implícito en el mensaje anterior. Imaginemos que le pedimos a un matemático que nos demuestre que \( \forall xy(x\subset y\land y\subset x\rightarrow x=y) \). Podemos comparar varias posibilidades:

Respuesta típica del matemático Por el axioma de extensionalidad.

Respuesta típica del matemático al que hemos mirado con cara de pocos amigos por haber acabado tan rápido Si tomas un \( u \) que esté en \( x \), tienes que estará en \( y \) por definición de inclusión \( x\subset y \), e igualmente al revés, luego tienes que \( x \) e \( y \) tienen los mismos elementos, luego son iguales por el axioma de extensionalidad.

Demostración formal:

Un matemático tiende a dar por evidentes ciertos pasos que, detallados al máximo, requieren varios razonamientos menores, pero si realmente sabe lo que está diciendo, es capaz de detallar más cualquier fragmento de su argumentación (como si pusiéramos una lupa sobre él). Es posible que si alguien con serios problemas para entender razonamientos lógicos presiona mucho al matemático preguntándole "¿y eso cómo  lo sabes?", "¿y eso por qué?", "no entiendo ese paso," etc., el matemático no sea capaz de llegar a detallar su argumento hasta el nivel de detalle que supone el razonamiento formal que hemos presentado, porque el matemático no necesita conocer \( K_{\mathcal L} \), ni qué es EC o IB. Sin embargo, lo verdaderamente importante es que si a un matemático desesperado porque no logra hacer ver a alguien que su argumento está justificado le enseñamos el razonamiento formal que hemos presentado y nos aseguramos de que lo entienda, no dirá "bueno... sí... es otra forma de verlo", sino que dirá, "¡exacto!, eso es lo que estaba tratando de explicar sin saber ya cómo".

Lo que quiero decir es que el razonamiento formal no es otra forma de razonar, distinta de la habitual del matemático, aunque éste la reconozca como válida, sino que es exactamente la forma de razonar del matemático, sólo que detallada al máximo. El matemático abrevia todos aquellos pasos que pueden darse "por pura lógica", sin necesidad de recurrir a alguna idea matemática propiamente dicha (y en niveles más avanzados incluso abrevia los pasos que un experto en la teoría tratada puede rellenar por su experiencia), pero esos pasos lógicos que abrevia son su lógica subyacente, independientemente de que pueda no estar familiarizado con la forma de expresarla formalmente (con un cálculo deductivo formal en concreto).

Si alguien ha estudiado lógica y se ha quedado con la idea de que lo que le han enseñado tiene cierta relación con el razonamiento matemático, pero es otra cosa, que se puede razonar algo "por lógica" o "como hacen los matemáticos", como si fueran dos cosas distintas, es que no ha entendido lo que le han enseñado o (muy probablemente) no se lo han enseñado bien.

La lógica que hemos expuesto aquí es la que subyace a todo razonamiento matemático "usual" exactamente en el mismo sentido en que el código máquina subyace a toda aplicación informática ejecutable en un ordenador. Un programador familiarizado con el lenguaje C puede no saber nada de código máquina, pero lo que al final está programando es una secuencia de instrucciones en código máquina, aunque el software de programación que utilice le permita explicitar sólo instrucciones de alto nivel que luego se pueden concretar mecánicamente (de eso se encarga su compilador). La diferencia es que, aunque todos los razonamientos de alto nivel de un matemático (si son correctos) se pueden desarrollar al lenguaje de bajo nivel de \( K_{\mathcal L} \), nadie se molesta en hacerlo porque no hace falta para nada.

De este modo, sin perjuicio de que la lógica sea un campo de estudio muy vasto, con mil direcciones para explorar, puede decirse que quien entienda todo lo expuesto aquí entiende todo lo que hay debajo del trabajo de un matemático "normal". Naturalmente, es posible dar cálculos deductivos distintos pero equivalentes al que hemos dado, es posible desarrollar la teoría de otro modo, etc., pero salvo variantes insustanciales, lo que sirve de fundamento al razonamiento matemático es que disponemos de un cálculo deductivo correcto y semánticamente completo que funciona como hemos visto que funciona. Razonar correctamente en matemáticas es razonar de forma que todos los pasos puedan desarrollarse hasta adquirir el aspecto del razonamiento formal precedente. Hacerlo en la práctica sería insufrible, porque los árboles no dejarían ver el bosque de los razonamientos: tanto paso insustancial impediría captar las ideas centrales de las demostraciones, sin contar con la prueba más elemental se haría eterna, pero, desde un punto de vista teórico, lo que hace un matemático es aplicar dando cien pasos en uno las técnicas de razonamiento que aquí hemos descrito, ni más ni menos.

Confío en que este artículo pueda servir a sus lectores para ver con más claridad tanto lo que es la concepción moderna de las matemáticas como lo que es la lógica formal que sirve de sustento a las matemáticas. La conexión concreta entre ambas se realiza a través de la teoría de conjuntos. No hemos entrado aquí en detalles sobre cómo es una teoría de conjuntos, pero para entender en qué consiste eso de usar una teoría de conjuntos basta haber entendido cómo se usa la teoría T, pues la diferencia entre T y ZFC es simplemente que en ZFC se pueden demostrar más cosas, pero siempre de la misma manera.