Register to reply

Is Godel's incompletness theorem complete?

by yuiop
Tags: godel, incompletness, theorem
Share this thread:
yuiop
#1
Mar23-08, 09:52 AM
P: 3,967
Hi,
I came across this article on Godel's incompletess theorem that seems to relate to number theory so I hope this is the right place to post this question.

This paragraph is from http://www.miskatonic.org/godel.html
=================================================================
In The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:

Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."
Now Gödel laughs his high laugh and asks UTM whether G is true or not.
If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").
"I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."
Think about it - it grows on you ...

With his great mathematical and logical genius, Gödel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics ...

Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth ... But, paradoxically, to understand Gödel's proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Gödel's name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.
=================================================================

Now as I see it the sentence:
"The machine constructed on the basis of the program P(UTM) will never say that this sentence is true."

can be replaced with:
"The machine constructed on the basis of the program P(UTM) will never say that G is true."

since G = "this sentence". That means the sentence can further be restated as:

"The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that G is true.") is true."

and then as :

"The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that ("The machine constructed on the basis of the program P(UTM) will never say that G is true.") is true.") is true."

Clearly the statement G is recursive and would take an infinite amount of time to even ask the full question in its full form. Is this not asking the UTM to give a true or false answer to a question that has no finite form?
Phys.Org News Partner Science news on Phys.org
New type of solar concentrator desn't block the view
Researchers demonstrate ultra low-field nuclear magnetic resonance using Earth's magnetic field
Asian inventions dominate energy storage systems
Hurkyl
#2
Mar23-08, 11:13 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Are you familiar with the halting problem?
yuiop
#3
Mar23-08, 11:58 AM
P: 3,967
Quote Quote by Hurkyl View Post
Are you familiar with the halting problem?
I was vaguely aware that it is impossible to determine if a Turing machine will eventually halt for certain non trivial algorhythms, but I had not noticed the very close connection with Godel's incompleteness theorem before. Thanks.

al-mahed
#4
Mar23-08, 09:04 PM
P: 258
Is Godel's incompletness theorem complete?

The key questions is: can the statement G be constructed using the "axioms" that are used by the UTM do its calculations?

I don't know much about this kind of advanced logic/maths, but I tink this is what the incompleteness theorems are about.
LukeD
#5
Mar24-08, 11:42 AM
P: 355
What Goedel proved was with that any system that is complex enough to define the ring of the natural numbers (i.e. 0, 1, 2, ..., as well as addition and multiplication on them) one can construct the statement G.

I've read through a sketch of the proof. He is able to find a finite version of the statement. I believe it has something to do with encoding the statement in a certain way and then asking the UTM (I believe that this is what my roommate, a computer science major, refers to as an oracle) about what the decoder should answer for truth value of the statement.

An interesting thing in my opinion is to consider what happens when you have multiple truth machines. Then you could ask one truth machine whether or not the statement referring to the other is true. Of course, you could then construct a statement that refers to both of your truth machines. But what happens if you have an uncountably infinite number of truth machines? Then it seems to me you'd need stronger axioms to construct a statement that refers to all of them.

Some day I will actually read through the proof.
Hurkyl
#6
Mar24-08, 03:56 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
The heart of Gödel's proof is that he establishes a way to translate questions about logic & turing machines into number theory. (The reverse direction should be clear) The first incompleteness theorem should really be a mere corollary of that fact.
loz
#7
Sep4-09, 11:35 AM
P: 8
The UTM could just answer False.
If the answer to "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." is given as false then this does not make G true, it simply means that on this occassion it was given as false.
Imagine somebody entering the UTM with the sentence.
"If G = NOT G". Is G true?
The answer would be TRUE.
Therefore both the previous answers are true.
FayeKane
#8
Sep26-09, 01:24 AM
FayeKane's Avatar
P: 32
For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience.
Yeah, but not to all of us. Gödel's G is just another version of TSIF ("this statement is false"). (Digression: I once had a T-shirt that said "The other side of this shirt is true" on the front and said--that's right--"The other side of this shirt is false" on the back.)

Formally, TSIF is not a proposition (P(P)=F) or even a legitimate statement because the argument of the predicate P is undefined, due to infinite recursion (technically, it's "not well-defined").

Now, if past is prologue, you will now point out that no part of G is undefined, as it is a string of well-defined decimal digits (in Gödel's proof, G is actually a number--though extremely long one).

But that's like saying that TSIF is well-defined because it has a representation which is both definite and finite (in, for instance, ASCII). But the statement G is exactly like saying "this statement is blue" after selecting a blue font. It artificially mixes two unrelated contexts through (admittedly clever) manipulation of symbols.

But even at a simpler level, the whole business of G proving mathematics incomplete is outrageous. Logicians (like Hoffstader) act as if he had proved Fermat's Conjecture unprovable, and he did no such thing. For all the amazing things Gödel did, all he did with the incompleteness theorem was prove that a sufficiently complex language allows you to write "funny" sentences.

Please note that the above is a statement of opinion, not a statement of mathematics.

--faye "spock" kane
Hurkyl
#9
Sep26-09, 04:35 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
It's not clear precisely what you're thinking, but I will try and respond anyways.

Quote Quote by FayeKane View Post
Formally, TSIF is not a proposition (P(P)=F) or even a legitimate statement because the argument of the predicate P is undefined, due to infinite recursion (technically, it's "not well-defined").
TSIF is constructed in naďve logic by a bog-standard diagonal argument, no different than you might see in Cantor's argument that every set has cardinality less than that of its power set, in the proof that the halting problem is undecidable, in Russell's paradox of naďve set theory, or in the proof that Zermelo set theory doesn't have a set of all sets.

1. Define a binary "evaluation" predicate (where X is a variable ranging over unary predicates and Y is unrestricted)
D(X,Y) := X(Y)
2. Negate the diagonal
G(X) := not D(X,X)
3. Self-evaluate:
G(G) = not G(G)
4. Observe the contradiction

The structure of "usual" modern logic -- first-order and higher-order logics where predicates are only allowed to operate on formulas of lower order -- is partly (if not wholly) motivated by the need to prevent this construction. The failure is at step 3: if we chose D to be an N-th order binary predicate, then G will be N-th order, and will only be allowed to operate on predicates of lesser order. Therefore, G is not in the domain of G.

For comparison, look at Cantor's diagonal argument: Assume the existence of an injective function f : P(X) --> X. Now:

1. Define a binary "evaluation" predicate P(X):
D(S, T) := S contains f(T)
2. Negate the diagonal:
G := { f(A) in X | not D(A, A) }
3. Self-"evaluate":
G contains f(G) <-*-> not D(G, G) <--> not (G contains f(G))
(The equivalence marked with a star depends is where I use the fact f is injective)

The meaning of "evaluation" here comes from the fact that subsets of X can be viewed as unary predicates on X. From this perspective, the intuitive content of the diagonal argument is an injection P(X)-->X blurs the distinction between "object" and "relation", and allows the Liar's paradox to come into play.

To make it more clear, define the following notation:
S[T] := "f(T) is an element of S"
the note that if we have any unary predicate on P(X), the following is a well-defined way to specify another element of P(X)
S[T] := Q(T)
because it defines the set
{ f(T) | T is in P(X) and Q(T) }
Using this new notation, the diagonal argument becomes
1. Define a binary "evaluation" predicate P(X):
D(S, T) := S[T]
2. Negate the diagonal:
G[A] := not D(A,A)
3. Self-"evaluate":
G[G] = not G[G]
FayeKane
#10
Sep26-09, 08:54 AM
FayeKane's Avatar
P: 32
>It's not clear precisely what you're thinking,

I'm thinking that Gödel's theorem (the one necessitating incompleteness), while very interesting, is merely a curiosity--and I've been thinking it for a long time.

In my opinion, it doesn't have the significance most logicians attribute to it because (to my limited knowledge) it can't be used to prove anything that's not about itself.

That is, it only shows that it's possible to construct the Gödel sentence in a certain (admittedly large) class of formal systems. Great! Interesting! But I don't see how that proves those systems incomplete in any useful way. They're only incomplete in the sense that that statements in them can have "G-like" structures. It says nothing about the completeness of a system when you don't bring G into it, and that includes all of mathematics except the incompleteness theorem.

What I'm saying is that mathematics may very well be complete, except for G. And if it is, that's a very powerful statement which will never be discovered because nobody will try to prove it since you can't prove G, and G can be constructed in a nontrivial system.

> but I will try and respond anyway

You responded to my statement that TSIF is not meaningfully representable in first-order logic, and you are right. But that was just an aside by me; my point was that, in my opinion, the incompleteness theorem doesn't really say anything useful. And you didn't address that. If you choose to do so however, I am certainly willing to become more educated. In fact, that's why I came here.

> TSIF is constructed in naďve logic

You mean first-order logic?

[Never mind, I looked it up]. I have not read the book "Naive Logic", but I assume your point is that one can construct TSIF without using statements about statements.

I have already conceded that.

> by a bog-standard diagonal argument, no different than you might see in...

Yes, yes, diagonalization is used in logic. It's just proof-by-contradiction all gussied up like a whore. (BTW, proof by contradiction is the most useful tool in my proving-stuff toolbox, though I can attest that it's deadly to try and use in real-life situations because all you end up proving is what you CAN"T do).

> For comparison, look at Cantor's diagonal argument...

Yeah, but Cantor's insight is of something useful. For example, it might be used when you need to prove that for every relation between two particular sets, the relation is not bijective. But that doesn't make Godel's proof useful---though it IS interesting, in a side-show kind of way.

> 1. Define a binary "evaluation" predicate P(X):
D(S, T) := S contains f(T)

I assumed that was a typo until I realized that the "P" key is nowhere near the "D" key. So now I need to ask how the definition of the unary function P(X) can be a binary function which references neither P (recursively) nor X. (Though I'm probably just missing something here).

> The meaning of "evaluation" here comes from the fact that subsets of X can be viewed as unary predicates on X. From this perspective, the intuitive content of the diagonal argument is an injection P(X)-->X blurs the distinction between "object" and "relation", and allows the Liar's paradox [TSIF] to come into play.

Yes, and that's just exactly what Gödel did. And I was never really comfortable with proofs that use that. The halting problem is an exception because other (useful) things can be proven equivalent to it. Precious few propositions are isomorphic to G.

> To make it more clear, define the following notation:
S[T] := "f(T) is an element of S"
the note that if we have any unary predicate on P(X), the following is a well-defined way to specify another element of P(X)
S[T] := Q(T)
because it defines the set
{ f(T) | T is in P(X) and Q(T) }
Using this new notation, the diagonal argument becomes
1. Define a binary "evaluation" predicate P(X):
D(S, T) := S[T]
2. Negate the diagonal:
G[A] := not D(A,A)
3. Self-"evaluate":
G[G] = not G[G]
[/QUOTE]

Yes, you've shown that TSIF and similar structures can be constructed by clever manipulation of symbols, allowing you to camouflage a second-order statement as a first-order one.

What you've NOT shown is how the Incompleteness Theorem is any more than a curiosity.

If you were a biologist, you'd have proved that you can generate a toad with three heads. While I'm sure the toad is the delight of small children, it's not as useful as creating an orange which can survive freezing, which is what Cantor and Turing (and even Gödel at other times) did.

--faye, who does NOT mean to insult you but probably did. Much as Vulcans find humor "a difficult concept", autistics find politeness like that.
Hurkyl
#11
Sep26-09, 10:31 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
(As a preliminary, I will agree that Gödel's incompleteness theorems are some of the most overstated or completely misunderstood theorems in mathematics)

(Just to check -- you are aware that "complete" and "incomplete" is actually a technical term with a specific definition in this context?)


The "big" application of Gödel's incompleteness theorem is purely philosophical in nature. (Some) people once had an ideal where one could explicitly write down axioms (or axiom schemes) that could both be proven consistent, and from which one could prove (or disprove, as appropriate) any mathematical proposition.

Gödel's two incompleteness theorems thoroughly killed that idea. Interest in formalization and consistency remains, of course, but they are geared towards somewhat more modest goals.


Mathematical applications of the theorems tend to be (to my knowledge) more specialized -- theorems mainly limited to the study of formal logic or to the theory of computation.

The way I've most frequently seen Gödel's incompleteness theorem used in proofs is in the same way you understand the utility of the halting problem: it exhibits number theory as a "standard" of a first-order theory that does not have a complete, recursive axiomatization. To prove this of some other theory, it suffices to show this other theory is strong enough to express number theory.

The translation to the theory of computability gets some use too -- it says, for example, that there does not exist any algorithm for solving Diophantine equations.

The actual proof of Gödel's theorem (at least the sketch I know) contains an interesting, albeit obvious in hindsight, fact: number theory is expressive enough to be able to encode text processing, and all the things you can do with that -- e.g. to reason about formal logic, or to study Turing machines by looking at their execution traces. For example, the halting problem is reducible a Diophantine equation.



When I said "naďve logic" I was using it analogously to the way "naďve set theory" is used; I don't know if it has any relationship to the book you found.


> 1. Define a binary "evaluation" predicate on P(X):
D(S, T) := S contains f(T)

I assumed that was a typo until I realized that the "P" key is nowhere near the "D" key. So now I need to ask how the definition of the unary function P(X) can be a binary function which references neither P (recursively) nor X.
Actually, that was a typo. I've fixed it above with red text. D is supposed to be a predicate with domain P(X) x P(X). (And I repeated this typo the next two times because I was using cut-and-paste. )

(edit: Wow, it's interesting to look back on these year-and-a-half-old threads long after I've forgotten about them)
FayeKane
#12
Sep26-09, 10:08 PM
FayeKane's Avatar
P: 32
Quote Quote by Hurkyl View Post
The "big" application of Gödel's incompleteness theorem is purely philosophical in nature.
I rest my case.

Quote Quote by Hurkyl View Post
Just to check -- you are aware that "complete" and "incomplete" is actually a technical term with a specific definition in this context?
Mmmm... I think it MAY have been mentioned when I took MATH447, "Completeness, Compactness, and Undecidability".

About 20 Kids were there the first day of class, and on the second day, all but four of us had dropped it. But Dr. Lopez-Escobar taught us four kids with the same infectious fire and enthusiasm as when he taught me Symbolic Logic I years earlier in a huge auditorium. He also took me aside personally outside class and introduced me to the Lambda Calculus.

To this day, I have considered MATH447 the peak of my academic life, and I have looked for him for many years, wanting to thank him.

-- faye kane, a mere padwan among Jedi
SixNein
#13
Dec25-09, 12:36 AM
PF Gold
SixNein's Avatar
P: 194
[QUOTE=Hurkyl;2366168]
The "big" application of Gödel's incompleteness theorem is purely philosophical in nature. (Some) people once had an ideal where one could explicitly write down axioms (or axiom schemes) that could both be proven consistent, and from which one could prove (or disprove, as appropriate) any mathematical proposition.
I always thought it revealed a little insight to the nature of systems.


Register to reply

Related Discussions
Godel's Theorem General Math 8
Godel's Theorem General Math 6
Godel's Theorem General Math 2
Godel's Theorem General Discussion 15
Godel's Theorem 2 General Math 6