Can anyone explain Godel's Incompleteness Theorem to me?

Question

Can anyone explain Godel's Incompleteness Theorem to me?

Answer 1

Imagine the following hypothesis: "A particular group of rules cannot prove this statement true."



If those rules can prove the hypothesis true, then it is false, and the set of rules are contradictory. On the other hand, if the set of rules cannot prove the hypothesis true, then the set is incomplete - there exists a true statement that the rules cannot prove.



Zing! Godel's Incompleteness Theorem!

Answer 2

Doctor Y's answer was exactly correct. Godel's genius was creating a method of saying "This sentence is not provable in this theory" within the framework of the most basic axiomatic language (which is as close as you can get to saying "This sentence is false").

Any axomatic theory contains some true sentences that cannot be proved within the language of that theory. Going outside the language of that theory creates a new axiom, and therefore a new theory, and there are new true sentences that cannot be proved.



The conclusion of the theory is exactly as explained by Doctor Y. "Any consistent theory is incomplete."



"This sentence is not provable in this theory"

If this theory proves that sentence, then the sentence is false.

If the sentence is false, then the sentence is provable in the theory.

That is a contradiction, and so the theory is inconsistent.



On the other hand, if the theory does not prove the sentence, then the sentence is true. So there is a true sentence that is not provable.



Since the sentence can be written in the framework of any basic theory, any basic theory that is consistent is incomplete.



Now here's how he made the sentence, roughly (this is the complicated part):

Any basic theory that at least contains sequential numbers is sufficient. Godel used prime factorization. The sentence is 2^X1 * 3^X2 * 5^X3 * 7^X4...

The exponents represent different possible characters in the theory. So you need a list of characters: {a, b, ->} (for a very simple set). The order must be fixed.

So to say a->b, you need a number that lists "a" first, then "->", then "b". That number would be 2^1*3^3*5^2, which is the unique prime factorization of the Godel number 1350.

It gets more complicated from there, you may want to look up Godel numbers. The system took several weeks to go over in my class, but the proof itself is pretty simple and we did it in a short time.



V.M.P.R. explained the process of the proof better than I did.

That's why he and Doctor Y are both contacts of mine.

Answer 3

I'm saving this link to review it in detail later.



I always had the intention of reviewing formal proofs of Godel's Theorems, because the simple account that involves intrinsically inconsistent self-reference does not do it for me. The examples given do it in a single statement (i.e. "This statement is false.") but it is possible to consider circumstances when the inconsistency is carried in multiple parts. When do we know then that in a complex proof that may run tens or hundreds of pages long, we did not insert mutually exclusive hypothesis?



Inconsistent self-reference is clearly the origin of the well known Russell's paradox in set theory, where it is specifically chosen a member of a set that is not contained in that set. Thus, the set that contains all sets that do not contain themselves is as much a matter of hierarchy of sets as is the male barber that shaves all men that do not shave themselves.



Anyway, if we remove the statements that contradict themselves, does the proof still hold? I'll get back to you on this.

Answer 4

I applaud all of the answers above, thank you guys! I'd also like to direct you to a similar topic on berry's paradox. Pretty interesting stuff.

Answer 5

In 1931, the Czech-born mathematician Kurt Gödel demonstrated that within any given branch of mathematics, there would always be some propositions that couldn't be proven either true or false using the rules and axioms ... of that mathematical branch itself. You might be able to prove every conceivable statement about numbers within a system by going outside the system in order to come up with new rules and axioms, but by doing so you'll only create a larger system with its own unprovable statements. The implication is that all logical system of any complexity are, by definition, incomplete; each of them contains, at any given time, more true statements than it can possibly prove according to its own defining set of rules.



Gödel's Theorem has been used to argue that a computer can never be as smart as a human being because the extent of its knowledge is limited by a fixed set of axioms, whereas people can discover unexpected truths ... It plays a part in modern linguistic theories, which emphasize the power of language to come up with new ways to express ideas. And it has been taken to imply that you'll never entirely understand yourself, since your mind, like any other closed system, can only be sure of what it knows about itself by relying on what it knows about itself.

Answer 6

it relatively is something like this: a assertion, G, says G isn't provable. observe that G would be unable to be shown, even with the indisputable fact that it would desire to be genuine. for this reason all issues that are genuine would be unable to inevitably be shown.

Answer 7

".... that the results show mathematics to be incompletable or inexhaustible and that one of them demonstrates that either...the human mind(even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems ...."

Answer 8

The general intuition of HOW does Gödel get there is pretty easy to grasp. I say this so you find a way to relax and see it as simple, calmed and focused as you can. (Often, psychological obstacles close certain comprehension windows in ourselves... concerning math, theorems and formal systems people often suffer from this closed-mindedness).



Gödel himself was inspired by the nowdays known as Richard's paradox. As you say to be aware of the main conclusions of Gödel's proof (of the first theorem), so I'll go to the point (to get an excellent intuition about it the main outcome, take Doctor Y sentence, but change "A..." for "Any particular group of rules that suffices to get the whole FOL..."). The thing that can be tricky is the baroque way that Gödel found and/or made (complex) isomorphisms between theories, concepts, the way we represent them grammatically and the like.



Here is a general (and pretendedly useful) intuition of how does Gödel made it;



Think of a theory (in a sense just a set of, written or spoken, sentences) of positive integers, zero and basic arithmetical functions such as sum, rest, division and multiplication. Include also the function of exponentiation. Lets call this theory about positive integers, zero and arithmetical functions, PA (for Peano arithmetic). Now imagine that you take the theory PA extensionally, which is, taking PA for every formulable and correctly derivable sentence concerning adds, rests, divisions, multiplication and exponentiation of positive integers, so you'll have a list made of only true formulae like this:



1. 2 + 2 = 4

2. 4 * 6 = 24

3. 25 / 5 = 5

4. 0 * 1 = 0



But we'd have also a lot more complicated sequences of numbers related also with basic arithmetical functions (suppose that 5 is correct):



5. 12098398473876283764587092 * 9028739823762387462

= 92981729837238746876238764987123......



Now you've considered every possible expressible and correct sentence of PA. Then, imagine that you a theory such as first order logic (FOL), in which naturally you'll have a way to express the universal quantifier, material implication, negation and probably the rest of logical connectives, letters for objectual variables, constant predicates and the rest. Now mix FOL with PA, so that you can express arithmetical truths with the whole logical apparatus. Taken FOL+PA extensionally, you'll have sequences as these:



6. Vx (Fx → Ax) ≡ Vx¬(Fx & ¬Ax)

7. ¬Vx ((Hx & Ax) & Vy ((y = x) → (Hy & Ay))

... but also senteces like this:

8. ¬Vx¬(VyVz (y + z = z) & (y = x)) = 0



(Imagine that not only well formed formulae are present in FOL+PA taken extensionally, but also correctly derivable formulae, i. e., theorems of FOL, theorems of PA, and theorems of FOL+PA, are in FOL+PA taken extensionally)



Now you find a way to map the set of sentences of FOL with a proper subset of sentences of PA in a bijective relation (which is called gödelization of meta-math), so that for an enumerable proper subset of positive integers, every theorem of FOL+PA finds a number and only one number, which would be, naturally also in some portion of PA taken extensionally. Let's call this mapping function, g. So as you can define and represent the function g in FOL+PA, then you have a way to represent, within and lawfully (?) the predicate "provability", since, as we've assumed, only theorems of FOL, PA and FOL+PA can be in the set of FOL+PA formulae taken extensionally. (All this can surely be done in a far more formal and detailed way).



This mapping actually works amazingly. All the work is made by choosing the correct arithmetical function. To gain an intuition of a decisive characteristic of this mapping in a very simplistic way consider, for instance:

11. p→q

12. p |- q



(To be read as, if p implies q, and p, then q)



This, a modus ponens, doesn't only works in FOL taken separately, but also in the arithmetical mapping of it, being some sort of:

11'. 2 * 3

12'. 6



So you can arithmetically analyse every positive integer and if it is under g taken extensionally, you can be confident that there is going to be a factorization such that you can re-translate every number of the PA subset of numbers of the g function, to a sentence of FOL or to a sentence of FOL+PA. And even more, that proper retranslation will give you a correctly derivable (or correct) sentence or a sequences of sentences of FOL+PA.



Now, you can construct the sentence that, intuitively says of itself that is not in the set of FOL+PA, transform it back, and voilá, the number for that sentence, let's us call it G, is in the subset of numbers of PA that compose the function g taken extensionally.



So, if there is a formal way to come down to G, in FOL alone, then you have an inconsistent system (in PA!?... no way!... that would be disastrous, and now we now, false, see Gentzen's proof for arithmetic consistency) or, you have a true sentence in PA, for which you do not have a way to grasp only with FOL tools. There we are in front of a number with a translation to a sentence, which is true in the system of FOL+PA, but which cannot be proved by FOL alone. The number is actually in your collection of formulae of our specific subset of PA, reached by our function g. FOL+PA is smaller than PA alone? This is where the tricky part is located...



As a general balance: You have a much more powerful system, PA, that cannot be wholly grasped by our most powerful proof system, which is, FOL. So, FOL+PA is incomplete. A diagnosis that I do (so you can take it in its own dimension) is that the set of possible relations of positive numbers PA (i.e. PA's, a very important set of definable recursive functions) is bigger than the syntactical relations (also functions) of FOL, so that FOL cannot handle FOL+PA, while, PA alone seems to be.



Gödel took this results as implying that numbers cannot be constructed inferentially in any way, so that they kind of existed independently of our rational powers. He actually died studying Husserl trying to find a better justification for mathematical truths, math epistemology. He was a platonist in fil of math.



Good luck with this exciting result!



(I am a lawyer and a non-analytically formed philosopher, so if I made a mistake in this sort of general survey-picture of Gödel's First Incompleteness Theorem, please, correct me attending the same mood... "how is that we actually get in there")



Further:

Y Doctor made an interesting mistake of oversimplification and he did also not answer the main question which is not "what does Gödel's Incompleteness Theorem (assuming it is the first) show", but how does he actually proves it. Joe.Finkle got it better. The mistake of Doctor Y is that his answer lacks a generalization clause, given the fact that First Order Logic is a formal science that studies the phenomenon of proof in general, not of 'a particular set of rules' but a gigantic, probably infinite, set of rules of inference. (I should not give Doctor Y thumbs up).



Further:

Thanks Joe.Finkle!

I made some minor corrections of typos and clarified sentences on march 9th, at 11:40 AM, hour of Mexico City.