Incompleteness

 
 Editor
F. Salto
 Incorporated contributions
Salto (4/2010)
 Usage domain
Transdiciplinary, Logics, Recursiveness theory, Formal semantics
 Type
Concept
 French
Incompletude
 German 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 its 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.


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.
Entries

New entry. Before doing a new entry, please, copy this line and the following ones and paste them at the column bottom. Next fill out the fields: 'name', 'date' and 'text', and delete this upper blue paragraph.

Author's Name (dd/mm/yyyy)

[Substitute this paragraph with your entry]


Entries under work

Maalesch Slim (25.07.2018, within the course "Odyssey of Philosophy and Information", facilitated by J.M.Díaz at HM)
[Note of the Facilitator (hereinafter referred as NF). Notes of the facilitator use this format and start with the identifier "NF". They intend to provide hints about how the text needs to be changed. Whever this has been addressed the auhor can write a comment using tha same format, but in green, or if the issue is resolved, just taking the NF comment away]
 
The entry was first based on the Borges' Babel Library book, where the complete existence of every book makes it incomplete because of the lack of incompleteness in itself [NF: You have confused here article and entry. You are writting an entry proposal, the text on the left column is the published article, for which the entry proposal intends to be an additional contribution]. This stirred some thoughts about the Paradox of the logic phenomenon and thus the incompleteness theorem and other theories then derived from it that will be stated and treated in this article.

1. Definition of Incompleteness

Incompleteness is the property of being incomplete, where incomplete is defined generally as not being complete, lacking some parts. It has unfinished, partial, fragmentary as synonyms  (Incomplete, 2018; Harper, 2018).

The philosophical point of view is extracted from the Gödel’s incompleteness theory which states: “no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of the natural numbers. For any such formal system, there will always be statements about the natural numbers that are true, but that are unprovable within the system. (…) system cannot demonstrate its own consistency." (Wikipedia, 2018: §0)

2. The paradox of logic itself 

Logic is the perfect way to conclude acceptable results and reasoning. But what if that same logic isn’t totally true or in other words incomplete? This was one of the main focuses in ancient Greek philosophy known as the Epimenides paradox or the paradox of the liar. "Epimenides was said to exclaim, 'This statement is false!' Is it false? If his statement is false, that means that it must be true. But if it’s true, it’s false. So whatever you assume about his veracity, you’re in trouble." (Chaitin, 2002: p.166). This kind of problem, where a statement is totally sound but self-contradictory, occupied the mathematician who later become a philosopher and later a humanist, Bertrand Russell. Russell’s Logical Paradoxes highlight the following idea "consider the set of all sets that are not members of themselves. Then ask, 'Is this set a member of itself?' If it is a member of itself, then it shouldn’t be, and vice versa. The set of all sets in the Russell paradox is like the barber in a small, remote town who shaves all the men who don’t shave themselves. That description seems pretty reasonable, until you ask, 'Does the barber shave himself?' He shaves himself if and only if he doesn’t shave himself." (Chaitin, 2002: pp.164-165).

Another well-known paradox is the Horned Man Paradox. The Horned Man is a version of the "When did you stop beating your wife?" puzzle. This is not a simple question, and needs a carefully phrased reply, to avoid the inevitable come-back to "I have not." How is one to understand this denial, as saying you continue to beat your wife, or that you once did but do so no longer, or that you never have, and never will? It is a question of what the "not," or negation means, in this case. If "stopped beating" means "beat before, but no longer," then "not stopped beating" covers both "did not beat before" and "continues to beat." And in that case "I haven't" is an entirely correct answer to the question, if you in fact did not beat your wife. However, your audience might still need to be taken slowly through the alternatives before they clearly see this. Likewise with the Horned Man, which arises if someone wants to say, for instance, "what you have not lost you still have." In that case they will maybe have to accept the unwelcome conclusion "I still have horns," if they admit "I have not lost any horns." Here, if "lost" means "had, but do not still have" then "not lost" would cover the alternative "did not have in the first place" as well as "do still have" -- in which case what you have not lost you do not necessarily still have (Slater, s.d.)

This paradoxical logic led to a lot of troubles in the philosophical world: How can something be true and false at the same time? How can it contradict itself? How can we give a proper answer while giving a clear outcome with no misunderstanding? 

A false solution. The Hilbert approach and its denial by the Gödel’s Incompleteness theorem and the Turing machine theorem

„One of the reactions to the crisis of logic was Hilbert’s attempt to escape into formalism. If one gets into trouble with reasoning that seems okay, the solution is to use symbolic logic to create an artificial language and be very careful to specify the rules so that contradictions don’t crop up. After all, everyday language is ambiguous—you never know what a pronoun refers to. “ In other words, Hilbert’s intention was to be completely precise about the rules of the game—about the definitions, the elementary concepts, the grammar and the language—so that everyone could agree on how mathematics should be done. In practice it would be too much work to use such a formal axiomatic system for developing new mathematics, but it would be philosophically significant“[NF: See how I solved the nested quotation marks problem in the first quotation from the same source, which is indeed an standarised proceedure] (Chaitin, 2002: [NF: see how to refere the place above, you have to specify the page. Do it alike]).

Gödel’s amazing discovery is that Hilbert was dead wrong: There is, in fact, no way to have a formal axiomatic system for all of mathematics in which it is crystal clear whether something is correct or not. More precisely, what Gödel discovered was that the plan fails even if you just try to deal with elementary arithmetic, with the numbers 0, 1, 2, 3,. . . and with addition and multiplication, because any formal system that tries to contain the whole truth and nothing but the truth about addition, multiplication and the numbers 0, 1, 2, 3,. . . will have to be incomplete. Actually, it will either be inconsistent or incomplete. So if you assume that it only tells the truth, then it won’t tell the whole truth. In particular, if you assume that the axioms and rules of deduction don’t allow you to prove false theorems, then there will be true theorems that you cannot prove.“ 

Gödel’s incompleteness proof is very clever. [NF: I have unify these two paragraphs, I hope you agree] He starts in effect with the paradox of the liar: the statement “I’m false!” which is neither true nor false. Actually what Gödel does is to construct a statement that says of itself, “I’m unprovable!” Now if you can construct such a statement in elementary number theory, in arithmetic, a mathematical statement that describes itself, you’ve got to be very clever—but if you can do it, it’s easy to see that you’re in trouble. Why? Because if that statement is provable, it is by necessity false, and you’re proving false results. If it’s unprovable, as it says of itself, then it’s true, and mathematics is incomplete." [NF: See how I solved the nested quotation marks problem in the first quotation from the same source, which is indeed an standarised proceedure] (Chaitin, 2002: [NF: see how to refere the place above, you have to specify the page. Do it alike]).

That theory devastated mathematical philosophers. Many were inspired by it. 5 years later Alan Turing discovered uncomputability also known as the “Turings machine“ 

His reasoning follows the following: Suppose that you could write a computer program that checks whether any given computer program eventually halts. Call it a termination tester. In theory, you feed it a program, and it would spew out an answer: “Yes, this program will terminate,” or, “No, it will go off spinning its wheels in some infinite loop and never come to a halt.” Now create a second program that uses the termination tester to evaluate some program. If the program under investigation terminates, have your new program arranged so that it goes into an infinite loop. Here comes the subtle part: Feed your new program a copy of itself. What does it do? Remember, you’ve written this new program so that it will go into an infinite loop if the program under test terminates. But here it is itself the program under test. So if it terminates, it goes off in an infinite loop, which means it doesn’t terminate—a contradiction. Assuming the opposite outcome doesn’t help: If it doesn’t terminate, the termination tester will indicate this, and the program will not go into an infinite loop, thus terminating. The paradox led Turing to conclude that a general purpose termination tester couldn’t be devised. The interesting thing is that Turing immediately deduced a corollary: If there’s no way to determine in advance by a calculation whether a program will halt, there also cannot be any way to decide it in advance using reasoning. [NF: See how I solved the nested quotation marks problem in the first quotation from the same source, which is indeed an standarised proceedure] (Chaitin, 2002: [NF: see how to refere the place above, you have to specify the page. Do it alike]).

Incompleteness leading to Randomness

Gregory J. Chaitin was the latest mathematical philosopher who added to the incompletness theory by looking at it from a physics approach, more precisely in quantum mechanics. He asked himself if there were randomness in mathematics as in quantum mechanics to finally think that it may have to do with the incompletness in maths. 

A case in point is elementary number theory. Consider the prime numbers. Individual prime numbers behave in a very unpredictable way, if you’re interested in their detailed structure.. So he began to think that maybe the inherent randomness in mathematics provided a deeper reason for all this incompleteness. 

He worked on a computing theory were he uses program-size complexity to define randomness. With the idea of „the less your input, the better the program“. Here he faces a problematic question: how do we know a program is ideal. The answer is: we can’t. The result was the following statement: „If you have n bits of axioms, you can never prove that a program is the smallest possible if it is more than n bits long“. [NF: See how I solved the nested quotation marks problem in the first quotation from the same source, which is indeed an standarised proceedure] (Chaitin, 2002: [NF: see how to refere the place above, you have to specify the page. Do it alike]).

A conclusion 

In practice, there’s this vast world of mathematical truth out there—an infinite amount of information—but any given set of axioms only captures a tiny, finite amount of this information. That, in a nutshell, is why Gödel incompleteness is natural and inevitable rather than mysterious and complicated. These incompleteness results certainly have a pessimistic feeling about them. If you take them at face value, it would seem that there’s no way to progress, that mathematics is impossible. But that incompleteness doesn’t bother current mathematicians as much as it bothers philosophers. That in itself is something the next generation may figure out.
[NF: The proposed contribution as a whole is too literal attached to Chaitin's. You have provided too little content from your side]

References


Entries Incorporated in the Article


Francisco Salto (4/2010)
 
[It corresponds to the directly edited article by the author/editor in the left column]
Comments