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.

338 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

20 Answers

Anonymous 0 Comments

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.

Anonymous 0 Comments

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.

Anonymous 0 Comments

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.

Anonymous 0 Comments

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.

Anonymous 0 Comments

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…

Anonymous 0 Comments

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.

Anonymous 0 Comments

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

Anonymous 0 Comments

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.

Anonymous 0 Comments

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.

Anonymous 0 Comments

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.