Math has a flaw

Primary Source video: Math has a flaw - Veritasium

There will always be statements in math that are true but can never be proven to be so.

What are those statements? No one knows... It's possible to know if a statement cannot be proven but there aren't real math statements that are known to be this way.

Something that could be this is the "Twin prime conjecture" which predicts that there are infinitely many twin primes (primes that have a difference of 2).

Game of life

Also known as John Conway's game of life is a 0 player game with simple rules.

The game is played on an infinite grid of square cells, each of which is either alive or dead. Any dead cells with exactly 3 alive cells come to life and any living cell with less than 2 or more than 3 neighbors die.

Different initial conditions lead to different outcomes. Some lead to a pattern that just fizzle out, some to patterns that grow forever and some come to an equilibrium state where they are either in a loop, static or moving forever.

The ultimate fate of a pattern in the game is undecidable. There is no algorithm that is guaranteed to tell you what will happen within a a finite amount of time.

Set Theory

In 1874, Georg Cantor published a paper on Set Theory. A set is just a well defined collection of things.

Set theory explained - wip

He wondered if there were more natural numbers or more real numbers between 0 and 1. Although there are an infinite number of both, they are not the same size. You can prove that there are more real numbers between 0 and 1 than there are natural numbers.
You use something called the "Cantor's Diagonalization Proof" to prove this.

Proof:

Let's first assume that there is an equal amount of natural and real numbers between 0 and 1. This means that you can map out each natural number to a real number between 0 and 1. You would have a complete list of this 1:1 mapping.

Now, let's construct a new number. Take the first digit of the first number add 1 and take the second digit of the second number and add 1, if the digit is a 9 roll it back to an 8.

So you would have a number that you have constructed that would be different from all the other numbers in the list by at least one digit. This new number will not be found on the list. Which is a contradiction. This contradiction arose due to the wrong assumption. Hence, there are more real numbers between 0 and 1 than there are natural numbers.

With a reference to the Hilbert Hotel where you could fit an infinite number of buses of infinite people into the hotel but you won't be able to fit all the real numbers from 0-1, because, as we proved, it's larger.

These numbers such as, all natural numbers is called "Countable infinity" the real numbers between 0 and 1 are called "Uncountable infinities"

Self-reference issue

In 1901, Bertrand Russell pointed out a problem in Cantor's set theory. If sets can contain anything then they can even contain themselves!

For example: The set of all sets must contain itself. As does the set of sets with more than 5 elements.

This leads to a problem, R= The set of call sets that don't contain themselves. If R doesn't contain itself then it must contain itself but if it does contain itself then by definition it must not contain itself. So R contains itself if and only if... it doesn't.

This is called the "Paradox of self-reference".

This problem was solved by restricting the concept of a set so the collection of all sets is not a set anymore. Similarly, the set of all sets that don't contain themselves is not a set. This eliminated the problems that came with self-reference. But this wasn't the end of self-reference.

Self-reference

Hao Wang was looking into a problem called Wang tiles. These were square tiles with different colors on each side. The rules are simple, touching edges must be the same color and you can't rotate or reflect tiles, only slide them around. The question is: if you are given an arbitrary set of these tiles, can you tile the plane.

You can't tell for an arbitrary set of tiles if they will tile the plane or not. The problem is undecidable, just like the game of life.

These problems occur, ultimately, due to self-reference!

Systems of proof

A system of proof starts with axioms, basic statements that are assumed to be true. Proofs are then constructed from these axioms using rules of inference.

The goal of Hilbert was to get a formal system of proof. A symbolic logical language with a rigid set of manipulation rules for those symbols.

If you drop a book, then it will fall can be expressed as A then B. Similarly, you can express that no human is immortal like follows:

The most important aspect of trying to create a formal system such as this was the fact that you could prove properties of the formal system itself.

The 3 big questions about math

• Is math complete? Does every true statement have a prove?
• Is math consistent? Is it free of contradictions? You shouldn't be able to prove both A and not A.
• Is math decidable? Is there an algorithm that can always determine whether a the statement follows from the axions?

Hilbert: "In opposition to the foolish ignoramus our slogan shall be We must know - we will know."

Ignoramus: we will never know.

Godel's incompleteness theorem

Kurt Godel had found that a complete formal system of mathematics is not possible.

Godel assigned each symbol in math a number which he called the Godel number. The symbol for "Not (~)" has the Godel number of 1 and "OR (V)" has the number 2.

0 get's it's own Godel number 6. If you want to write 1 you just put a successor symbol next to zero.

Each equation, such as 0 = 0 (which have the Godel numbers 6, 5, and 6) can be their own card with their own Godel number. The way to get a Godel number for an equation if to take the prime numbers and raise each one to the power of the Godel numbers of the equation.

So 0=0 has a Godel number of 234 Million.

Each symbol will have a Godel number and so will each equation. This will be an infinite number of Godel numbers. In this whole system, there are going to be true statements and there are going to be false statements.

How do you prove something is true:

You need to refer to the axioms, which are also formed in the same way as any other equation.

So the above proves that 1 does not equal 0 and it's given a Godel the number just like the rest using the same format.

Godel goes through all this trouble to find one statement in his system: "There is no proof for the statement with Godel number g" and the fun part, the Godel number of this statement is g!

So the statement talks about itself. And what the statement is really saying is that the statement is not provable! There is no proof anywhere in the system.

If this statement is false, then what you have proven is that there is no proof which leads to a contradiction! This must mean that the statement is true!

That means that the mathematical system has true statements in it that are not provable! That means mathematics is incomplete!

Mathematicians hoped that this is just something that comes when you perform these self-referencing acts but that is not the case.

Godel's second incompleteness theorem

In this, he proves that any formal consistent system cannot prove it's own consistency!

With the two incompleteness theorems, Godel proved that the best you could hope for is a system that is incomplete but is consistent. But such a system cannot prove its own consistency and hence a contradiction may crop up in the future revealing that the system you've been working with has been inconsistent!

Alan Turing's turing machine

In 1936, Alan Turing had to invent the modern computer!

Turing imagined a computer that could perform any mathematical operation but simple any to be able to reason through it's operation.

So he came up with a machine that takes as input an infinitely long tape of 0s and 1s. The machine has a read-write head that can read one digit at a time and it can perform one of only a few tasks, overwrite a new value, move left, move right or just halt. When a program halts it's completed.

The program consists of a set of internal instructions which tell the machine what to do based on its internal state and the digit it reads. This program can be exported to any other turing machine which would then perform in exactly the same way as the first.

Although this sounds simple, a turnig machine's arbitrarily large memory and program means it can execute any computable algorithm, given enough time. Addition, subtraction, or even the entire google search algorithm.

When a turing machine halts, the program has stopped running and the tape is the output. But sometimes a turing machine never halts. It is possible to tell whether a program will halt or not before it's executed? This halting problem is similar to the decidability problem. If you could figure out if a program will halt or not you can also tell if a statement will follow from the axioms.

For example, you could solve the twin prime conjecture but writing a turing machine program that states with the axioms and constructs all theorems that can be produced in one step by using the rules of inference. Then 2 steps, then 3, and so on. It halts only if each time it generates new theorems if one of them is the twin prime conjecture.

Let's assume a machine h that can determine whether a turing machine will halt or not on a particular input. You insert the program and the input and h predicts what will happen. Printing out either halts or never halts.

We can modify the h machine by adding additional components. One, if h outputs halt the machine will go into an infinite loop or if it receives never halts then it immediately halts. (So basically the opposite of what the input program and its input would do.)

We can call this new machine h+.

We then export the program for h+. Now what happens if you give this the same machine its own code as both program and input.

Now h is simulating what h+ would do. Basically, h is trying to determine what a machine (One that contains h) would do. If h concludes that the program will stop then h+ will do the exact opposite and never stop. If h concludes that h+ will never halt then h+ will stop. No matter what h predicts h+ by definition will do the exact opposite of that.

This means that whatever output that h gives turns out to be wrong! Which is a contradiction. The only explanation is that a machine like h cannot exist. You cannot tell if a turing machine will halt or not on a given input!

This proves that maths is undecidable! There is no algorithm that can determine whether a statement is derivable from the axioms.

What this means is that there are statements in math that maybe can never be known! And you can't know if you can know!

Spectral Gap Problem

The undecidable nature of things comes up in the real world too.

The difference between the ground state and the first excited state of a many-body system. This is known as the spectral gap.

Some systems have a significant spectral gap and some are gapless all the way down to the ground state. This is important because gapless quantum systems can undergo phase transitions while gapped systems cannot, they don't have the energy needed to overcome the spectral gap.

This problem of whether a system is gapped or gapless has long been known to be a hard problem. In 2015, mathematicians proved that the spectral gap question is undecidable.

"Even a perfect, complete description of the microscopic interactions between a material's particles is not always enough to determine its macroscopic properties."