8 ms·

Gödel's Incompleteness Theorem explained

111 points by simonbrown 15y ago

petercooper 15y ago
The BBC had a 45 minute radio panel with Marcus du Sautoy and some other mathematicians going through Godel's theorems: http://www.bbc.co.uk/programmes/b00dshx3 http://www.bbc.co.uk/programmes/b00dshx3 (I believe people outside of the UK can listen to it.. if not, sorry! For some reason the 'listen' image does not appear for me, but is to the left of '(45 minutes)'). (And if you like it, the whole set of math and science episode of In Our Time are similarly excellent.)
lotharbot 15y ago
It should be noted that Godel gave two Incompleteness Theorems. The first says that, in a system based on a list of axioms, there will always be some statements that aren't provable. (Remember Mr. Spock confusing a computer by telling it "I am lying"? "This statement can't be proved" behaves the same way -- it's true, but you can't prove it, because if you did then you couldn't prove it.) In other words, there is always truth the system can't account for. The second theorem builds on the first. It says a system can't prove itself consistent, and that if a system includes the claim "this system is consistent" then it is necessarily inconsistent. (In essence, you can construct a more complex version of the "I am lying" statement in any system that includes a claim of "I am telling the truth".) In other words, the only way to prove something consistent is from outside of it.
- dmfdmf 15y ago
  > "This statement can't be proved" This statement (and Godel's mathematical equivalent) does not assert anything to be proved, it is contentless, which is why logical, axiomatic systems choke on it, essentially due to recursion or self-reference. Logically there are only two fundamental ways to err; by contradiction and by circular reasoning. > In other words, the only way to prove something consistent is from outside of it. This is what I take from Godel's theorems but this is a poor formulation of the idea. A better way to say it is that proof presupposes consistency and more specifically the law of identity which is a metaphysical law that has to be validated not proved (since proof depends on it).
  - gburt 15y ago
    A "strange loop", perhaps.
- vgm 15y ago
  Interestingly, Godel gave a presentation somewhere within 5 - 7th September at Koningsberg presenting the first incompleteness theorem. At this time, he did not have the second. [1] Von Neumann was in attendance and he wrote a letter to Godel on November 20th announcing his discovery of the second incompleteness theorem. As it turns out, Godel had just sent a paper for publication on November 17th with the proof of the second incompleteness theorem. In reply to Godel, finding out he had just been scooped, von Neumann wrote: "As you have established the theorem on the unprovability of consistency as a natural continuation and deepening of your earlier results, I clearly won't publish on this subject." [2] [1] http://goo.gl/uJH9Q http://goo.gl/uJH9Q [2] http://goo.gl/AXfQV http://goo.gl/AXfQV (Links are very long, hence the shortner. They take you to Google Books.)
mappu 15y ago
By using a UTM as a metaphor for the axioms themselves, the UTM must run itself, essentially describing an infinite loop over the finite program, which is another point to consider; with any axiomatic system, is it possible to describe a UTM which you can guarantee halts in finite time? Probably not necessarily. It seems to be a solid notion that if a paradox can be constructed, then the space is unverifiable, but in this case it feels like the paradox results only from a poorly specified question (the correct answer exists, and is an acknowledgement that the input is meaningless). The important part to take away is that Gödel himself exists in a logical space where he is able to understand and deal with the absurdity of his paradox, which is outside the scope of the UTM. Every logical system containing a paradox, is a subset of a logical system wherein the absurdity of the paradox is understood. So, perhaps a logical system which explicitly recognises paradoxes as absurd, can be complete. Like NaN in IEEE754, or int|null in dynamic languages. The result clearly only applies to logical spaces where the paradox is translatable, so i'd be interested to see if a version exists for only basic arithmetic. A similarly interesting related discussion is the total, abject, and infinite unavailability of a "quadratic formula" for polynomials in x^5 or greater.
- kmm 15y ago
  > the UTM must run itself, essentially describing an infinite loop over the finite program, Exactly. I came up with this counterargument not so long ago. It's why neither Gödel's theorems nor the Halting problem ever really impressed me. I don't doubt their validity but the conclusion that no system can be complete is only true for very stringent definitions of "complete". I still believe the Halting problem can be solved in some sense of the word solve. But perhaps I'm being too pragmatic. > So, perhaps a logical system which explicitly recognises paradoxes as absurd, can be complete. Gödel explicitly counters this with his second incompleteness theorem which says that no consistent system can provide a proof of its own consistency. In other (but equivalent) words, I might be confident that my mind works correctly but there's technically no way to be completely sure. In fact if I were sure of it, my mind wouldn't be working fine.
  - keeperofdakeys 15y ago
    > I still believe the Halting problem can be solved in some sense of the word solve. But perhaps I'm being too pragmatic. While its true there are some forms of functions that can be found to either halt or not, some can't. For example, ask the user for a boolean, and do a while loop based on this value. You can't say whether this will halt or not, but it does contain unspecified variables. Then consider the Collatz Conjecture. We can't prove any other number then 1 actually reaches 1 without simulating the process. Since we don't even know if the next step will reach the destination, we can't make any decision about when it will halt. If we can't even decide it for such a simple function, then I don't think we can 'solve' it, even for a general 'solve'.
buu700 15y ago
Relevant: http://www.reddit.com/r/explainlikeimfive/comments/j8yq3/can_anyone_eli5_or_12_the_implications_of_g%C3%B6dels/c2a5pp4 http://www.reddit.com/r/explainlikeimfive/comments/j8yq3/can...
deleted 15y ago
[deleted]
icandoitbetter 15y ago
Its relevance in philosophy/epistemology/science/computing has been inflated out of proportion by the confused arguments of Hofstadter, Penrose, etc. Just because it's difficult to understand doesn't mean that it will tell you the meaning of life. Of course it's a mathematical theorem of profound importance, but it has absolutely nothing to do with the limits of rational thought.
- brudgers 15y ago
  Well...I think about Godel's theorem as the mathematical implementation of Kant's ideas about the limits of reason based upon human experience, i.e. there are some truths which are inaccessible because time and space are preconditions of all human experience. Not to dwell on arguments about whether or not time and space actually exist independently of human experience, what Kant was getting at is that the way in which humans experience the world limits our ability to draw conclusions to a particular subset of all truths. If Godel's theorem is true, then from a Kantian perspective, mathematics no longer enjoys a uniquely privileged place in regards to human rationality. That's pretty important philosophically - at least to some people. Positivists may take a different view.
  - icandoitbetter 15y ago
    Godel doesn't talk about space, time, human experience, truths that exist independently of human experience. I fail to see how he's relevant.
    - shmerl 15y ago
      He does. Learn more about his biography and his interest in mysticism and philosophy: http://www.amazon.com/G%C3%B6del-Logic-John-L-Casti/dp/0738205184 http://www.amazon.com/G%C3%B6del-Logic-John-L-Casti/dp/07382...
      - rcthompson 15y ago
        Perhaps he does, but I don't think he does so in the proofs of his incompleteness theorems.
ropz 15y ago
The referenced page doesn't deliver on the hype of the HN headline, it merely offers: "... some selections that will help you start to understand it."""
flurie 15y ago
The greatest explanation I've ever seen for the Incompleteness Theorems comes from Palle Yourgrau in his book A World Without Time. He gives an excellent introduction to his explanation: "To appreciate Godel's theorem is your birthright; let no one, including the mathematical police, deprive you of what you have a right to enjoy."
- derleth 15y ago
  Who in the world are the 'mathematical police'?
  - keithpeter 15y ago
    A rhetorical and shadowy group who discourage ordinary people from reading about or becoming interested in mathematics. A lot of popular science authors invoke this underground organisation, so it must exist.
rcthompson 15y ago
Think of it kind of like the Sieve of Eratosthenes, but for provability instead of primeness. You start with one axiom and prove everything you can based on that. Then you pick one of the statements you couldn't prove and add it as a second axiom (thereby expanding your axiomatic system), then prove everything that you can with those two axioms. The pick another unproven statement as your third axiom and repeat. Godel's incompleteness theorem is equivalent to saying that you will never run out of axioms, and that you will be able to continue this process indefinitely (just like there are an infinite number of primes). It's not an exact comparison, but it gives you the idea.
- bjornsing 15y ago
  An interesting comparison. Just one important difference though if I understand correctly: In Gödel's world you will sooner or later ruin your axiomatic system by adding an axiom that is inconsistent with one or several of your earlier axioms. There's no way to know (from within the system) when that happens, except perhaps that it gets a whole lot easier to prove weird stuff. :)
  - rcthompson 15y ago
    I guess I should have said that you pick as your new axiom a statement that you couldn't prove and also couldn't disprove. Though I'm not sure if even that is the same as logical independence, which is what you really want.
- xyzzyz 15y ago
  I think your comparison misses an important point. If you pick in every step a sentence that is non-provable from your current axioms, but not contradictory with them either, after infinitely many steps[1] you will have picked all of them, and get a system called True Arithmetic, in which every true sentence is provable, essentially by definition. The reason why Goedel's incompleteness theorem does not work here is that your set of axioms is not recursively enumerable, and this is a necessary assumption of GIT. [1] - If "after infinitely many steps" sounds fishy to anyone, please keep in mind that you start with an infinite list of axioms anyway -- first order Peano arithmetic theory has an induction axiom schema Ind that basically says that for every sentence f, Ind(f) (the sentence you get by substituting every occurrence of a single free variable in Ind with f) is an axiom of PA.
cop359 15y ago
Seems like a silly paradox. Why is it important? Also it seems very similar to this famous paradox: (from 600BC btw.) http://en.wikipedia.org/wiki/Epimenides_paradox http://en.wikipedia.org/wiki/Epimenides_paradox
- rcthompson 15y ago
  Constructing the paradox is just the means of proving the theorem. The paradox itself is not particularly important. Also, the paradox in Godel's theorem is "This statement is unprovable" not "This statement is false".
hammock 15y ago
Gödel showed that provability is a weaker notion than truth This, to me, is a great summation and one of the most important conclusions we can draw. When you reflect on it it's easy to see how Godel's theorems reach beyond computer science and into philosophy, ethics and religion.
- erichocean 15y ago
  Not that easy, because it only applies to truths represented in a system of symbols. Very abstract stuff, and in fact, trivial to overcome – use two sets of symbols. The theorem was important at the time because it ended one pursuit (one single-level system to rule them all), but its actual impact on anything of importance in the wider world of, well, anything, is vastly overrated.
- rcthompson 15y ago
  I believe you would need to establish some sort of equivalence between arithmetic on the set of natural numbers and philosophy, ethics, and religion in order to apply Godel's incompleteness theorem to any of them, since Godel's theorem applies to sets of axioms used to prove things about the natural numbers.
tumes 15y ago
While it might not be the most technically accurate, the ways in which David Foster Wallace touches on Gödel in Everything and More are worth a look for interested parties.
bjornsing 15y ago
I of course have no proof, but I sometimes get a feeling that Gödel does have something to do with the limits of rational thought. To me it seems humans have found a way to cope with Gödel's incompleteness: we accept that some of our axiomatic systems are inconsistent and adapt by simply discounting the value of proofs. It's difficult to explain, but let me give an example. Among engineers you can often reason along very long logical chains and have your conclusions accepted. Among (some) business people you can't. They seem to refuse the validity of logic itself, being nervous about trusting logical conclusions. I think that's because they know their axiomatic systems are self-inconsistent. :) By observing business people I have come to the conclusion that the best you can do in an a self-inconsistent axiomatic system is to look for "nuggets of truth" and never wonder too far from them. You can hear people say stuff like "limiting tweets to 140 characters will brings out creativity - people are less afraid to create when they are constrained" and similar. If you accept that as truth then you can wonder a short short distance from it and reason about business opportunities, but you can't combine that nugget with some other nugget and be sure to come to a correct conclusion. Perhaps it is so, that the likelihood of "proving" an untrue statement in a self-inconsistent system increases with the number of axioms you are basing your proof on. That's perhaps why many people are very skeptical of "proofs" that seam to involve a lot of axioms? :)
- mjw 15y ago
  Surely a simpler explanation for that is that business people don't usually work with crisp, binary data. Instead they're (implicitly) doing some kind of statistical inference on noisy data. Propositional logic might be an acceptable approximation to this kind of inference in certain narrow situations, but the approximation breaks down quicker when the chain of inference gets longer.
  - bjornsing 15y ago
    That could certainly be a simpler (and therefore better) explanation. :) When your "axioms" are fuzzy so to speak, and not real axioms, it's of course dangerous to draw conclusions from several of them (because the risk of one of them being false increases exponentially). But I still have a feeling there's something there... :) For example, I remember reading here on hacker news about this CS professor who had found a way to predict performance in entry level programing courses: http://www.eis.mdx.ac.uk/research/PhDArea/saeed/ http://www.eis.mdx.ac.uk/research/PhDArea/saeed/. Basically, they just tested their students ability to form a self-consistent model of how programming works. If they could they did well in the course. If they couldn't they did poorly, and it was very difficult to help them. That experiment leads me to believe that about 50% of the population is in the habit of constructing self-inconsistent systems of hypothesis (provisional axioms you could say). :) If that's true I'm not sure yours is a simpler explanation... ;)
batista 15y ago
With regards to the "Rucker, Infinity and the Mind" except that says: >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: (...) Actually, Godel's theorem is not that simple at all. It involves lots of hard math. And it's not about some hazy "Universal Truth Machine", it's about a specified axiomatic mathematical system with certain specific properties. The "simple" thing that RI&TM describes is a variation of the Liar's paradox. Which is somewhat like what Godel used, but he did not use it in a simplistic way, not at that level of coarseness, and surely not "embarrassingly simple to relate".
powertower 15y ago
> The implication is that all logical system of any complexity are, by definition, incomplete; each of them contains, at any given time, more true statements than it can possibly prove according to its own defining set of rules. Here is an even simpler explanation: A description of a thing is not the thing itself, it's just a description that allows you to: interact with that thing and place that thing into a framework. And an even more accurate description of a thing is still not the thing itself, it's just a more accurate description. Add more layers, and you still have just a description, and never the thing itself. It's like an onion, and each layer gets more distant from the core. Then those layers begin to interact with other descriptions of other things. So more layers are added to explain those interactions. It goes on and on until you've simulated the universe. The problem is it's exponential, and even if it was not, you're still just stuck with just a description, and not the thing itself. Some people will claim otherwise here, so just ask them if a description of a thing is the same as the thing itself and go back to the start of all this.
- derrida 15y ago
  If I'm not mistaken, one way of seeing GIT is just as a reductio ad absurdum on the idea that truth is just that which is proved. Perhaps you should consider that talking about ontology clouds the water here, this explanation might have some analogical value, but isn't 'simpler'.

111 points by simonbrown 15y ago

The BBC had a 45 minute radio panel with Marcus du Sautoy and some other mathematicians going through Godel's theorems: http://www.bbc.co.uk/programmes/b00dshx3 http://www.bbc.co.uk/programmes/b00dshx3 (I believe people outside of the UK can listen to it.. if not, sorry! For some reason the 'listen' image does not appear for me, but is to the left of '(45 minutes)'). (And if you like it, the whole set of math and science episode of In Our Time are similarly excellent.)

lotharbot 15y ago

It should be noted that Godel gave two Incompleteness Theorems. The first says that, in a system based on a list of axioms, there will always be some statements that aren't provable. (Remember Mr. Spock confusing a computer by telling it "I am lying"? "This statement can't be proved" behaves the same way -- it's true, but you can't prove it, because if you did then you couldn't prove it.) In other words, there is always truth the system can't account for. The second theorem builds on the first. It says a system can't prove itself consistent, and that if a system includes the claim "this system is consistent" then it is necessarily inconsistent. (In essence, you can construct a more complex version of the "I am lying" statement in any system that includes a claim of "I am telling the truth".) In other words, the only way to prove something consistent is from outside of it.

dmfdmf 15y ago
> "This statement can't be proved" This statement (and Godel's mathematical equivalent) does not assert anything to be proved, it is contentless, which is why logical, axiomatic systems choke on it, essentially due to recursion or self-reference. Logically there are only two fundamental ways to err; by contradiction and by circular reasoning. > In other words, the only way to prove something consistent is from outside of it. This is what I take from Godel's theorems but this is a poor formulation of the idea. A better way to say it is that proof presupposes consistency and more specifically the law of identity which is a metaphysical law that has to be validated not proved (since proof depends on it).
- gburt 15y ago
  A "strange loop", perhaps.
vgm 15y ago
Interestingly, Godel gave a presentation somewhere within 5 - 7th September at Koningsberg presenting the first incompleteness theorem. At this time, he did not have the second. [1] Von Neumann was in attendance and he wrote a letter to Godel on November 20th announcing his discovery of the second incompleteness theorem. As it turns out, Godel had just sent a paper for publication on November 17th with the proof of the second incompleteness theorem. In reply to Godel, finding out he had just been scooped, von Neumann wrote: "As you have established the theorem on the unprovability of consistency as a natural continuation and deepening of your earlier results, I clearly won't publish on this subject." [2] [1] http://goo.gl/uJH9Q http://goo.gl/uJH9Q [2] http://goo.gl/AXfQV http://goo.gl/AXfQV (Links are very long, hence the shortner. They take you to Google Books.)

mappu 15y ago

By using a UTM as a metaphor for the axioms themselves, the UTM must run itself, essentially describing an infinite loop over the finite program, which is another point to consider; with any axiomatic system, is it possible to describe a UTM which you can guarantee halts in finite time? Probably not necessarily. It seems to be a solid notion that if a paradox can be constructed, then the space is unverifiable, but in this case it feels like the paradox results only from a poorly specified question (the correct answer exists, and is an acknowledgement that the input is meaningless). The important part to take away is that Gödel himself exists in a logical space where he is able to understand and deal with the absurdity of his paradox, which is outside the scope of the UTM. Every logical system containing a paradox, is a subset of a logical system wherein the absurdity of the paradox is understood. So, perhaps a logical system which explicitly recognises paradoxes as absurd, can be complete. Like NaN in IEEE754, or int|null in dynamic languages. The result clearly only applies to logical spaces where the paradox is translatable, so i'd be interested to see if a version exists for only basic arithmetic. A similarly interesting related discussion is the total, abject, and infinite unavailability of a "quadratic formula" for polynomials in x^5 or greater.

kmm 15y ago
> the UTM must run itself, essentially describing an infinite loop over the finite program, Exactly. I came up with this counterargument not so long ago. It's why neither Gödel's theorems nor the Halting problem ever really impressed me. I don't doubt their validity but the conclusion that no system can be complete is only true for very stringent definitions of "complete". I still believe the Halting problem can be solved in some sense of the word solve. But perhaps I'm being too pragmatic. > So, perhaps a logical system which explicitly recognises paradoxes as absurd, can be complete. Gödel explicitly counters this with his second incompleteness theorem which says that no consistent system can provide a proof of its own consistency. In other (but equivalent) words, I might be confident that my mind works correctly but there's technically no way to be completely sure. In fact if I were sure of it, my mind wouldn't be working fine.
- keeperofdakeys 15y ago
  > I still believe the Halting problem can be solved in some sense of the word solve. But perhaps I'm being too pragmatic. While its true there are some forms of functions that can be found to either halt or not, some can't. For example, ask the user for a boolean, and do a while loop based on this value. You can't say whether this will halt or not, but it does contain unspecified variables. Then consider the Collatz Conjecture. We can't prove any other number then 1 actually reaches 1 without simulating the process. Since we don't even know if the next step will reach the destination, we can't make any decision about when it will halt. If we can't even decide it for such a simple function, then I don't think we can 'solve' it, even for a general 'solve'.

buu700 15y ago

Relevant: http://www.reddit.com/r/explainlikeimfive/comments/j8yq3/can_anyone_eli5_or_12_the_implications_of_g%C3%B6dels/c2a5pp4 http://www.reddit.com/r/explainlikeimfive/comments/j8yq3/can...

deleted 15y ago

[deleted]

icandoitbetter 15y ago

Its relevance in philosophy/epistemology/science/computing has been inflated out of proportion by the confused arguments of Hofstadter, Penrose, etc. Just because it's difficult to understand doesn't mean that it will tell you the meaning of life. Of course it's a mathematical theorem of profound importance, but it has absolutely nothing to do with the limits of rational thought.

brudgers 15y ago
Well...I think about Godel's theorem as the mathematical implementation of Kant's ideas about the limits of reason based upon human experience, i.e. there are some truths which are inaccessible because time and space are preconditions of all human experience. Not to dwell on arguments about whether or not time and space actually exist independently of human experience, what Kant was getting at is that the way in which humans experience the world limits our ability to draw conclusions to a particular subset of all truths. If Godel's theorem is true, then from a Kantian perspective, mathematics no longer enjoys a uniquely privileged place in regards to human rationality. That's pretty important philosophically - at least to some people. Positivists may take a different view.
- icandoitbetter 15y ago
  Godel doesn't talk about space, time, human experience, truths that exist independently of human experience. I fail to see how he's relevant.
  - shmerl 15y ago
    He does. Learn more about his biography and his interest in mysticism and philosophy: http://www.amazon.com/G%C3%B6del-Logic-John-L-Casti/dp/0738205184 http://www.amazon.com/G%C3%B6del-Logic-John-L-Casti/dp/07382...
    - rcthompson 15y ago
      Perhaps he does, but I don't think he does so in the proofs of his incompleteness theorems.

ropz 15y ago

The referenced page doesn't deliver on the hype of the HN headline, it merely offers: "... some selections that will help you start to understand it."""

flurie 15y ago

The greatest explanation I've ever seen for the Incompleteness Theorems comes from Palle Yourgrau in his book A World Without Time. He gives an excellent introduction to his explanation: "To appreciate Godel's theorem is your birthright; let no one, including the mathematical police, deprive you of what you have a right to enjoy."

derleth 15y ago
Who in the world are the 'mathematical police'?
- keithpeter 15y ago
  A rhetorical and shadowy group who discourage ordinary people from reading about or becoming interested in mathematics. A lot of popular science authors invoke this underground organisation, so it must exist.

rcthompson 15y ago

Think of it kind of like the Sieve of Eratosthenes, but for provability instead of primeness. You start with one axiom and prove everything you can based on that. Then you pick one of the statements you couldn't prove and add it as a second axiom (thereby expanding your axiomatic system), then prove everything that you can with those two axioms. The pick another unproven statement as your third axiom and repeat. Godel's incompleteness theorem is equivalent to saying that you will never run out of axioms, and that you will be able to continue this process indefinitely (just like there are an infinite number of primes). It's not an exact comparison, but it gives you the idea.

bjornsing 15y ago
An interesting comparison. Just one important difference though if I understand correctly: In Gödel's world you will sooner or later ruin your axiomatic system by adding an axiom that is inconsistent with one or several of your earlier axioms. There's no way to know (from within the system) when that happens, except perhaps that it gets a whole lot easier to prove weird stuff. :)
- rcthompson 15y ago
  I guess I should have said that you pick as your new axiom a statement that you couldn't prove and also couldn't disprove. Though I'm not sure if even that is the same as logical independence, which is what you really want.
xyzzyz 15y ago
I think your comparison misses an important point. If you pick in every step a sentence that is non-provable from your current axioms, but not contradictory with them either, after infinitely many steps[1] you will have picked all of them, and get a system called True Arithmetic, in which every true sentence is provable, essentially by definition. The reason why Goedel's incompleteness theorem does not work here is that your set of axioms is not recursively enumerable, and this is a necessary assumption of GIT. [1] - If "after infinitely many steps" sounds fishy to anyone, please keep in mind that you start with an infinite list of axioms anyway -- first order Peano arithmetic theory has an induction axiom schema Ind that basically says that for every sentence f, Ind(f) (the sentence you get by substituting every occurrence of a single free variable in Ind with f) is an axiom of PA.

cop359 15y ago

Seems like a silly paradox. Why is it important? Also it seems very similar to this famous paradox: (from 600BC btw.) http://en.wikipedia.org/wiki/Epimenides_paradox http://en.wikipedia.org/wiki/Epimenides_paradox

rcthompson 15y ago
Constructing the paradox is just the means of proving the theorem. The paradox itself is not particularly important. Also, the paradox in Godel's theorem is "This statement is unprovable" not "This statement is false".

hammock 15y ago

Gödel showed that provability is a weaker notion than truth This, to me, is a great summation and one of the most important conclusions we can draw. When you reflect on it it's easy to see how Godel's theorems reach beyond computer science and into philosophy, ethics and religion.

erichocean 15y ago
Not that easy, because it only applies to truths represented in a system of symbols. Very abstract stuff, and in fact, trivial to overcome – use two sets of symbols. The theorem was important at the time because it ended one pursuit (one single-level system to rule them all), but its actual impact on anything of importance in the wider world of, well, anything, is vastly overrated.
rcthompson 15y ago
I believe you would need to establish some sort of equivalence between arithmetic on the set of natural numbers and philosophy, ethics, and religion in order to apply Godel's incompleteness theorem to any of them, since Godel's theorem applies to sets of axioms used to prove things about the natural numbers.

tumes 15y ago

While it might not be the most technically accurate, the ways in which David Foster Wallace touches on Gödel in Everything and More are worth a look for interested parties.

bjornsing 15y ago

I of course have no proof, but I sometimes get a feeling that Gödel does have something to do with the limits of rational thought. To me it seems humans have found a way to cope with Gödel's incompleteness: we accept that some of our axiomatic systems are inconsistent and adapt by simply discounting the value of proofs. It's difficult to explain, but let me give an example. Among engineers you can often reason along very long logical chains and have your conclusions accepted. Among (some) business people you can't. They seem to refuse the validity of logic itself, being nervous about trusting logical conclusions. I think that's because they know their axiomatic systems are self-inconsistent. :) By observing business people I have come to the conclusion that the best you can do in an a self-inconsistent axiomatic system is to look for "nuggets of truth" and never wonder too far from them. You can hear people say stuff like "limiting tweets to 140 characters will brings out creativity - people are less afraid to create when they are constrained" and similar. If you accept that as truth then you can wonder a short short distance from it and reason about business opportunities, but you can't combine that nugget with some other nugget and be sure to come to a correct conclusion. Perhaps it is so, that the likelihood of "proving" an untrue statement in a self-inconsistent system increases with the number of axioms you are basing your proof on. That's perhaps why many people are very skeptical of "proofs" that seam to involve a lot of axioms? :)

mjw 15y ago
Surely a simpler explanation for that is that business people don't usually work with crisp, binary data. Instead they're (implicitly) doing some kind of statistical inference on noisy data. Propositional logic might be an acceptable approximation to this kind of inference in certain narrow situations, but the approximation breaks down quicker when the chain of inference gets longer.
- bjornsing 15y ago
  That could certainly be a simpler (and therefore better) explanation. :) When your "axioms" are fuzzy so to speak, and not real axioms, it's of course dangerous to draw conclusions from several of them (because the risk of one of them being false increases exponentially). But I still have a feeling there's something there... :) For example, I remember reading here on hacker news about this CS professor who had found a way to predict performance in entry level programing courses: http://www.eis.mdx.ac.uk/research/PhDArea/saeed/ http://www.eis.mdx.ac.uk/research/PhDArea/saeed/. Basically, they just tested their students ability to form a self-consistent model of how programming works. If they could they did well in the course. If they couldn't they did poorly, and it was very difficult to help them. That experiment leads me to believe that about 50% of the population is in the habit of constructing self-inconsistent systems of hypothesis (provisional axioms you could say). :) If that's true I'm not sure yours is a simpler explanation... ;)

batista 15y ago

With regards to the "Rucker, Infinity and the Mind" except that says: >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: (...) Actually, Godel's theorem is not that simple at all. It involves lots of hard math. And it's not about some hazy "Universal Truth Machine", it's about a specified axiomatic mathematical system with certain specific properties. The "simple" thing that RI&TM describes is a variation of the Liar's paradox. Which is somewhat like what Godel used, but he did not use it in a simplistic way, not at that level of coarseness, and surely not "embarrassingly simple to relate".

powertower 15y ago

> The implication is that all logical system of any complexity are, by definition, incomplete; each of them contains, at any given time, more true statements than it can possibly prove according to its own defining set of rules. Here is an even simpler explanation: A description of a thing is not the thing itself, it's just a description that allows you to: interact with that thing and place that thing into a framework. And an even more accurate description of a thing is still not the thing itself, it's just a more accurate description. Add more layers, and you still have just a description, and never the thing itself. It's like an onion, and each layer gets more distant from the core. Then those layers begin to interact with other descriptions of other things. So more layers are added to explain those interactions. It goes on and on until you've simulated the universe. The problem is it's exponential, and even if it was not, you're still just stuck with just a description, and not the thing itself. Some people will claim otherwise here, so just ask them if a description of a thing is the same as the thing itself and go back to the start of all this.

derrida 15y ago
If I'm not mistaken, one way of seeing GIT is just as a reductio ad absurdum on the idea that truth is just that which is proved. Perhaps you should consider that talking about ontology clouds the water here, this explanation might have some analogical value, but isn't 'simpler'.