Godel’s Incompleteness Theorem states that for any consistent formal system, within which a certain amount of arithmetic can be carried out, there are statements which can neither be proved nor disproved. Thereby setting bounds to what mathematics could prove.

English translation of the original paper:
https://www.jamesrmeyer.com/ffgit/god...

In this video we’ll examine the context for the theorem, get a gist of what it’s all about and then we’ll step through a semi-formal proof of it, for those who’d like to dig a little deeper.

At the start of 20th century mathematicians, such as David Hilbert, Bertrand Russell, Alfred North Whitehead, had a sense that given just the right set of axioms of a formal system, any mathematical theory could be proven to be true or false by systematically applying these axioms in a chain of logical operations. This is where Kurt Gödel, in his 1931 paper, shook the foundations of mathematics, proving that for any consistent formal system, within which a certain amount of arithmetic can be carried out, such as Paleo Arithmetic, there are statements which can neither be proved nor disproved.

The axiomatic system must be consistent, which means that no statement and it’s negation can both be derived by just following a different sequence of axioms and theorems.

And finally, the mention of “certain amount of arithmetic” refers to being able to at least enumerate the theorems of the language. So a very simple system that has no computing power, may in fact be consistent and entirely complete. But then it also won’t have the power needed to express even simple computations.

Let’s now examine how Godel proved his theorem. In essence, he constructed a legitimate, well formulated mathematical statement that implied that it itself is not provable.

To construct such a statement, we start with this linguistic paradox:

“This statement is not true”

Simply reading it out presents a problem, since if we were to assume that the statement is true, it’s meaning would suggest the opposite. On the other hand, if the statement is not true, then its implied meaning turns out to be true, hence the paradox.

So what would it take to construct a similar statement, but express it formally, in mathematical notation?

There are two immediate problems to handle. First of all, the word “true”, somewhat surprisingly, is not defined axiomatically. Numbers and formulas don’t have a property of “true”. We think of axioms as being defined to be true and any theorems that are derived from them would therefore also be true. But the concept of truth would then still be outside of the system itself.

Tarski's undefinability theorem:
https://en.wikipedia.org/wiki/Tarski%...

The other problematic word is “this”. It refers to the statement itself, without the statement having been defined yet. It’s like saying “This video is exactly 16 minutes and 9 seconds long” without first having made the video.

To get around this problem, Godel established a way to convert statements, such as theorems and even proofs of those theorems, into natural numbers as a type of encoding. Then, having listed encodings of specific kinds of formulas, he showed that there is a natural number in that list that corresponds to a formula that states its own unprovability.

Godel Encoding establishes a one to one correspondence between a unique sequence of characters and some unique number. This allowed Godel to convert any mathematical statement, as well as a proof of that statement into two unique numbers.

A Simple Proof of Gödel's Incompleteness Theorems
https://mat.iitm.ac.in/home/asingh/pu...

Examples of unprovable statements
https://en.wikipedia.org/wiki/Paris%E...

Further reading on Godel's Incompleteness Theorems:
https://plato.stanford.edu/entries/go...

Written and narrated by Andre Violentyev