Incompleteness
| Collection | GlossariumBITri |
|---|---|
| Author | Francisco Salto Alemany |
| Editor | Francisco Salto Alemany |
| Year | 2010 |
| Volume | 1 |
| Number | 1 |
| ID | 48 |
| Object type | Concept |
| Domain | Formal Semantics Logics Recursiveness Theory Transdiciplinary |
| es | incompletud, incompletitud |
| fr | incompletude |
| de | Unvollständigkeit |
Gathering things is quite different from gathering sentences. Things, in its most general sense (what the classics called transcendental) are gathered in sets or bigger classes, up to the proper class of everything. We may say such a huge collection is complete. But notice it is deprived of the collection of all and only incomplete collections. Hence it is not complete after all.
More modestly, we may gather all things that are sentences of a language. Just as in Borges' Babel Library, where the infinite set of all possible sentences are compiled. This set may seem somehow complete, but again notice it is not particularly interesting, since it is a trivial chaos where anything expressible is expressed.
So let's now gather, even more modestly, only all the true sentences of a language. This is the first useful sense of completeness. Given a domain of interpretation and a language referring to it, a set of sentences is model-complete if it contains all sentences that are true in such a domain. Notice that other languages with different expressive power may also contain this set among their sentences; just as such a domain may be described by other languages. A mathematically precise notion of “domain of interpretation” brings us to distinct semantics. It's certainly not easy to gather model complete set of sentences. Accumulating all truths about my left little finger is a huge task. Even gathering all expressible truths about my left little finger is an impressive unprobable piece of work. However, there are a number of such huge tasks that we perform with our tiny brain, poor resources and limited time.
Learning a natural language is one of them, since it involves the task of acquiring a recursive procedure to access the infinite set of all sentences. Another example of the application of finite rules to construct an infinite amount of finite sequences is Babel's Library as described by Borges, which is learnable or constructible with just the alphabet.
Another computable procedure with the same recursive structure is the one constructing deductions or proofs from rules and axioms. In this case sequences of sequences are recursively formed, in such a way that an infinite set of truths can be condensed in a finite, even small, set of axioms.
Is there a similar procedure to recursively obtain a model-complete set of truths?, that is, a recursive or computational means to access all truths with respect to a certain domain of interpretation?
Take for example the natural numbers, as the infinite domain standardly interpreting arithmetic. Let the language of arithmetic be given, say as was informally taught to us in school. Moreover, we have a computational procedure to calculate logical consequences from basic axioms of arithmetic (as discovered by Peano and Frege). Do we have then a logical procedure to compute all arithmetical truths? Gödel proofed that such a procedure does not consistently exist, the proof being the first incompleteness theorem. This answers negatively the question whether a model complete collection of truths is accessible by purely recursive or computational means. Notice it does not answer the question of whether non-recursive methods are available to access the set of all truths (arithmetical or of another nature).
Annexed files include several explicit proofs and additional materials. for the notion of inform.
References
- BOOLOS, G.; R. JEFFREY, J. BURGUESS (2002). Computability and Logic. Cambridge: Cambridge University Press.
- BORGES, J.L. (1996). “La biblioteca de Babel” en: Ficciones, Obras Completas I. Barcelona: Emecé.
- FITTING, M. (2007). Incompleteness in the Land of Sets. New York, Berlin: Springer.
- GÖDEL, K. (1931). “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme”. Monatshefte für Mathematik und Physik, 38, 173-198.
- SALTO, F. (2006). “Verdad y Recursividad.” en: J.M. Méndez (ed.). Artículos de segunda mano. Salamanca: Varona.
- SMULLLYAN, R. (1992). Gödel's Incompleteness Theorems. New York: Oxford University Press