Live data from Hacker News

What Gödel Discovered

stopa.io

71–80 of 271 posts

Re: What Gödel Discovered

#71
post #19

Earlier quoted context omitted.

From Wikipedia [0]: > The proof constructs a particular Gödel sentence for the system F, but there are infinitely many statements in the language of the system that share the same properties, such as the conjunction of the Gödel sentence and any logically valid sentence. [0] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

Yes, but the "such as..." example incorporates the original "this statement is not provable" statement, so it seems a bit of a cheat. If you could exclude that statement, it would also by definition exclude any compound versions of it. It seems to me that the issue boils down to, can "this statement is not provable" be leveraged to get to something like 1 + 1 = 3?

You can exclude any particular Gödel statement (a specific string of symbols), and as you're suggesting you can even exclude an infinite sequence of derived statements too, found by systematically adding the previous ones as axioms and applying a "Gödelisation" procedure to make another.

But "this statement is not provable" isn't a statement in the logic. It's an English language description of a type of statement, one which has certain self-referential characteristics and shows us the incompleteness of the logic.

There are an infinite number of statements in the logic which fit that type by having the relevant characteristics, and they aren't all obvious. The self-referential recursion implied in Gödel's construction is designed to make it obvious, but it can be encoded in less and less obvious ways while still containing an encoded image of themselves.

You can even get to statements where the self-reference is encrypted (using an actual encryption algorithm)! Only a mathematician with the "secret key", or a clever super-mathematician with amazing brute-forcing skills, would be able to read the statement and confirm that it's true!

And so "perceivable truth" is a thing too. Some truths are too complex for an ordinary mind to verify, yet still true.

To exclude all self-referential statements in the logic of type "this statement is not provable", you would need a decision procedure to tell you which statements in the logic are those.

Unfortunately you can't make such a decision procedure. It's very similar to Turing's halting problem. Just as you can't make a program which will take any input X and tell you if the program encoded as X will eventually terminate, you can't make a procedure which will take any statement S and tell you if it contains a fancy encoding of itself.

There's just no way to do it. The fact it can be related to Turing's halting problem, which is about real machines and real algorithms running on them, may give you some idea that the core principle can be grounded in something quite down to earth which affects practical applications.

Re: What Gödel Discovered

#72
post #43
post #26

Earlier quoted context omitted.

Others have explained why you can't wave away inconsistency (principle of explosion) nor incompleteness (adding new axioms just creates a new axiomatic system with its own Godel sentences). However you might also find it interesting what incompletenesses exist in our own mathematical system (ZFC) -- the most well-known example is the Continuum Hypothesis[1]: > There is no set whose cardinality is strictly between tha…

> being able to prove the CH is an incompleteness in ZFC. It's only incompleteness if the CH is true or false at the semantic level, "outside" of the logic system under discussion. But the CH may be neither true or false, semantically, if the meaning of "existence of a set whose cardinality is strictly between that of the integers and the real numbers" strictly depends on the axioms and logic used to define sets and…

Hm? I thought (in)completeness was just about whether or not , for each well-formed-formula, either there is a proof of it, or a proof of its negation.

The CH is a syntactically valid statement in ZFC.

So, shouldn't the fact that ZFC cannot prove or disprove CH, be an example of ZFC being incomplete, regardless of whether CH is in fact true, false, or not-a-proposition-that-has-a-truth-value ?

Re: What Gödel Discovered

#73

This is remarkably well done. I'm reading Hofstadter's Godel, Escher, Bach and found this at the perfect time. Thanks for the write up!

Man, I just searched about that book, and it is like there is a world I don't know anything about. Would you mind sharing the names of your favorite books?

Gödel’s Proof by Nagel and Newman is quite good. ISBN 0814758371

Re: What Gödel Discovered

#74
post #7

I’m a mathematician who spent many hours thinking about Goedel theorem and adjacent topics. The author in a self-deprecating way says that he’s not a mathematician, but just a programmer. Bear no mind to that: this is one of the best popular expositions of Goedel theorem I’ve seen. Everything is very accurately explained, there are no silly mistakes and untruths one often sees mentioned in context of Goedel theorem,…

This brought a big smile to read, thank you :)

Re: What Gödel Discovered

#75

Loving this so far! One tiny typo that threw me for a loop for a second was: > when apples are a fruit, then bananas or applies implies bananas or fruits which should be: > when apples are a fruit, then bananas or apples implies bananas or fruits

Will address, thanks!

Re: What Gödel Discovered

#76

This is really excellent. Amazing how much clearer the author’s Lisp code makes things (even to a non mathematician and non lisper). It’s rare to find explanations of difficult topics that are this well communicated, but I hope it becomes a trend.

Thank you for the kind words! :)

Re: What Gödel Discovered

#78
I really like the conversion to a representation that's more familiar but I suspect it's also confusing me. Here are the questions that I have to start:

Does 'there-is' evaluate to a boolean (is boolean a thing? is evaluation a thing?)

I was surprised that the axioms don't use there-is but I sense I shouldn't be?

what does '(when 0 (or 0 1))' mean, it's described as 'when 0, then there is either 0 or 1' but I'm not sure what that means? is '(when 0 0)' true and '(when 1 0)' false? Why not use '(when A B)' as equals?

Not a question but in the axioms I assume pairs should be pears and applies should be apples.

How goes 'implies' get introduced by '(when (when q r) (when (or p q) (or p r))'? Also, this introduces a category in the example i.e. fruits but not sure how that happened.

Why do we need to have second '(not (factor? x 3^22 ...))', isn't it sufficient to say that (factor? x 3^21 ...) to establish that the 2nd term is 'there-is'?

Re: What Gödel Discovered

#79
post #12

Thanks for great write-up, fun to read! I only notices one tiny typo: "when apples are a fruit, then bananas or applies implies bananas or fruits" - "applies" should be "apples" I guess.

And "pairs" should be "pears"!

Will address both, thanks team!

Re: What Gödel Discovered

#80
post #12

Thanks for great write-up, fun to read! I only notices one tiny typo: "when apples are a fruit, then bananas or applies implies bananas or fruits" - "applies" should be "apples" I guess.

Two more typos:

> These symbols map closely to the logical statements we are used too in programming.

too => to

> Hofstadter’s “I’m a Stange Loop”

Stange => Strange

Post reply on HN