What does Godël’s Incompleteness Theorem actually mean and imply? I just saw Ted-Ed’s video on this topic and didn’t fully understand what it means or what the implications of this are.

57 views

What does Godël’s Incompleteness Theorem actually mean and imply? I just saw Ted-Ed’s video on this topic and didn’t fully understand what it means or what the implications of this are.

In: 742

The dream of math is to be able to say “if a fact is true, then we can prove it”. By which I mean, write a mathematical proof using the rules of math and logic. This would make the math “complete”. Every true thing can be proven and every provable thing is true. Beautiful.

Godël came along and laughed at this idea. He demonstrated that it is not true, and the proof is demonstrating that you can build a statement that must be true, but for which the math cannot prove. Thus no matter what type of math you’re using, you can just build your unprovable statement. Ergo, “if it’s true, then we can prove it” is already incorrect.

One of the most common real-world examples is the computing halting problem. No computer program can consistently, reliably and correctly answer the question “will this program halt?” (as opposed to getting stuck in an infinite loop). The proof builds a program which is self-contradictory, but only assuming that the halting problem can be solved. Ergo, the problem cannot be solved. However, intuitively you can imagine that yes, some programs will never finish running, so in theory it should be possible to perform such classification. However we cannot reliably give a thumbs-up/down verdict using computing to make that decision. It’s a little example of incompleteness in computing. A computer program cannot analyse a computer program and figure it out while being limited to the confines of what we define a computer as.

I think the other responses are good enough but I would highly recommend you to watch this video by Veritasium to understand exactly and in a very visual way as to what it means.

https://youtu.be/HeQX2HjkcNo

Ever seen the statement, “This statement is false.”?

Now codify that using the language of pure math.

If you can do so, this statement means your language can have contradictions.

If you remove the statement, then the language is incomplete, because it no longer contains that statement.

So now decide which math language you want: one that is complete with contradictions, or one that is incomplete with no contradictions, because you can’t have both.

Cool, huh?

Up to his theorem, it was believed that a pure math language could be written that described everything, and was consistent with no contradictions. Bertrand Russel and Alfred Whitehead even wrote a giant book called The Principia Mathematica to formalize all know math. Bummer for them.

Ultimately it means there will be some contradictions a complete language. The implications are that math isn’t perfect, or the definition of perfect must contain contradictions. An epistemology crisis, with no real impact to the average person.

In mathematics there are axioms and theorems. We consider axioms as something given and theorems as something we can prove. But what is a proof? It is just words, and it can be incorrect. How can we verify the proof? Could there be mistakes? If 10 mathematicians say it’s correct, is it enough or not? 100 mathematicians? 1000?

All this is questionable. But what if we can design a system where it will be possible to formally verify any proof? A system where there will be a procedure to check any proof of any theorem and tell whether this proof is correct or not. For example, a computer would be able to do it. Then we will have a big advantage. But is it possible?

Before even making such a system we can formulate its fundamental properties. There should be no possibility to prove and disprove the same theorem at the same time (obviously) and there should be a possibility to prove any correct theorem (within the bounds of the system).

Goedel proved that this is impossible for some formal systems. The important word here is “some”. For example, formal 1st order logic is complete and non-contradictory. Also, any modular arithmetic is complete and non-contradictory. But traditional infinite arithmetic is not.

What are properties of a system that make it incomplete? First of all it has to be a formal system, i.e. where it is possible to express any proof (and any theorem or axiom) as a number or a string of symbols of any kind and there is an algorithm that decides on the correctness of this proof. Second, the formal arithmetic should be a part of the system. Then this system is incomplete.

Why is this theorem important? It states that a formal system can be incomplete. So – no formal system will save mathematics from possible errors.

The similar theorem exists in theory of algorithms. It states that it is impossible to make a computer program that will tell us whether any given program will run forever or will stop in some distant future.

That means you cant use math to proof everything which is true in math.

you can use other stuff than math to proove that. but not ONLY math.

its not complete in itself.

similar as you cannot concretley describe your consiousness although you definetly know its there.

it might be that you are not “good enough” to do so yet, and someone might be able to do so. OR its simply not doable.

As far as the implications go :

You set out to do this very difficult problem in physics in which you use maths as a language to express things.

Now years ago people believed that there is a way to proove everything they can observe in reality with maths.

but goedel says nope.

So when you now set out to do something – you know you can fail because you suck – OR – because its not possible – but you’ll never know…

That any system which can be used to “prove” anything will always contain things it cannot prove… basically paradox and contradiction is encoded in fundamental logic and truth… and tha’s proven with maths and stuff

Imagine that mathematical theorems are physical buildings. If a theorem is true, that means the building can be built and won’t just fall down.

Buildings are built with bricks, mortar, steel beams, etc. These are the building blocks. Math similarly has building blocks called axioms.

So say someone has said “I’m pretty sure we can build a building that looks like *this picture*”. People toil away until they figure out which building blocks to use and how, then they go and build it. Voila, they have just proved that building can be built (the theorem is proven).

But now imagine some builder comes along and shows that there must be some buildings that will not fall down, but cannot be built with any building blocks we have no matter how hard we try, and no matter what set of building blocks we use.

This is a nightmare for builders. We want to not only be able to build everything, we want to build it with as limited of a set of building blocks as possible. And we definitely don’t want perfectly good buildings to be unbuildable using our tools. But it turns out that no matter what, we can’t, and we just have to accept that we can’t build some buildings.

Edit: I’ll just add that what I described is called the *consistency* of math. Godel’s theorem actually comes in two parts, the other concerning the *completeness* of math.

Using the same analogy it would go something like this.

We *can* have limited systems which are consistent. We can have systems where we’re only concerned with brick buildings. In that system, we *can* build all possible “good” brick buildings. The obvious problem is that our system is incomplete. We can only build brick buildings, not every kind of building.

The full incompletes thereom basically says you can have one or the other, but not both. You can either be able to build all brick buildings and be limited in that way, or be able to build every kind of building, but not be able to build some of them. But you can’t have both consistency and completeness.

TLDR it means that some mathematical statements are unprovable. This means that some conjectures or problems may not actually have derivable solutions, and it’s impossible to know which problems do or don’t.

If you make a formal logical system powerful enough to derive the rules of arithmetic, then it will always be possible to construct a sentence of the system that is true but which cannot be proved in the system.

The arithmetic part is important. If someone ever tells you that Godel’s result applies to all logical systems, then they do not know what they are talking about. The sentential calculus, aka propositional logic, for example, is complete: all true statements within it can be proved by it. But you cannot derive arithmetic from it.

I like the russian nesting doll example for it. To explain everything in one doll you need another to encapsulate it. Scale that up a ton and you’d need to be outside of the universe to explain everything inside the universe.

All valid systems of math will have paradoxical problems that can’t be solved by switching to a “superior” system of math. Paradoxes are unavoidable in math systems, so mathematicians can quite trying to come up with “superior” systems (languages).

Recommend reading Godël, Escher Bach by Douglas Hofstadter if you are intrigued enough to pursue this as a lay person. I started reading it in HS well before I was really capable of understanding a lot of it. (I was a musician and mother was an art teacher so Escher and Bach were quite familiar.) But it was still entertaining and gave me an appreciation of a lot of stuff that later became applicable in college while pursuing a math minor.

It basically just says that, for certain types of mathematical systems (I can never remember the actual definition, but it ends up being most systems we care about), there will always be theorems that are _independent_ of the axioms of the system and/or that the system itself is _inconsistent_ (i.e. implies a contradiction). An independent statement is a statement that cannot be definitely proven true or false _within_ that system. Or, more precisely, there will be _models_ of the system where the statement is true and others where its false.

The analogy that I typically use is that, for a given work of fiction, there will almost certainly be questions that have no canonical answer because the author simply hasn’t provided sufficient information within the canon to answer. For example, in the Harry Potter universe, there’s no canonical answer to the question of how _exactly_ a horcrux is made because J.K. Rowling never specified. Hence, there can be fan fictions that answer the question one way and others that answer it a different way, and, all else equal, each one would be equally valid, so long as they don’t contradict anything from the original work. Of course, this is only an analogy and certainly an imperfect one, but it really helped me get comfortable with the idea of something being “true in one model but false in another.”

Ravaturno’s corollary: You can choose to be consistent or complete but not both at the same time. Example: Science is consistent but will never know everything; religion is “complete” but full of contradictions.

I like to use the following example.

Let’s say we have a library and are creating useful indexes for it.

We make a red book that lists all the library books that refer to the themselves. Encyclopedias, dictionaries, etc.

We make a green book that lists all the library books that don’t refer to themselves. That will be most of them.

Now, logicians and mathematicians started the 20th century working on the rules of logic that would let us decide for every statement whether it was true or false. Somewhere God should have an answer book listing all the true statements in our system of logic. For any function we would like to be able to determine whether F(x) or not F(x) is in God’s answer book.

Russel’s paradox asks: “Does the green book lists itself?” We can’t answer “yes,” because if it does it shouldn’t. We can’t answer “no” because if it doesn’t, it should. We can’t find either F(x) or not F(x) in God’s answer book. Oops.

And there is another question we could ask. “Does the red book list itself?” If it does…great! “F(red book)” goes in God’s answer book. If it doesn’t…great! It shouldn’t! “Not F(red book)” goes in God’s answer book.

Oops. We don’t want both F(x) and notF(x) to be true.

You probably think “this book refers to itself” sounds like a really weird function. Maybe we can just leave it out of our system of logic? Sweep the problem under the rug.

But Gödel proved that any formal logic with enough tools to include statements like (1+2=3) will have this problem.

Math is a language that is build by a few rules, for example, x+y = y+x, and with these rules mathmaticians try to proof every statement they make. The dream of mathematics was to have a language that is in itself consistent and complet, in which you can speak about everythink and proof it.

Gödel showed that there can never be such a language. you can for example have a statement about infinity and the proof for this statement takes infinit steps, so it is not provable. The part of math that actualy work without infinit steps is constructive mathematics aka computation. In math you work with lim (limes) which is like saying we take a really big nummer because we cant go to infinity. Or in the limit it will behave very much like infinity, but we dont calculate it because it would take infinit steps.

a system can be complete or consistent. not both.

therefore there are unknowable truths of math and logic for instance.

This problem’s unsolvable. This problem’s unsolvable. This problem’s unsolvable. This problem’s unsolvable. Here… let radiolab ELI5 this for you! Doesn’t quite sound like it at first, but the part about Godel starts in the beginning.

https://www.wnycstudios.org/podcasts/radiolab/segments/161758-break-cycle

For a long time in mathematics the words *true* and *provable* meant the same thing.

Godel showed that they are not. There can be true statements that are unprovable.

It means that any fixed Turing-recognizable model of arithmetic will either fail to prove some factually true things about arithmetic, or else it will be inconsistent, meaning that it will prove everything, including false things. In that sense, every Turing-recognizable and consistent model of arithmetic is “incomplete,” since it will have “blind spots” in terms of true things for which it actually provides a proof. It means that no fixed formal computational model of arithmetic can account for all of the things that are actually true about arithmetic.

Basically, any reasonable mathematical system will have some statements that can never be proven true or false.

The easiest way to understand what this means is, ironically, is by listening to children

“Mom, why is the world round?”

“Because we have gravity, that pulls all the dirt and water into a ball.”

“Why?”

“Because anything with mass emits a little bit of gravity.”

“Why?”

“…. Because it just does…”

**”Why Mother?”**

(Side note: Oversimplified Example is Oversimplified)

The reason most parents get infuriated by this incessant “Why? Why? Why? Why?” is because kids don’t understand this principle yet. If you keep asking “Why”, the answer will eventually become “Because it is”

No matter what system of logic you use, some things just **are**. Every system of logic has certain universal principles that are just facts. You can’t really prove why 1+1=2. That’s just how arithmetic works.