Godel’s Incompleteness theorem vs determinism
Posted: 28 March 2008 11:43 PM   [ Ignore ]
Sr. Member
Avatar
RankRankRankRankRankRankRankRankRankRank
Total Posts:  573
Joined  2007-08-21

Can somebody explain to me what Godel’s Incompleteness theorem means in plain English? Also, what implications does it have on determinism?

 Signature 

Vi veri veniversum vivus vici

Profile
 
 
Posted: 29 March 2008 08:50 AM   [ Ignore ]   [ # 1 ]
Administrator
Avatar
RankRankRankRankRankRankRankRankRankRank
Total Posts:  15354
Joined  2006-02-14

It means that in any consistent logical system there will be certain truths of that system that are not formalizable from within the system itself. Or something like that; it’s been several years.

For more about it, check the wiki page; unfortunately the formatting doesn’t come across for a link, but you can get at it through Kurt Gödel’s page HERE.

No idea what that has to do with determinism, and I’m somewhat skeptical that it does.

 Signature 

Doug

-:- -:—:- -:—:- -:—:- -:—:- -:—:-

El sueño de la razón produce monstruos

Profile
 
 
Posted: 29 March 2008 09:03 AM   [ Ignore ]   [ # 2 ]
Sr. Member
Avatar
RankRankRankRankRankRankRankRankRankRank
Total Posts:  573
Joined  2007-08-21
dougsmith - 29 March 2008 08:50 AM

It means that in any consistent logical system there will be certain truths of that system that are not formalizable from within the system itself. Or something like that; it’s been several years.

For more about it, check the wiki page; unfortunately the formatting doesn’t come across for a link, but you can get at it through Kurt Gödel’s page HERE.

No idea what that has to do with determinism, and I’m somewhat skeptical that it does.

thanks, I have been researching it ever since it was been brought up as an argument against determinism. With further research, if found it often being brought up as an opponent of determinism. But I am not seeing the relationship and I am curious if people are improperly understanding it and using it in this sense.

 Signature 

Vi veri veniversum vivus vici

Profile
 
 
Posted: 29 March 2008 09:19 AM   [ Ignore ]   [ # 3 ]
Member
RankRankRankRankRankRank
Total Posts:  142
Joined  2007-06-17

There are two things that Godel proved that brought into everyday language mean something entirely different from what they do in technical language.

The first is that an axiomatic system (like arithmetic, or Euclidean geometry) will produce contradictions; that is, no matter how logical you are, you will end up contradicting yourself.

The second is that you will be able to formulate true statements that you will not be able to prove are true within the system.

It could relate to determinism in that free will could be posited as such an unprovable truth, within some posited system of logic.  Alternately, you could say that the apparent contradiction between determinism and free will is a contradiction produced by a perfectly logical system.

Either one is a stretch, because Godel was working with a pretty specific kind of system, or set of systems, and the proofs do not translate very well to looser systems, or some conception of “reason” that is not really a system at all.  His proofs were revolutionary, but their application is not as wide as some people makes it out to be.

Profile
 
 
Posted: 29 March 2008 09:27 AM   [ Ignore ]   [ # 4 ]
Sr. Member
Avatar
RankRankRankRankRankRankRankRankRankRank
Total Posts:  573
Joined  2007-08-21
rsonin - 29 March 2008 09:19 AM

There are two things that Godel proved that brought into everyday language mean something entirely different from what they do in technical language.

The first is that an axiomatic system (like arithmetic, or Euclidean geometry) will produce contradictions; that is, no matter how logical you are, you will end up contradicting yourself.

The second is that you will be able to formulate true statements that you will not be able to prove are true within the system.

It could relate to determinism in that free will could be posited as such an unprovable truth, within some posited system of logic.  Alternately, you could say that the apparent contradiction between determinism and free will is a contradiction produced by a perfectly logical system.

Either one is a stretch, because Godel was working with a pretty specific kind of system, or set of systems, and the proofs do not translate very well to looser systems, or some conception of “reason” that is not really a system at all.  His proofs were revolutionary, but their application is not as wide as some people makes it out to be.

aha, thank you rsonin.

 Signature 

Vi veri veniversum vivus vici

Profile
 
 
Posted: 29 March 2008 01:32 PM   [ Ignore ]   [ # 5 ]
Administrator
Avatar
RankRankRankRankRankRankRankRankRankRank
Total Posts:  15354
Joined  2006-02-14
rsonin - 29 March 2008 09:19 AM

The first is that an axiomatic system (like arithmetic, or Euclidean geometry) will produce contradictions; that is, no matter how logical you are, you will end up contradicting yourself.

Please explain what you mean by this. Gödel’s theorems are explicitly over consistent systems, that is, those that do not produce contradictions. An axiomatic system that produces a contradiction is useless. Gödel’s theorem only implies that the system itself cannot assert its own completeness; that is, it cannot assert that it is without contradiction. But that is quite different from asserting a contradiction!

 Signature 

Doug

-:- -:—:- -:—:- -:—:- -:—:- -:—:-

El sueño de la razón produce monstruos

Profile
 
 
Posted: 30 March 2008 01:17 AM   [ Ignore ]   [ # 6 ]
Member
RankRankRankRankRankRank
Total Posts:  142
Joined  2007-06-17

Yeah - I wasn’t precise.  The contradictions are not within the system itself, but between the system and some meta-system.  I’m remembering from notes, but as I recall Godel constructed a formula that was not formally demonstrable within an arithmetical system which was demonstrably demonstrable (!?) outside the system.  Something like “every integer possesses such-and-such an arithmetical property”, which every integer can be tested for, but which the arithmetic cannot prove.  That is, you can come up with formulas that the arithmetic says are not demonstrable, but which are demonstrable outside the arithmetic (which, as far as the arithmetic goes, means nothing, because it involves a statement/formula the arithmetic can’t even contemplate).

If you take a consistent arithmetic on its own terms, it can be consistent, but as soon as you consider it from outside, you will see that the “truths” it comes up with are contingent on remaining within that system, and that some of its truths can be false when considered outside of the system (or without the proviso of “within this system, this formula is true).  But Godel wasn’t talking about that - other people do, and tend to vastly overstate what he came up with (like I did).

I believe he also showed that you cannot use an arithmetic to prove its own consistency.  You need to go outside the system to prove it, but then you will end up using another system which cannot prove its own consistency, and so on (I don’t think he got into that, though).  While that is not a contradiction, it opens up the logical possibility that there are contradictions (because you cannot demonstrate the opposite).  But that is not the same as saying that there are in fact contradictions.

I find that I understand it well enough when immersed in it, but that it is very, very difficult to say in plain language because it is very subtle.

Profile
 
 
Posted: 20 June 2008 06:31 PM   [ Ignore ]   [ # 7 ]
Jr. Member
Rank
Total Posts:  1
Joined  2008-06-20

The accounts in this thread, including the corrections and followups to them, of the incompleteness theorems are terribly errant.

The best book for the layman about the incompleteness theorems is ‘Godel’s Theorem: An Incomplete Guide To Its Use And Abuse’ by Torkel Franzen. It is simply, lucidly, and beautifully written by an expert on the subject.

For a book that is more technical but still fairly informal, see ‘An Introduction To Godel’s Theorems’ by Peter Smith. This recently published book is wonderful for its plain spoken development of different approaches to the theorems and of many of the immediately related subjects. However, in my opinion, the book is best read after one has acquired at least some background in beginning symbolic logic.

For an actual textbook on the subject, one of the best and most referrenced is ‘A Mathematical Introduction To Logic’ by Herbert Enderton, which I highly recommend for its clarity and rigor, though I feel that one should first have a good working knowledge of symbolic logic and of basic axiomatic set theory.

Profile
 
 
Posted: 11 July 2008 07:57 AM   [ Ignore ]   [ # 8 ]
Sr. Member
Avatar
RankRankRankRankRankRankRankRankRankRank
Total Posts:  573
Joined  2007-08-21
ZermellowFrankhello - 20 June 2008 06:31 PM

The accounts in this thread, including the corrections and followups to them, of the incompleteness theorems are terribly errant.

The best book for the layman about the incompleteness theorems is ‘Godel’s Theorem: An Incomplete Guide To Its Use And Abuse’ by Torkel Franzen. It is simply, lucidly, and beautifully written by an expert on the subject.

For a book that is more technical but still fairly informal, see ‘An Introduction To Godel’s Theorems’ by Peter Smith. This recently published book is wonderful for its plain spoken development of different approaches to the theorems and of many of the immediately related subjects. However, in my opinion, the book is best read after one has acquired at least some background in beginning symbolic logic.

For an actual textbook on the subject, one of the best and most referrenced is ‘A Mathematical Introduction To Logic’ by Herbert Enderton, which I highly recommend for its clarity and rigor, though I feel that one should first have a good working knowledge of symbolic logic and of basic axiomatic set theory.

Thanks ZermellowFrankhello.

 Signature 

Vi veri veniversum vivus vici

Profile