#gödels theorems

[mthevlamister]

Let's Discuss Gödel's Incompleteness Theorems

Second big math post! I may keep doing this as I prolong writing!

This series of posts is also called "I put all my money into learning mathematics and its explorers, now you have to deal with it."

Background Info:

Statement: a sentence that either always true or always false [3 is rational is a true statement]

In contrast to this, an Open Sentence: a sentence that uses variables that does not have a clear truth/false indicator [x = 3. How do I know that? X doesn't always equal 3].

Formalist: a mathematician who believes that we create math. It's like a game of chess. We make the rules.

Platonist: a mathematician who believes math exists beyond us. We cannot create math. We can only discover it's true nature.

So, let's get into it.

There are two theorems by Gödel that discuss incompleteness.

The first is as follows: Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of F which can neither be proved nor disproved in F.

The second is: For any consistent system F within which a certain amount of elementary arithmetic can be carried out, the consistency of F cannot be proved in F itself.

Let's break down the thought process of these.

When we have a statement, we know the rules listed above. However, will we always find a proof for it? Sure, I could prove that the square root of thirteen is irrational [very fun proof if you ever want to look into it], but will I find a proof of why the grass in my yard is green? It's a true statement. My grass is very green, but I can't really prove it [maybe I can! I'm lazy].

And will there be a contradiction? Yes, the grass is green now, but what happens when the amount of sunlight changes? Are some bits yellow? Are my color-rods just dogshit? What about when the grass isn't there? Is it still green?

I can't prove that my grass' color will never lead to a contradiction! It very well could! One day, in one hundred years, maybe grass will change to be a different shade! My proof is now contradicted because of future events, but I don't know that at the moment.

Now there are two types of mathematicians: platonists and formalists. If you're like me, you may wish to say you're a mix. That it's a game we can play, but we didn't invent it. That being said, I'm a platonist for sure, but that's besides the point. My point is that this theorem follows the platonist imo. There are statements that exist that we cannot prove, whether true or false, but they exist freely without us showing the truth.

I. Adore. Math.

[noosphe-re]

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.

Natalie Wolchover, How Gödel’s Proof Works, Quanta Magazine, July 14, 2020

[dorothytheexplorothy]

my toxic trait is believing that, once I get to understand the proof of fermat's last theorem, I'll be able to simplify it down to high school graduate level

[maxwellshimbo]

RIP Kurt Gödel you would have loved "What if kinkshaming was my kink?"

[girlonthelasttrain]

where's that xkcd comic about overestimating how much the general public knows about any specific scientific subject. gotta make a version for mathematics and logic...

[falseandrealultravival]

The Greatest Genius in Mathematics - Leibniz: Mathematics Note- 9 (Essay)

Leibniz

Leibniz is a German philosopher, theologian, mathematician, politician, etc., and is also called an "universal genius" because of his wide range of fields. He is said to have had an IQ of over 200, according to psychologists. What makes him famous may be the fact that he fought fiercely with his contemporary Newton of England for the honor of being the first discoverer of calculus.

However, Newton discovered the calculus earlier. But the mathematical symbols we use today were invented by Leibniz. Why? Notationally, Leibniz's sign was far superior. Newton called his method of calculus the "flux method," but his interest was mostly in mechanics, and it is likely that it was a poor mathematical tool because he specialized in it.

Leibniz has a terrifying idea. modern linear algebra. He must have thought that solving simultaneous polynomial equations was troublesome, although it was a field of study that studied the properties of vectors and matrices. He tried to lump the coefficients together and solve them all at once. It is precisely this "troublesomeness" that secures the development of mathematics.

He also developed a calculator. It was of course time constrained and mechanical, but more importantly, he listened to the I Ching in China and learned to combine 0 and 1 to represent numbers. Arriving at the principle of decimal system. This is the principle of modern computers.

Leibniz's achievements, especially the richness of his ideas, are noteworthy, and I call him the greatest genius in mathematics history. Usually they tend to mention Archimedes, Newton and Gauss.

I just wrote above about Newton and Leibniz's calculus notation. It also extends to logic, and I feel that it was in anticipation of the current symbolic logic. He was just one step away from the most important achievement of modern mathematics, Gödel's incompleteness theorem.

(2023.04.22)

[klavierpanda]

You know that autism thing where you get really frustrated and upset when people get something wrong about your special interest? Half of my degree gets maths wrong

[chevril-glove]

I love this so much

When I was a kid, I remember being really astounded by the fact that arithmetic is consistent. Like uh, 2 + 3 + 4 is 9. And 9 - 4 is 5, which is 2 + 3, and 9 - 2 is 7, which is 3 + 4! And 7 is also 6 + 1, and guess what, 9 is also 6 + 1 + 2, and even more amazingly, 6 is 4 + 2, and (remember 9 - 4 is 5) 2 + 2 + 1 is 5! No matter what you do it's always consistent, you can't trick it by adding and subtracting some convoluted sequence of numbers until it gives you an answer that's inconsistent with the rest.

When I was first learning arithmetic I remember that I just found this crazy, like, how does it always work out? That shouldn't be possible. And I figured that, naturally, when I got older, someone would eventually give me the answer to this incredibly pressing question. And, well, it turns out nobody has the answer, and they actually proved that it's impossible for anyone to give a satisfying answer. So, that's a bit disappointing.

[auporias]

the amount of space that gödels incompleteness theorem takes up in my head is unreal

like the idea that any sufficiently complex consistent formal system cannot be complete (there are always truths inaccessible from within a formal system)

so sometimes we have to step outside of the rigidities of structure in order to access truth

if this interests you, the book gödel escher bach by douglas hofstadter is an incredible trip

[lifesfeelings]

Incompleteness Theorem

Okay, so that whole last post got y’all ready for another lesson on something that I find interesting and want to just write about 1) to remember the information but 2) teach others about it/ask real knowledgeable people to teach me! So, tldr on my last post, I have entered a math fixation in my learning, though, not how to do it but rather the logics and theories behind it. With that, I just started reading “Gödel, Escher, Bach.” I’m only like 50 pages in and I did hear someone online say it took him 7 years to read it lol!! but it’s FASCINATING so far! And don’t quote me on being any kind of knowledgeable person when it comes to this: I don’t do math and I study English. But I just wanted to take some notes on what I’ve learned! So this actually goes way back to a Veritasium video, “Math’s Fundamental Flaw,” which taught on Gödel’s “Incompleteness Theory.” In terms of how Hofstadter tells it: no system is able to be “completed” in that there are no set of proofs that can both 1) prove all statements in a system to be universally true and 2) not self-contradict itself at some point. I guess at its core that basically there will always be truths in math that are true but not provable. The proofs are simply too weak to ever actually reach certain truths without then creating paradoxes in the system. Hofstadter actually starts the book first though by describing Bach’s music and Escher’s art as these things called “strange loops” in which they both will seemingly move forward in a direction (Bach’s music would go up in pitch or Escher’s drawing would show stairs going upward), and yet always return to the it’s original place—the music would return to its original key and the stairs would return to the bottom of the painting. I’m honestly so scared for the rest of this book just because the complexity it’s described with on Wikipedia. I don’t know if half of it will make sense and apparently there’s all these hidden themes and patterns in the Achilles stories he tells too? I’m not good at picking out hidden shit like that and I feel like half of it will go over my head haha! If I got anything wrong or if people want to just sdd to this post I would LOVE that :)

[its-a-hil]

*holds out my hand* we can fix this. together

[maxwellshimbo]

Neither provably true nor provably false but a secret third thing (unprovable within the current system of axioms and theorems)

[osmiumpenguin]

The problem with every machine learning model currently being marketed as “AI” is that it can prove the consistency of its own axiomatic system.

[mysteriouslyseeing]

The difference is that mathematicians have proven that it is literally impossible to figure it all out

[dragonflavoredcake]

Etho: If I wore a shirt inside out, the entire universe would be wearing the shirt except me.

Cleo: Congratulations, you just explained Gödel's Theorem in a single sentence.

Joel: Nerd.

Cleo: Bold words from a man who can't count to twenty with his shoes on.

Joel: >:O

[max1461]

I *think* the deal with Gödel's incompleteness theorems is that it's just a cardinality thing, it's like a pigeonhole principle thing (in spirit; it's not literally the pigeonhole principle). Like that's sort of what diagonalization arguments are, and Gödel has a diagonalization argument. If you set up some system of rules, there will always be consequences of that system that you can't prove because you're limited to "too few possible proofs". I think even Gödel himself said something to this effect somewhere but I can't find it.

It's like. Imagine some sentence in PA that's like ∀nP(n), right. Well it might be unprovable in PA. In fact, Con(PA) is of exactly this form: "∀n(n does not encode a valid derivation of a contradiction)" or whatever, and it's unprovable in PA. But from the outside ∀nP(n) is still true in the sense that, well, no matter how many numbers n you check, you'll never find one that doesn't satisfy P. In fact, any statement of the form ∀nP(n) which is unprovable must be true, because if it were false we could find a counterexample. But we can't make that inference from within PA, we have to make it "on the outside".

I find this sort of unsettling because...

Nevermind. I don't find it unsettling any more. I think it's normal and no big deal. There are definitely interesting issues around this but I think in itself it's kind of no big deal. Especially if you're like, a Curry style formalist and you think of math as the empirical study of the behavior of systems of rules and proofs as repeatable experiments (reducing math to metamath, and making it a science).

It's just all, all Gödel is saying is that mathematical systems are "too small" to directly tell you everything about themselves. Again, *I think*. It's like, no more mysterious than the halting problem, because it literally is the halting problem. I don't think the halting problem is that wacky either. Ok there's no algorithm that tells you whether other algorithms will halt. Sure, an algorithm for a decision problem is a pretty restricted sort of thing. It's not really a surprise that there isn't one that does that.

Anyway the upshot is I don't think Gödel forces us to be any more Platonist than we already are. Like in general, even without Gödel, if you want to be a game formalist, say... and you claim "I've proven φ from the axioms of PA", and you want that to be interpreted in roughly the same way as "I made the move ke4 in a chess game", or whatever... well, to interpret the latter claim, I have to ask questions like "what's a chess game?", "what does it mean to make a move?", and these still get me into the territory of ontology of abstract objects and semantics of claims about abstract objects. So game formalism doesn't save you from this sort of thing. And conversely I don't think Gödel produces any more issues of this kind. If I claim "∀nP(n) is true but unprovable in PA", the thing is it might be hard for me to know I'm right (because ∀nP(n) is uprovable, so I have to investigate empirically, à la Curry's idea), but if the trouble is over the semantics, well, I'm still just making a truth claim about an abstract object (the system PA), so it's like. We're semantically in no more dubious territory than with the claim about making a move in chess or the claim about a totally non-Gödelian proposition proved in PA. It's just that it's harder to establish our claim as true.