Lógica y teoría de conjuntos (1)

[alexpglez]

Esta es la primera de varias entradas divulgativas sobre lógica y conjuntos. En ésta, vamos a comentar la necesidad de basar la matemática (y en consecuencia la física) en una teoría lógica sólidamente fundamentada.

Comenzaremos por dar un breve repaso del sistema numérico:
Los números naturales, $\mathbb N$, son los números que sirven para describir cantidades contables: 1 casa, 3 libros, etc. Sin embargo, si se quiere hablar de "deber" cierta cantidad o incluso si se intentan resolver ecuaciones sin solución como $x+y=z, \;\; z\leq y$, pero que físicamente "deberían" tener solución, uno se encuentra con la necesidad de definir otro tipo de números, los enteros $\mathbb Z$. Al igual que pasaba antes, uno se encuentra con más posibilidades interesantes en la descripción de la realidad: hablar de porciones de la unidad y permitir la posibilidad de división que nos lleva a los números racionales $\mathbb Q$, definir ciertos números no representables mediante la división de enteros como el $x$ tal que $x^2=2$ (que nos lleva a definir $\mathbb R$), o incluso ciertos números que, aunque no representen nada físico directamente, sí que nos sirven para resolver ecuaciones como el $x$ que $x^2=-1$ (que nos lleva a $\mathbb C$).

Uno puede por tanto construir así el sistema numérico y prácticamente toda la matemática de esta manera, si no fuese por un pequeño problema: no sabemos si es correcto. Por ejemplo, no sabemos qué es un número natural más que por una ligera inspiración (aunque muy certera e incluso algo rigurosa) y por tanto no sabemos cómo definir las operaciones ni cómo construir los demás conjuntos numéricos. Podemos seguir desarrollando la matemática sin preocuparnos de esto, como lo han hecho históricamente los matemáticos y los físicos durante muchos siglos, o bien estudiar cómo se deben construir las matemáticas. Nosotros optaremos por esto último. Propongo de ahora en adelante basarnos en, como diría Descartes, algo tan claro y evidente que sea imposible de ser falso: el lenguaje y la lógica.


Lenguajes formales:
Llamaremos un lenguaje formal de primer orden $L$, al conjunto de símbolos $L=\{c_i,x_i,f_i^n,R_i^n,=,\neg,\rightarrow, \forall, |\}$, donde cada cosa son constantes, variables, funtores de n variables, relatores de n variables, igualador (que es un relator diádico, de dos variables), negador, implicador, cuantificador universal o generalizador y descriptor, respectivamente, (léase $L=...$ como una representación únicamente pictórica y familiar). Podemos interpretar y leer los cuatro últimos símbolos como "no", "implica", "para todo", "tal que". Ahora se explicarán con todo detalle con ejemplos.
Una cadena de signos en $L$, es una sucesión de tales símbolos. Dos cadenas de signos son equivalentes si constan de los mismos signos en el mismo orden, diremos que $\alpha\equiv \beta$, y $\alpha \not\equiv \beta$ en caso contrario (a menudo se usa tal definición para dar diferentes nombres a una misma cadena de signos). Podemos definir así dos conceptos lingüísticos que denominaremos expresiones:
- Fórmula: es una cadena de signos de los tipos, $\neg \alpha$, $\alpha \rightarrow \beta$, $R_i^nx_1...x_n$ o $\forall x_i \alpha$, donde las $\alpha$ y $\beta$ son fórmulas (el resto son símbolos que ya hemos visto).
- Término: cadena de signos del tipo $c_i$, $x_i$, $f^n_i x_1...x_n$, $x|\alpha$ donde $\alpha$ es una fórmula.

Veámoslo con varios ejemplos:
- Sea $LL$ y $SMJ$ dos relatores monádicos, $LLx$ y $SMJx$ se leerán como "el día $x$ llueve" y "el día $x$ el suelo se moja".

$$\forall x \;\; LLx \; \rightarrow \; SMJx$$

"Para todos los días $x$, que el día $x$ llueva implica que el día $x$ el suelo se moja". O más abreviado, "el día que llueve el suelo se moja".
- Consideremos el relator diádico $H(x,y)$ "x e y son hermanos", y el funtor monádico (de una variable) $P(x)$ "padres de x" (que es claramente un término). (En adelante trabajaremos a menudo en notación matemática, escribiendo los debidos paréntesis después de funtores, relatores y demás expresiones para que se entiendan mejor).

$$\forall xy \;\; P(x)=P(y) \rightarrow H(x,y)$$

"Si los padres de x e y son iguales, x e y son hermanos".
- La siguiente cadena de signos no es una expresión, (¿por qué?, ejercicio: explicar conforme a los criterios lingüísticos anteriores)

$$\forall xy \;\; y=H(x) \rightarrow H(x,y)$$

Ahora vamos a definir el resto de símbolos lógicos "o", "y", "si y sólo si", "existe" y "existe un único" (ambos cuantificadores) :

$$\alpha \vee \beta \equiv \neg \alpha \rightarrow \beta$$

$$\alpha \wedge \beta \equiv \neg (\neg \alpha \vee \neg \beta)$$

$$\alpha \leftrightarrow \beta \equiv (\alpha \rightarrow \beta) \wedge (\beta \rightarrow \alpha)$$

$$\exists x \; \alpha \equiv \neg \forall x \; \neg \alpha$$

$$\exists! x \; \alpha \equiv \exists x \; \alpha \; \wedge \forall xy \; (\alpha(x) \wedge \alpha(y) \rightarrow x=y)$$

A su vez, es necesario hacer una distinción útil entre tipos de variables:
- Libres: aparecen en la fórmula pero no están ligadas a ningún cuantificador o descriptor.
- Ligadas: aparecen ligadas a algún cuantificador o descriptor.
Esto nos permite definir la sustitución de variables, que dependerá de según aparezcan libres o ligadas, por ejemplo:
$S_x^t c\equiv c$, $S_x^tf(x,y)\equiv f(t,y)$, $S_x^t \forall t \; \alpha(x,t)\equiv \forall y \; \alpha(t,y)$
Cabe decir que para un matemático, al menos en mi caso, la comprensión de las variables y la sustitución es casi inconsciente, puede que por la traducción al lenguaje humano de tales expresiones. Por ejemplo, no tendría ningún sentido definir la sustitución así $S_x^t \forall t \; \alpha(x,t)\equiv \forall t \; \alpha(t,t)$, ya que, mientras que a la izquierda hay una variable libre en la fórmula, a la derecha no aparece ninguna. No entro en más detalles, sólo comentar que para los demás casos la definición de sustitución es análoga.

Ahora que ya tenemos construido nuestro lenguaje, vamos a pasar a definir ¿qué es demostrar?, ¿qué es verdadero y qué es falso?

- Modelos:
Antes de nada necesitamos definir lo que es un modelo. Un modelo $M$ de un cierto lenguaje formal es una colección de objetos y un cierto criterio que asocia expresiones del lenguaje con objetos del modelo. Representaremos $M \vDash \alpha$ si la fórmula es verdadera en el modelo, y $M \vDash \neg \alpha$ si es falsa. Diremos que en $M$, $\alpha$ es consecuencia de un conjunto de fórmulas $\Gamma$ y representaremos por $M, \Gamma \vDash \alpha$ si podemos razonar $\alpha$ a partir de sus premisas, llamaremos a estos resultados reglas de inferencia semántica si se cumplen en todo modelo. Se dice que $\alpha$ es lógicamente válida si es verdadera en todo modelo (lo representaremos por $\vDash \alpha$), insatisfacible si es falsa en todo modelo, satisfacible si es verdadera en algún modelo y falseable si es falsa en alguno.
En la práctica, un modelo es una colección de objetos y reglas de inferencia semántica que permiten realizar demostraciones de manera un tanto "informal". Por ejemplo, el modelo del lenguaje de la lógica proposicional es el determinado por las tablas de verdad:


- Sistemas deductivos formales:
Un sistema deductivo formal $F$ es un conjunto de fórmulas, llamados axiomas, y un conjunto de reglas primitivas de inferencia, que determinan cuando una fórmula es consecuencia inmediata de otras fórmulas de $L$. Dado un conjunto de fórmulas $\Gamma$, se dice que $\alpha$ se deduce de ellas (se representará $\Gamma \vdash_F \alpha$), si es consecuencia inmediata de las premisas $\Gamma$ y de los axiomas y reglas de inferencia de $F$. Si en la deducción no se utilizan premisas, $\alpha$ se denomina teorema. Se dice que $F$ es correcto si todos sus axiomas son fórmulas lógicamente válidas, y sus reglas primitivas de inferencia son reglas de inferencia semánticas, esto a su vez implica que todo teorema es lógicamente válido y que $\Gamma \vDash \alpha$ si y sólo si $\Gamma \vdash_F \alpha$.
En otras palabras, una demostración en un sistema deductivo formal correcto equivale a una demostración "informal" en el modelo. La gracia de definir estos dos conceptos separados está en tener un conjunto mínimo de axiomas y reglas de inferencia de los que podamos deducir todas las reglas del modelo, es decir, que el sistema deductivo sea el más simple posible. Llamaremos $K_L$ al sistema deductivo formal que contiene estos 8 esquemas de axiomas y 2 reglas de inferencia:

$$\beta \rightarrow (\alpha \rightarrow \beta)$$

$$(\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))$$

$$(\neg \alpha \rightarrow \neg \beta) \rightarrow (\beta \rightarrow \alpha)$$

$$\forall x \alpha \rightarrow S_x^t \alpha$$

Si $x$ no está libre en $\alpha$, (no aparece en la fórmula o está ligada a cuantificadores):

$$\forall x (\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \forall x \beta)$$

Si $x$ no está libre en $t$:

$$\forall x (x=t \rightarrow \alpha) \leftrightarrow S^t_x \alpha$$

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

$$\neg \exists! x \alpha \rightarrow x|\alpha=y|(y=y)$$

Modus Ponens:

$$\alpha, \alpha \rightarrow \beta \vdash_{K_L} \beta$$

Introductor generalizador:

$$\alpha \vdash_{K_L} \forall x \alpha$$

Es fácilmente verificable que los axiomas 1-3 y el MP son lógicamente válidos por medio de las tablas de verdad. Los axiomas 4 y 5 y el IG definen el generalizador, el 6 define el igualador y el 7 y 8 el descriptor. El 8 aparece como un "residuo": si se usa el descriptor, cuando $\exists! x \alpha$, $x|\alpha$ es el único término que cumple $\alpha$, pero aunque $\neg \exists! x \alpha$ algo tendrá que valer $x|\alpha$ y el 8 afirma asignar cada término de este tipo a un término "concreto" $y|(y=y)$.
Comentar que hay que leer estos axiomas y reglas de inferencia como esquemas: si sustituimos en cualquier esquema cada fórmula y término que aparecen por unos concretos, tenemos un axioma o regla de inferencia determinados. De ahora en adelante $\vdash$ significará $\vdash_{K_L}$ y llamaremos teoremas lógicos a los teoremas demostrables en $K_L$.
$K_L$ es lo suficientemente potente como para derivar todo el cálculo deductivo usado en cualquier rama de la lógica. A modo de ilustración, demostremos el Modus Barbara $\alpha \rightarrow \beta, \beta \rightarrow \gamma \vdash \alpha \rightarrow \gamma$:

$$\alpha \rightarrow \beta$$

$$\beta \rightarrow \gamma$$

$$(\beta \rightarrow \gamma) \rightarrow (\alpha \rightarrow (\beta \rightarrow \gamma))$$

$$\alpha \rightarrow (\beta \rightarrow \gamma)$$

$$(\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))$$

$$(\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma)$$

$$\alpha \rightarrow \gamma$$

Así pues:

$$\alpha \rightarrow \beta, \beta \rightarrow \gamma \vdash \alpha \rightarrow \gamma$$

En la siguiente entrada definiremos lo que es una teoría axiomática y pondremos ejemplos de ellas introduciendo (por fin) las teorías de conjuntos.

Fuente: Carlos Ivorra Lógica Matemática, cap. 1 y 2

[alexpglez]

Es mi primer artículo. He intentado ser lo más breve posible, y aunque he cortado bastante, sigue ocupando mucho en mi opinión. Tampoco sé muy bien cómo dar un formato más legible al texto.
Me he dado cuenta que definir en una página lo que es un lenguaje formal no es algo tan sencillo como pensaba al principio...

Espero que se entienda y que se disfrute. Cualquier corrección, duda o sugerencia, encantado de leeros

[Alriga]

¡Todo muy lógico alex!, saludos.

[alexpglez]

¡Todo muy lógico alex!, saludos.

Muchas gracias Alriga, ¡espero que te haya gustado! Si no me hubieras recomendado el libro de lógica de Carlos no estaría escribiendo estos artículos, por no hablar de que tal libro me influyó mucho en escoger un grado de matemáticas. Muchas gracias.

Por cierto, ¿consideras que debería subir un glosario con todas las reglas de inferencia lógicas? sobre el implicador, negador, particularizador, conjunción, etc. Personalmente creo que ayudaría bastante, para quien no esté familiarizado.