Teorema de incompletitud de Gödel


Kurt F. Gödel, en «Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas afines» [paráfrasis]:

«Existen argumentos lógicos imposibles de ser deducidos verdaderos o falsos; entre ellos, la coherencia de dichos razonamientos.»

La existencia verdadera o falsa de algo (por ejemplo, las piedras; al contrario, las hadas), no implica que la misma sea demostrable así, ni que deba o no tenerse fe en cualquiera de estas posibilidades.

·

La creatividad surge de hallar –pensando diferente del resto– ideas absurdas, para así nuevamente pensarlas y darles coherencia.

Ahí la importancia de la Lógica: porque sólo con ella es posible tanto hallar los absurdos como obtener la coherencia.

·

miércoles, 12 de diciembre de 2012

GÖDEL'S THEOREM

Sentences are used for reasoning. For example, «She is 24 years old» is a sentence with which everyone can reason. Another striking example about sentences used for reasoning is the recognition of kinships, that is, from phrases like «She is my mother», «He is the son of her», and «Everyone who is son of my mother, is my brother» it can be deduced «He is my brother». Gödel's theorem comes from reasoning.

What Kurt Gödel proves with his theorem is the existence of sentences which can be used for reasoning, but that can't be demonstrated neither true nor false: such sentences are known in logics as undecidable. The article where his theorem was published for the first time is called On Formally Undecidable Propositions of Principia Mathematica and related systems. Principia Mathematica was a list of sentences with which the mathematician Bertrand Russell aimed to bring together all the previously known (until the 20's of the XX century) about Mathematics. The task was not easy because he had to avoid the presence of contradictions in his mathematical derivations. For example, a contradiction would be 0=1 (when in fact it is known that 0=0). Apparently he achieved it, but Kurt Gödel demonstrated that it can not be demonstrated by only reasoning that Principia Mathematica does not lead any contradiction.

To prove that Principia Mathematica does not lead to any contradiction involves the demonstration of the truth of all its sentences. Gödel's theorem says that there are sentences that can not be demonstrated neither true nor false, so is ruled out the possibility that Principia Mathematica can be demonstrated without contradiction in itself. Now, Gödel's article not only discusses Principia Mathematica, but also about «related systems». These related systems talk about things other than Mathematics, or about Mathematics, but without using the sentences proposed by Bertrand Russell, always using reasoning. From there that would be so revealing Gödel's theorem (also called Gödel's incompleteness theorem, in contrast to the Gödel's completeness theorem which is something different) because people think through arguments.

One of many related systems talks about kinships (which has already been mentioned). It can be structured in a formal way (the term «formal» refers to symbols using fixed patterns, for example, formulas similar to the equations) as follows:

1. Every individual has both birth mother and father; the individual is called a son of its birth mother or father.
2. If an individual is a son of my mother or my father, then it is my brother.
3. If an individual is a brother of my mother or my father, then it is my uncle in the first degree.
4. If an individual is the mother or father of any of my birth parents, then it is my grandfather.
5. If an individual is a brother of my grandfather, then it is my (grand)uncle in the first degree.
6. If an individual is a son of my uncle in the first degree, then it is my first cousin.
7. If an individual is a first cousin of my father, then it is my uncle in the second degree.
8. If an individual is a son of my uncle in the first degree, then it is my second cousin.
9. If an individual is a first cousin of my grandfather, then it is my (grand)uncle in the second degree.
10. If an individual is the mother or the father of my grandfather, then it is my great grandfather.
12. If an individual is a son of my brother, then it is my nephew in the first degree.
13. If an individual is a son of my first cousin, then it is my nephew in the second degree.
14. If an individual is a son of my second cousin, then it is my nephew in third grade.

Note that it is irrelevant the forced use of male or female (it is implied). The list above can get transformed into formulas similar to equations by means of abbreviations such as H(i,j) that says «i is a son of j» and the like. The system really has not been completed because kinship relations can be established indefinitely. Also note the relative low complexity of this list and compare with the difficulty that should have represented the same to Bertrand Russell in Mathematics.

In logics we say that a sentence is true when all instances given as examples of it are corroborating what it says, otherwise it is said false. For example, x=x is true if any number is entered as an example, say 8=8 from among many possible. Take into account that x=x has not been said to be «absolutely true» but «if any number is entered». This is important because this defines the examples which are valid for a given sequence of sentences in a very precise way. Likewise, for kinship can be taken any family to corroborate the truth of the sentences proposed. However, even the sentences of kinship system can get sentences that are not true or false; we can not check that the kinship system does not derive any contradiction in the same way the Principia Mathematica could not be checked in thereof. Gödel's theorem of incompleteness is called like that because the systems of sentences that can not be verified true for all its sentences are called incomplete systems. As will be seen, even when all the sentences that comprise the system are true, none can be complete.

The case of an undecidable sentence (which is not demonstrable neither true nor false) for the set of sentences that define kinships can be obtained by imagining incestuous relationships. For example, remember in One Hundred Years of Solitude the relationship between Amaranta Úrsula and Aureliano. There is the relationship between him and his aunt, and they have a son; this child is his cousin and her nephew in the second degree also. It is relevant to refer the child remains second cousin and nephew in the second degree for himself. The fundamental question to understand Gödel's theorem is whether there is a chance that someone would, for example, stay as a son of oneself. This is not present in the sentences of the kinship system, nevertheless it could be suspected that the deduction may exist.

On the other hand, intuition suggests that the sentence «I am my son and my father at a time» is false, or that the sentence «I can not be my son and my father at a time» is true. However, Gödel's theorem says that these type of sentences can not be deduced neither true nor false from the sentences of the kinship system. These sentences are undecidable. Do not do a thousand and one combinations trying to get through one or other deductions to statements about the relationship with oneself, because no real example (about real life) verifies this as a possibility and therefore the sentence of type «I can not be my son and my father at a time» is actually true, and of course, «I am my son and my father at a time» is actually false.

Let us clarify ideas: 1) The sentences about the kinship with oneself are correct and 2) neither of both can be derived from such sentences of the kinship system. These two conclusions are crucial when speaking in general terms of «related systems» because they end up resulting in 1) Demonstrating through logical deductions that all sentences are true for any system is not possible (even if they are) and 2) There are undecidable sentences. Point 1) can be translated directly into «all systems that do not lead to contradictions are incomplete».

Gödel's theorem is very important to human reasoning. With it anybody can get sentences similar to that obtained on the kinships. For example, the phrase «The Universe originates from...» and then in any case is undecidable, because anything that is in the universe could prove the existence of himself (the Universe could not create itself). Other similar are undecidable, as knowing if one is actually dreaming or not. In summary, many proposals can not reach an answer. And this was a mathematic unique result that forced scientists to look for hard evidence that the Mathematics represent real things of nature, a situation that is necessary to avoid falling into contradictions in any deduction.

 
October 4th , 2012
 
 

No hay comentarios:

Publicar un comentario