Is this really an adequate proof of Godel's First Incompleteness Theorem

[Ed Quanta]

http://www.math.hawaii.edu/~dale/godel/godel.html

Does this really prove it? Or is this just a rough sketch of a proof?

 

[quantumdude]

It's a sketch of the proof. Goedel's actual proof is here:

http://home.ddc.net/ygg/etext/godel/godel3.htm

 

[Ed Quanta]

Any suggestions for any good logic books that I can read to get the formal training I need to understand this proof?

 

[quantumdude]

Yes: Language, Proof and Logic by by Barwise and Etchemendy. It assumes only maturity in mathematical reasoning and comes with a CD with some logic tools for evaulating arguments.

There is an online copy available, if you can do without the CD. But the CD really enhances the book in a big way.

http://netra.wustl.edu/~adpol/research/Math/Language%20Proof%20and%20Logic.pdf

 

[Philocrat]

http://www.math.hawaii.edu/~dale/godel/godel.html Liar Paradox. "Truth" for English sentences is not definable in English.
Proof. Suppose it is. Then so is its complement "False".
Let s be the sentence "This sentence is false" .
Since the phrase "This sentence" refers to s, we have
s iff "This sentence is false" iff "s is false" iff not s.
A contradiction.

Well, the phrase "This sentence.." is metaphysically, epistemolically, and semantically doomed. For a start, it is Referentially Empty as it is semantically devoid of referents! It is referring neither to itself nor to anything esle in the world. For it to contain and mean something it must contain or refer to something concrete such as another self-standing sentence within it or outside it.

The second part of the sentence is "..is false" is epistemologically twice as doomed. Epistemologically, you are simply naively implying:

'A sentence that says nothing or points to nothing in the world is false, which is logically equivalent to pure nonesense. What is neither true nor false is false? Or simply, 'Nothing' is false? Is that what you are implying? Does that make sense?

Metaphysically, the Phrase "This sentence' is governed by an EXCLUSIONARY LAW or PRINCIPLE which forces it to take on a 'METAFORM' which is a completely new Metaphysical Catigory. If this is correct then, sentence S must inevitably be forced to take the form:

This sentence "John is alive" is false.

This setence is now metaphysically sound because it has been properly cartigorised, naturally permitting one logical form to be embeded in another logical form that referentially points to it. Metaphysically, this is a form within a metaform, a form that is metaphysically 'pregnant' with another form', which in this very case both are metaphycally, epistemologically, logically, semantically consistent and synchronised. The 'metasentence' as it may quite rightly be called can assert the truth value (truth or falsness) of the embeded sentence.

The same will be true of such sentence as:

That sentence "John is alive" is false

When someone looks over there, he or she should see nothing more than the sentence "John is alive" written on the black board or in the sky or anywhere else distanced from the speaker.

And equally of another of Russesll's Paradoxical sentence:

The sentence on the other side of the Paper "John is alive" is false

Hence when someone turns the paper over we expect the person to see the sentence "John is alive" and not a self-referential one as:

"The sentence on the other side of the paper is false'

For this sentence refers neither to itself on Side A of the paper nor to the same on Side B of the paper.


NOTE: It is very important to observe here very carefully how the Metasentence Self-debugs or self-disambiguates by semantically separatring itself from the embeded sentence, while at the same time metaphysically excluding itself from self-referential error which in my opinion is pure and simple a Category Mistake' A metasentence is logically and semantically redundant (neither true nor false) in virture of being referentially redundant (it neither refers to itself nor asserts anything about itself).

 

[quantumdude]

Well, the phrase "This sentence.." is metaphysically, epistemolically, and semantically doomed. For a start, it is Referentially Empty as it is semantically devoid of referents! It is referring neither to itself nor to anything esle in the world. For it to contain and mean something it must contain or refer to something concrete such as another self-standing sentence within it or outside it.

Well Goedel didn't see it that way, but fine. If you prefer the paradox can be rephrased thusly:

The sentence below is false.

The sentence above is true.

 

[Philocrat]

http://www.math.hawaii.edu/~dale/godel/godel.html There is a weak theological parallel in the Problem of Evil:
God doesn't exist since an ultimate ruler must be responsible for all things but a perfectly just being wouldn't be responsible for evil acts.

Not when the process of Creation by God is Quantitatively and Logically Continues! You need a 'Multivalent Parametric Calculus' (MPC) that can precisely describe Dynamic Continues Processes in a mathematically and logically progressive way. The current Logic and Mathematics tend to naively concentrate on the description of Dynamically Circular States of the world in a stagnant and non-progressive manner.

CIRCULAR CONTINUITY (as I sometimes call it) is metaphysically and epistemologically fictional. Any mathematics or logic that attempts to describe it must run into logical paradoxes and contradictions because it cannot account for progress. Of course, it may account for the dynamics of the system and demosntrate how Proprietory States service Intermediate States, and how they are collectively recycled to maintain the system and consquentially generate what I sometimes call 'FALSELY CONSTITUTED SENSE OF CONTINUITY' which in turn is a 'FALSELY CONSTITUTED SENSE OF NORMALITY'. But what it cannot do is account for how deficits in the creative process are systematically discounted from the whole process to generate a GENUINE SENSE OF CONTINUITY which in this very sense is a PROGRESSIVE CONTINUITY in the strictest sesne of the word.

MPC, if it can be formulated within the context of LPL (Logically Pefect Language), should be able to account for:

(1) God's Achievements to date in the Creative process

(2) Deficits (evil, causal and relational errors) in the Creative Process that are Outstanding

MPC must empircally demonstrate how the outstandind deficits in the creative processes are being systamtically reduced or discounted from the Sum Totality of God's Creation. The Biggest challenge now is for the 'NOISY LOTS' to create MPC within the context of LPL.

 

[Philocrat]

Well Goedel didn't see it that way, but fine. If you prefer the paradox can be rephrased thusly:

The sentence below is false.

The sentence above is true.

It is not me that the formalist has to worry about. Here I am only voicing my own concerns with regards to metaphysical categories of sentences that take the paradoxical route.

The people that the formalist should be worried about are people in certain institutions of our society that rely heavily on logic to do their businesses on daily basis. For example, in the court of law, Lawyers and Judges who are heavy users of logic would attempt to disambiguate most of the paradoxical statements found in mathematical, logical and scientific textbooks. If Lawyers fail to pick up logical confusions or vaguenesses in those paradoxical snetneces, Judges would, especially high cour judges. Judges, especially, are very good at disambiguating paradoxical statements. Infact, if you ask judges whether they have ever created any law, they will deny that they ever did. Most of them would say "Oh, we do not really create any law ...only parliamentarians do". Well, this is not strictly true. Many laws have been created and are still being created by Judges and most of these 'Judge-Created Laws' usually occur when Judges are attempting to disambiguate paradoxical terms or sentences, which I personally predict can only occur at the 'Natural Law' (and metaphysical) level. Many judges unconsciously venture or wander into the natural law level to draw inferences and disambiguate without reasling it. This is something I have personally realized for many years and kept my mouth tightly short. The only threat to this process is when ill-informed politicians turn up with primitive or draconian ideas that has no foundation in natural law to be written into the statute books as laws to service their private prejudices.

What I am trying to say here is that our NL (Natural Language) have already, built-in quantitative and logical devices for disambiguating metaphysically vexing Self-referential Symbols or terms or sentences. It is therefore unfair for the formalists to treat the native speakers of NL as total idiots. Of course, undeniably, some of us do muddle things up a little bit and cause confusion and vagueness with sentential constructs in our routine communcation with each other; yet equally we must also admit that the majority of us do construct clear and logically precise sentences while at the same time disambiguating paradoxical ones during routine conversations.

My prediction as always is that we can allert everyone to self-debugging or self-disambiguating quantitative and logical devices that are already contained in NL by comprehensive education. Just educate everyone from very early in his or her educational life how to construct clear and logically precise sentences. As for me, paradoxes are fictions, and for personal convenience, I have catigorised them into two fundamental types: 'Parafuses' (confusions, vagueness, and msiunderstandings) and 'Paracepts' (natural limitations of some physical kind).

NOTE: The interface of Natural Law with Man-made Law comes in degrees of consistency and appropriateness. By saying that judges do unconsciously venture and wander into the realm of natural law to draw inferences and disambiguate, I am merely pointing out that many of the so-called Judge-created Laws do substantially address justice at the level of nature, at least at the level of 'Nature as it is'. But if you start to penetrate nature to a level where you start to ask questions as to why the world is as it is or why do offenders offend at all, then you are venturing into a region of Natural Laws best left to science.

 

[Philocrat]

The sentence below is false

"John is alive"

The sentence above is false

Here I am only teaching the world how to bankrupt those who invent fictions ...to sell books!

 

[gravenewworld]

I wouldn't recommend that you read On Formally Undeciable Systems By Godel. Although the proof is indeed brilliant, Godel himself is not all that good of a writer and people have cleaned up his proof to make it much shorter and much more refined. Intermediate logic books usually have a proof for the Godel theorems. To tell you the truth, you won't be able to just pick up a book on introductory logic and expect to understand his proof. It takes a lot of work. Become very familiar with first order logic, recursive sets, relations, and funcitons, godel numbering, arithmetization of syntax, metalogic, arithmetical definability before you try to tackle his proof. If you aren't looking to technically understand his proof, but just the result in a layman's sense there are plenty of books out there that will explain it in good plain old English such as Godel, Escher, and Bach: The Eternal Golden Braid. I am currently doing an independent study on logic and I am almost at the point where I can begin the chapter on Indefiniability, undecidability, and incompleteness (which proves Godel's Theorems) and I will admit this stuff is TOUGH. This is by far the most challenging material I have ever done. Recursion theory and arithmetization is very difficult to understand at times at the more advanced levels.

 

[Philocrat]

I wouldn't recommend that you read On Formally Undeciable Systems By Godel. Although the proof is indeed brilliant, Godel himself is not all that good of a writer and people have cleaned up his proof to make it much shorter and much more refined. Intermediate logic books usually have a proof for the Godel theorems. To tell you the truth, you won't be able to just pick up a book on introductory logic and expect to understand his proof. It takes a lot of work. Become very familiar with first order logic, recursive sets, relations, and funcitons, godel numbering, arithmetization of syntax, metalogic, arithmetical definability before you try to tackle his proof. If you aren't looking to technically understand his proof, but just the result in a layman's sense there are plenty of books out there that will explain it in good plain old English such as Godel, Escher, and Bach: The Eternal Golden Braid. I am currently doing an independent study on logic and I am almost at the point where I can begin the chapter on Indefiniability, undecidability, and incompleteness (which proves Godel's Theorems) and I will admit this stuff is TOUGH. This is by far the most challenging material I have ever done. Recursion theory and arithmetization is very difficult to understand at times at the more advanced levels.

Yes, I have watched in utter amazement as people marvel and daydream at the beauty of 'FORMS', be they mathematical, logical or metaphysical. Of course FORMS and METAFORMS are mathematically, logically and metaphysically beautiful. Sweet dreams, Formalists!

But Godel completely forgot one fundamental parameter in his formula: HIMSELF. He comepletely forgot himself as a fundamental metaphysical category that must inevitably become an 'ESSENTIAL PARAMETER' in his calculus. How could he have come to such radical conclusions about the UNCERTAINTY AND INCOMPLETENESS PRINCIPLE by metaphysically (hence quantitatively) rulling himself out as an essential parameter needed to reconcile every other parameter in his formula? So, by excluding himself from the formula, he fell into a fundamental CATEGORY MISTAKE, because the category that he removed from the whole metaphysical picture of the world is by far the most significant and important.

NOTE: The "HUMAN PARAMETER" as I would like to very much call it can be reduced either to a single parameter or to a set of parameters. My prediction is that the resultling solutions would be the same. For all that it would do is adjust the whole formula to be fully dynamic and flexible, to ultemately allow for INTER-SCALE RECONCILING. You should see the magic unfold as the fully charged parameters internally adjust from one scale of reference to the next. This should theoretically and in actaul fact fully account for STAGNATION, CONTINUITY and PROGRESS in the overall configuration or structure of the world. That would be the REAL beauty to marvel and daydream at!

 

[Philocrat]

Add Godel to the formula and:

(a) the Uncertain becomes certein

(b) the incomplete becomes complete

If anything is uncertain or incomplete about the epistemologically status of the world, it is because Godel himself (the spectator or perceiver) is missing in the formula.

 

[Hurkyl]

You're relentlessly attacking a strawman:

Well, the phrase "This sentence.." is metaphysically, epistemolically, and semantically doomed.

You are attacking this intuitive description of the proof as if it is the proof itself. Gödel wasn't so naïve that he simply claimed "This statement is unprovable" was a logical formula, and thus logic is incomplete.

What Gödel does is work out a way to encode logic in arithmetic -- propositions are translated to numbers, and the provability of a statement is reduced to an arithmetic proposition. The statement "This sentence is unprovable" does not literally say that -- it's constructed as some sentence S whose truth is equivalent to whether its corresponding number is a "provable" number.


Gödel's proof is certainly not the only proof either. This sketch comes from computability theory:

(Number theory means the true statements in the language of natural numbers, addition, and multiplication)

(1) There is no decision algorithm for number theory.

A decision algorithm is one that takes a sentence in number theory, and is guaranteed to eventally stop and say whether the sentence is true or false. This is proven by showing you can use a decision algorithm for number theory to create a decision algorithm for the halting problem -- something provably impossible (via a diagonal argument).

(2) There is an algorithm that can verify a proof in number theory

This is fairly simple -- make sure that each logical step follows from the previous ones.

(3) There exists a true, unprovable statement in number theory.

Assume that true statements were provable, then we could construct a decision algorithm for number theory: given a sentence S, step through all possible strings of symbols. Test if the string of symbols is a proof of S, or if it is a proof of ~S. Since all true statements are provable, either S or ~S is provable, and thus this algorithm halts and gives the correct answer. But, since we know a decider doesn't exist, our assumption is false: therefore there is a true statement that is unprovable.



Then to construct the sentence that 'says' "I am not provable", one designs an algorithm S that:
(1) Ignores its input.
(2) Constructs a sentence P (in the language of number theory) that is true if and only if S does not accept the string "0". (Involves the recursion theorem)
(3) For every possible string of symbols:
(3a) Run the proof verifier to see if it's a proof of P.
(3b) If a proof of P is found, accept the input.


If S accepted the string "0", that means it found a proof of P, but that would mean P is true, and thus S doesn't accept the string "0".

Therefore, S does not accept the string "0", and the statement P it constructed is a true statement. P must be unprovable, because otherwise S would have accepted the string "0".

 

[honestrosewater]

Then to construct the sentence that 'says' "I am not provable", one designs an algorithm S that:
(1) Ignores its input.
(2) Constructs a sentence P (in the language of number theory) that is true if and only if S does not accept the string "0". (Involves the recursion theorem)
(3) For every possible string of symbols:
(3a) Run the proof verifier to see if it's a proof of P.
(3b) If a proof of P is found, accept the input.

I don't get the part about S ignoring its input. If S ignores its input, how can it accept any input? You mean it passes its input to the verifier and accepts if the verifier accepts?

 

[Hurkyl]

I'm defining an algorithm that does exactly the same thing, no matter what the input is. Such an algorithm either:

(1) Accepts every possible input
(2) Rejects every possible input
(3) Runs forever on every possible input.

 

[honestrosewater]

Okay, thanks for sharing, I won't ask any more questions here :)

 

[learningphysics]

Well, the phrase "This sentence.." is metaphysically, epistemolically, and semantically doomed. For a start, it is Referentially Empty as it is semantically devoid of referents! It is referring neither to itself nor to anything esle in the world. For it to contain and mean something it must contain or refer to something concrete such as another self-standing sentence within it or outside it.

Here's what I think is a good illustration of a godel type situation. There is no self reference. The referrants are all there. Suppose there exists some person named Jack.

Sentence S: "Jack can never prove that Sentence S is true."

Now... Sentence S is completely defined. It refers to the string of characters in the quotes.

Assign truth value to a sentence as follows: Sentence S is true if there is a meaningful statement conveyed by Sentence S in the English language, and this statement is true. If there is a meaningful statement conveyed by Sentence S and the statement is false, then the Sentence S is false. If there is no meaningful statement conveyed by Sentence S, then the Sentence S is false.

Is there a meaningful statement conveyed by Sentence S, in the English language? Yes there is. Everyone will agree with this. Including Jack.

Now, anyone other than Jack will know that the Sentence S is true. But Jack will never know. Jack reasons himself... "If I prove that Sentence S is true, then Sentence S is false. If I prove that Sentence S is false, then Sentence S is true. Hence I can never prove that Sentence S is true or false." Everyone other than Jack knows that this is the dilemma he faces and the impossibility of him proving Sentence S... hence they know that the Sentence S is true.

The thing is that sentences are just string of characters (unlike statements). Referring to them is no problem. This would be a problem:

Sentence S: "Jack can never prove that the statement conveyed by Sentence S, in the English language, is true."

Above... there is no meaningful statement conveyed by Sentence S in the English language. We have true self reference, and nonsense.

 

[gravenewworld]

Thats one of the more interesting aspects of the proof- the notion that provability and truth are NOT the same thing.

 

[gravenewworld]

WAHOO! I finally did it! I finally went through and understood how to prove Godel's incompleteness theorems. This is by far one of the greatest achievements of my undergrad. career. I finally feel like I accomplished something since I have been doing this material on my own as and independent study.