- #1

- 297

- 0

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Ed Quanta
- Start date

- #1

- 297

- 0

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

- #2

Tom Mattson

Staff Emeritus

Science Advisor

Gold Member

- 5,500

- 8

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

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

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

Last edited by a moderator:

- #3

- 297

- 0

- #4

Tom Mattson

Staff Emeritus

Science Advisor

Gold Member

- 5,500

- 8

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 [Broken]

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 [Broken]

Last edited by a moderator:

- #5

- 598

- 0

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

The second part of the sentence is

Metaphysically, the Phrase "This sentence' is governed by an

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 '

The same will be true of such sentence as:

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

And equally of another of Russesll's Paradoxical sentence:

Hence when someone turns the paper over we expect the person to see the sentence "

"

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

Last edited:

- #6

Tom Mattson

Staff Emeritus

Science Advisor

Gold Member

- 5,500

- 8

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

- #7

- 598

- 0

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

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

(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

Last edited:

- #8

- 598

- 0

Tom Mattson said: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 text books. 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.

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:

Last edited:

- #9

- 598

- 0

The sentence above is false

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

- #10

- 1,104

- 25

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.

Last edited:

- #11

- 598

- 0

gravenewworld said: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

But Godel completely forgot one fundamental parameter in his formula:

- #12

- 598

- 0

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

- #13

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

You're relentlessly attacking a strawman:

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

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

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

Last edited:

- #14

honestrosewater

Gold Member

- 2,105

- 5

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

Last edited:

- #15

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

(1) Accepts every possible input

(2) Rejects every possible input

(3) Runs forever on every possible input.

- #16

honestrosewater

Gold Member

- 2,105

- 5

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

- #17

learningphysics

Homework Helper

- 4,099

- 6

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

Last edited:

- #18

- 1,104

- 25

- #19

- 1,104

- 25

Share: