Discussion about this post

User's avatar
Steve Berman's avatar

You get an A in geeking out.

Expand full comment
Chris J. Karr's avatar

"Essentially, Gödel said that any logical proof involving mathematics cannot be both consistent—provable within itself—and complete, meaning it can prove its own consistency."

Another way to think about it is this way: logical systems both have a language for expressing statements ("2 + 2 = 4") and rules for how those statements may be constructed so that the "truth" of any given statement can be evaluated to be "true" or "false". What Gödel showed was that language for expressing these statements is ALWAYS more "powerful" than the evaluation portions of the logical system, because in ANY logical system, you can say things (using the language) that your system cannot evaluate to determine if what you are saying is true or false.

This first(?) emerged when Georg Cantor was building a mathematics around the rules of set theory and encountered two sizes of infinity: the "smallest" infinity that is the size of of all countable numbers (integers) and a larger infinity, which is the size of all real numbers (continuous, infinitely divisible numbers, including irrational numbers). He was trying to prove if there were any OTHER infinities of a size between these two ("aleph-zero" for the smaller infinity, and "aleph-one" for the larger infinity). There's a fun pop-science book called "The Mystery of the Aleph"[1] that goes over Cantor's discovery and him pretty much driving himself crazy trying to figure out a proof about the relationship between these two sets of numbers.

In the absence of a proof one way of the other, mathematicians added a new "rule" to evaluate this special case (Zermelo–Fraenkel set theory), and Gödel showed that adding this rule enabled the expression of new mathematical statements that came along with the new rule that were similarly undecidable. Doug Hofstadter explores this in his books "Gödel, Escher, Bach" (GEB) and "I Am A Strange Loop", hypothesizing that this may be an emergent property of self-referential systems. (I'm still working my way through GEB, so don't take that as a complete or authoritative interpretation of Hofstadter's work.)

We run into a similar issue in computing (another logical system subject to Gödel's theorem) with something called the Halting Problem, which basically states that it's impossible to build a computer that can inspect at ALL programs that might it may be able to run and determine if it contains an infinite loop (hence the "halt"). You can build more powerful computers with capabilities that allow them to determine if all of prior generations' programs will halt or not, but in the process, the new architecture will allow NEW programs to be written that were not possible on the older architecture, and among these new programs will be NEW programs that the new computer cannot determine whether they halt or not. This is the fundamental reason antivirus and malware-related work will always be a running arms battle into the future.

Anyhoo - apologies for geeking out over this small point in Steve's post. This is a fun corner of math and computer science, and I love sharing how odd and interesting it is.

[1] https://www.goodreads.com/book/show/5786.The_Mystery_of_the_Aleph

Expand full comment
6 more comments...

No posts