miércoles, 4 de marzo de 2015

Suficiencia y necesidad

Las nociones de "suficiencia" y "necesidad" suelen utilizarse en lenguaje coloquial para referir a una serie de propiedades y patrones formales comunes en variadas estructuras lógicas. En este artículo nos referiremos con un poco más de profundidad a ellas.

NOTA: "necesidad" aquí no entendida en el sentido modal.

La versión fome

Decimos que una condición A es suficiente para B, cuando la ocurrencia de A fuerza a la ocurrencia de B. Por el contrario, decimos que A es una condición necesaria para B, cuando la ausencia de A fuerza a la ausencia de B.
Esto es lo que ambas palabras significan en el lenguaje ordinario. Cuando la profesora reprende al niño diciéndole: "¡es suficiente!" lo que le está queriendo decir es que su sólo comportamiento ya la ha hecho enojar. Por otra parte, cuando un paciente muy enfermo pregunta si tiene que someterse a un tratamiento y el doctor le dice: "es necesario", le está diciendo que no podrá mejorar si no se aplica dicho tratamiento.
Aquí, por supuesto, el concepto de "ocurrencia" debe entenderse en el sentido más amplio. Quince minutos de cocción son suficientes para que el queso sobre la pizza se derrita. Después de quince minutos, no debería seguir el queso frío. Si hacemos caso a la canción, entonces "para bailar la bamba se necesita una poca de gracia"; si no le pones una poca de gracia, no vas a poder bailar la bamba.
Ahora lo interesante es ver cómo estos conceptos funcionan juntos. Pasemos a los simbolitos entonces.

La versión proposicional: condicionales materiales

Muchas personas en su primer curso de lógica tienen problemas para entender qué clase de relación existe entre el antecedente y el consecuente de un condicional, y se preguntan si acaso esta relación refleja el mismo sentido que las oraciones de la forma "si... entonces...". Tarde o temprano llega el momento en que uno se hace ciertas preguntas, muy atinadas: ¿son los condicionales materiales relaciones de causalidad -de algún tipo? ¿Se trata de una relación de evidencia? ¿De conjunción constante? ¿De fundamentación?
Pero no; el condicional material clásico expresa una doble relación, relación a la que llamamos, convenientemente, implicación material. Dado "$p \to q$", lo que estamos expresando es que "$p$" es condición suficiente de "$q$", pero también que "$q$" es condición necesaria de "$p$".
Uno de los descubrimientos lógicos más sorprendentes de todos, acaso el más importante de toda la historia de la lógica, es el que Aristóteles y los megáricos hicieron hace todos esos siglos, aunque no lo hayan formulado más que de maneras intuitivas y a veces oscuras: que cuando ciertas condiciones son suficientes para asegurar A, la ocurrencia misma de A es necesaria para que dichas condiciones se den todas juntas. Esta es la base de la intuición fundamental que nos sugiere que nuestras creencias y conocimientos no están puestos así no más en nuestra memoria, uno al lado del otro, sino que unos se apoyan en otros y apoyan a otros a su vez.
Mi condicional material favorito -"si llueve entonces las calles se mojan"- siempre es un buen ejemplo. La lluvia es condición suficiente para que las calles se mojen, y en esto todos podemos estar de acuerdo; pero no es tan inmediato entender porqué el que las calles se mojen es condición necesaria de que llueva. Pero pensémoslo de este modo: si no se están mojando las calles, ¿en qué sentido estaremos dispuestos a aceptar que está lloviendo? Tal vez vivimos en una ciudad cubierta, o bajo tierra; pero en estos dos contextos, no parece adecuado decir que está lloviendo tampoco, sin agregar información adicional -está lloviendo "afuera", "arriba", por ejemplo.
Para no entramparnos en las vicisitudes de la pragmática, el otro buen ejemplo es el analítico: si hay veinte ceros en el desarrollo decimal de pi, entonces hay diecinueve ceros en el desarrollo decimal de pi. No puede ser que haya veinte, si no hay al menos diecinueve, ¿verdad?
Otros ejemplos que no exhiben la forma "si...entonces..." de todas maneras guardan relaciones de implicación material, razón por la cual podemos formalizarlas con condicionales: "el local cierra los domingos" = "si es domingo, entonces está cerrado". Podría cerrar por muchas razones, pero al menos sé que los domingos cierra; y si no está cerrado, tengo una buena razón para asegurar que no es domingo, entendiendo que el condicional es verdadero, por supuesto.
En los tres casos tenemos la misma doble relación: que llueva es suficiente para que se mojen las calles, que haya veinte ceros es suficiente para que haya diecinueve, que sea domingo es suficiente para que el local esté cerrado; que las calles se mojen es necesario para que llueva, que haya diecinueve ceros es necesario para que haya veinte y que el local esté cerrado es necesario para que sea domingo.
Sobre todo el último ejemplo sirve muy bien para ilustrar por qué la relación de implicación es puramente formal: la necesidad de que esté cerrado el local para que sea domingo es, ciertamente, una relación que no parece ser muy "real", o de contenido. Y sin embargo, no deja de ser una relación que desde la perspectiva lógica es sumamente interesante.

Aumentando el juego

Las relaciones de necesidad y de suficiencia no sólo atañen al condicional material, sino que atraviesan la lógica proposicional completa. Aunque tal vez no hayamos reparado en ello, a menudo aprendemos todas las conectivas lógicas siguiendo relaciones de suficiencia y necesidad: decimos, por ejemplo, que para que una conjunción "$p \land q$" sea verdadera es necesario que ambas, "$p$" y "$q$", sean verdaderas; o que para que una disyunción "$p \lor q$" sea verdadera es suficiente que al menos una, "$p$" o "$q$", sea verdadera. Podemos decir, en un sentido bastante apropiado, que la conjunción es una conexión de necesidad, mientras que la disyunción es una conexión de suficiencia.
¿Nunca se han topado con la expresión "condiciones conjuntamente suficientes y separadamente necesarias"? Ahora estamos en posición de analizarla más de cerca. Esta retahíla es la cláusula central de un cierto tipo de definición llamada "funcional". Por ejemplo, si queremos definir un concepto, digamos, "humano", buscamos qué propiedades debe tener algo a lo que le aplicaremos este concepto: cada una de esas condiciones debe ser necesaria por sí sola, y todas juntas deben ser suficientes para que el concepto se aplique correctamente. Por ejemplo, podría ser que una de esas propiedades sea "tener hígado". Por supuesto, "tener hígado" no es suficiente para ser humano, pero sí necesario. Por eso, es más fácil buscar las condiciones necesarias de una en una, e ir considerando al total en cada paso, hasta que nos de una suma suficiente. Parece engorroso, pero en realidad el magnífico Aristóteles ya se nos adelantó en esto: su definición formal de "definición" -el género más amplio y la especie más acotada- define un conjunto de condiciones conjuntamente suficientes y separadamente necesarias: si X es humano, entonces X es animal y X es racional; y si X es animal y racional, entonces es humano.
Y esto a su vez es porque la distinción categorial entre géneros y especies es una forma de implicación material. Dice Aristóteles: "el género se predica de la especie pero la especie no se predica del género". El verbo "predicarse de" está colocado en la misma relación asimétrica que nuestras "ocurrencias" de la primera sección: en términos modernos diríamos que "la especie implica el género".
Volvamos entonces a la lógica proposicional. Decíamos que una definición funcional establece condiciones conjuntamente suficientes y separadamente necesarias para que se de -en el más amplio sentido de esta palabra- algo, digamos, "$p$". Supongamos que sólo hay una tal condición, "$q$". Entonces podemos decir:

$q \to p$

Pero también:

$p \to q$

Que de hecho es lo mismo que decir que:

$p \equiv q$

¡Maravilloso resultado! Precisamente porque otro de los nombres del bicondicional es el de "equivalencia". Entonces, ¿cuándo dos proposiciones son equivalentes? Bueno, cuando cada una de ellas es suficiente y necesaria para afirmar la otra. Y se da, trivialmente, que toda proposición es suficiente y necesaria para afirmarse a sí misma, y por eso entonces

$p \equiv q$

Algo que ninguna relación de evidencia, de causa o de fundamentación admite -excepto quizás las de Dios, pero ése es precisamente el punto de las discusiones, ¿no?
Ahora supongamos que tenemos varias condiciones, digamos "$q$" y "$r$". Entonces queremos que sean conjuntamente suficientes...

$qr \to p$

Pero separadamente necesarias...

$p \to q \lor r$

Dos expresiones que no pueden juntarse directamente en una equivalencia; pero que se las puede transformar en tal. Basta con recordar que "$p \lor q$" es equivalente a " $\neg p \lor q$", con lo que obtenemos que...

$qr \to p = \neg (qr) \lor p$

Y que...

$p \to q \lor r = \neg p \lor q \lor r$

Y por DeMorgan podemos todavía extender más la primera fórmula en...

$qr \to p = \neg (qr) \lor p = \neg q \lor \neg q \lor p$

Lo que nos da ahora los dos términos de nuestra conjunción final:

$(qr \to p) \land (p \to q \lor r) = (\neg q \lor \neg r \lor p) \land (\neg p\lor q \lor r)$

Fórmula que, por tabla de verdad, sólo es falsa cuando...

$p = (1,1,1,1,0,0,0,0)$
$q = (1,1,0,0,1,1,0,0)$
$r = (1,0,1,0,1,0,1,0)$
$(\neg q \lor \neg r \lor p) \land (\neg p\lor q \lor r) = (1,1,1,0,0,1,1,1)$

..."p" es verdadera y "q" y "r" son ambas falsas, o cuando "p" es falsa y "q" y "r" son ambas verdaderas. Pero esto es, como se puede notar, ¡una relación de equivalencia!


Más allá de las conectivas

Otras nociones con las cuales los conceptos de suficiencia y necesidad tienen que ver, son las propiedades metalógicas de Completud y Corrección. ¿Alguna idea de cuál es cuál?
Veámoslo de esta forma: un sistema formal es completo cuando al menos todas las verdades son deducibles; y es correcto cuando sólo las verdades son deducibles. Una paráfrasis apropiada sería esta: la completud asegura que todas las verdades se deducen, y la corrección asegura que si una fórmula no es una verdad entonces no se deduce. Es decir: dado un sistema S, completud afirma que:

Si una fórmula es verdadera, entonces es un teorema de S

Mientras que corrección afirma que:

Si una fórmula es un teorema de S, entonces es verdadera

Esto por supuesto tiene la apariencia de un doble condicional, por lo que tener ambas propiedades es equivalente a afirmar que:

Una fórmula es verdadera si y sólo si es un teorema de S

Lo que puede parafrasearse por:

Una fórmula es verdadera siempre y cuando sea un teorema de S

O, convenientemente:

Para que una fórmula sea verdadera es suficiente y necesario que sea un teorema de S

Pero como Completud y Corrección son propiedades sobre el sistema deductivo, nos conviene usar la otra redacción:

Para que una fórmula sea un teorema de S es suficiente y necesario que sea una fórmula verdadera*

Ahora volvamos a separarlas y veamos cuál es cuál:

Para que una fórmula sea un teorema de S es suficiente que sea una fórmula verdadera

Esto es lo mismo que decir que si una fórmula es verdadera, entonces puedo afirmar que es un teorema de S; pero esto es lo que asegura la Completud.
Por otra parte,

Para que una fórmula sea un teorema de S es necesario que sea una fórmula verdadera

Dice que una fórmula no será un teorema de S si no es una fórmula verdadera. Pero esto es lo que asegura la Corrección.
Consideremos ahora el conjunto $Cn(S)$, que contiene todos los teoremas del sistema S. Si la semántica sobre el lenguaje de S es bivalente y asumimos que toda fórmula es verdadera o falsa, entonces Completud nos asegura que: si "p" es una fórmula cualquiera,

O bien $p \in Cn(S)$, o bien $\neg p \in Cn(S)$

Porque, entre "$p$" y "$\neg p$", al menos una de ellas es verdadera; por otra parte, Corrección nos asegura que

Nunca se dará que $p \in Cn(S)$ y $\neg p \in Cn(S)$

Porque al menos una de ellas es falsa. Pero estas dos afirmaciones, como se ve de inmediato, son respectivamente una disyunción y una conjunción -expresadas en el metalenguaje. Y no sólo eso, de hecho son formulaciones -más abstractas- ¡de los principios de Tercero Excluido -Completud- y No Contradicción -Corrección!

La recurrencia

Estas nociones duales de suficiencia y necesidad se repiten una y otra vez a través de los diferentes sistemas lógicos. Por ejemplo, en la lógica de primer orden, un cuantificador existencial y un cuantificador universal comparten esta misma relación asimétrica; por ejemplo, que un objeto cualquiera "a" ostente la propiedad "F" es suficiente para que "$\exists x F(x)$" sea verdadera; mientras que es necesario para que "$\forall x F(x)$" lo sea.
Lo mismo ocurre con las semánticas de mundos posibles: para que "$\Box p$" sea verdadera es necesario que en un mundo posible accesible "$p$" sea verdadera; mientras que es suficiente para que "$\Diamond p$" lo sea. De ahí que los cuantificadores puedan ser vistos -en semánticas particulares- como sumatorias -disyunciones iteradas- y productorias -conjunciones iteradas-, y los operadores modales como cuantificadores sobre los mundos posibles -el operador modal de necesidad cuantifica universalmente sobre los mundos posibles, mientras que el operador de posibilidad cuantifica existencialmente sobre ellos.

Espero que todos estos ejemplos hayan resultado sugerentes. La consideración de estas relaciones dentro y fuera de los sistemas formales es una herramienta muy valiosa para el análisis lógico, no sólo en sentido matemático sino también en sentido práctico y filosófico, porque ayuda a aproximar y a relacionar cercanamente esferas y fenómenos en apariencia muy disímiles.

IMå

---------
*: Esta inversión es inocua, pero coloca las relaciones de suficiente y necesidad al revés, por la naturaleza dual y asimétrica de la implicación material que ya comentamos más arriba.

martes, 17 de febrero de 2015

Lógica Antigua en 7 sencillos pasos

Muchos de nosotros cuando pensamos en el sistema silogístico se nos vienen a la mente aburridas mnemotecnias, largas listas de reglas que tienen que ver con cómo disponer enunciados y gruesas listas de aburridos resultados. En contraste con la elegante lógica matemática y todas sus maravillas, las conectivas raras, los teoremas sorprendentes y los resultados inesperados, la lógica de la tradición nos hace pensar en un frío e inhóspito castillo medieval lleno de goteras y monjes de ojeras largas y muecas de fastidio.
Yo mismo fui de esta opinión por mucho tiempo, y me rehusé a estudiar la lógica aristotélica asumiendo que, como ya conocía el cuadro de oposiciones y sabía dibujar diagramas de Venn, estaba al menos preparado para enfrentar los escasos desafíos en los que la vida me exigiera conocer el trabajo del maestro.
Sin embargo, cuando me llegó el momento de por fin tomar el organon y echarle una mirada, quedé sorprendido por la agilidad y simplicidad del analítico tal como Aristóteles lo plantea. Los latinos y medievales, que sin duda ampliaron y perfeccionaron esta herramienta, se fueron por el lado práctico y en lugar de enseñar a hacer el trabajo manualmente, listaron todos los posibles resultados en sus graciosas retahílas; práctica que hoy, y con justa razón, nos parece de lo más aburrida.
En mi reencuentro con la lógica antigua quise pues retomar los múltiples resultados de la tradición pero más en el estilo de Aristóteles, aprendiendo los cálculos y no memorizando las tablas. En este artículo entonces voy a presentar algo que podría llamarse, con algo de humor, Lógica Antigua en 7 sencillos pasos. No es exactamente la lógica de Primeros Analíticos sino la silogística ampliada de los medievales, pero, como verán, con el cambio positivo de asumir la técnica "memorizar poco y hacer mucho" antes que "memorizar mucho y hacer poco".

Una cita para comenzar

"En casi todos los libros de Lógica anda escrito que, construyendo por los modos conocidos todos los silogismos a que se prestan las cuatro clases de proposiciones que llevamos estudiadas, se contarán diez y nueve clases correctas de argumentos, a las cuales se llama los diez y nueve modos del silogismo. Estos se dividen en cuatro figuras, y cada figura se distingue por la posición que el término medio ocupa en las premisas. Hace mucho tiempo que los lógicos examinaron los casos de cada figura en que es válido el silogismo, y recogieron el frito de su examen en ciertas curiosísimas líneas formadas con nombres latinos, y que comienzan con estas palabras: Barbara, Celarent, Daria [sic], palabras todas escogidas de manera que las vocales de cada una de ellas, a modo de índice mnemotécnico, enseñan la clase de proposiciones que, dispuestas de un modo particular, producen un buen silogismo. Pero entender vale más que recordar. Lo que importa es saber analizar, descomponer, aquilatar por medio del uso de las reglas el valor de las proposiciones del silogismo. El que sabe de memoria parece que sabe; mas puede no saber. El que aplica reglas, penetra en las entrañas del argumento, y ajusta y mueve sus partes como un buen jugador de ajedrez sus piezas, ése de seguro sabe. Barbara, Celarent, Daria es una curiosidad de los tiempos pasados: pensará mal, y luego obrará mal, todo el que no se habitúe a pensar por sí"

W. Stanley Jevons
en "Nociones de Lógica"

Los Juicios Categóricos

El primer paso que daremos será abandonar la redacción medieval del tipo "Todos los S son P" y volveremos sobre la que Aristóteles utiliza. Los términos, representados por mayúsculas latinas, son predicables en el más amplio sentido de la palabra.
Ahora un poco de galimatías: una proposición es la afirmación de algo acerca de algo. Una proposición es afirmativa si dice que algo se da unido a algo, y negativa si dice que algo se da separado de algo -calidad. La proposición es universal si se dice de todos los algo, y particular si se dice de algunos algo -cantidad.
Ahora las cuatro formas de la proposición categórica:

Universal afirmativo: A se da en todo B
Universal negativo: A se da en ningún B
Particular afirmativo: A se da en algunos B
Particular negativo: A no se-da-en todo B o A no-se-da en algunos B

Abreviaremos con la siguiente convención:

Universal afirmativo: AaB
Universal negativo: AeB
Particular afirmativo: AiB
Particular negativo: AoB

Pero teniendo presente que este orden de términos es apuesto al de la nomenclatura medieval; en la griega, el predicado es el nominativo y el sujeto el dativo. Lo que significa que

A se da en todo B

Corresponde al juicio medieval:

Todos los B son A

La utilidad de la redacción griega es que deja al cuantificador dentro de la proposición, y hace más entendible la elección de una nomenclatura como AaB. Tiene además la ventaja de ordenar naturalmente los términos en el silogismo perfecto, como veremos un poco más adelante.
En los ejemplos de este artículo, sin embargo, usaré ambas redacciones, principalmente porque la medieval tiene la gran ventaja de sonar mucho más natural que la griega.

Las oposiciones

Las oposiciones son las reglas formales de acuerdo con las cuales la verdad o falsedad de un juicio fuerza a la falsedad o verdad de otro. El cuadro de oposiciones medieval contiene cuatro oposiciones, dos de las cuales son aristotélicas y podrían considerarse como primitivas.

Contradicción

Son opuestas contradictorias las proposiciones que difieren en calidad y en cantidad, es decir:

AaB y AoB
AeB y AiB

Dos opuestas contradictorias no pueden ser ambas verdaderas y tampoco pueden ser ambas falsas. La verdad de una fuerza a la falsedad de la otra y la falsedad de una fuerza a la verdad de la otra.

Contrariedad

Son opuestas contrarias las universales que difieren en calidad:

AaB y AeB

Dos opuestas contrarias no pueden ser ambas verdaderas pero sí ambas falsas. La verdad de una fuerza a la falsedad de la otra.

De estas dos oposiciones se siguen estas otras dos:

Subcontrariedad

Véase: cuando AaB y AeB son ambas falsas, sus contradictorias son ambas verdaderas. Pero como AaB y AeB son contradictorias, nunca pueden ser ambas verdaderas; luego sus contradictorias no pueden ser ambas falsas. Esta oposición es la subcontrariedad:

AiB y AoB

La falsedad de una fuerza a la verdad de la otra.

Subordinación

Véase: cuando AaB es verdadera, AeB está forzada a ser falsa. Y cuando AeB es falsa, AiB es verdadera, porque es su contradictoria. De igual forma, cuando AiB es falsa, AeB es verdadera; y cuando AeB es verdadera, AaB es falsa. Lo mismo aplica para AeB y AoB. De manera que obtenemos la oposición de subordinación:

AaB y AiB
AeB y AoB

La verdad de la primera fuerza a la verdad de la segunda. La falsedad de la segunda fuerza a la falsedad de la primera.

Desde un punto de vista proposicional, las oposiciones se comportan como las siguientes conectivas:

Contradictoriedad: negación del bicondicional -la "disyunción fuerte"
Contrariedad: negación de la conjunción -incompatibilidad
Subcontrariedad: disyunción
Subordinación: condicional

Las conversiones

Las reglas de conversión son algoritmos para transformar juicios en otros equivalentes, como las reglas de DeMorgan en la lógica clásica.
La posibilidad de todas las conversiones viene de la noción de distribución de los términos. Un término está distribuido -o tomado universalmente- cuando el juicio nos dice algo acerca de todos los sujetos acerca de los cuales se predica el término, y no está distribuido -o tomado particularmente)-cuando el juicio nos dice algo acerca de algunos pero no de todos los sujetos acerca de los cuales se predica el término. ¿Galimatías? Siempre se entiende mejor con símbolos:

AaB
AeB
AiB
AoB

Se ha destacado en negrita el término distribuido.

El predicado -primer término- de las afirmativas nunca está distribuido, en cambio el predicado de las negativas siempre está distribuido; el sujeto -segundo término- de las universales siempre está distribuido, en cambio el sujeto de las particulares nunca está distribuido.
Aquí ya es buen momento de entregar una última noción, que es la de negación interna o complemento lógico. No hay forma de decirlo en palabras que sea más fácil de entender que con un ejemplo: si "humano" es un predicable, "no-humano" es su complemento lógico. Si A es un predicable, designamos su complemento por A'. 
Ahora, aquí viene el truquito para las conversiones: se debe conservar la distribución de los términos. en todo momento Si uno se sabe la regla de distribución, las siguientes conversiones pueden deducirse muy fácilmente; si no, la lista tampoco es tan larga:

Conversión simple

Dado que sólo los juicios y proposiciones particulares afirmativas y universales negativas tienen sus dos términos tomados en igual cantidad, puedo invertirlos directamente. Esto se llama conversión simple:

AeB = BeA
AiB = BiA

En efecto: si ningún griego es americano, ningún americano es griego. Si salado se da en algunas comidas, ser comida se da en algunas cosas saladas.

Contraposición

El juicio universal afirmativo y el particular negativo -¿ya se notó que uso juicio y proposición como sinónimos?- también se pueden invertir, pero hay que tomar el complemento de cada término porque la distribución es desigual. Por lo tanto,

AaB = B'aA'
AoB = B'oA'

Decir que la bondad se da en todos los niños es decir que todos los no-buenos son no-niños. Si americano se da en todo argentino, no-argentino se da en todo no-americano.
Similarmente, si algunos americanos no son argentinos, algunos no-argentinos no son no-americanos.

Obversión

La más entretenida de las conversiones lógicas es la obversión. Todas las proposiciones se pueden obvertir, y se hace cambiando la calidad y tomando el complemento del predicado -el primer término. De tal forma:

AaB = A'eB
AeB = A'aB
AiB = A'oB
AoB = A'iB

Todos los humanos son mortales, ningún humano es inmortal.
Ningún griego es americano, todos los griegos son no-americanos.
Felicidad se da en algunos casados, tristeza no se da en todos los casados.
Algunos americanos no son argentinos, algunos americanos son no-argentinos.
Se cumple una ley: si un término está distribuido en una proposición, existe una equivalente a ella que no distribuye a su complemento y vice-versa. Podemos comprobar que esta ley se cumple para la obversión:

AaB = A'eB
AeB = A'aB
AiB = A'oB
AoB = A'iB

Y también para la contraposición:

AaB = B'aA'
AoB = B'oA'

Ahora puede probarse la regla de doble negación para las particulares, usando contraposición y obversión:

AoB = B'oA' = BiA' = A'iB = AoB

El primer paso es contraposición; el segundo es obversión, el tercero es conversión simple y el último es de nuevo obversión.
Ejemplo: Algunos americanos -B- no son argentinos -A-; algunos no-argentinos no son no-americanos; algunos no-argentinos son americanos; algunos americanos son no-argentinos; algunos americanos no son argentinos.

Conversión accidental

Existe todavía una conversión más, pero es sospechosa. El problema con ella es que no da como resultado un término equivalente, sino uno derivado del original. Se trata de la conversión accidental, y sólo funciona cuando no se toma en cuenta que los predicables puedan no aplicar a cosa alguna -dicho en términos tradicionales, cuando se asume el importe existencial en todos los juicios. De acuerdo con ella, podemos pasar de un cuantificador universal a uno particular, invirtiendo los términos:

AaB pasa a BiA
AeB pasa a BoA

Decir que todos los argentinos son americanos es lo mismo que decir que algunos americanos son argentinos. Decir que ningún griego es americano es lo mismo que decir que algunos americanos no son griegos.
Digo que es sospechosa ya que, por la regla de conversión simple, esto es lo mismo que extraer de un juicio universal el particular correspondiente:

AaB pasa a BiA -conversión simple de BiA
BeA -conversión simple de AeB- pasa a BoA

Pero entonces no podría tratarse de una equivalencia, sino de una derivación subordinada.
Por lo tanto, la menciono por completud pero me abstendré de utilizarla.

El silogismo perfecto

Hasta ahora todo lo que hemos dicho puede parecer altamente sofisticado y abstruso, y alguien podría estar pensando que, al final, mi promesa de enseñar lógica aristotélica en 7 simples pasos no va a cumplirse nunca. Pero aquí es donde ese alguien debería quedar sorprendido.
Yo mismo quedé sorprendido cuando leí Primeros Analíticos y descubrí la sofisticada elegancia con que el Estagirita utiliza su noción de razonamiento perfecto. Se trata de aquel único modo en que la verdad de la conclusión queda perfectamente forzada por la verdad de sus premisas, y con la cual su validez es eterna. Este silogismo perfecto es aquel en el cual un primer término se predica de todos o ningún elemento del segundo término, y el tercero se predica de todos o algunos elementos del tercero, dando lugar a cuatro posibles conclusiones, una por cada juicio categórico. Lo sorprendente de este razonamiento perfecto -que corresponde a los modos de la primera figura en la lógica medieval- es que es todo lo que hay que saber para descubrir los otros diecinueve silogismos válidos; todos son conversiones a partir de sus cuatro formas primitivas.
Estas cuatro formas primitivas son las siguientes: -y aquí sí usaremos los nombres mnemotécnicos, porque son sólo cuatro y, a la larga, los único que necesitamos aprendernos:

Barbara:
AaB, BaC |: AaC

Celarent: -se pronuncia /kelarent/, usted dígalo bien
AeB, BaC |: AeC

Darii:
AaB, BiC |: AiC

Ferio:
AeB, BiC |: AoC

Y ya está. Ahora se ve por qué la nomenclatura griega es preferible a la medieval para hacer la simbolización: en este orden queda mucho más claro porqué el término mayor es el mayor, el medio es el del medio y el menor es el menor; en Barbara, por ejemplo, ocurre una inclusión natural del tipo A > B > C, donde las letras han quedado, por la redacción, en el orden correcto.
Ahora, para todo lo que sigue, esto es lo único que nos interesa de las premisa mayor y menor; no tenemos que preocuparnos por el orden ni por la designación, ni ninguna de las otras particularidades de la lógica medieval. Si nos sabemos las cuatro formas del razonamiento perfecto y las tres reglas de conversión, podemos deducir de aquí los diecinueve silogismos válidos.
Aprender la silogística por este método es más eficiente que al estilo medieval, porque donde ellos ven cuatro silogismos -Celarent, Camestres, Cesare, Calemes- nosotros vemos sólo uno, Celarent, donde los dos juicios negativos universales pueden convertirse para dar lugar a las otras tres combinaciones. Con las cuatro formas primitivas se obtienen nueve nuevos silogismos, aplicando sólo inversiones simples. Los otros cinco modos se obtienen aplicando obversiones y contraposiciones, recordando que un complemento lógico es de igual modo un predicable.

La utilidad de la lógica antigua

Aunque en el último siglo el avance de la lógica matemática ha cernido la sospecha sobre el viejo método lógico de los antiguos, nunca es conveniente olvidarlo, porque todavía presta una gran ayuda en razonamientos cotidianos. Recordemos que Aristóteles diseñó este sistema como un arma analítica contra la sedición de los sofistas, y hemos de convenir en que, aunque hemos progresado mucho desde sus días, en el ámbito de las conversaciones y debates sobre política, moral, y en general en los temas que son de mayor incumbencia pública, el estilo de engaño y error no ha cambiado mucho; de ahí que no se trate de una herramienta del todo obsoleta en nuestros días. Pero, a mi parecer, esta utilidad reposa mucho más en las oposiciones y en las conversiones, que en los silogismos propiamente tal.
Por ejemplo, un razonamiento que escucho muy a menudo va más o menos así:

"La gente no es pobre porque no tenga oportunidades, es pobre porque es floja; y es que yo he conocido muchas personas que, aunque sus padres no les dejaron mucho, trabajaron y se esforzaron toda una vida para darle un mejor pasar a su familia".

Lo que este razonador nos quiere hacer creer es que la gente pobre -P- es pobre porque es floja -F-. Es decir, que la flojera es algo que se da en todos los pobres -FaP-. Para probar esto, presenta casos que él conoce de personas esforzadas -no-F- que llegaron a ser ricas -no-P-. Esto corresponde a decir que algunos no-flojos son no-pobres -P'iF'.
Dado que su garantía no es una demostración ni un silogismo, -porque es una sola proposición-, la única forma en que podría tratarse de una prueba válida sería que su conclusión fuera subordinada o equivalente a dicha garantía. Pero FaP no es la subordinada de P'iF', ni tampoco son equivalentes por vía de ninguna de las conversiones que hemos visto. Eso significa que es posible hacer verdadera a la garantía y falsa a la conclusión. Y el caso más simple de ésto podría ser:

Diego, Pedro -P-, Pablo -F-

Algunos no-pobres son no-flojos -Diego; pero no es cierto que todos los pobres sean flojos, en particular porque Pedro no es flojo pero es pobre.
Otra manera de verlo es notar que FaP se puede contraponer a P'aF', con lo que queda en evidencia que se está razonando desde el particular al universal.
Casos como éste y otros parecidos pueden abordarse, analizarse y compararse muy fácilmente, con el método que les he expuesto. La regla general es la siguiente: una proposición es prueba o garantía de otra si la subordina o le es equivalente; y una proposición es una refutación de otra si subordina o es equivalente a su contradictoria.

Los 7 sencillos pasos:

  1. Aprenderse los cuatro juicios o proposiciones categóricas.
  2. Aprenderse las cuatro oposiciones.
  3. Aprenderse la regla de distribución de los términos.
  4. Aprenderse las tres conversiones. -sin la accidental-
  5. Aprenderse los cuatro silogismos perfectos.
  6. Teniendo en mente estos dieciséis elementos, aprender a formalizar, recordando que la redacción "A es B" debe traducirse por "B se da en A".
  7. Aprender cuándo una proposición prueba o refuta alguna otra.

La versión corta:

  1. Aprender los cuatro juicios o proposiciones categóricas.
  2. Aprender las dos oposiciones principales.
  3. Aprender la regla de distribución de los términos.
  4. Aprender la definición del silogismo perfecto.
  5. Aplicar estos elementos para deducir todos los demás hasta que se vuelva un hábito.

IMå

NOTA: no olvidar revisar la bibliografía integrada.

martes, 10 de febrero de 2015

Completud y Corrección

Completud y Corrección son dos importantes propiedades de los sistemas deductivos. En esta oportunidad comentaremos algunas interesantes aplicaciones de estos dos conceptos, además de adelantar un poco cómo se utilizan en lógica.
Comencemos por un ejemplo sencillo. Supongamos que asistimos a un curso de verano abierto a todo público. El profesor a cargo de la actividad deja correr una hoja de papel para que todos los asistentes se anoten y así él pueda tener una lista de estudiantes. Si todos los presentes son responsables, todos anotarán su nombre y sólo su nombre. Si todos los asistentes anotan su nombre, la lista tiene el nombre de todos los asistentes y por lo tanto está completa. Por otra parte, si cada persona anota sólo su nombre, la lista no contiene ningún nombre que no corresponda a alguien presente, y entonces la lista es correcta.
Puede pasar, por ejemplo, que alguien haya ido a la primera clase pero todavía esté inseguro acerca de si participar o no de la actividad más adelante; por lo tanto, cuando llega la hoja, no se anota. La lista queda entonces incompleta.
Tampoco faltan los graciosos que, escudándose en el hecho de que es un curso abierto y gratuito, anotan nombres graciosos, como "Zoila Cerda" o "Esteban Quito" -cuando entré a estudiar filosofía solía haber en la lista nombres tales como "Protágoras de Abdera" o "Heráclito de Éfeso". Una lista así, que tiene nombres de personas que realmente no están presentes, es incorrecta. 
La cosa parece inofensiva cuando se trata de ejemplos como éste, pero no es difícil encontrar casos en los que es un poco más importante hacer listas completas y correctas, por ejemplo en el catastro de víctimas de una catástrofe o un accidente; no queremos que se nos pase un difunto, pero tampoco queremos que figuren más muertos de los que realmente hubo -la prensa amarillista y los gobiernos terroristas a menudo generan estadísticas incorrectas cuando desean hacer que un pequeño atentado sea un gran atentado.
Sin embargo, en todos estos casos, tenemos listas que pueden verificarse directamente, es decir, la completud y la corrección se comprueban por vía directa: preguntándole a cada persona su nombre y llamando en voz alta a todos los nombres de la lista. La cosa cambia cuando el conjunto de los registros o el de los registrados es inaccesible o infinito.
Imaginemos ahora una sopa de letras y una lista de palabras que tenemos que buscar dentro de ella. Tendemos a pensar que una sopa de letras es un juego relativamente inofensivo, pero lo cierto es que esconde un peligro no menor. Muchas veces nos habrá pasado que nos sentamos a hacer la sopa de letras de alguna revista, y después de mucho cabecearnos, descubrimos que falta una palabra. Y no es sencillo darse cuenta de eso y estar seguro, porque la cantidad de posibles direcciones en que puede estar escondida son, por lo general, muchísimas. Pero también pasa que a veces, en el transcurso del juego, encontramos una palabra que está de más, es decir, una que no estaba en la lista. Entonces nos ataca la duda: ¿cuántas palabras más podré encontrar, si sigo buscando? Otra vez, el desafío me lleva a tener que considerar todas las posibles direcciones en las que puede esconderse una palabra.
Una sopa de letras que contiene más palabras que las listadas, es incorrecta, y una que contiene menos es incompleta. Parte de la decisión de jugar o no una sopa de letras, es confiar en que ella es completa y correcta.
Imaginemos ahora que la sopa de letras es infinita, pero la lista es finita. -Esto no es muy difícil de imaginar; supongan una cuadrícula que sigue indefinidamente en las cuatro direcciones. Ahora la completud y la corrección de la sopa nos dicen mucho más que antes. Por ejemplo, si la sopa es completa, entonces sé que podré encontrar todas las palabras de la lista en un tiempo finito, por grande que sea. Esto es evidente desde el momento en que las palabras de la lista son finitas. Puede que las dos más lejanas estén separadas por veinte millones de letras, pero veinte millones, aunque es un número grande, igual es un número finito. Asimismo, si la sopa es correcta, entonces se me asegura que existe una sección de la sopa -una sub-sopa- finita y definida dentro de la cual están todas las palabras que pueden encontrarse, aunque no conozca de antemano las dimensiones de este rectángulo. Esto es así, nuevamente, porque la lista de palabras a buscar es finita. Corrección me dice que cuando encuentre todas las de la lista, me aseguro de que más lejos nunca se da una palabra.
Cuando la sopa de letras es completa y correcta, se me asegura otra cosa todavía más extraordinaria. De una sopa de letras infinita puedo sacar infinitas sub-sopas finitas -e infinitas también-. Sin embargo, en todas esas infinitas sub-sopas que puedo sacar de la sopa infinita, ninguna de ellas puede tener más palabras que la sopa original, y ninguna de esas palabras puede ser diferente a las primeras; de hecho, si saco sub-sopas de lugares fuera de la sección rectangular que contiene todas las palabras de la lista, obtendré un montón de sopas de letras sin una sola palabra escondida en ellas. Y este resultado ya es bastante sorprendente por sí mismo.
Ahora viene la pregunta crucial: ¿cómo puedo saber que una sopa de letras infinita es completa? Si pensamos en la sopa de letras como un montón de letras puestas en una cuadrícula al azar, entonces tendríamos que aceptar -hay un teorema en teoría de la probabilidad que nos lo asegura- que todas las palabras y todas las combinaciones de letras posibles están en la sopa. Pero no todas las sopas de letras son aleatorias. Por ejemplo, una sopa de letras puede tener una sección finita con letras variadas, y todo lo demás fuera de esa sección ser una y otra vez la letra B. Así definida, de tener palabras en la sección variada, por ser una sección finita, es posible hacer una lista completa y correcta de las palabras que se dan dentro de ella.
Vayamos ahora a la lógica.
Supongamos que tengo un álgebra de proposiciones con una semántica de tablas de verdad. las tablas de verdad serán las acostumbradas: para $p = (1,1,0,0)$ y $q = (1,0,1,0)$ tenemos las combinaciones: $pq = (1,0,0,0)$, $p \lor q = (1,1,1,0)$, $p \to q = (1,0,1,1)$ y $\neg p = (0,0,1,1)$.
En mi álgebra llamo tautología a todas las fórmulas que toman el valor 1 en todas las combinaciones posibles, por ejemplo: $p \to p$, $p  \lor \neg p$, $p \to (q \to p)$, etc.
Dado que tanto la conjunción y la disyunción son funciones idempotentes -es decir, $p=pp$ y $p=p \lor p$-, se da trivialmente que el conjunto de tautologías es infinito: si $p \to p$ es una tautología, entonces también lo es $(p \to p) \land (p \to p)$, y también $(p \to p) \land (p \to p) \land (p \to p)$, y así sucesivamente.
Lo que haremos a continuación será construirle a este álgebra de proposiciones un cálculo, es decir, un sistema deductivo. Para ello tengo que elegir mis axiomas y mis reglas -puedo tener axiomas y reglas, o sólo reglas-, pero no los elegiré de cualquier manera. ¿Qué es de lo que debo preocuparme, a la hora de definir mi cálculo? Imagino que ya lo habrán adivinado: que sea capaz de deducir todas las tautologías, pero también que deduzca sólo tautologías. En otras palabras, que sea completo y correcto.
Para que el sistema sea correcto es suficiente asegurarse de que todos los axiomas sean tautologías y que en todas las reglas de inferencia la conclusión sea consecuencia tautológica de las premisas. De esta forma, todas las proposiciones lógicas que se deriven de los axiomas serán también tautologías, que era lo que queríamos asegurar.
Pero la completud es tema completamente aparte. Las tautologías son infinitas, y no todas son series recurrentes de fórmulas idempotentes como en el caso de $p \to p$, $(p \to p)$, $(p \to p)(p \to p)$, $(p \to p)(p \to p)(p \to p)$... ¿Cómo se asegura uno la completud del sistema?
Hay diversas formas de demostrar que un cálculo es completo, porque hay diversas maneras de entender lo que significa la completud. Por ejemplo, Post decía que un sistema -clásico- es completo si la agregación de una fórmula no derivable como axioma provoca explosión, es decir, permite deducir cualquier fórmula. En un sentido mucho más abstracto, Tarski decía que una teoría -conjunto total de proposiciones verdaderas- es completa si para cada proposición "p" puede demostrarse o bien "p" o bien "\neg p". De igual manera, el estilo va a cambiar si quien lleva a cabo la demostración es un matemático o un lógico con más inclinaciones hacia la filosofía o hacia el lenguaje.
Por la definición de Tarski es interesante notar cómo la completud guarda alguna relación con el Principio del Tercero Excluido. Si entendemos este en un sentido filosófico general y no como la versión informal de la fórmula $p \lor \neg p$, veremos que el sentido final de que un sistema sea completo es que no existen espacios de indeterminación: dada una valuación total para las proposiciones, mi sistema es capaz de discernir la verdad o falsedad -verdad de la negación, en la lógica clásica- de todas las fórmulas posibles. De hecho, en algunas demostraciones de completud, el teorema $p \lor \neg p$ es utilizado directa o indirectamente para llegar al resultado final -véase por ejemplo Novikov, 1964. Se da ahí también una bella simetría con la corrección, que Tarski entendía como el hecho de que, dada una teoría, nunca se pueda demostrar una proposición "p" a la vez que su negación, "$\neg p$"; dual que se corresponde en el meta-lenguaje con el Principio de No Contradicción.

Espero que estas ideas les hayan parecido sugerentes. En el futuro escribiré artículos más detallados sobre algunas de las nociones que aquí lancé al pasar.

IMå

sábado, 7 de febrero de 2015

Algunas Falacias formales

Se llama "falacias formales" a las que se derivan de una incorrecta apreciación de la forma del argumento esgrimido. Muchas veces ocurre que las premisas no tienen la fuerza lógica suficiente para sostener la conclusión, y por lo tanto habrá casos en que las premisas serán verdaderas y sin embargo la conclusión será falsa.
Las más estudiadas y siempre más referidas son las dos primeras; yo agregué algunas otras que, aunque no siempre mencionadas en los manuales de lógica, sin embargo son bastante comunes.

El Modus Morons

La expresión "Modus Morons" es un dog latin -una expresión en inglés que se disfraza de locución latina- con el que se nombra a las dos más comunes falacias formales: la negación del antecedente y la afirmación del consecuente.

Negación del antecedente:

$\lbrace p \to q, \neg p \rbrace \vdash_{!} \neg q$

Ejemplo: si una persona está enferma de Peste Bubónica, entonces no está vacunado. Pero mi amigo no está enfermo de Peste Bubónica; por lo tanto, está vacunado.
Hay un ejemplo divertido en un capítulo de Los Simpsons, que les dejo aquí abajo para que lo analicen.


La lógica de Homero, como bien señala Lisa, es la siguiente: si hay tigres a la vista, entonces mi piedra espanta-tigres no funciona. Pero no hay tigres a la vista; luego, la piedra espanta tigres sí funciona. Ambas premisas son verdaderas, porque sabemos que la piedra espanta-tigres es inofensiva en presencia de un tigre y sabemos que no hay tigre. Pero la conclusión es evidentemente falsa también, casi por lo mismo que ya hemos dicho.

Afirmación del consecuente:

$\lbrace p \to q, q \rbrace \vdash_{!} p$

Ejemplo: si suena la alarma entonces el edificio está siendo evacuado. Pero el edificio está siendo evacuado; luego la alarma suena.
Si un incendio en el edificio impide que suene la alarma, pero las personas dentro comienzan a evacuar el lugar... bueno, se ve.
Un ejemplo encantador del uso catastrófico del Modus Morons lo podemos encontrar en este diálogo de la película Monty Python and the Holy Grail, que les comparto aquí en español.



Esta referencia la encontré leyendo esta entrada de blog: http://everything2.com/title/modus+morons.

Otras falacias formales

Es increíble lo fácil que es engañarse con el sentido de expresiones lógicas relativamente simples, sobre todo las que comprometen el condicional; esto se debe, en gran medida, a que el condicional material y su particular tabla de verdad no rescata "exactamente" lo que queremos decir con las expresiones de la forma "si...entonces", pero también porque es una conectiva formal que, a diferencia de las otras, tiene gran flexibilidad para ser expresada. De ahí que muchas de estas falacias formales sean no sólo recurrentes, sino que en muchos casos cueste darse cuenta de dónde está el error.

Falsos silogismos constructivos:

Igual como podríamos decir que los Modus Morons derivan de una incorrecta comprensión de las reglas de Modus Ponendo Ponens y Modus Tollendo Tollens, hay al menos dos que derivan de una incorrecta comprensión de la regla del silogismo constructivo.
El silogismo constructivo, que es un modo argumental válido, es como sigue:

$\lbrace p \to q, q \to r \rbrace \vdash p \to r$

Si tengo veinte manzanas, entonces tengo diecinueve manzanas. Y si tengo diecinueve manzanas, entonces tengo dieciocho. Por lo tanto, si tengo veinte manzanas, entonces tengo dieciocho manzanas. Limpio y claro.
Sin embargo, pueden darse algunos errores en la interpretación, como éstos:

$\lbrace p \to q, r \to q \rbrace \vdash_{!} p \to r$

Ejemplo: si el Estado no regula los precios arbitrariamente habrá aumento de la inflación, y también habrá aumento de la inflación si los trabajadores forman sindicatos y se van a paro; por lo tanto, si el Estado no regula los precios arbitrariamente los trabajadores formarán sindicatos y se irán a paro.

$\lbrace p \to q, p \to r \rbrace \vdash_{!} q \to r$

Casi el mismo ejemplo: si el Estado no regula los precios arbitrariamente habrá aumento de la inflación pero mantendrá a raya el descontento del sector empresarial. Por lo tanto, si aumenta la inflación se mantendrá a raya el descontento del sector empresarial.
Conclusión inusitadamente absurda.

Falsos silogismos disyuntivos:

La disyunción también es una operación lógica extraña, porque es verdadera cuando ambos disyuntos son verdaderos a pesar de que, en nuestra cotidianidad, muchas veces ambas alternativas no pueden darse juntas -Horn en A natural history of negation presenta un buen argumento contra la pretendida "disyunción fuerte". Aquí hay otra falacia formal que se sigue de lo mismo:

$\lbrace p \lor q, p \rbrace \vdash_{!} \neg q$

Ejemplo: el postulante debe saber inglés o alemán. Pero sabe inglés; luego no debe saber alemán.

-NOTA: no confundir con el Modus Ponendo Tollens.

Todavía una más con disyunciones:

$\lbrace p \lor q, q \lor r \rbrace \vdash_{!} p \lor r$

Ejemplo: hoy es martes o jueves, y es jueves o viernes; luego, hoy es martes o viernes.
Si hoy es jueves, ambas premisas son verdaderas y la conclusión es falsa.

E incluso un par con conjunciones:

$\lbrace \neg (pq) \rbrace \vdash_{!} \neg p \land \neg r$

Ejemplo: Carlos no se va a venir con la Juani y con la Sofía; así que ni la Juani ni la Sofía se van a venir con Carlos.
Carlos se puede venir sólo con la Sofía y sin la Juani; la premisa es verdadera y la conclusión es falsa.

$\lbrace pq \to r, \neg r \rbrace \vdash_{!} \neg p$

Ejemplo: si hay buen tiempo y despierto con ánimo, iremos a la playa; pero no iremos a la playa, por lo tanto, hay mal tiempo.
Hacía un día radiante, pero amanecí con pataleta. ¡Qué se le va a hacer!

Aunque parezca increíble -por lo inverosímil de mis ejemplos-, estos errores argumentales son todos mucho más comunes de lo que parece. Aquí les dejo algunos ejemplos más; jueguen a descubrir cuál es cuál:

  1. Hoy pretendías ir al centro y ver una película en el cine, pero me dijiste que no lo hiciste; por lo tanto, no pudiste haber estado ni en el centro ni en el cine durante la tarde.
  2. Si caminas por la calle escuchando música te pueden atropellar, y te pueden atropellar si eres imprudente; por lo tanto, si caminas por la calle escuchando música es que eres imprudente.
  3. Necesitabas un buen currículo y una correcta presentación personal para conseguir el trabajo, pero no lo conseguiste; así que vas a tener que procurar mejorar tu currículo.
  4. Mi mamá dice que las elecciones las gana el candidato de izquierda o el candidato de derecha, pero mi papá dice que de seguro ganará el de derecha o el independiente. Al menos en algo están de acuerdo mis papás, y es que todo queda entre el candidato de izquierda y el independiente.
  5. Dijo que iba a venir hoy o mañana; y ya vino hoy, así que no vendrá de nuevo mañana.
  6. Si me llama es porque me quiere; si me llama, quiere decir que no está tan enojada conmigo; así que, si me quiere significa que no está tan enojada conmigo.
  7. Me dijiste que siempre estarías disponible para mi si yo te llamaba; pero no te he llamado, así que asumo que no estás disponible para mí ahora.
  8. Te dije que siempre estaré disponible para ti si me llamas; hoy estaba disponible, debiste llamarme.

IMå

El Teorema de Incompletud de Gödel

El Teorema de Incompletud -o incompletitud, o a veces incluso "incompleción"- de Gödel es el teorema "más importante" de la lógica matemática. Los alcances de sus consecuencias así como su popularidad abarcan terrenos bastante más amplios que los de la lógica misma, pero, como suele ocurrir con resultados demasiado abstractos, no siempre se manejan versiones "exactas" de él, lo que acarrea, naturalmente, que se malinterprete muchas veces su sentido y se extraigan de él consecuencias que difícilmente pueden tener alguna relación con lo que realmente dice.
Este famoso "Teorema de Gödel" no es un resultado cualquiera, y por lo tanto no puede ponerse en palabras simples sin que se abuse del significado de las palabras con que se lo presenta -por regla general, en matemática las palabras casi nunca significan lo mismo dentro y fuera de la disciplina. Cuando recién comencé a buscar información en torno al tema, lamenté que en Internet no hubiera una página donde una explicación completa y pedagógica se ofreciera, por lo que ahora que me siento capacitado para hacerlo, quise suplir esta necesidad de los futuros interesados en el área.

Preliminares: el problema de la Completud

Kurt Gödel
Kurt Gödel es el más grande lógico que ha dado la humanidad después de Aristóteles y Gottlob Frege. La calidad, cantidad y profundidad de los resultados que obtuvo en sus investigaciones y creaciones intelectuales son piedras fundacionales de la lógica como la conocemos hoy en día, así también como pensamos otras áreas del conocimiento como las matemáticas o la informática.
El Teorema de Incompletud, acaso su resultado más popular -lo que no disminuye el mérito de los demás-, lo publicó en el año 1931, cuando recién tenía 25 años, habiendo terminado su Doctorado en Viena el año anterior. El nombre del ensayo es Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, "Sobre proposiciones formalmente indecidibles en Principia Mathematica y sistemas afines". y marca un antes y un después tanto en el desarrollo de la lógica como de la matemática contemporánea.
Pero, ¿por qué este resultado es tan importante? ¿Qué significa que una proposición sea "formalmente indecidible" y qué tiene eso que ver con la Incompletud? Para poder dar respuesta a estas preguntas, debemos volver un poco atrás, al tiempo en que los proyectos metamatemáticos estaban en su apogeo y se barajaban las más altas expectativas respecto a sus éxitos.

El "problema de la Completud" fue uno de los desafíos más importantes para los lógicos matemáticos de comienzos del siglo pasado. Dicho en breve, el problema de la Completud consistía en demostrar que todas las verdades matemáticas son demostrables.
Esto es, por supuesto, un problema mucho más abstracto que demostrar tal o cual teorema matemático particular. No se trata de hallar todas las demostraciones posibles -que son infinitas-, sino más bien probar que, dado un cierto sistema deductivo capaz de axiomatizar la matemática, él es también lo suficientemente expresivo como para asegurar que, cualquiera sea la verdad que queramos demostrar, nuestro sistema será capaz de dar con una prueba para ella.
Una demostración de Completud puede hacerse de variadas formas, pero la más habitual es algo más o menos en el espíritu de lo siguiente:

  1. Se elige una verdad semántica cualquiera.
  2. Mediante ciertas manipulaciones -el cuerpo de la demostración- se muestra cómo existe un teorema formal equivalente a la verdad semántica escogida.
  3. Dado que escogimos cualquier verdad semántica, se sigue que todas ellas son demostrables -recordemos que en lógica "cualquier x" y "todo x" son expresiones sinónimas.

Las demostraciones de Completud son más o menos sencillas dependiendo de la complejidad del sistema que se esté utilizando. Por ejemplo, la demostración de la Completud del cálculo proposicional con respecto a la semántica de tablas de verdad -es decir: probar que todas las tautologías son teoremas de mi sistema deductivo-, aunque compleja, es sin embargo bastante más sencilla que la demostración de la Completud del cálculo de predicados de primer orden -dicho sea de paso, este último resultado también se lo debemos a Gödel.
Para el caso de las matemáticas entonces el problema era el siguiente: tenemos la teoría aritmética en su conjunto -números naturales, enteros, racionales, reales... etc- y todas las operaciones sobre ellos -suma, resta, multiplicación, división, exponenciación... etc. En esta teoría hay algunas proposiciones que son verdaderas -como por ejemplo, que para todo $a, b$ números enteros siempre es verdadero que $a + b$ también es un número entero- y también hay algunas proposiciones que son falsas -como por ejemplo, "$0 = 1$". Al momento de fabricar un sistema deductivo donde se pueda axiomatizar la aritmética -es decir, un sistema basado en un lenguaje con el poder expresivo suficiente para poder expresar en él los axiomas fundacionales de la aritmética-, dos preguntas deben plantearse: ¿este sistema es capaz de deducir todas las proposiciones verdaderas? Y ¿este sistema es capaz de deducir sólo proposiciones verdaderas, y ninguna falsa? El primero es el problema de la Completud y el segundo el problema de la Corrección.
Ahora bien, imaginemos que nuestro lenguaje formal esté afectado de una característica que lo lleve a expresar proposiciones indecidibles; es decir, proposiciones que, aunque tienen sentido y están bien formadas, no pueden ser ni verdaderas ni falsas, porque decidirlas verdaderas las lleva a ser falsas y vice-versa. Cuando esto ocurre, uno de estos dos problemas surge:

  • Si la proposición se logra deducir, quiere decir que es verdadera; pero entonces es falsa, y el sistema es incorrecto.
  • Si la proposición no se logra deducir, quiere decir que es falsa; pero entonces es verdadera, y al no haber sido deducida, el sistema es incompleto.
En el lenguaje común y natural, como el español, conocemos muchas proposiciones indecidibles: son las famosas "paradojas" con las que los niños aprenden a jugar desde muy temprano. La clásica es la paradoja del mentiroso: esta oración es falsa. La razón por la cual en el español -y en cualquier otro idioma natural- estas paradojas se dan, es que se trata de lenguajes demasiado expresivos, y que por lo tanto son capaces de hablar acerca de sí mismos. Por lo tanto, cuando se intenta formalizar la aritmética o cualquier otra ciencia, se usan lenguajes artificiales justamente para evitar esta característica incómoda de la lengua común. Entonces se pide que el lenguaje utilizado sea suficientemente expresivo como para hacer la formalización, pero no lo suficiente como para permitir las proposiciones indecidibles.
Ahora les puedo contar el final del chiste: el resultado de Gödel fue probar que cualquier lenguaje con el poder expresivo suficiente para axiomatizar la aritmética contiene, por este mismo hecho, proposiciones indecidibles. De ahí se sigue que cualquier axiomatización de la matemática es intrínsecamente incompleta.

La demostración de Gödel

Para probar su Teorema, Gödel elegirá un sistema deductivo capaz de axiomatizar la matemática -él eligió el de Principia Mathematica, la obra monumental de Whitehead y Russell, aunque está consciente de que su resultado no es una consecuencia exclusiva de éste- y luego mostrará que una de las fórmulas bien formadas de este sistema dice esto: "yo no soy demostrable". Este es el teorema G. Ahora mírese. Igual a como teníamos antes:

  • Si G es un teorema, entonces se puede demostrar; pero entonces lo que él dice es falso; luego él es un teorema falso, y el sistema es incorrecto.
  • Si G no es un teorema, entonces no se puede demostrar; pero entonces lo que él dice es verdadero; luego él es una verdad que no se puede demostrar, y el sistema es incompleto.
Para poder llevar a cabo este proyecto, primero debe mostrar tres cosas:

  1. Que el sistema deductivo escogido es autorreferente; es decir, es capaz de hablar acerca de sí mismo.
  2. Que el sistema puede hablar acerca de sus propias demostraciones.
  3. Que las proposiciones pueden hablar acerca de sí mismas.
Hagamos ahora un seguimiento de cómo Gödel consigue estos tres pasos.

Paso 1) El sistema es autorreferente: la numeración Gödel

Gödel exige sólo dos cosas para llevar a cabo su demostración: 1) que el sistema deductivo sea capaz de formalizar la aritmética, y 2) que el lenguaje utilizado sea recursivo y numerable.
Esta segunda condición es crucial. Por recursivo queremos decir que todas las fórmulas bien formadas se obtienen a partir de un conjunto finito de elementos atómicos mediante la aplicación de un número finito de manipulaciones en un número finito de pasos: por ejemplo, un lenguaje formal de la lógica proposicional puede considerar como símbolos primitivos sólo la "$p$", el apóstrofe " ' ", y los signos "$\neg$", "$\to$", y los paréntesis $\text{(}, \text{)}$. Luego las reglas de construcción dicen:

  1. "$p$" es una fórmula bien formada atómica.
  2. Si $A$ es una fórmula bien formada atómica, entonces "$A'$ " es una fórmula bien formada atómica.
  3. Todas las fórmulas bien formadas atómicas son fórmulas bien formadas.
  4. Si $A$ y $B$ son fórmulas bien formadas, entonces "$(A \to B)$" y "$\neg A$" son fórmulas bien formadas.
  5. Nada más es una fórmula bien formada.
Y cuando decimos que son numerables queremos decir que aunque sean infinitas fórmulas, ellas siempre pueden contarse con los números naturales. Aunque no sea evidente a simple vista, la condición 5 es suficiente para asegurar esto.
Resulta que el lenguaje de Principia Mathematica es recursivo y numerable, pero no sólo eso, también todos los otros lenguajes formales que se usan en matemáticas, en ciencias de la computación y en general en casi cualquier área donde se requieran lenguajes artificiales.
El primer paso en la demostración de Gödel es mostrar que, dado un lenguaje recursivo y numerable, existe una forma de traducir este lenguaje símbolo por símbolo a la teoría de números naturales, de manera que a cada fórmula bien formada del lenguaje le corresponde un y sólo un número natural que contiene la misma información que él. El procedimiento de Gödel es engorroso, pero una vez que se nota la idea, se pueden hacer tantas variantes como se quiera. No estamos por la labor de formalizar un lenguaje de Orden Superior como el de Principia Mathematica, pero para ilustrar el punto voy a dar la g-numeración del ejemplo anterior.
Tenemos seis símbolos primitivos: $p$ , $'$ , $\neg$ , $\to$ , $\text{(}$ , $\text{)}$ .
A cada uno de estos le asignaremos un número del 1 al 6, así:

  • $p$ = 1
  • $'$ = 2
  • $\neg$ = 3
  • $\to$ = 4
  • $\text{(}$ = 5
  • $\text{(}$ = 6
Y ahora vamos a traducir las cinco reglas de formación de fórmulas bien formadas a expresiones aritméticas. Esto es bastante sencillo:
  1. 1 es una fórmula bien formada atómica.
  2. Si $x$ es una fórmula bien formada atómica, entonces $(x * 10) + 2$ es una fórmula bien formada atómica.
  3. Todas las fórmulas bien formadas atómicas son fórmulas bien formadas.
  4. Si $a$ es una fórmula bien formada de $m$ dígitos y $b$ es una fórmula bien formada de $n$ dígitos, entonces "$(5(10^m + n +2))+(a(10^n +2))+(4(10^n +1))+(10b+6)$" y "$(3(10^m))+a$" son fórmulas bien formadas.
  5. Nada más es una fórmula bien formada.
La regla 4 se ve escalofriante, pero en realidad es bastante simple. Primero, fijémonos en las proposiciones atómicas. Cuando el otro sistema generaba estas:

$p$, $p'$, $p''$, $p'''$, $p''''$...

El nuevo sistema general estas:

$1$, $12$, $122$, $1222$, $12222$...

Ahora, el primer sistema nos dice que, si tenemos por ejemplo "$p$" y "$p'''$", podemos construir "$(p \to p''')$". Pero el segundo sistema nos dice que, si "$1$" y "$1222$" son dos fórmulas bien formadas -y lo son-, entonces... -la $m$ aquí es 1 porque "1" tiene un dígito, y la $n$ es 4 porque "1222" tiene cuatro dígitos:

$(5(10^1+4+2))+(1(10^4+2))+(4(10^4+1))+(1222*10+6)$
$(5(10^7))+(1(10^6))+(4(10^5))+(1222*10+6)$
$(50000000))+(1000000))+(400000)+(12220+6)$
$51412226$

Y en este número cada dígito queda exactamente en el mismo lugar que su correspondiente en la fórmula del otro lenguaje: el 5 en el lugar del primer paréntesis, el 1 en el lugar de la "$p$", el 4 en el lugar de "$\to$"... y así sucesivamente.
Lo asombroso de esto es que, por complicado que sea el lenguaje, siempre es posible hallar una manera de asignarle a cada fórmula un y sólo un número natural -de hecho el método particular de Gödel sirve para cualquier lenguaje recursivo y numerable-. Estos número se llaman, convenientemente, números Gödel o g-números, y son tan asombrosamente útiles que se los ha empleado en computación y en muchas otras ciencias aplicadas -después de todo, ¿quién no querría un método directo para enseñarle cualquier lenguaje a una calculadora?
Pero no perdamos el hilo de lo que estamos haciendo. Ya dijimos que el lenguaje del sistema deductivo que escogimos es recursivo y numerable, pero también dijimos que puede axiomatizar la aritmética. Ahora mírese con cuidado: como este sistema puede axiomatizar la aritmética, puede expresar enunciados sobre números. Y como existe una g-numeración para él, él puede expresarse en términos de números. Pero entonces, si el lenguaje puede expresar enunciados sobre números y los números pueden expresar las proposiciones de este lenguaje... el lenguaje es capaz de hablar acerca de sí mismo, si lo hace a través de los números Gödel.
Esta es la parte en que algunos se levantan y salen a correr y a gritar por la cuadra. Para cuando vuelvan los que quieran hacerlo, aquí sigue el resto de la demostración.

Paso 2) El sistema puede hablar acerca de sus demostraciones: los pares de prueba.

Ahora tenemos un lenguaje capaz de hablar de sí mismo, pero esto todavía no es suficiente para generar el teorema G. El problema que tenemos que enfrentar ahora es que, aunque el lenguaje puede decir cosas acerca de sus fórmulas, todavía tenemos que traducir una noción más sofisticada, que es la de demostración.
Recordemos: una demostración formal es una seguidilla finita de fórmulas, cada una de las cuales es un axioma, una premisa o un teorema obtenido de la aplicación de alguna regla de inferencia sobre los pasos anteriores. La última fórmula de la serie es la conclusión, o lo que se está demostrando.
Ahora lo que haremos será construir el número Gödel de una demostración formal.
Hay dos maneras de hacer esto. En lo personal la que más me gusta es la segunda, donde, usando el Teorema de la Deducción, se prueba que para cada demostración formal existe una y sólo una fórmula condicional que expresa su sentido, y luego basta con dar la noción de conclusión en términos de g-números. Pero voy a mostrar en cambio la primera, que es la que usa Gödel y que no necesita el Teorema de Deducción.
Dijimos que una demostración formal es una serie finita de fórmulas. Podemos enseñarle al lenguaje a expresar estas series, si le damos dos nuevos símbolos: un tabulador -puede ser la coma ","- y un signo de introducción de la conclusión -por ejemplo: "$\vdash$"). Ahora damos reglas de construcción de "demostraciones", donde todos los pasos aparecen en orden, separados por tabuladores, y el último aparece separado del penúltimo por un signo de introducción de la conclusión. Entonces la demostración formal de Z a partir de los A, D, E, F y H pasos deductivos se podría ver así:

$A , D , E , F , H \vdash Z$

Este nuevo lenguaje ampliado para escribir las deducciones como si fueran fórmulas también es recursivo y numerable, por lo tanto, todas estas demostraciones tienen g-números.
La relación entre un teorema y su demostración puede entonces expresarse en términos numéricos. En su excelente libro, Gödel, Escher, Bach: un Eterno y Grácil Bucle Douglas Hofstadter llama a estos números "pares de prueba", porque relacionan unívocamente una demostración con su conclusión -por ejemplo, el g-número de "$A,D,E,F,H \vdash Z$" con el de "Z"-. Esta relación puede expresarse en términos de relaciones entre números. Y como nuestro lenguaje es capaz de decir cosas acerca de los números, el siguiente signo de relación es bien formado:

$D(x,y)$ : "x" es el g-número de la demostración de una fórmula cuyo g-número es "y".

Lo que, dicho en simple, es:

$D(x,y)$ : "x" es la demostración de "y".

Ahora puedo cuantificar esta fórmula y obtener esta valiosa fórmula general:

$\exists x D(x,y)$ : "Existe una demostración para "y".

Paso 3) Las fórmulas pueden hablar acerca de sí mismas: el predicado de autorreferencia.

El paso final y quizás el más sofisticado consiste en lograr que una fórmula pueda hablar acerca de sí misma usando la numeración Gödel. El problema crucial aquí radica en lo siguiente: considérese la paradoja del mentiroso:

Esta oración es falsa

Aunque entendemos lo que quiere decir, esta oración no habla directamente de sí misma, porque ella no está incluida en ella misma como sujeto. El demostrativo "esta" nos ayuda a saber de quién se habla, pero no lo hace explícito. Y no sólo eso, sino que es imposible explicitarlo:

"Esta oración es falsa" es falsa

Ya no es la misma oración de arriba. Si intentamos reemplazar el "esta oración" por la oración consecuente, obtenemos una regresión infinita que nunca llega a la oración original:

""""""..." es falsa" es falsa" es falsa" es falsa" es falsa" es falsa" es falsa

Lo mismo ocurre con los g-números. Una fórmula cualquiera, digamos, X, tiene un g-número, digamos, 2356543213467. Si, por ejemplo, el g-número de una variable allí dentro es el primer 6, introducimos el número entero en la expresión y nos queda esto: 2352356543213467543213467. Pero este ya no es el mismo número de X.
Sin embargo, Gödel inventó una forma bastante original de lograr que una proposición hable acerca de sí misma con la numeración Gödel.
Considérese el siguiente signo de relación bien formado:

$Q(x,y,z)$ : "x" es el g-número que se obtiene de reemplazar cada variable libre en la fórmula cuyo g-número es "y" por "z".

Este signo es bien formado, porque expresa una proposición acerca de números y ya dijimos que nuestro lenguaje puede hablar acerca de los números. Lo que él dice es que, si reemplazas las variables de "y" por "z", obtienes la fórmula "x". Siguiendo el ejemplo anterior, la siguiente proposición sería verdadera:

$Q(2352356543213467543213467,2356543213467,2356543213467)$ (mírese bien dónde están las comas).

Ahí lo único que dice es que, si ponemos el último número en la variable libre -el primer seis- del segundo número, obtenemos el primer número.
Como este es un caso particular en el cual la "y" y la "z" son el mismo número, haremos un predicado especial:

$S(x,y)$ : "x" es el g-número de la fórmula que se obtiene de reemplazar toda variable libre en la fórmula cuyo g-número es "y" por "y".

Ahora viene la magia. Combinemos todos los elementos que tenemos para crear el teorema G.
Lo que queremos es que el teorema G diga: "yo no soy demostrable". Esto va a salir de otra fórmula más simple, que dice: "x no es demostrable". Esta fórmula ya sabemos escribirla:

$\neg \exists x D(x,y)$

Ahora, queremos introducir el g-número de esta fórmula en el lugar de la "y" para obtener una paradoja. Pero sabemos que si lo hacemos directamente, obtendremos una tercera fórmula, que no dirá lo mismo que la primera. Para eso hemos creado la relación S. Mírese:

$\neg \exists x (D(x,y) \land S(y,z))$

Ahí lo que dice es que: no hay una demostración para "y", y además "y" es la fórmula que se obtiene de hacer que "z" hable acerca de sí misma. Pero queremos que "y" exista, así que lo mentamos explícitamente:

$\exists y \neg \exists x (D(x,y) \land S(y,z))$

Ahora bien, esta fórmula tiene un g-número. Va a ser un número muy grande, pero imaginemos que empieza con 2365... y termina con ...8361. Este número puede ser utilizado para reemplazar la única variable libre en su fórmula, que ahora es la "z". Y se obtiene esta fórmula:

$\exists y \neg \exists x (D(x,y) \land S(y,2365 \cdots 8361))$

Ahí lo que dice es: la fórmula que se obtiene de reemplazar cada variable libre en la fórmula cuyo g-número es 2365...8361 por este mismo número no es demostrable. Pero esta fórmula ¡es la fórmula que se obtiene de reemplazar cada variable libre en la fórmula cuyo g-número es 2365...8361 por este mismo número! Por lo tanto, lo que dice esta fórmula -que es, como se habrán imaginado, el teorema G- es, finalmente: yo no soy demostrable.

Paso final: la Incompletud

¿Qué es lo que pasa a continuación? Ya lo dijimos más arriba:
  • Si G es demostrable, entonces el sistema es incorrecto.
  • Si G no es demostrable, entonces el sistema es incompleto.
Algún ingenioso aventuró, cuando se publicó el resultado por primera vez, que quizás se podía evitar la Incompletud agregando G como un Axioma -después de todo, los axiomas son todos teoremas no demostrables. Pero Gödel mostró que, si se hace esta maniobra, un nuevo teorema G puede obtenerse dentro de este sistema "arreglado".
Pero, ¿qué implica esto de que los sistemas que axiomatizan la aritmética sean incompletos? Esta es la parte más sutil del argumento y la que debe ser mejor entendida.
Lo que el Teorema de Gödel prueba es hay verdades matemáticas que no pueden ser demostradas. También, que no existe un lenguaje a la vez lo suficientemente expresivo para axiomatizar la aritmética y no lo suficiente como para hablar acerca de sí mismo. También demuestra que ningún sistema puede demostrar su propia consistencia; hacerlo lo convierte en un sistema incorrecto, que es lo mismo que hacerlo inconsistente.
Cuando el Teorema de Gödel fue publicado la primera vez, algunos pensaron que se trataba de una anomalía que no tendría consecuencias prácticas, dado que el teorema G es una curiosidad, una fórmula como la paradoja del mentiroso. Pero lo asombroso es que pocos años después Jeff Paris y Leo Harrington llegaron a un resultado en teoría de números que se basaba en el Teorema de Gödel. Este Teorema, llamado convenientemente "Teorema de Paris-Harrington", muestra que una cierta proposición en la teoría de Ramsey es verdadera en la aritmética de Peano, pero no demostrable. El camino que utilizaron fue el de la reducción al absurdo, pero a un nivel de abstracción más alto del que se acostumbraba hasta ese entonces: lo que hicieron fue probar que, si la proposición considerada era demostrable en la aritmética de Peano, entonces eso permitía demostrar que la aritmética de Peano es consistente; pero eso equivale a decir que la aritmética de Peano puede probar su propia consistencia. Pero el Teorema de Gödel dice que ningún sistema puede probar su propia consistencia; luego, por absurdo, la proposición considerada no es demostrable -aunque sigue siendo verdadera.

Lo que NO dice el Teorema de Gödel

Lamentablemente, muchas veces se le ha atribuido al Teorema de Gödel más significado del que realmente tiene. Sólo para aclarar las cosas, digamos brevemente que el Teorema de Gödel:
  1. NO prueba que la verdad no existe
  2. NO prueba que las matemáticas son falsas
  3. NO prueba que todo es relativo
  4. NO prueba que existe Dios
  5. NO prueba que se va a acabar el mundo
  6. NO prueba que vienen los extraterrestres
  7. NO garantiza la verdad de ninguna doctrina ocultista
  8. NO tiene mucho que ver con la Teoría del Caos
  9. NO prueba la inmortalidad del alma
  10. NO dice nada remota o cercanamente relacionado con los nueve puntos anteriores

Parte de la seriedad en la investigación lógica y matemática consiste en saber cuándo sacar algo a colación y cuándo no. Por regla general, quienes sacan a relucir el Teorema de Gödel en televisión, en la radio o en cualquier conversación de taberna sin que el tema sea específicamente la lógica, la filosofía -académica- o la matemática, de seguro no es un investigador serio o no entiende realmente lo que es el Teorema de Gödel. La palabra "Incompletud" en modo alguno debe ser entendido fuera de su justo contexto, que fue el que explicamos aquí.

Referencias

Para quienes deseen explorar por sí mismos la demostración que aquí he resumido, les recomiendo ir en orden, desde las versiones más simples hasta las más complejas -con un poco de suerte, nunca tendrán que enfrentarse al texto original de Gödel. El camino que yo puedo recomendar es éste: partir con Forever undecided de R. Smullyan, traducido al español como Juegos por siempre misteriosos. Luego, toda la primera parte de Gödel, Escher, Bach, lo que para algunos será excesivo pero para los realmente interesados será un viaje apasionante; luego, el artículo del mismo Smullyan en el Blackwell companion to Philosophical Logic aproxima las cosas de una manera más formal, para continuar con una versión ya seria y bien explicada, como puede ser la de Ladrière en Límites internos de los formalismos. Si estas versiones se comprenden correctamente, ir al texto original de Gödel debería hacerse con pocas -nunca sin- complicaciones.

IMå