
Title:
2116 Godel's Incompleteness Theorem

Description:

You may or may not have heard of Godel's Incomplete Theorem,

but since they are also mentioned in conjunction with the Halting Problem

and undecidability,

it worth saying a few words about them.

Godel's Incompleteness Theorem is named Austrianborn mathematician, Kurt Godel,

are concerned with mathematics,

but are actually closely related to undecidability

and as you might know, any mathematical system starts out

with a set of axioms.

What are axioms?

Axioms are statements which you assume to be true

without having any formal proof of them,

such as if A equals B

and B equals C, then A must also equal C

or you can always draw a line from one point to another point,

no matter where they are.

Those would be axioms.

Now axioms often sound very trivial, like this one here

or the fact that you can always draw a line between 2 points

but for many of them

there are actually scenarios where they are not true.

So axioms are the basis of

any mathematical theorem or proof.

Now what Kurt Godel showed, and it was a shocker at his time

and to many it is still today,

is the following:

So what Kurt Godel showed was that if you had a set of axioms

and they don't contradict each other

and they are listable,

which means you could have an algorithm that lists you all of these axioms,

so either they are finite or

they can even be infinite as long as you have an algorithm

that can produce them all; if this is the case,

then there are some statements

that are true but which you cannot prove

based on these axioms and this is what he meant by incompleteness

how he basically showed that

no matter what foundation you base

a mathematical system on,

as long as that is a consistent foundation,

then you can not prove everything

without adding additional axioms at least.

He also showed, and this is the second Incompleteness Theorem,

which is basically an extension of the first one

that a system of axioms

cannot not demonstrate its own consistency

and what that means is that

very informally,

a mathematical system can not be used to show that

it itself is consistent.

These 2 statements

are in a way very similar to the Halting Problem and Undecidability.

The axioms; you can think of those as programming statements.

So any program or algorithm

is composed of a number of simple instructions

that are then arranged,

and of course there is an infinite number of possible computer programs

that you can write, but they are made up of a fine set of building blocks

and the second Incompleteness Theorem

is of course very similar to undecidability

in the sense that it shows that

you cannot use a system to prove everything about that system,

very loosely speaking,

and the undecidability of the Halting Problem

and all of the other undecidable problems, of course

says that we cannot use algorithms

to calculate everything about algorithms.

I know that from a practical perspective

there's lots of criticism of this,

but truth be told, I just find that super fascinating.