The Issue of Chance: Godel's Theorem (Evolution)

by David Turell , Monday, October 31, 2022, 16:30 (752 days ago) @ Matt S.
edited by David Turell, Monday, October 31, 2022, 17:00

A new review of Godel's incompleteness theorem:

https://www.quantamagazine.org/how-godels-incompleteness-theorems-work-20200714

"In 1931, the Austrian logician Kurt Gödel pulled off arguably one of the most stunning intellectual achievements in history.

"Mathematicians of the era sought a solid foundation for mathematics: a set of basic mathematical facts, or axioms, that was both consistent — never leading to contradictions — and complete, serving as the building blocks of all mathematical truths.

"But Gödel’s shocking incompleteness theorems, published when he was just 25, crushed that dream. He proved that any set of axioms you could posit as a possible foundation for math will inevitably be incomplete; there will always be true facts about numbers that cannot be proved by those axioms. He also showed that no candidate set of axioms can ever prove its own consistency.

"His incompleteness theorems meant there can be no mathematical theory of everything, no unification of what’s provable and what’s true. What mathematicians can prove depends on their starting assumptions, not on any fundamental ground truth from which all answers spring.

"In the 89 years since Gödel’s discovery, mathematicians have stumbled upon just the kinds of unanswerable questions his theorems foretold. For example, Gödel himself helped establish that the continuum hypothesis, which concerns the sizes of infinity, is undecidable, as is the halting problem, which asks whether a computer program fed with a random input will run forever or eventually halt. Undecidable questions have even arisen in physics, suggesting that Gödelian incompleteness afflicts not just math, but — in some ill-understood way — reality.

***

"Gödel’s main maneuver was to map statements about a system of axioms onto statements within the system — that is, onto statements about numbers. This mapping allows a system of axioms to talk cogently about itself.

"The first step in this process is to map any possible mathematical statement, or series of statements, to a unique number called a Gödel number.

[a long clear discussion of Godel's proof follows]

"However, although G is undecidable, it’s clearly true. G says, “The formula with Gödel number sub(n, n, 17) cannot be proved,” and that’s exactly what we’ve found to be the case! Since G is true yet undecidable within the axiomatic system used to construct it, that system is incomplete.

"You might think you could just posit some extra axiom, use it to prove G, and resolve the paradox. But you can’t. Gödel showed that the augmented axiomatic system will allow the construction of a new, true formula Gʹ (according to a similar blueprint as before) that can’t be proved within the new, augmented system. In striving for a complete mathematical system, you can never catch your own tail.

"We’ve learned that if a set of axioms is consistent, then it is incomplete. That’s Gödel’s first incompleteness theorem. The second — that no set of axioms can prove its own consistency — easily follows.

"What would it mean if a set of axioms could prove it will never yield a contradiction? It would mean that there exists a sequence of formulas built from these axioms that proves the formula that means, metamathematically, “This set of axioms is consistent.” By the first theorem, this set of axioms would then necessarily be incomplete.

"But “The set of axioms is incomplete” is the same as saying, “There is a true formula that cannot be proved.” This statement is equivalent to our formula G. And we know the axioms can’t prove G.

"So Gödel has created a proof by contradiction: If a set of axioms could prove its own consistency, then we would be able to prove G. But we can’t. Therefore, no set of axioms can prove its own consistency.

"Gödel’s proof killed the search for a consistent, complete mathematical system. The meaning of incompleteness “has not been fully fathomed,” Nagel and Newman wrote in 1958. It remains true today."

Comment: this applies to using math to absolutely prove any part of reality. It means we have to accept certain concepts about reality on faith.