Is there a paradox in the proof of Godel's incompleteness theorem? [closed]

Question

The Gödel Incompleteness Theorem was a major discovery in modern logic that has consistently attracted the attention of scientific and philosophical circles.

However, since the Gödel Incompleteness Theorem was put forward, the scientific and philosophical significance of its proof has been questioned; in particular, Wittgenstein regarded it as a certain logical paradox. In Gödel’s view, Wittgenstein does not understand the incompleteness theorem; Gödel said,

He interpreted it as a logical paradox that, but in fact, on the contrary, is a mathematical theorem of an undisputed part of mathematics (limited number theory or combinatorial mathematics).” (Wang Hao, 2009, p227).

Who is right?

Answer 1

Gödel was right. O'Connor 2005 meets every known objection: it is constructive and finite, indeed it runs on commodity hardware in reasonable time; it includes Rosser's trick, it is not relative to ZFC, it addresses first-order axioms, and a large body of empirical work endorses the correctness of the proof in terms of both hardware and software. Smith 2007 rebuilds Gödel's approach using all of the tools developed by his contemporaries. Lawvere 2006 explains how Gödel's theorem is a special case of Lawvere's 1967 fixed-point theorem, and how the latter theorem is proved without any self-referential techniques; Yanofsky 2003 contextualizes Lawvere's theorem by showing that many apparently-self-referential paradoxes neatly decompose as special cases.

There is an important philosophical lesson here. Sometimes a philosopher — here, Wittgenstein — is wrong. Their reputation and prior work are irrelevant. The strength of their opinion and the beauty of their justification are irrelevant. Only the evidence presented is relevant. For mathematics, formal proof is very strong evidence, and insightful analogies are even stronger evidence; Gödel provided the (first) proof, and Lawvere provided the analogy.

Answer 2

You do not understand the incompleteness theorem. It does not require "coding", and it does not depend on "actual infinity", and it does not "hide" any paradox. You cannot reject it as long as you accept basic facts about finite binary strings.

Answer 3

In an appendix to Part I of Remarks on The Foundations Of Mathematics, Wittgenstein criticized the following argument:

I imagine someone asking my advice; he says: “I have constructed a proposition (I will use ‘P’ to designate it) in Russell’s symbolism, and by means of certain definitions and transformations it can be so interpreted that it says: ‘P is not provable in Russell’s system’. Must I not say that this proposition on the one hand is true, and on the other hand is unprovable? For suppose it were false; then it is true that it is provable. And that surely cannot be! And if it is proved, then it is proved that it is not provable. Thus it can only be true, but unprovable.”

^{(Translation by G.E.M. Anscombe; can be viewed with the original German here.)}

The surrounding text seems to be a reasonable takedown of that argument. That argument is what many people believe to be Gödel's argument—enough that it is worth putting some effort into showing that it's wrong—but it's not Gödel's actual argument, which doesn't depend on a notion of truth.

Whether Wittgenstein was one of those who believed that that was Gödel's argument, I don't know. He didn't explicitly say so, nor otherwise. If he believed he was criticizing Gödel's theorem in that section then he was wrong.

Answer 4

I'm not entirely sure that I'm justified in rejoining this question by way of a full answer, because I'm not entirely sure as to the justification of the question itself. But so I've decided to read your paper, and I will list my critical responses here, as I go along (if I find too many errors in a short enough time, I'll list those and give up on the remainder of the text, however):

1. "In 1901, Russell discovered Russell’s Paradox, which brought a third crisis to the development of mathematics. The solution to this paradox has not been found." There are multiple solutions to Russell's paradox available, starting with the direct, "Don't accept the axiom of unrestricted comprehension," or then, "Don't combine a universal set with separation." So another can be found within the theory of proper classes (the Russell class is a proper class and not a proper set; note that, phrasing aside, this solution is roughly on a par with, "Don't combine a universal set with separation," since some understandings of proper classes is that they are separation-minus objects). Paraconsistent set theory is a bullet-biter reply: "The Russell set is, and is not, an element of itself." And there are probably solutions I'm forgetting.

2. "... the philosophical collision between Wittgenstein and Gödel was the most fascinating and extreme in the twentieth century." This seems like hyperbole (why wouldn't various debates in ethical philosophy, or philosophy of religion, be more fascinating and extreme, especially per the 20th Century, the century of Hitler and Mao's hyper-genocidal slaughters?).

3. "Question-1: The basis of the proof of the GIT is the idea of actual infinity. In the proof of the GIT, the relation W(p,q) and predicate W(x1, x2) do not agree; the object of the former is a potential infinity, while the object of the latter is an actual infinity. This clearly contradicts the “expressible relationship” between them. Therefore, the Gödel formula does not belong to the effective definition do-main of the predicate W(x1, x2)and cannot be used to prove the GIT." How is this a question? Note: a question, written in English, should typically include a question mark (?) or a clear erotetic marker of some other kind. Also, the potential/actual-infinity distinction is not to be formalized in your implicit manner of doing so, it would seem.

4. [citing Wang Hao] we believe that the basis of the proof of the GIT is a complete idea of actual infinity. Hao's reputation notwithstanding, it is not clearly evident to me that this is correct: for Hofstadter's reputation notwithstanding either, still I know now that Hofstadter might not have fully appreciated the nature of the "true but unprovable" sentence either, and so why would I assume that Hao is right, here? But then again, maybe this isn't even an important point (in reality, I mean; it's important in your argument, granted).

5. Since the actual infinity is different from the potential infinity, the relation W(p,q) and the predicate W(x1, x2)must be equivalent, and this requires that the object that the predicate W(x1, x2) processes should not be an actual infinity.The former is primitive recursive, an impossible self-loop, while the object processed by the latter is an actual infinity, which must contain its own judgment of itself, and must appear self-loop,thus destroying its own primitive recursiveness. Alright, I'm (mostly) going to have to give up here. As far as I can tell, you are contradicting yourself completely at this point, saying that primitive recursiveness both does, and doesn't, mean "an impossible self-loop." Now, on the other hand, then, maybe there's a way to rehabilitate your interpretation using paraconsistent logic?

It's concerning, moreover, that in your list of references for your paper, you don't list Gödel. Here is a link to his own work w.r.t. this issue. I will admit that I'm not as good with almost any formal system as I would like to be, so I could read Gödel's essay a hundred times over again and still learn far more than I grasp regarding it now. (P.S. the references you do list, aren't in alphabetical order.)

Finally, as I said, I would mostly give up as of (5). But I want to add that Gödel shows us the existence of his peculiar sentence such as to show the incompleteness of mathematical theories of a certain strength. Other, weaker but still perhaps "true" mathematical theories need not run afoul of the principle of the matter, and we (the academic community) have acknowledged this all along, seeing as it's kind of the point of the whole principle in the first place.

Answer 5

Wittgenstein's criticism can be summed up as "it is not true that Goedel's proof is purely syntactic, in fact it cannot be". Wittgenstein was indeed very critical to the whole Aristotelian, Fregean, Russellian approach to logic. And, for the chronicle, some even have it that in fact Wittgenstein was quite right, or at least that his objections are quite legitimate.

But, as a word of caution, one has to read and study W. himself, not his critics, at least not to begin with, in particular the mail correspondence between W. and Russell before and up to the Tractatus is quite illuminating as to the actual debates: just maybe keep in mind that W. is not any less misrepresented and misunderstood than Marx himself is...

Answer 6

Cogito ... Gödel's argument is that in a given axiomatic system capable of math, call it A, there is a statement/mathematical theorem, call it T, such that:

1. T is true
2. T is unprovable in A

A few points that are non liquet:

1. Did Gödel prove an unprovable?
2. In deductive logic at least it would be the case that T is true IFF T is proven (for that T has to be provable) or some weaker version of that. How come then that T is true AND T is unprovable? At a minimum this is counterintuitive.

From what I've read in the posts, my reading of Gödel's argument is way off the mark; it seems he's not claiming that there's a mathematical theorem T that's true and blah blah blah. At least there's no controversy here regarding unprovability.

Another thing I don't understand is why Gödel's paradox (if I may call it that) and its implications are accepted while Russell's paradox prompted a revision of set theory, specifically to rid math of the paradox?

Yet another issue is that if the Gödel sentence G asserts G is unprovable, how is that different from the proof-variant of the liar paradox viz. This sentence is unprovable? I recall reading Gödel admitted to using a spinoff of the liar sentence.

Answer 7

In my paper, there are two core ideas that are mutually corroborating and well-documented.

1. I found a paradox in the proof of Gödel's Incompleteness Theorem and found the concrete form of the paradox. This is, first of all, a new discovery, and one that has been overlooked. This obviously makes up for the weakness of Wittgenstein's argument.
2. Gödel's formula is a cyclic expression. This is obviously not recursive and thus violates the principle of representability. Therefore, it is also obviously absurd that we should discuss this Gödel's formula only outside the valid domain of the predicate W.

Answer 8

The paradox certainly exists. Because first-order logical systems are essentially like naive set theory, they lack restrictions on the definition of propositions (as arbitrary elements in naive set theory), resulting in self-contradictory definitions such as Godel's formula. Just as we need to develop naive set theory into ZFC axiomatic set theory, we also need to improve first-order logical systems in order to avoid paradoxes.