SOBRE LA NATURALEZA SUFICIENTE (COMPLETA) DE LOS SISTEMAS FORMALES DE RAZONAMIENTO

Kurt Gödel, El lógico.

Un sistema formal de razonamiento tiene ciertas características. Por sistema se entiende a una colección de objetos. Asimismo, el sistema es formal porque los objetos de la colección son símbolos, que pueden ser escritos en un solo caracter. Esto se emplea para razonar, para establecer deducciones donde unos símbolos lleven necesariamente a otros símbolos de acuerdo a unas reglas de deducción que determinen este hecho.

Como el título refiere, se reconocerá la naturaleza suficiente de estos sistemas, es decir, que basta con un sistema de este tipo para deducir todos los símbolos posibles de ser deducidos. También se puede nombrar a esa naturaleza suficiente como completa porque no haría falta ningún símbolo ni regla ajenos a estos sistemas para deducir todos los símbolos posibles de ser deducidos.

El hallazgo de esta naturaleza suficiente fue hecho por vez primera gracias a Kurt Gödel en su artículo «La suficiencia de los axiomas del cálculo lógico de primer orden» en el año 1930.

Aquí se toma un camino distinto al original de Gödel para llegar al mismo resultado. Primeramente se establecerán todos los símbolos que conformen a los sistemas formales de razonamiento. Luego, se detallarán las reglas de deducción para, finalmente, observar que una consecuencia del sistema formal de razonamiento es la suficiencia.

ESTABLECIMIENTO DE UN LENGUAJE LÓGICO

Sea un lenguaje lógico tal que cuente necesariamente con:

1. Variables (i, j, k, etc.). Hacen referencia a «cosas», aquello sujeto a un razonamiento. Por ejemplo, al referirse a los hijos de una mujer se tienen las variables hijo₁, hijo₂, hijo₃, etc. (hasta donde sean posibles o existentes) y mujer. Estas variables pueden abreviarse con letras: hijo₁=i, hijo₂=j, hijo₃=k, etc., y mujer=χ.

2. Constantes (a, b ,c, etc.). Hacen referencia a «cosas» fijas y sujetas a un razonamiento. Por ejemplo, María es una constante y se podría simbolizar como m.

No es necesario contar con las constantes para el lenguaje, pero es posible tenerlas presentes.

3. Cuantificador universal (∀). Hace referencia a la totalidad. Por ejemplo, cualquier hijo se escribe ∀i, siendo i la representación en forma de variable de los hijos. Se dice cualquier hijo, cualquier madre y se escribe ∀i∀j, o simplificando, ∀ij.

4. Relatores. Al menos uno que relacione pares de variables. Por ejemplo, Riχ, donde i y χ son las variables relacionadas por el relator R. Es posible que R sea el relator de la relación i es el hijo de χ.

5. Negador (¬). Muestra el complemento de una expresión. Por ejemplo, de la relación Rij mencionada, ¬Rij expresa la relación i no es hijo de j, que es la expresión complementaria a la primera.

Si se tiene una parte (como Rij), su complemento (¬Rij) es lo faltante, y no hay más. Por lo tanto, el complemento del complemento de una relación es necesariamente dicha relación (a Rij le falta ¬Rij; el complemento del complemento, ¬¬Rij, es aquello que le falta a ¬Rij, o sea Rij).

La negación ¬∀ expresa lo que no es la totalidad, o sea la parcialidad, cuando sólo se conoce la existencia de una parte. La negación ¬∀ se simboliza como ∃ y dice para algún, y se observa que no se refiere a la totalidad, sino a una parte. También ∃ es un cuantificador (cuantificador particular). Más adelante, al detallar las reglas de deducción lógica, se especificará la naturaleza de éste.

6. Implicador (→). Hace que una relación implique a otra. Por ejemplo, con la relación Rij mencionada, i es hijo de j, también se puede expresar que j es madre de i con la relación Sji. Entonces queda →RijSji, si i es hijo de j, entonces j es madre de i.

A partir del negador y el implicador se pueden abreviar y simbolizar algunas expresiones como el:

7. Conjuntor (Λ). Sean A y B expresiones con relatores (como Rij). Se tiene que →A¬B puede abreviarse como ΛAB.

Por ejemplo, con la relación Rij ya conocida y otra relación Qij diciendo i es hermano de j es posible establecer ¬→Rij¬Rkj, es decir, la negación (¬) de si (→) i es hijo de j (Rij), entonces k no es hijo de j (¬Rkj). Esta negación refiere a lo faltante de dicha condición, es decir donde no se tiene la condición. Si la condición está ausente para que ambos i y k sean hijos de j, simplemente se admite que ambos lo son, o sea tanto i es hijo de j como k es hijo de j, o ΛRijRkj.

También se puede expresar ΛRijRkj como i es hijo de j y k es hijo de j.

Así, la expresión →ΛRijRkjQik dice si (→) i es hijo de j y k es hijo de j (ΛRijRkj), entonces i es hermano de k (Qik).

8. Disyuntor (V). Sean A y B expresiones con relatores. Se tiene que →¬AB puede abreviarse como VAB.

Por ejemplo, con la relación Sij mencionada (i es madre de j) es posible establecer que →¬SijSik, es decir, si (→) i no es madre de j (¬Sij), entonces i es madre de k (Sik). Esto sólo especifica que en caso de que el hecho ¬Sij ocurra, será que necesariamente Sik también ocurra. Sin embargo, que no ocurra ¬Sij no implica necesariamente que el hecho Sik deje se ocurrir; sólo lo anterior ofrece garantía de validez lógica.

Entonces cuando Sik ocurre, tanto si ¬Sij ocurre o no, es decir, tanto si Sij o ¬Sij ocurren o no. Cuando ¬Sij no ocurre se sabe directamente que no ocurre Sik, o bien, que ¬Sik ocurre.

En resumen, cuando Sik ocurre pueden ocurrir ¬Sij o Sij. Si no ocurre ¬Sik es porque Sij ocurre (no ocurre ¬Sij). Puede ser que Sik y Sij ocurran juntos, o que uno ocurra y el otro no. Se dice, según esto último, que ocurre Sik o Sij (o ambos), o sea VSijSik (que i es madre de j, o i es madre de k, o i es madre tanto de j como de k).

9. Biyector (↔). Sean A y B expresiones con relatores. Se tiene que Λ→AB→BA puede abreviarse como ↔AB.

Con las relaciones ya conocidas, tanto →RijSji (si i es hijo de j, entonces j es madre de i) como →SjiRij (si j es madre de i, entonces i es hijo de j) ocurren. Esto se sabe puede expresarse como Λ→RijSji→SjiRij, o bien como ↔RijSji (que i es hijo de j si y sólo si j es madre de i).

Mientras todas las abreviaciones puedan expresarse en términos del implicador y el negador, se dirá que sólo basta con esos recursos para establecer el lenguaje. No obstante, las abreviaciones facilitan el empleo del mismo, simplificando expresiones que podrían quedar realmente largas. Cualquier definición a partir de las abreviaciones (como aquella empleada para el biyector) es válida, pues todas ellas se encuentran en términos del implicador o el negador.

REGLAS DE DEDUCCIÓN

El lenguaje establecido permite expresarse de forma razonable, lógica, sobre las «cosas». La frase «expresarse de forma lógica» significa que pueden deducirse relaciones entre las «cosas» sabiéndose con anterioridad algo más sobre éstas. Para ello también se requiere de reglas sobre tales deducciones. Algunas ya se han expuesto:

1. Las expresiones A y B se forman con relatores. Cuando A implica B (cuando A lleva a deducir B), se escribe →AB. Cuando tanto A como B ocurren o se conocen, se escribe ΛAB. Cuando A o B (o ambas) ocurren, se escribe VAB.

2. →¬¬AA. (Si ¬A se niega, entonces queda A, o ¬¬A implica A).

3. ↔¬∀xA∃x¬A. (El complemento del cuantificador universal se da si y sólo si se da el cuantificador particular; x es cualquier variable presente en los relatores de A).

4. ↔∀xAA (A es si y sólo si ∀xA, con x una variable en A)

5. →Λ→ABAB. (→AB y A implican que B).

6. →VΛABAΛAB (Tanto A como B, o A –o ambas– implican que sean tanto A como B).

7. →ΛVABAA (Tanto A o B –o ambas–, como A implican A).

8. ↔↔AB∀xy...zΛ→AB→BA Aquí x, y, …, z son variables que se encuentran en las relaciones conformando tanto a A como a B.

Con ellas las deducciones adquieren precisión.

Por ejemplo, retomando las relaciones Rij, Sij y Qij conocidas, se realizan algunas deducciones comunes:

1. →ΛRijRkjQik se sabe que si i y k son hijos de j, ambos resultan hermanos.

2. Rij se sabe que i es hijo de j.

3. Rkj se sabe que k es hijo de j.

4. ΛRijRkj porque Rij y Rkj se saben, según la regla 1.

5. Λ→ΛRijRkjQikΛRijRkj porque tanto la condición (→ΛRijRkjQik) como ΛRijRkj se saben.

6. Qik como se sabe aquello en 5, según la regla 3 debe ser así, que implique Qik. En ese caso, de la regla 5 A es ΛRijRkj y B es Qik.

Se dedujo que i es hermano de k.

Con las reglas y los recursos considerados pueden conseguirse razonamientos favorables y acordes con aquello presente en la intuición general, donde según el ejemplo observado, efectivamente, si dos individuos son hijos de la misma madre, ambos son hermanos.

Las deducciones pueden ampliarse y complicarse de las formas más diversas, estableciéndose reglas nuevas derivadas de las ocho reglas de deducción establecidas. Todo ello puede aplicarse a lo que es sabido, lo que se conoce, de las «cosas» sin importar qué sean dichas «cosas», con tal de descubrir nuevos aspectos de las mismas.

LA NATURALEZA SUFICIENTE

A continuación, se presenta una deducción donde las «cosas» expresadas en el razonamiento son unas cuya naturaleza se especificará con tal de demostrar que los recursos aquí presentados son suficientes para expresarlo todo de forma lógica.

Hasta el momento se ha asumido que esto es posible, que todo puede expresarse de forma lógica, pero no se ha mostrado la contundencia de ello, es decir, que esto resulte creíble no sólo porque así sea expuesto sino porque así sea realmente observado. Porque esa situación pueda ser puesta a discusión de forma lógica.

La pretensión es, por consiguiente, deducir que el lenguaje establecido junto con sus reglas puede expresar deducciones válidas para todas las «cosas». De antemano, si esto es cierto, quiere decir que 1) todas las expresiones lógicas posibles refieren únicamente a las «cosas» y que entonces 2) de todas esas expresiones sólo pueden deducirse otras expresiones y ninguna otra cosa. O que todas las expresiones son deducibles únicamente a partir de otras expresiones lógicas. Porque si todas las expresiones se refieren a todas las «cosas», cualquier expresión deducida tendría, por lo anterior, que hacer referencia a una de las «cosas».

Se supondrá que existe aquella «cosa» que no puede ser referida por medio de expresiones lógicas. Esto es, Exy dice x se expresa con (el lenguaje lógico) y. Y se está considerando que hay un x tal que ¬Exy.

Se sabe que existe dicha «cosa» inexpresable con el lenguaje y si y sólo si entonces no existen los símbolos para generar la expresión refiriéndose a tal «cosa». Esto puede expresarse como sigue: ∀ij↔¬Eij¬∀kΣki donde Σki dice k simboliza a i (o que k no es parte de los símbolos en la expresión de i). También, según la regla 3, puede expresarse como ∀ij↔¬Eij∃k¬Σki, o sea que para cualquier «cosa» (i) y para cualquier lenguaje lógico (j), si la «cosa» no es expresable con ese lenguaje (¬Eij), entonces existe un símbolo (k) tal que no simbolice a la «cosa» (∃k¬Σki).

Sin embargo, todos los símbolos ∀, i, j, →, ¬, E, ∃, k, Σ, se hallan presentes en la expresión que refiere a la «cosa» que se suponía inexpresable. En otras palabras, se sabía que si la «cosa» era realmente inexpresable, entonces haría falta algún símbolo para expresarla. No obstante, los símbolos se han presentado y resultan suficientes para expresar cómo es que la «cosa» inexpresable resulta ser así. Entonces, se sabe por la evidencia que ¬∃k¬Σki; no hay símbolo (¬∃k) tal que no logre simbolizar a la «cosa» inexpresable (¬Σki).

De todo esto se tiene la siguiente deducción:

1. ∀ij↔¬Eij∃k¬Σki ó ∀ij↔¬Eij¬∀kΣki premisa 1 (primera circunstancia conocida).

2. ¬∃k¬Σki premisa 2 (segunda circunstancia conocida).

3. ∀kΣki según la regla 3.

Para continuar se deducirá previamente que:

A. ↔AB premisa A.

B. ¬A premisa B.

C. Λ→AB→BA según la abreviatura que es el biyector.

D. ΛV¬ABV→B¬A según la abreviatura que es el disyuntor.

E. ΛV¬ABAV→B¬A porque tanto A como ΛV¬ABV→B¬A se conocen.

F. ΛAV→B¬A según la regla 6.

G. ΛV→B¬AA porque la expresión no se modifica (tanto A como V→B¬A, o bien, tanto V→B¬A como A).

H. ¬B según la regla 6.

I. →Λ↔AB¬A¬B porque tanto ↔AB como A se conocen e implican ¬B.

Por lo tanto,

5. ↔¬Eij¬∀kΣki por la regla 8.

6. Λ↔¬Eij¬∀kΣki∀kΣki tanto lo anterior como ∀kΣki se conocen.

7. Eij según la deducción de I.

8. ∀ijEij según la regla 4.

Esto expresa que para todas las «cosas» y todos los lenguajes lógicos (∀ij), todas las «cosas» son expresables con ellos (Eij).

Así se garantiza la contundencia de que el lenguaje lógico establecido pueda referirse a las todas las «cosas» y que, en consecuencia, todas las expresiones sólo se refieren a dichas «cosas».

Finalmente, todas las expresiones del lenguaje lógico sólo deducen expresiones elaboradas con el mismo lenguaje. Nótese que se dedujo válido Eij para todo los lenguajes lógicos, pero deben ser sólo aquellos donde pueda ser deducible Eij. Y aquellos donde es deducible Eij deben presentar, al menos, las reglas de deducción aquí expuestas y utilizadas.

Para observar la deducción de cualquier expresión lógica es suficiente tener tanto al lenguaje lógico como sus reglas de deducción.

Con dicho lenguaje y sus reglas de deducción no hace falta nada más para observar la deducción de cualquier expresión lógica. El sistema formal de razonamiento está completo, pues no tiene ni símbolos ni reglas faltantes.

15 de Julio de 2013

TEOREMAS DE INDECIDIBILIDAD. EL TEOREMA DE GÖDEL

[El siguiente texto contiene la demostración formal e inductiva que fue obtenida en primer lugar que las presentes en este blog. Una demostración que contiene los conceptos de Alfred Tarski que facilitan la resolución de las conclusiones de Gödel. Una demostración que simplifica las dadas por Henkin, Boolos y el mismo Gödel, pues resulta más accesible, admisible, el hecho intuitivo de la indecidibilidad. Aun así, las sentencias indecidibles siguen sin ser demostrables verdaderas o falsas.]

Se sugiere un sistema formal [SF] donde cada relator, funtor y constante que presenta tiene asociado uno y sólo un objeto dado un modelo [M] de valoraciones conocidas. Se asume a SF consistente.

En el planteamiento de este sistema formal, SF incluye la sentencia A:

Sentencia A. Todo modelo se relaciona.

∀iFYiMF donde Yij representa cualquier relación lógicamente válida y MF dice el objeto asociado a la sentencia F dado el modelo M.

Cabe aclararse que F es una sentencia cualquiera, incluyendo las de SF, y el objeto MF se refiere a aquel conformado por objetos presentes en el universo del modelo M en cuestión, asociados ya sea a sus relatores, o a sus funtores, o a las constantes. En este punto del análisis se puede estudiar el fenómeno inductivo presente: cuando se establece una sentencia A₁ cuyo objeto presente en el universo del modelo se halle determinado, esta sentencia induce a una sentencia A₂ (según SF lo admite como otra F) cuyo objeto correspondiente se puede determinar y que nuevamente induce a otra A₃ y sucesivamente se puede obtener una A_n. Si se detiene la obtención inducida de objetos presentes en el universo del modelo, la sentencia A_n carece de un objeto como tales. Esto es una demostración del siguiente:

Teorema I. Si se relacionan los objetos presentes en el universo de un modelo dado, asociados estos a las sentencias de un sistema formal consistente, existe al menos una de estas sentencias que necesariamente carezca de un objeto asociado y presente en el universo mencionado.

Esto en virtud de la Definición 1 [El teorema fundamental de la Lógica, 31 de Marzo de 2012; 20 de Diciembre de 2012 en este blog], sobre la verdad de una sentencia, que permite decidir la veracidad (o deducir el carácter de verdadero o falso) de la misma, implica identificar el:

Teorema II. En un sistema formal consistente, la veracidad de alguna de sus sentencias (efectivamente verdaderas) es necesariamente indecidible.

Si no se tiene el objeto asociado que pertenezca al universo del modelo dado, no se puede observar que la sentencia (del tipo A) sea verdadera o falsa dado que las valoraciones no caben dentro de su análisis. Como el sistema formal se sabe consistente, la sentencia es, en efecto, verdadera, pero esto, porque carece de objeto asociado, no posible decidirlo a partir de alguna demostración en el mismo sistema formal. Esto es el teorema de Gödel. Por supuesto, el Teorema fundamental de la Lógica permitiría decidirlo solamente deduciendo todos los teorema posibles y hallando que no se tengan contradicciones, pero la cantidad de teoremas posibles es incalculable: cada teorema deducido implica uno más al menos. De allí que la única forma factible para decidir la veracidad de una sentencia sea a través de su objeto asociado. También, según se obtiene del Teorema fundamental de la Lógica, el sistema puede que deduzca sentencias verdaderas y no sus negaciones y aún así habrá alguno del cual se desconozca realmente si no es deducible su negación; esto último fue descubierto por George Boolos [1989] en su demostración por medio de algoritmos.

La demostración de Gödel mediante recursivas emplea a los números como objetos asociados a las sentencias del propio sistema formal que los estudia, la Matemática. En el caso presente, las sentencias del tipo A funcionan como las recursivas de Gödel y se logra, como en la demostración numérica, obtener que alguna sentencia tenga su objeto asociado indeterminado.

Partiendo del Teorema II se obtiene la segunda conclusión de Gödel, esto es:

Teorema III. Ningún sistema formal consistente puede deducir su propia consistencia.

También se puede expresar, que ningún sistema formal consistente tiene como teorema su propia consistencia. Esto se nota considerando la indecidibilidad de la sentencia a la cual se refiere el Teorema II. Si el sistema se observa que es consistente y se dedujo que presenta al menos un teorema indecidible, entonces el hecho de que el mismo sistema pudiere deducir su consistencia en forma de un teorema no es posible, porque contradiría al Teorema II y en consecuencia, el hecho de que el sistema es consistente. Como la aseveración de la consistencia del sistema formal es verdadera pero no se puede deducir por lo estipulado en el Teorema III, se asume que es la misma una sentencia de las que el Teorema II propone indecidibles. Nótese que de no asociársele a la aseveración de la consistencia del sistema formal un objeto dado el modelo que permite valorar dicha consistencia, entonces sí podría ser deducible para cualquier sistema formal consistente pero quedaría indecidible como señala el Teorema I.

1 de Abril de 2012

 

 

EL TEOREMA FUNDAMENTAL DE LA LÓGICA

Dada la forma de sentar las bases de un sistema formal (con relatores, funtores, constantes, variables, cuantificador generalizador, implicador y negador junto con los axiomas lógicos, las reglas de inferencia correspondientes y los axiomas del sistema) así como la admisión de modelos y valoraciones correspondientes, se tiene:

Definición 1. Una sentencia (según se las tiene entendidas) es verdadera respecto a un modelo siempre y cuando cualesquiera valoraciones posibles la validen.

Se tienen, por hipótesis, dos sentencias que bajo el mismo modelo resultan verdaderas. Se dice que ambas son consistentes entre sí y que la colección de sentencias que forman es consistente. En general:

Definición 2. Una colección de sentencias y el sistema formal al cual comprenden, se dicen consistentes si para todas las valoraciones posibles de un modelo dado todas las sentencias quedan verdaderas.

Las sentencias de un sistema formal consistente deducen teoremas (sentencias obtenidas de una deducción por medio de las reglas de inferencia, los axiomas lógicos y los axiomas del sistema) consistentes porque se los valora según el mismo modelo. De tal forma, los teoremas también se admiten como parte del sistema formal.

Teniendo un sistema formal desconocido consistente o inconsistente se efectúa una demostración en la cual se deduce cierto teorema. Luego partiendo de otra demostración se deduce la negación del teorema que se obtuvo de la primera demostración. A este tipo de sistemas se les dice inconsistentes (no consistentes) porque no hay forma de que alguna valoración según un modelo dado pueda validar ambos teoremas. Esto es, si se da el caso de un sistema formal inconsistente porque deduce contradicciones (teoremas y sus negaciones) y se impone a éste cualquier modelo, en ningún caso (evidentemente) se podrá observar que las valoraciones determinen que todas las sentencias son verdaderas: si una de las deducidas por el sistema queda verdadera, la negación queda no verdadera, es decir, falsa.

Por esto se expresa el siguiente:

Teorema fundamental de la Lógica. Si de un sistema formal se deduce al menos un teorema y también su negación, entonces el sistema formal se dice inconsistente.

∎

31 de Marzo de 2012

DEMOSTRACIÓN INDUCTIVA DEL TEOREMA DE GÖDEL

Téngase un sistema formal convencional tal que las sentencias A contengan una relación directa, formal, entre alguna sentencia válida del sistema en cuestión, que se supondrá consistente, y el objeto que le corresponde en el universo de un modelo cualquiera. El objeto correspondiente está compuesto por la colección de los objetos correspondientes a cada uno de sus símbolos (relatores, funtores, etc.)

Sea entonces un ejemplo de sentencia A:

Para toda F, R(F,M(F))

Donde F es cualquier sentencia, M(F) el objeto que le corresponde dado un modelo, y R(a,b) la estructura de la relación referida.

Así pues, asúmase que de todo el sistema formal se han constituido las sentencias A correspondientes a los axiomas, y que de allí se obtienen las sentencias A de los teoremas. Como el sistema formal asume como teoremas a todas las sentencias A, entonces cualquiera de ellas puede a su vez participar como una sentencia F y se constituiría una nueva sentencia A. Haciendo esto sucesivamente, se llega a sentencias A_n que poseen un objeto M(A_n) correspondiente. Luego, suponiendo que las sentencias A_n+1 son las últimas posibles de obtenerse, es decir, que se detiene la sucesión de sentencias A, las sentencias A_n+1 carecen de un objeto correspondiente M(A_n+1) porque de ser así se generaría forzosamente la obtención de sentencias A_n+2. Al carecer de tal objeto M(A_n+1), quedan indecidibles dichas sentencias verdaderas, porque no hay valoraciones que puedan aplicarse a ellas. Entonces se obtiene la primera conclusión:

I. En todo sistema formal consistente, se tienen como posibles teoremas sentencias indecidibles.

Del hecho que el sistema formal sugerido es consistente, pero imposible de corroborarse en todas sus sentencias se tiene la segunda conclusión:

II. Ningún sistema formal que sea consistente puede demostrar su propia consistencia. Todo sistema formal consistente es necesariamente incompleto.

Supóngase la existencia de una cantidad indefinida de sentencias A, tal que todas ellas posean un objeto M(A) correspondiente. Entonces el sistema queda completo (porque la hipótesis de la cantidad indefinida de sentencias A demuestra su completitud) y consistente, pero indecidible para algunas sentencias. Esto es, las sentencias A_j cuyo número j sea desconocido y que se presentan por la cantidad indefinida de sentencias, son indecidibles porque se las sabe verdaderas pero no deducibles verdaderas (a diferencia de las sentencias A_n+1 que fueron deducidas verdaderas a partir de una secuencia lógica, un razonamiento mecánico o sistemático).

En todo caso, los sistemas formales de utilidad tienen una cantidad definida de sentencias, por lo cual todos ellos pueden ser consistentes, aunque jamás completos ni tampoco decidibles.

Obsérvese que la consistencia de un sistema formal depende de que la sentencia «el sistema es consistente» o la sentencia «el sistema es inconsistente» sean indecidibles. De allí, que en particular la primera de ellas pueda ser parte del sistema, sin embargo sea indecidible necesariamente. Ésta sentencia sería del tipo A_n+1.

∎

Julio 2012