Godel's Theorem

  • Thread starter drag
  • Start date

drag

Science Advisor
1,055
0
Greetings !

NOTICE:
O.K. first of all I'd like to say I only
had the MOST superficial look at it as
possible and I'll probably pass out
if I even see the tiniest fraction of
the math involved in the actual proof.
So, since my humble doubts that I wish
to express here are complete BS, this
thread will at least, hopefully, benefit
those of you whoos acqaintance with this
is as pathetic as mine. Enjoy the reading.

Now, to the subject, here's a couple of links :
http://www.ncsu.edu/felder-public/kenny/papers/godel.html
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/georgia.html [Broken]

My pathetic understanding :
As I see it through a partial glance
at the above explanations Godel's Theorem
is basicly a mathematical Liar's Paradox
(A liar says: I'm a liar).
Here's the G sentence (which supposedly contains
it in mathematical form) from the first link :
" G: The arithmoquine of "The arithmoquine of
a is not a valid TNT theorem-number" is not
a valid TNT theorem-number. "

What's unclear to me ?

Well, the following: What is a liar in math ?
How can you use "a" in math if it's not valid ?

I understand you can say 1 does not equal 2.
But, how can you use it for a more constructive
argument ? You're turning a contradiction into
a part of an argument and you can't do that.
To me, it seems like using nothing in physics
to explain physical effects - you just can't do
that, it makes no sense within the system.

A statement/number/whatever in math has definite
values/value ranges - true/false, real number/
natural number/...
BUT, if it's INVALID - it's NOT an axiom.
It can NOT be used to construct an argument
WITHIN that abstract system. Can it ?

Conclusion:
So, you see my pathetic dillema here with
the certain simple solution that I'm simply
too stupid or lazy to get. Feel free to humiliate
me in public so that I may learn something.

Thanks !

Live long and prosper.
 
Last edited by a moderator:
1,596
0
Originally posted by drag
Greetings !

NOTICE:
O.K. first of all I'd like to say I only
had the MOST superficial look at it as
possible and I'll probably pass out
if I even see the tiniest fraction of
the math involved in the actual proof.
So, since my humble doubts that I wish
to express here are complete BS, this
thread will at least, hopefully, benefit
those of you whoos acqaintance with this
is as pathetic as mine. Enjoy the reading.

Now, to the subject, here's a couple of links :
http://www.ncsu.edu/felder-public/kenny/papers/godel.html
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/georgia.html [Broken]

My pathetic understanding :
As I see it through a partial glance
at the above explanations Godel's Theorem
is basicly a mathematical Liar's Paradox
(A liar says: I'm a liar).
Here's the G sentence (which supposedly contains
it in mathematical form) from the first link :
" G: The arithmoquine of "The arithmoquine of
a is not a valid TNT theorem-number" is not
a valid TNT theorem-number. "

What's unclear to me ?

Well, the following: What is a liar in math ?
How can you use "a" in math if it's not valid ?

I understand you can say 1 does not equal 2.
But, how can you use it for a more constructive
argument ? You're turning a contradiction into
a part of an argument and you can't do that.
To me, it seems like using nothing in physics
to explain physical effects - you just can't do
that, it makes no sense within the system.

A statement/number/whatever in math has definite
values/value ranges - true/false, real number/
natural number/...
BUT, if it's INVALID - it's NOT an axiom.
It can NOT be used to construct an argument
WITHIN that abstract system. Can it ?

Conclusion:
So, you see my pathetic dillema here with
the certain simple solution that I'm simply
too stupid or lazy to get. Feel free to humiliate
me in public so that I may learn something.

Thanks !

Live long and prosper.
Godels theorema states that any formal system of logic (f.i. mathematics) can not be both complete and consistent.
That is because in any formal system we can find 'statements' that can not be expressed using the logic rules of that system, but which are nevertheless true, which means the system can not be complete.
If we try to 'complete' the system though, by adding such statements, it can be shown that inconsistencies occur. As in the example fo the TNT number G, which claims that itself can not be a number within TNT. But when we add G to TNT, is is a TNT number, so that makes an inconsistency!
So this means that it is impossible to create a formal system of logic that is both complete and both consistent. Of course for that it also must be proved that there are not formal systems of logic which are stronger then TNT.
 
Last edited by a moderator:

jammieg

I don't understand it.
That's interesting that it relates to the liars paradox I was just thinking about that last week. The old question that if everything the liar says is a lie how can they say "everything I say is a lie", and this be true? Then I got a notion that this statement could be true and still be a lie. The reason is that following the reasoning of it forms a contradiction and paradox which is in itself a form of lying, so that a complete liar could make this truthfully lying statement and still be lying.
 

drag

Science Advisor
1,055
0
Re: Re: Godel's Theorem

Greetings !
Originally posted by heusdens
As in the example fo the TNT number G, which
claims that itself can not be a number
within TNT. But when we add G to TNT, is
is a TNT number, so that makes an inconsistency!
I still don't get it. If G IS a TNT number
then it is false to claim it is not. If G
is NOT a TNT number then it is equivalent to
saying 1=2 and then using this in other
operations like an axiom, despite the fact
that it clearly contradicts other axioms
of the same system. I just can't see how
you can arrive at that contradiction within
the enitial axioms of math.

Now, I'll try another approach here in my
(probably very pathetic to those who know this
stuff ) attempt to understand this subject:
I want to construct an abstract system.
So, what do I do ?
I first define some end-points or
entities/relations. In math these are
stuff like numbers, numerical operations and
much more.
Why did I also call them end-points ?
Because within the arguments of my abstract
system they are the most basic consituents
that can not be expalined. Why did I put the
entities and the relations together ?
Because entities and relations are just
matters of perspective.

Now, provided that I did all of the above
I am now facing a potential dillema:
How can I know for certain = prove that
none of the exioms contradict each other ?
And, if it is at all possible then - can
I do this within the system itself ?
Also, in general, how do I even begin to
construct such an argument and how deep
do I need to go to try and prove it (in
terms of the system's practice complexity) ?

Thanks !

Live long and prosper.
 
Last edited:
1,596
0
Re: Re: Re: Godel's Theorem

Originally posted by drag
Greetings !

I still don't get it. If G IS a TNT number
then it is false to claim it is not. If G
is NOT a TNT number then it is equivalent to
saying 1=2 and then using this in other
operations like an axiom, despite the fact
that it clearly contradicts other axioms
of the same system. I just can't see how
you can arrive at that contradiction within
the enitial axioms of math.

Now, I'll try another approach here in my
(probably very pathetic to those who know this
stuff ) attempt to understand this subject:
I want to construct an abstract system.
So, what do I do ?
I first define some end-points or
entities/relations. In math these are
stuff like numbers, numerical operations and
much more.
Why did I also call them end-points ?
Because within the arguments of my abstract
system they are the most basic consituents
that can not be expalined. Why did I put the
entities and the relations together ?
Because entities and relations are just
matters of perspective.

Now, provided that I did all of the above
I am now facing a potential dillema:
How can I know for certain = prove that
none of the exioms contradict each other ?
And, if it is at all possible then - can
I do this within the system itself ?
Also, in general, how do I even begin to
construct such an argument and how deep
do I need to go to try and prove it (in
terms of the system's practice complexity) ?

Thanks !

Live long and prosper.
The problem with the number "G" is that "G" claims about ITSELF that it is not part of TNT. If we ADD G to TNT , we have a inconsistency.
If we do NOT add G to TNT, it is shown that TNT is incomplete.
 

drag

Science Advisor
1,055
0
Re: Re: Re: Re: Godel's Theorem

Greetings heusdens !
Originally posted by heusdens
If we do NOT add G to TNT, it is shown that
TNT is incomplete.
How's that ?
Why would it be incomplete without G ?
Why would it be complete if we add something
invalid to it ? Is there even such a notion as
invalid that is possible to observe from
WITHIN the system (math) ? For example, can
I say (in the real world) that I add "nothing"
to my drink and stir it ?

Thanks !

Live long and prosper.
 
1,596
0
Re: Re: Re: Re: Re: Godel's Theorem

Originally posted by drag
Greetings heusdens !

How's that ?
Why would it be incomplete without G ?
Why would it be complete if we add something
invalid to it ? Is there even such a notion as
invalid that is possible to observe from
WITHIN the system (math) ? For example, can
I say (in the real world) that I add "nothing"
to my drink and stir it ?

Thanks !

Live long and prosper.
Your intend of this post was to clearify the theorema of Godel, right?

Well the theorema itself is a long mathematical proof of some number system TNT. You would have to work out the proof of this theorema yourself, to know all the details.

What comes up as a conclusion of the theorema, is that for any formal system, it can be proved that either the formal system is incomplete, or the formal system is inconsistent.

A nice book about Godel's theorema is the book "Godel, Escher and Bach" from Douglas Hofstaedter.

PS.
Remember that G is not just a number, but is a statement, expressed in formal notation of TNT, but is coded in numbers.
 
476
0
Being probably even more pathetic than you older guys and risking to get laughed out of the room, I'd add this slightly different view that helped me understand Godel intuitively.
- No theory can proove itself true without external reference.
This includes our very own logical reasoning system, it can be used, but it cannot be used to proove it itself to be valid.

How do you know theory is true? You need external referee that decides whether its true or false. How does that external referee know that its correct? For that you'd need yet another external referee, ad infinitum. If there is no external referee, you can't possibly know whether your theory is true or false.

Any theory can be traced back to fundamental assumption that cannot be proved, its incomplete.
The only way to 'proove' itself is via circular reasoning, which is inconsistent.
So, there are only 2 possibilities: either incomplete, or inconsistent.

Hopefully it wasn't way off topic.
 

drag

Science Advisor
1,055
0
Greetings !

heusdens, from your response and suggestions
I see I've reached the limmits of your credible
explanation ability on this subject.
I'd like to thank you very much for your
input which got this thread "going"
and for your suggestions and hope to
see you posting more here ! :smile:
(Maybe I'll follow them, but my laziness
and more practical reasons, which are still
mostly the result of laziness , compell
me to attempt to seek an expert explanation
here first, where it's potentially a lot
easier to find it and there's interaction.)
Originally posted by wimms
Being probably even more pathetic than you
older guys and risking to get laughed out
of the room, I'd add this slightly different
view that helped me understand Godel intuitively.
- No theory can proove itself true without
external reference. This includes our very
own logical reasoning system, it can be used,
but it cannot be used to proove it itself to be valid.

How do you know theory is true? You need
external referee that decides whether its
true or false. How does that external referee
know that its correct? For that you'd need yet
another external referee, ad infinitum. If there
is no external referee, you can't possibly know
whether your theory is true or false.

Any theory can be traced back to fundamental
assumption that cannot be proved, its incomplete.
The only way to 'proove' itself is via circular
reasoning, which is inconsistent. So, there are
only 2 possibilities: either incomplete, or
inconsistent.

Hopefully it wasn't way off topic.
Nope, that was very good and I fully
agree with it. Further more, I think it
was important to mention the above
precisely due to the reason that this
may be a confusing point in terms of
its relevance to this discussion.

Basicly, I understand that Godel proves
his point WITHIN math. Now, if I were to
explain the existence of my abstract system
I created then like wimms mentioned above -
that would be impossible and I'd need an
external system (me in this case).

As I understand it so far - Godel's Theorem
is WITHIN math and it is NOT an attempt to
justify that system's premises. It is just
mathematical operations that lead to the
inconsistency. That is why I do not understand
how it is possible. If you consider some effects
of an external system - like internal axiom
justification attempts then you can't say
the system is internally inconsistent, can you ?
I mean, if I were just to USE the system's
axioms (add, multiply, devide and much more)
why should I arrive at any inconsistency ever ?
Perhaps I would, but then it seems more
reasonable to check the realtions between all
my axioms first before assuming some Universal
rule that says that any system (2 or more axioms)
is INTERNALLY inconsistent. btw, is the above
rule precisely the one that Godel's Theorem
proves ? Or is it more subjective - just math ?

In addition, the strangest thought occured
to me - can we at all explain Godel's result ?
Does it have equivalent verbal explanations ?

P.S. Again, if to the experts my stupidity at
this point appears to be infinite then I truely
ask you to forgive my ignorance and remember that
in such case my remarks should at least seem
humorous to you - and humour is very healthy. :smile:

Live long and prosper.
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
Incompleteness theorems are hands down the most subtle mathematical proofs I have ever encountered, so none of you should feel the least bit foolish for not completely understanding it!


I'm not entirely familiar with Godel's theorems; the proof I studied was based on computation theory, though the result and the idea are similar.


You're turning a contradiction into
a part of an argument and you can't do that.
Anyways, this is where you're getting confused. "Proof by contradiction" is an integral part of mathematics (unless you're a constructivist).

Formally, the relevant deduction looks like this:

P => Q
P => ~Q
-----------
~P

In words, this says:

If P implies Q is true and P implies Q is false, then P is false; basically, if the truth of P implies a contradiction, then P must not be true (and thus must be false).

Looking at it backwards might help. We know that Q is either true or false.

If Q is true, then the only way "P => ~Q" can be true is if P is false.
If Q is false, then the only way "P => Q" can be true is if P is false.

Therefore P must be false.

The usual structure of a proof using this deduction goes as:

Assume P is true.

... some work ...

Therefore Q is true.

... some work ...

Therefore Q is not true.

This is a contradiction, therefore our assumption was wrong, so P must be false.



Part of Godel's proof uses this structure. If you assume G is provable, then it's trivial to prove G is provable. However, by the construction of G, you can also prove G is not provable. Therefore the assumption must be incorrect, and G is not provable.



I don't understand it.
That's interesting that it relates to the liars paradox I was just thinking about that last week. The old question that if everything the liar says is a lie how can they say "everything I say is a lie", and this be true? Then I got a notion that this statement could be true and still be a lie. The reason is that following the reasoning of it forms a contradiction and paradox which is in itself a form of lying, so that a complete liar could make this truthfully lying statement and still be lying.
You are right, it relates very strongly to the liar's paradox, in that both rely heavily on self-reference as part of the proof.

The formal version of the liar's paradox goes like:

Define P(x) := ~x(x)
Define Q := P(P)
Assume Q is true, then P(P), therefore ~P(P).
Thus Q is false.
Therefore ~P(P), therefore P(P), therefore Q is true.

And this is an honest to goodness contradiction.

The resolution was to rewrite formal logic so that propositions are not allowed to operate on propositions. In particular, when we define P(x), x cannot be a proposition, so we cannot write x(x).

The trick to Godel's proof is that he finds an indirect way to write propositions about propositions, by encoding propositions into numbers, with which propositions are allowed to operate. Fortunately, one cannot encode "true" and "false" into TNT, otherwise we'd have the Liar's paradox all over again.

so...


I still don't get it. If G IS a TNT number
then it is false to claim it is not. If G
is NOT a TNT number then it is equivalent to
saying 1=2
You're incorrectly applying what "TNT number" means.

Something is a "TNT number" if and only if it can be deduced from the axioms.

Assume G is a TNT number, then G is deducible from the axioms, and thus G must be true. However, that implies G is not a TNT number, which is a contradiction, therefore our assumption is incorrect and G must not be a TNT number.

Now, if G is not a TNT number, G is true, but G is not deducible from the axioms. That is not the same thing as saying G is false!.

In fact, if you assume "P is not deducible from the axioms" to be equivalent to "P is false", you derive a contradiction (as you eloquently put as saying G is equivalent to 1=2). However, that is still an assumption, and because it leads to a contradiction we've proven it false.

Godel's theorem says that for any sufficiently powerful (consistent) theory, there exists a true statement that is not provable.


How can I know for certain = prove that
none of the exioms contradict each other ?
- No theory can proove itself true without external reference.
That's an independant question, and my thoughts on this subject would be beyond the scope of this thread. (I've always wanted to say that! )


Why would it be incomplete without G ?
The definition of a "complete" theory is that all true statements are provable. Because G is a true statement in TNT, but isn't provable from the axioms, TNT must be incomplete.


So, there are only 2 possibilities: either incomplete, or inconsistent.
Incorrect. If a theory is not powerful enough to encode the pseudostatement "This statement is not provable", then Godel's proof cannot work.

For a concrete example, Euclidean geometry is a complete theory. Euclidean geometry even satisfies a stronger requirement; within Euclidean geometry not only are all true statements provable, but all statements are either true or false. I can't remember the technical term for this (other than decidibility, but that's not the one of which I'm trying to think), can anyone help me out with that?


I mean, if I were just to USE the system's
axioms (add, multiply, devide and much more)
why should I arrive at any inconsistency ever ?
In traditional formal logic, "Inconsistent" simply means that there exists a statement P such that P is provable and ~P is provable. It's certainly possible to choose a set of axioms where this is possible. E.G.

(1) All the axioms of arithmetic
(2) 1 = 2

The axioms of arithmetic allow us to prove (1 = 2) is false, while the next axiom allows us to prove (1 = 2) is true, thus this system is internally inconsistent.


In addition, the strangest thought occured
to me - can we at all explain Godel's result ?
Does it have equivalent verbal explanations ?
Do you mean something like

"There exists a true statement that can't be proven"

or something else?
 

drag

Science Advisor
1,055
0
Thanks Hurkyl ! :smile:

But wait ! So, you're saying that Godel's
theorem is only applicable to some advanced
fields of relativly modern mathematics ?
Could it also be the result of these fields
being incomplete ?
Originally posted by Hurkyl
You're incorrectly applying what "TNT number" means.

Something is a "TNT number" if and only if it
can be deduced from the axioms.

Assume G is a TNT number, then G is deducible
from the axioms, and thus G must be true. However,
that implies G is not a TNT number, which is
a contradiction, therefore our assumption is
incorrect and G must not be a TNT number.

Now, if G is not a TNT number, G is true,
but G is not deducible from the axioms.
That is not the same thing as saying G is false!.
I see why what I said about 1=2 is inapplicable
here. Indeed it is often used in proof by contradiction.

I'm sorry but I did not follow you from the
"however" sentence, what'd'ya mean by "that implies" ?

Thanks again !

Live long and prosper.
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
But wait ! So, you're saying that Godel's
theorem is only applicable to some advanced
fields of relativly modern mathematics ?
Could it also be the result of these fields
being incomplete ?
Going by the proof in my computability theory text, a theory only has to be powerful enough to make propositions about the natural numbers involving addition and multiplication.

Examples of theories not powerful enough are Euclidean geometry, and the natural numbers with addition alone.


I'm sorry but I did not follow you from the
"however" sentence, what'd'ya mean by "that implies" ?
Because G effectively says "I'm not deducible from the axioms", if G is true then it's not deducible from the axioms.
 

drag

Science Advisor
1,055
0
Originally posted by Hurkyl
Because G effectively says "I'm not
deducible from the axioms", if G is
true then it's not deducible from
the axioms.
Well, can't you just check G ?
I mean, if it's right then the TNT
is wrong. Also, if the TNT required
that G be deduced then G without deduction
is not a valid input thingy, is it ?
(I still don't get it... )

Thanks either way ! :smile:

Live long and prosper.
 

ahrkron

Staff Emeritus
Gold Member
735
1
Originally posted by drag
Well, can't you just check G ?
I mean, if it's right then the TNT
is wrong.
I think you are getting confused because you haven't disentangled a couple of concepts.

When you have an axiomatic system (i.e., basic statements plus some rules to get new statements), there are two features of it that are of interest:

1. Its consistency, and
2. Its completeness.

The first one means that you cannot obtain contradictory statements by correctly following the rules.

Regarding the second, a system is said to be complete if all truths that can be represented on it can be obtained using its axioms and rules.

Let me put it this way.

Imagine a chess board. The initial positions of the pieces are the "axioms", and the rules of the game are the "logic rules".

From there, you can reach ("proof") many positions (i.e., you can obtain them by allowed moves from the initial positions in the board), but there are also many positions you can imagine with the pieces that cannot be achieved using the rules (a simple example is having all bishops in white squares).

These positions are the equivalent of the proposition G. The system can represent the proposition, but it cannot be proven using the system's rules.

Going back to your questions:
Originally posted by drag
Well, can't you just check G ?
It may be possible to check G, but that is not the issue. The point is that G, though correct, cannot be proven using the system's "rules"

I mean, if it's right then the TNT
is wrong.
You have the right idea here, just instead of "wrong", you want to say "incomplete".

Also, if the TNT required that G be deduced then G without deduction is not a valid input thingy, is it ? (I still don't get it... )
TNT does not "require" G to be deduced. TNT allows many deductions, and G is one of the true propositions that can be written in TNT, but that cannot be proven by it.

I hope that helps.
 

drag

Science Advisor
1,055
0
Greetings !

Thanks ahrkron !

I think I'm starting to get this now.
Your chess example with the bishops
really helped a lot ! So now I see
why I can not obtain a truth value
for such a statement too - and hence
the inconsistency ! :smile:

I have a follow-up question then:
Are there generally understood and
defined rules to indicate when a system
is or is not sufficiently complex ?
I mean, rules that do not only apply
to mathematical theories but to any
axiomatic system ?

Thanks !

Live long and prosper.
 

drag

Science Advisor
1,055
0
Oops... Sorry about that, in retrospective I saw
that ahrkron already posted this just above
the example which cleared it up for me. It's
just that I didn't get it before that.
Thanks again ! :smile:
 

Related Threads for: Godel's Theorem

  • Posted
2
Replies
30
Views
7K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
6
Views
3K
Replies
26
Views
10K
Replies
36
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top