Is Kurt Gödel's Incompleteness Theorem a “cheap trick”?

Question

I found a throw-away critique of Kurt Gödel's Incompleteness Theorem in an essay about Deconstruction:

The basic enterprise of contemporary literary criticism is actually quite simple. It is based on the observation that with a sufficient amount of clever handwaving and artful verbiage, you can interpret any piece of writing as a statement about anything at all. The broader movement that goes under the label "postmodernism" generalizes this principle from writing to all forms of human activity, though you have to be careful about applying this label, since a standard postmodernist tactic for ducking criticism is to try to stir up metaphysical confusion by questioning the very idea of labels and categories. "Deconstruction" is based on a specialization of the principle, in which a work is interpreted as a statement about itself, using a literary version of the same cheap trick that Kurt Gödel used to try to frighten mathematicians back in the thirties.

Now this statement strikes me as perfectly apt, but not sufficiently grounded. I suspect that it's correct, but there isn't enough there to know.

So is the Incompleteness Theorem a "cheap trick" or is it a serious argument that propels philosophy forward? (I presume that the theorem is perfectly valid and valuable in mathematics where it originated.)

Answer 1

Gödel himself worried that his incompleteness theorems were a kind of cheap trick, just a hidden trivial version of the liar paradox, but using "this statement is not provable" instead of "this statement is false." So I think the question is a good very one.

And although I have huge admiration for the theorems, let me describe another sense in which the first incompleteness theorem can be viewed from the modern perspective as a cheap trick: it is just the halting problem in disguise.

Let me explain. It is comparatively easy to prove (see below) that the halting problem is undecidable, that is, there is no computable procedure that can reliably determine whether a given program/input pair will lead to a halting computation. Suppose now that T is a true theory with a computably axiomatizable list of axioms. If T were complete, then we could solve the halting problem in the following way: given program p and input x, we systematically search through all possible proofs from T of either the statement asserting that p does halt on x, or of the statement asserting that p does not halt on x. If T is true and complete, then we will eventually find such a proof on one side or the other. Thus, we will be able to say in finite time yes-or-no whether p halts on input x. This contradicts the undecidability of the halting problem. So T must not be complete after all. In other words, there will be true statements not provable in T. One can use the proof to show that there are such statements of the form, "such-and-such program does not halt on such-and-such input." The statement is true, in the sense that that program does not halt on that input, but we are unable to prove this statement in T.

This proof of the incompleteness theorem allows one to dispense with the usual arguments via the Gödel-fixed point lemma, which can sometimes be confusing, and reveals the incompleteness theorem instead simply as a version of the halting problem. Indeed, many readers may believe that the self-referential aspects of the fixed-point lemma lay at the heart of the incompleteness phenomenon, but this proof seems completely to avoid self-reference (well, it confines the self-reference aspect to the proof of the undecidability of the halting problem itself).

So what was Gödel's real achievement? Perhaps the most important idea that he had in his theorems was the arithmetization of syntax, the idea that assertions of number theory can be viewed as assertions about assertions. This idea is profound, and I used it above in the halting problem argument, in presuming that the assertion that a program halts or does not halt is expressible as a statement that might be proved or refuted in T. The arithmetization idea has now been woven completely into the modern perspective, as we all know that the philosophical articles that we write on our computer, as well as photos, music, videos and so on that we have there, are represented ultimately with zeros and ones inside the computer, and so it is an easy step for us to think of an article as really a very long sequence of bits, essentially an enormous number. And this is the essence of arithmetization.

---

Proof that the halting problem is undecidable. If there were a computable procedure to reliably determine whether a given program/input halts, then design a new program q that on input p first asks whether p halts on input p, and then performs the opposite behavior itself. It now follows that q halts on input q if and only if it doesn't, a contradiction.

Answer 2

Gödel's Incompleteness theorems are not cheap tricks in any sense of the phrase. If you want to call an ingenious method that no-one else anticipated a 'trick' then so be it - but it is in no way cheap. Let's review what Gödel proved in his two so-called incompleteness theorems. I will state the theorems informally but note that every single term in the statement has a formal and perfectly determinate counterpart:

Gödel's First Incompleteness Theorem (G1T) Any sufficiently strong formalized system of basic arithmetic contains a statement G that can neither be proved or disproved by that system.

Gödel's Second Incompleteness Theorem (G2T) If a formalized system of basic arithmetic is consistent then it cannot prove its own consistency.

Now, as I see it, you are asking two questions:

1. Are these theorems 'serious arguments'?
2. Do they propel philosophy forward?

The answer to both questions is yes. I answer them in turn:

1. The argument itself is metamathematical which means that it employs a meta-language to prove things about the object language of ordinary mathematics.

   The way Gödel does this is he takes his metalanguage to be one that includes intuitive notions of arithmetic (the natural numbers) together with an understanding of what primitive recursive functions on the natural numbers are. Using this meta-language he proves that any formalization of basic arithmetic can capture its own provability relation. He first defines what is called a Gödel numbering scheme in which every formula of the language in our formalization is assigned a unique number (in our metalanguage.)

   He then proves that there is a formal one-place open formula NotProv(x) that can be interpreted to mean "x is unprovable" where x is a numeral in the formalization (remember that what is under consideration is a formal system of basic arithmetic so it will contain the equivalent of intuitive numbers, i.e. numerals) that correspond to a given sentence in the language via the Gödel numbering.

   Now, given NotProv(x) we can do what Gödel called a diagonalization, namely apply NotProv(x) to itself, i.e. take x to be the numeral corresponding to the formula NotProv(x). Call the resulting sentence G = NotProv(NotProv). And since NotProv(x) says that 'x is unprovable' you can see that G says 'I am unprovable'. And something that says it is unprovable cannot be proved nor disproved.

   This is a very quick and informal way to present the argument - one would normally have to distinguish between the semantic and the syntactic versions of the theorem. But the point is that as you can see there is serious and rigorous work going on here.

   The proof of (G2T) is similar. Using NotProv(x) you can define a 'consistency sentence' for your given formalization by writing NotProv(0=1), i.e a sentence that says 'No contradiction is provable' which is equivalent to 'This system is consistent.' And by a similar but more technically subtle argument you can argue that this sentence is unprovable, given that the system is in fact consistent.

2. The second theorem is arguably more epoch-making than the first because it spelled the end of Hilbert's Program. This is a major philosophical shift in the philosophy of mathematics, essentially spelling the end of the philosophical school of formalism.

   Furthermore, people have argued that (G1T) proves that we can never fully capture arithmetical truth because a further consequence of (G1T) is that the sentence G is actually true and hence we can conclude that any formalization of arithmetic will contain statements which we can see are true but which are not in fact provable in that system.

   This has led people like Michael Dummett (an intuitionist) to label arithmetical truth as 'indefinitely extensible' (cf. Dummett 'The Philosophical Significance of Godel's Theorem'.) People like Lucas and Penrose have used both (G1T) and (G2T) to argue in favour of what is called an anti-mechanist thesis, i.e. that minds cannot be machines (cf. Penrose 'The Emperor's New Mind' and Lucas 'Minds, Machines and Godel'.)

In general, I have to say that the philosophical impact of both (G1T) and (G2T) cannot be overstated. They were events of monumental significance for analytic philosophy, for the philosophy and practice of mathematics as well as for theories of computation and machines. Most people (especially idiotic and ignorant continental postmodernists who have made it a sport to abuse mathematics in their pursuit of alternative vocabularies) fob them off as tricks because they have not bothered to look at the actual technical details involved and think that the idea of the proof gives them a perfect grasp of its implications. Popularizations don't really do the theorems justice.

If you are interested I recommend you go through the whole argument - the moment of revelation when it clicks together is as near an aesthetic experience as you're ever likely to have doing formal logic.

Answer 3

As no one else has yet taken the other side, I'll try my hand at devil's advocate. Keep in mind that I am not a mathematician so the answer will likely contain mistakes and I'm not committed to this view, but am interested in seeing the debate become a debate. Further, my understanding of Gödel's work comes largely from my reading of Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter. As such, this may be a criticism of Hofstadter's book rather than of Gödel Incompleteness. Caveat lector!

First, I accept its value in mathematics. (How can I not?) I will point out that Gödel's work did seem to end the Principia Mathematica project, which might be what the article means by "frighten[ing] mathematicians back in the thirties." In addition, the Wikipedia article on Foundations of mathematics suggests that the incompleteness theorems have diverted mathematics from Hilbert's program of formalism:

In a sense, the crisis has not been resolved, but faded away: most mathematicians either do not work from axiomatic systems, or if they do, do not doubt the consistency of ZFC, generally their preferred axiomatic system. In most of mathematics as it is practiced, the various logical paradoxes never played a role anyway, and in those branches in which they do (such as logic and category theory), they may be avoided.

Second, I accept that the Theorems are, in fact, true. For this I'm greatly indebted to GEB, which may be a popularization, but also produced in me something akin to an "aesthetic experience". The remarkable idea that a formal system can be made to evaluate itself and that such a self-referential operation implies that the system will thereby be rendered incomplete took hold of me as I read and understood it. Further, the concept seems inescapable, because it is.

So what we are left with is the application of Gödel Incompleteness outside of mathematics.
And the more that I think about it, the more that I think, "So what?" Obviously it's of great help if you are in a dialog with someone who wants to create a complete, consistent, self-validating system of thought. But as we are all postmodern in the chronological sense, that doesn't seem to be an issue all that often. And of course Gödel's work will be invaluable to those who are looking for the limits of Artificial Intellegence or who wonder if there is any mechanical model that can simulate a mind.

When I try to make sense of the ideas in the context of the intellectual landscape, I feel like I'm waking from a beautiful dream. It was profound and compelling when I was under its spell, but now I shake off drowsiness and wonder how the core idea is any different from the Epimenides paradox:

They fashioned a tomb for thee, O holy and high one
The Cretans, always liars, evil beasts, idle bellies!
But thou art not dead: thou livest and abidest forever,
For in thee we live and move and have our being.

– Epimenides, Cretica

Surely, an interesting puzzle, but not really something upon which to build a philosophical argument upon. Which makes me think that Gödel is often cited by non-mathematicians because he's a famous mathematician with an umlaut in his name. And that, I think we can all agree, would be a cheap trick.

Answer 4

No it's not a cheap trick if you want to understand whether something is true or both true and provable. For example can you prove that you don't have a proof? If you can then you have a proof and the proof is false. So it might be true that there is no proof though if you try to prove it it's proving the opposite of what you want to prove.

But yes it's a cheap trick since consistency not is a sufficient feature. Consistence very well could be a necessary feature but you can make a counterexample which disproves that being consistent is enough information.

Consistency only seem to mean that you can't prove a false statement and that what you prove must also be true.

Proving yourself to be a liar by not telling the truth is an old paradox that defies the law of the excluded middle and one solution to self-references is to avoid self-references completely so that everything true can be proven and vice versa everything provable is true.

For example a tautology is true (A=A is true) but a tautology doen't prove anything. So A=A is true and doesn't prove anything. Therefore typically false statements ("Peter is not being himself" is like "A is not A") can be more provable than exact truths (A=A) due to similarity instead of equality.

Answer 5

I think you are right : the Incompleteness Theorem is a perfectly valid mathematical result and is of GREAT value in mathematics where it originated.

Regarding his "philosophical significance" ... the discussion is impressive and the conclusion is still missing.

This - I think - is a common pattern : in XVII century the pooof of Law of Gravitation by Newton (a perfectly valid mathematical result proved from Newton's axioms (the Law of Motion) and with a good fitting with empirical evidence) give birth to a big discussion between philosophers (newtonians vs leibnitians) about the nature of force (are them really existing ?), absolute space, presence of God in the physical world ...

The same with regard to Quantum Mechanics laws and determinism, etc.

So the same hold for Godel's Theorems : INSIDE Mathematics, they give us a lot of information. OUTSIDE Mathematics, they suggest ideas regarding (for example) human mind and knowledge, but is very difficult to think that (as in previous historical examples) they can "solve" big philosophical problems.

Answer 6

It is an important challenge.

According to the Theory of Types, every proposition belongs to a certain order. In original Gödel sentence G, the order of G is ambiguous.

The original sentence

 ~(T -> G)

should be a simultaneous assertion of multiple sentences of this kind:

 ~(T -> Gn), where n is a natural number, 
             and Gn stands for "G of the nth order."

Let G stand for the series of "is not provable by T": G1, G2, G3, ..., Gn, ...

Let S stand for the correlation function "is not provable by T"

Then G2 = S(G1); G3 = S(G2); G4 = S(G3); ... Thus

 G = G1, G2, G3, G4, ... 
S;G= G2, G3, G4, G5, ...

where ; is a PM notation for applying correlation function on a series; G cannot be treated as a class because no two G's are of the same order (there is a lot of room for expansion in the theory of types, as of today and by the theory of types, I can't even utter phrases like "two G's".).

Since there is no G1, S;G and G are the same series. (I realize that G1 is a problem; if logical types can also be extended downwards ad infinitum, then this solution is complete.)

And G should be read as:

This series of statements cannot be proved by theory T.

Notice that the input "this series of statements" and the output of the above sentence are the same. It appears to be self-referential, but it is not individually; it is the same series shifted to the right; in a similar fashion, adding 1 to the series of integers results in the same series.

If the order of G is spelt out, G is a simultaneous assertion of the following sentences:

The first order statement G1 in this series cannot be proved. 
- this is the 2nd order statement G2, which is False
  because there is no G1. Gn is a statement about a statement, 
  and a statement about a statement is at least 2nd order.


The 2nd order statement G2 in this series cannot be proved.
- this is the third order statement G3, which is True 
  because we just showed G2 is false.


The 3rd order statement G3 cannot be proved.  - G4
---False, we just showed G3 is true.

    So on so forth.

See Liar's paradox in Principa Mathematica

On the other hand, if G is taken literally, it is nonsense according to the theory of types:

No proposition can say anything about itself, because the propositional sign cannot be contained in itself (that is the "whole theory of types").

Wittegenstein, Tractatus 3.332

Answer 7

I will try to analyze this argument using proposition dependency. But why must dependency of proposition? Because proposition must be associated with existences or it's meaningless, and how an existence related to other existence is through a dependency.

Proposition dependency:

• A proposition is constructed to understand realities (existences). Existences can be perceived by us because of their functionality, therefore nodes of a proposition exist as functions.

• Anything that exists has functionality. There are two possibilities; dependence upon something else (A->B) or "not" dependence upon something else (A|B).

• Therefore, a 'proposition' consists of nodes of functions that form a series of dependency

  Terms:

  • Cause = (c)
  • Caused = (cd)

Liar Paradox

An example of the use of dependency of proposition can be implemented to analyze this issue, a liar paradox.

Liar paradox, "He is telling the truth that He is lying, therefore He is not lying."

Syllogism

1. H then T = (c1) -> (cd1) (If there is him, then, there is telling something)
2. T then Ac = (cd1) -> (cd2) (If there is telling something, then, there is action from himself)
3. H then Ac = (c1) -> (cd2) (If there is him, then, there is action from himself - telling the truth)
4. Ac then Ev = (cd1) -> (cd3) (If there is action from himself, then, there is another event which is never happened as he told - he is lying)

5. H then Ev = (cd1) -> (cd3) (Therefore, If there is him, then, there is another event which is never happened as he told - he is lying)

   • "He is not lying" is not contradict with "He is lying (H then Ev), because "He is not lying" is pointing to (H then Ac).

   • H then Ac = (cd1) -> (cd2) is line with H then Ev = (cd1) -> (cd3)

Therefore there is no contradiction & paradox here.

Incompleteness Theorem

Incomplete because there is a kind of proposition that left behind to be proved.

I don't understand fully about how Godel made argumentation with his Godel's number and more, but i tried to understand the essence of what did Godel mean by incompleteness theorem. Through my simple understanding about Godel's incompleteness theorem, i tried to deepening further to see a clear distinction and put it in appropriate places.

Kurt Godel Logical Framework

Suppose there is a programming system that has ability to prove any proposition, therefore:

1. A proposition is always provable (by a programming system)
2. "G" is a proposition

3. Therefore, "G" is always provable"

   • "G" is unprovable proposition
   • Therefore "unprovable proposition is provable"

Syllogism

1. (All)P are provable
2. G is P

3. G is provable

   • G = unprovable proposition

Consequences

• If G is provable then = unprovable proposition is provable = INCONSISTENT.
• If G is unprovable then = unprovable proposition is unprovable = INCOMPLETE (because there is a proposition left behind that is unprovable)

Dependency of Proposition for Incompleteness Theorem

Now, we try to place this incompleteness theorem issue to a dependency of proposition to learn something whatever it is.

Kurt Godel Logical Framework

Syllogism

G = Unprovable Proposition

1. (All)P then Pr = All(cd1) <- (c1)

   (If there are all propositions, then, those are provable)

2. (several)P then G = several(cd1) -> (cd2)

   (If there are some propositions, then, several of propositions are typical G)

3. G then Pr = (cd2) <- (c1)

   (If some of propositions are typical G, then, those are provable)

   • G = unprovable proposition

Consequences

INCONSISTENT

• If G is provable then = unprovable proposition is provable = INCONSISTENT.

From here i will use dependency on proposition to make us see a clear distinction for possible arrangement (easier then using syllogism).

• (several)P -> ~Pr = several(cd1) | (c1) = "unprovable proposition"

  (a proposition has no relation with provable)

• {(several)P -> ~Pr} then Pr = several(cd1) | (c1) <-> (c1) or (c1) -> several(cd1) | (c1)

  (If there are some propositions that has no relation with provable, then, those are provable) = (If there are some propositions that has no relation with provable, then, those proposition has relation with provable)

• From syllogism asserts that there is contradiction

• From dependency of proposition, {several(cd1) | (c1) <-> (c1)} or {(c1) -> several(cd1) | (c1)} asserts

  • several(cd1) | (c1) <-> (c1) = several(cd1)
  • (c1) -> several(cd1) | (c1) = (c1) -> several(cd1) = several(cd1) <- (c1)

There is contradiction (according to syllogism) and there is no inconsistency here (according to DOP).

INCOMPLETE

• If G is unprovable then = unprovable proposition is unprovable = INCOMPLETE.

From here i will use dependency on proposition to make us see a clear distinction for possible arrangement (easier then using syllogism).

• (several)P -> ~Pr = several(cd1) | (c1) = "unprovable proposition"

  (a proposition has no relation with provable)

• {(several)P -> ~Pr} then ~Pr = several(cd1) | (c1) | (c1) or (c1) | several(cd1) | (c1)

  (If there are some propositions that has no relation with provable, then, those are not provable) = (If there are some propositions that has no relation with provable, then, those proposition has no relation with provable)

• From syllogism asserts that there is no contradiction

• From dependency of proposition, {several(cd1) | (c1) | (c1)} or {(c1) | several(cd1) | (c1)} asserts

  • several(cd1) | (c1) | (c1) = several(cd1)
  • (c1) | several(cd1) | (c1) = (c1) | several(cd1) = several(cd1) | (c1)

There is no contradiction (according to syllogism) and there is no inconsistency here (according to DOP).

Electrical Circuit of Reasoning

To make this assertion clear enough to be understood, i am going to use popular example,

• A proposition is (the light) and provable is (switching on)

• (Unprovable proposition) is equal to (the light that can't be switched on)

• Unprovable proposition that is provable = A light that can't be switched on was trying to be switched on

  • A light that can't be switched on was trying to be switched on, therefore no light was on.

  • The key understanding in this case, is that a system still had ability to test a connection (ability to prove, ability to send electricity), but since a target (unprovable proposition) can't be attempted to switched on, then the light (unprovable proposition, the light that can't be switched on) is still off. But it didn't assert that a system was failed to run its fully functional.

  • The failure to aware this, it's because on semantically level, one proposition to another may become ambiguous, with no clear distinction about its own barrier. But by associating it to existences (beyond semantically level). We finally found that there is no consistency and there is no incompleteness as asserted by Godel Incompleteness Theorem.

Indeed we may be understand (through another direction) the truth that if we want to make a well defined statement, then it must be completed but inconsistent and a statement is consistent but it's not complete. But Kurt Godel's theorem has no related with incompleteness and inconsistency.

---

Please, refer to this link for better understanding: Dependency of Proposition.

Answer 8

The basic enterprise of contemporary literary criticism is actually quite simple. It is based on the observation that with a sufficient amount of clever handwaving and artful verbiage, you can interpret any piece of writing as a statement about anything at all.

This is a degeneration of Derridas Deconstruction which could be viewed as an attack on the then dominant (& stagnant) school of Structuralism or a way past it. To use a mathematical analogy: mathematics (in one sense) is about axiomatic systems, but this does not mean that any axiomatic system is of equal value. Likewise not every interpretation of a piece of writing is of equal value. Judgements of taste must still be made.

The broader movement that goes under the label "postmodernism" generalizes this principle from writing to all forms of human activity, though you have to be careful about applying this label, since a standard postmodernist tactic for ducking criticism is to try to stir up metaphysical confusion by questioning the very idea of labels and categories.

Postmodernism is a questioning and reaction of Modernism; in the same way that Romanticism was a reaction to early Modernism. From some point in the future looking back it may be seen as part of Modernism. Its really too early to say (though of course one does).

"Deconstruction" is based on a specialization of the principle, in which a work is interpreted as a statement about itself, using a literary version of the same cheap trick that Kurt Gödel used to try to frighten mathematicians back in the thirties.

Deconstruction is roughly about inverting dominant modes of interpretation, in various modes, and its not a new technique: after all Marx inverted Hegel to present a critique of Capitalism. One could say that Deconstruction is both a literary & political tool.

Godels theorem, from a mathematical logic perspective is not a cheap trick, but certainly it has been used as a cheap trick by philosophical & mathematical hustlers. Paradox & antinomies have been used by serious philosophical thinkers, such as Hegel and Kant (in passing only) in the West; and by Nagarjuna and Daoism in the East.

Godels achievement, in context, is one part of the reinvigoration of formal logic since Frege, he introduced new techniques and questions into mathematical logic. However most popular expositions miss the importance of Paradox and tying it into the larger framework of Paradoxical thought in Philosophy - they settle for an exposition of Godels proof, whereas his main ideas are explicable in fairly simple terms - as they should be - and they do not give the larger & broader picture of Mathematical Logic: categorical Logic, intuitionist logic, inconsistent mathematics, paraconsistency and so on.

There is an incredible amount of verbiage about Godels Theorem, important though it is, which should be contemplated alongside the incredible amount of verbiage around Deconstruction, important though that is.

One of the elements of Badious Programme is to prune back this verbiage & metaphysical idiocy by making mathematics the site of ontology. But one should note that his book Being & Event references the Event of Derrida in the paper he presented at Columbia University which was to consolidate Structuralism but actually became a springboard for Deconstruction.

Although, Godels Theorem is presented usually as a death-knell of Mathematical Logicism, there has been found ways past it; certain parts of his programme has been completed. For example Gentzens proof of the consistency of PA, paraconsistent logic helps overcome contradictions in the rational architecture of mathematics by localising them.

There appears to be a general tendency towards Logical Pluralism which might be considered the outcome of the Logical Monism of Hilberts programme after a century of thought.

So far from Post-Modernism being inconsequential, one can see that the grand narrative of logical monism which may be seen as part of the modernist project has become Post-Modern by moving towards Logical Pluralism. Not the One but the Multiple.