Hot answers tagged

74

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


64

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


28

After a bit of searching, I found some promising leads (and quite a few consistent descriptions) which suggest that Russell thought Gödel's results were of cardinal importance, but misunderstood their implications. In particular, he thought that Gödel's result essentially entailed that Peano Arithmetic was inconsistent rather than incomplete; but ...


27

Any effectively axiomatized formal system that extends a very basic theory of formal arithmetic called Robinson Arithmetic (Q) will contain an undecidable sentence. In full generality, you can state the syntactic version of the First Incompleteness Theorem as follows: (G1T) For any effectively axiomatized theory T that extends Q there exists a T-sentence ...


24

Here's what Jordan Ellenberg, a professor of mathematics at the University of Wisconsin, has to say about this topic in his Does Gödel Matter? article: What is it about Gödel's theorem that so captures the imagination? Probably that its oversimplified plain-English form—"There are true things which cannot be proved"—is naturally appealing to anyone ...


16

There isn't anything wrong with justifying a claim that Peano Arithmetic is either inconsistent or incomplete by reference to Gödel's Incompleteness Theorems; the claim is a direct application of the first Incompleteness Theorem. Gödel showed that any formal system of adequate expressive power for doing formal arithmetic was either inconsistent or ...


15

Such arguments are indeed ... shall we say "hopeless", to be polite. For a demolition job, take a look at Torkel Franzén's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse.


15

The common axiom systems for intuitionistic logic are both sound and complete. It is interpretable as an S4 modal logic or as a weakening of classical logic (essentially you just drop the law of excluded middle and double negation elimination and then tweak the quantifier rules). Since it is both sound and complete it is not incomplete. The fact that they ...


12

Not on this at least. Wittgenstein is alluding to Frege on logical syntax. From Tractatus:"Frege says that any legitimately constructed proposition must have a sense. I say that any proposition is legitimately constructed". Laws of syntax are similar in form to ethical laws: thou shalt not (form such and such sentences). Wittgenstein's response in both cases ...


11

A statement being uprovable is very different from it being an inconsistency of the theory. If a statement is shown to lead to an inconsistency, then you can use it to prove statements and their converse statement, which cast a bad shadow on all statements in the theory. Even then, you don't want to drop the theory but examine what led to the bad apple ...


11

What the result means, essentially, is that in certain toy models there can be no algorithm deriving some macroscopic characteristics (spectral gap) from microscopic parameters of the models. The main import is that we get a Gödel sentence that unlike the original has some explicit mathematical meaning. Let's be generous and assume that the situation extends ...


11

It is a natural idea, but unfortunately the answer is no, it is not feasible. The root of incompleteness is not numbers, but the possibility of (implicit) self-reference, arithmetic is just the simplest structure that already realizes that possibility. In fact, one does not even need the Peano arithmetic, but a much weaker Robinson arithmetic without even ...


11

Gödel's theism is discussed by Franzen in Gödel’s Theorem: An Incomplete Guideto Its Use and Abuse. He penned a version of the ontological argument, and in 1961 ranked the worldviews “according to the degree and the manner of their affinity to or, respectively, turning away from metaphysics (or religion)... Skepticism, materialism, and positivism stand on ...


10

You observe, correctly, that just because a formal system S "asserts" its own consistency — by means of a proof which, in a meta-language M, is isomorphic to a proof of consistency of S — does not mean that you should therefore trust S to be consistent. Any inconsistent system which is rich enough to admit Gödel numbering (or an equivalent ...


9

For detailed discussions of the so-called Lucas-Penrose arguments, see : Torkel Franzén, Gödel's theorem : An incomplete guide to its use and abuse (2005), Ch.6 Gödel, Minds, and Computers, page 115-on and Francesco Berto, There's Something about Gödel : The Complete Guide to the Incompleteness Theorem (2009), Ch.11 Mind versus Computer: Gödel and ...


9

(Disclaimer: All of what follows is explicitly done under the assumption that the mind is a Turing machine and that we can formally axiomize our mathematical thinking. This has, of course, never been shown to be possible. What I'm describing is the state of affairs that would obtain if that were possible, given the metamathematical and metalogial results of ...


9

Perhaps against my better judgment, I'll take a stab at answering this - this incarnation of the OP's issue does come closest to being a real question in my opinion. First, let's trim away all the excess and unclear verbiage ("stipulated relation"? "conceptual truth"? "ontological engineering"?). You're supposing that we have some formal system T (say, ...


8

The other answers miss something important. The real impact of the Second Theorem isn't in the limitations it places on a theory's proving its own consistency. The key point is this. If a nice arithmetical theory T can't even prove itself to be consistent, it certainly can't prove the consistency of a richer theory T+ which extends T (since proving the ...


8

The following is from a late paper of Russell's titled "Logical Positivism". It can be found in "Logic and Knowledge" It appeared that, given any language, it must have a certain incompleteness, in the sense that there are things to be said about the language which cannot be said in the language. This is connected with the paradoxes - the liar, the class ...


8

If a statement is not provable an inconsistency or self-contradiction may or will develop that invalidates the system. That's not the case. You are somehow mixing together the first and the second incompleteness theorem and drawing a misleading conclusion. Briefly put: The first theorem proves that all consistent axiomatic formulations of number theory ...


8

Godel's theorem says nothing about human understanding. It only places limits on certain formal axiomatic systems. Humans have ways of understanding that transcend formal axiomatic systems; for example, we can extend a given axiomatic system to prove the truths that were unprovable in the unextended system. As an example, Zermelo-Fraenkel set theory (ZF) ...


8

He did not write it anywhere. The quote itself only calls Gödel and Skolem "alleged proponents", and later in the article Eklund remarks that "the (supposed) evidence that Skolem adhered to first-order logic is that Skolem held that set theory and arithmetic should be given first-order axiomatizations, whereas... evidence that Gödel adhered to first-order ...


8

We can construct a computer that implements an inconsistent formal theory to which Gödel theorem does not apply just like we can construct a computer that implements Peano arithmetic. A simple example is Meyer's relevant arithmetic R# that allows some contradictions, but uses paraconsistent logic (without the law of explosion) to limit their effect. In R# ...


7

If you allow infinitary rules like the omega-rule, more becomes provable so PA plus the omega-rule proves the Gödel-sentence for PA. But PA plus the omega-rule still isn't complete -- a result that goes back to Rosser's 1937 JSL paper on Gödel theorems for non-constructive logics. Dan Isaacson's paper on the omega rule might be helpful here: "Some ...


7

This reminds me of the older question Was Wittgenstein anticipating Gödel? There is more to it in the case of Kant than there was in the case of Wittgenstein though, at least in spirit. One could say that Kant pioneered in epistemology the stratification into levels of discourse, which Gödel later applied to formal semantics. When the Gödel theorem ...


7

It is worth separating the logic from the epistemology. Let's start with the logic. A (first order) theory is a set of sentences. Usually we are interested in deductive systems, so we require a theory to be closed under the relation of provability. A theory T is axiomatizable if there exists a subset of T, the axiom set, such that all of the sentences in T ...


6

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


6

If you defined an isomorphism between the natural numbers and some element of a physical theory, this would imply that there exist statements about the physical theory could not be proven or disproven within the theory. It certainly doesn't say that every statement in the theory is beyond falsification; and it proves nothing whatever about what might happen ...


6

The two notions (completeness and incompleteness) are not opposites but very much connected (not only by Godel's name in the name of the two theorems). Do take into account that Godel's Completeness Th of First-Order Logic is : if a sentence is true in all the models of the axioms (i.e. it is a logical consequence of the axioms) then it is also formally ...


Only top voted, non community-wiki answers of a minimum length are eligible