Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What Do Gödel's Incompleteness Theorems Mean?

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 72 posts

Re: What Do Gödel's Incompleteness Theorems Mean?

#31

Post by kerwioru9238492 »

pdonis wrote: post #25
seanhunter wrote: post #12

As far as I can see people always radically exaggerate the effect of the incompleteness theorems. It seems interesting that any nontrivial axiomatic system has statements which are true but unprovable but to say that derails Hilbert’s project seems just obviously untrue when you can for example join math postgrad programs now which are focused on formalisation. [1] So formalisation is very much still going on, probab…

> any nontrivial axiomatic system has statements which are true but unprovable Although this is a common way of stating what Godel's incompleteness theorem tells us, it's actually not correct. As was posted upthread, when you combine Godel's first incompleteness theorem with Godel's completeness theorem (all this in first-order logic), you find that, for any sentence that is not provable in a system of first-order lo…

[flagged]

Re: What Do Gödel's Incompleteness Theorems Mean?

#32

Post by kakaz »

lioeters wrote: post #3
marojejian wrote: post #2

Interesting points in here. e.g. that Godel didn't think this scrapped Hilbert's project totally: >Gödel believed that it was possible to redefine what we mean by a formal mathematical framework, or allow for alternative frameworks. He often discussed an infinite sequence of acceptable logical systems, each more powerful than the last. Every well-formulated mathematical question might be answerable within one of them…

That part you quoted was interesting to me too. I remember once re-reading the incompleteness theorems - where it talks about a "finite set of axioms", it seemed there may be a loophole if we can imagine a theoretically infinite set of axioms, as a way to approach completeness. Overall I really enjoyed this article, short interviews with mathematicians and philosophers on a topic I've often thought about.

[dead]

Re: What Do Gödel's Incompleteness Theorems Mean?

#33

Post by dist-epoch »

seanhunter wrote: post #12

As far as I can see people always radically exaggerate the effect of the incompleteness theorems. It seems interesting that any nontrivial axiomatic system has statements which are true but unprovable but to say that derails Hilbert’s project seems just obviously untrue when you can for example join math postgrad programs now which are focused on formalisation. [1] So formalisation is very much still going on, probab…

> As far as I can see people always radically exaggerate the effect of the incompleteness theorems

Like people saying Godel theorems "prove" LLMs could never invent new mathematics because being a software system Godel applies to their operation, but not to humans which are not axiomatic systems, and thus humans can go beyond them and beyond the limits of Godel, humans can "know" a result to be true even if Godel says you can't prove it.

Re: What Do Gödel's Incompleteness Theorems Mean?

#34

Post by retrocryptid » 

      Natalie mentions  the Newman &  Nagel's text "Gödel's  Proof," a
      (//the//?) 1958 classic on the subject. [[ 1 ]]  Having left IBM
      in December  1990, I spent a  month with the text,  dipping into
      mild insanity, taking to strange  wines to relieve myself of the
      fear that my previous years  long study of Whitehead & Russell's
      "Principia Mathematica" [[ 2 ]] was useless.
   
      I  really  appreciate  the  inclusion of  Alvir's  statement  on
      whether  or not  Gödel  thought he  proved  all logical  systems
      undecidable and incomplete.   About 80% into the  article is her
      quote:
   
      >> Often people will speak as if  the CH is the smoking gun that
      >> shows sometimes  mathematical questions have no  answer.  But
      >> in my  opinion, this situation provides  very little evidence
      >> that   there   are  “absolutely   undecidable”   mathematical
      >> problems, relative to any given permissible framework.
   
      Though  I  would have  added  a  reference to  Infinitary  Logic
      [[ 3 ]]  after dropping  the  reference  to L-omega-1-omega.   I
      suspect most  readers would find discussion  of higher-order and
      modern logic a bit confusing  without a pause for further study.
      But a guide post pointing  in the appropriate direction would be
      good.

      That this is  the only critique I have of  the article speaks to
      Wolchover's  skill  in communicating  complex  ideas  for a  lay
      audience.  I really  liked this article, so  thank you @baruchel
      for posting the reference to it.
   
   :: References
   
      1. https://search.worldcat.org/title/1543160023
   
      2. https://search.worldcat.org/title/933122838
   
      3. https://en.wikipedia.org/wiki/Infinitary_logic

Re: What Do Gödel's Incompleteness Theorems Mean?

#35

Post by oulipo2 »

svantana wrote: post #7

Of all the incompleteness-style theorems, I find the Halting problem to be the most approachable and also the most interesting. Maybe it's because I'm a software dev that dabbles in math rather than the other way around. But that makes me wonder if all of Gödel's theorems can be stated if 'software form', so to speak.

Halting problem concerns decidability, not completeness

Re: What Do Gödel's Incompleteness Theorems Mean?

#36

Post by Epa095 »

pdonis wrote: post #22
danbruc wrote: post #19

Earlier quoted context omitted.

That is interesting, I always thought that the incompleteness theorems says, there are theorems that are true or false in all models but cannot be proved to be so. But if it that is not the case and there always exist models where the theorem is true and false, that makes it sound to me, like the incompleteness theorem is not really about proving things. With that it sounds more like the inability of a sufficiently c…

> I always thought that the incompleteness theorems says, there are theorems that are true or false in all models but cannot be proved to be so. As the GP points out, that's not what Godel's incompleteness theorem actually shows. Although it's a common misconception (one which unfortunately is propagated by many sources that should know better). The key point of the incompleteness theorem is that it shows that (at le…

> The key point of the incompleteness theorem is that it shows that (at least in first order logic, which is the logic in which the theorem holds) no set of axioms can ever pin down a single model.

No, this was known before the incompleteness theorem, ref Löwenheim–Skolem theorem.

Re: What Do Gödel's Incompleteness Theorems Mean?

#37

Post by cobbal »

lacewing wrote: post #9
svantana wrote: post #7

Of all the incompleteness-style theorems, I find the Halting problem to be the most approachable and also the most interesting. Maybe it's because I'm a software dev that dabbles in math rather than the other way around. But that makes me wonder if all of Gödel's theorems can be stated if 'software form', so to speak.

Right, if you're a software engineer, the realization that the two theorems are nearly-equivalent really takes the air out of a lot of the existential philosophizing around Gödel's incompleteness. Gödel's argument basically says that any system of mathematics powerful enough to implement basic arithmetic is a computer. This shouldn't be surprising to software engineers because the equivalency between Boolean logic an…

I think that's selling the theorems a little short. A math system with arithmetic is equal to, or more powerful than, a computer. For an example, even classical logic comes with the law of excluded middle that can say (internally) if a program halts or not. Incompleteness applies to all the stronger systems as well.

Re: What Do Gödel's Incompleteness Theorems Mean?

#38

Post by hughw »

From E.T. Jaynes' Probability Theory [1] :

  To understand the above Gödel result, the essential point is
  the principle of elementary logic that a contradiction
  Ā A implies all propositions, true and false. 
  (Given any two propositions A and B, we have A ⇒ (A+B),
  therefore  Ā A ⇒  Ā (A+B) =  Ā A +  Ā B ⇒ B.) 
  Then let A = {A1, A2, ..., An,} be the system of axioms
  underlying a mathematical theory and T any proposition,
  or theorem, deducible from them:
  
  A ⇒ T.

  Now, whatever T may assert, the fact that T can be deduced
  from the axioms cannot prove that there is no contradiction
  in them, since, if there were a contradiction, T could
  certainly be deduced from them!
  
  This is the essence of the Gödel theorem, as it pertains to
  our problems. As noted by Fisher(1956), it shows us the
  intuitive reason why Gödel's result is true. We do not
  suppose that any logician would accept Fisher's simple
  argument as a proof of the full Gödel theorem; yet for most
  of us it is more convincing than Gödel's long and
  complicated proof.
[1] https://bayes.wustl.edu/etj/prob/book.pdf

Re: What Do Gödel's Incompleteness Theorems Mean?

#39

Post by bananaflag »

alan-crowe wrote: post #30

As a child, I noticed that the proofs of mathematical theorems were esoteric knowledge, known only to a few adults. I struggled to follow even the simplest proofs, and hoped that one day I might learn to create a proof or two of my own. This was not only a high aspiration, but a dangerous one. I saw no reason why certain knowledge of a true fact would be accessible to humans via proof. Any-one who embarked on the que…

> Gödel completeness theorem is the really big deal. Except it isn't. That computer program turns out to be one of those wretched tree search ones that soon bogs down. The real problem turns out to be the combinatorial explosion inherent in unstructured search through the Herbrand universe.

Yup. Incompleteness is sort of a red herring. P≠NP (even though unproven) yields the real, practical, painful incompleteness.

Re: What Do Gödel's Incompleteness Theorems Mean?

#40

Post by pdonis »

Epa095 wrote: post #36
pdonis wrote: post #22

Earlier quoted context omitted.

> I always thought that the incompleteness theorems says, there are theorems that are true or false in all models but cannot be proved to be so. As the GP points out, that's not what Godel's incompleteness theorem actually shows. Although it's a common misconception (one which unfortunately is propagated by many sources that should know better). The key point of the incompleteness theorem is that it shows that (at le…

> The key point of the incompleteness theorem is that it shows that (at least in first order logic, which is the logic in which the theorem holds) no set of axioms can ever pin down a single model. No, this was known before the incompleteness theorem, ref Löwenheim–Skolem theorem.

The Lowenheim Skolem theorem only applies to first-order axiom systems that have an infinite model. So it would apply to the axioms for the natural numbers, yes.

The Godel theorems apply to any first-order axiom system, regardless of whether it has an infinite model or not.

Post reply on HN