# Is Godel's incompletness theorem complete?

by yuiop
Tags: godel, incompletness, theorem
 Emeritus Sci Advisor PF Gold P: 16,091 Are you familiar with the halting problem?
P: 3,967
 Quote by Hurkyl 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.

 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.
 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.
 Emeritus Sci Advisor PF Gold 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.
 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.
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
Emeritus
PF Gold
P: 16,091
It's not clear precisely what you're thinking, but I will try and respond anyways.

 Quote by FayeKane 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)

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]
Emeritus
PF Gold
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)
P: 32
 Quote by Hurkyl The "big" application of Gödel's incompleteness theorem is purely philosophical in nature.
I rest my case.

 Quote by Hurkyl 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
PF Gold
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.

 Related Discussions General Math 8 General Math 6 General Math 2 General Discussion 15 General Math 6