Math's Fundamental Flaw

The Hole in Math

This section discusses the hole in math and how there will always be true statements that cannot be proven.

The Twin Prime Conjecture

• Twin primes are prime numbers separated by just one number.

• The Twin Prime Conjecture is that there are infinitely many twin primes.

• As of right now, no one has proven this conjecture true or false.

Conway's Game of Life

This section introduces Conway's Game of Life and its rules.

Rules of the Game

• The game is played on an infinite grid of square cells.

• Each cell is either live or dead.

• Any dead cell with exactly three neighbors comes to life.

• Any living cell with less than two or more than three neighbors dies.

Patterns in the Game

• Some patterns are stable and never change, while others oscillate back and forth in a loop.

• A few patterns can travel across the grid forever, while many patterns fizzle out.

• A few patterns keep growing forever and generate new cells.

Undecidability in the Game

• Given the simple rules of the game, it is impossible to determine what will happen to any pattern in a finite amount of time.

• The ultimate fate of a pattern in Conway's game of life is undecidable, meaning there is no possible algorithm that can answer the question in a finite amount of time.

Georg Cantor and Set Theory

This section discusses Georg Cantor's set theory and his question about sets of numbers.

Sets and Numbers

• A set is a well-defined collection of things.

• Cantor was thinking about sets of numbers like natural numbers, positive integers, real numbers which include fractions like a third five halves and also irrational numbers like pi e and the square root of two.

Cantor's Question

• Cantor wondered if there are more natural numbers or more real numbers between zero and one.

• To check this logic, Cantor imagined writing down an infinite list matching up each natural number on one side with a real number between zero and one on the other.

Cantor's Diagonalization Proof

In this section, we learn about Cantor's diagonalization proof and how it shows that there are more real numbers between 0 and 1 than there are natural numbers.

Cantor's Diagonalization Proof

• Cantor creates an infinite list with each integer acting like an index number for a unique identifier for each real number on the list.

• To create a new real number, take the first digit of the first number and add one. Then take the second digit of the second number and again add one. Keep doing this all the way down the list. If the digit is nine, roll it back to eight.

• The resulting number won't appear anywhere on our list because it has to be different from every number on the list by at least one digit.

• This is called Cantor's diagonalization proof, which shows that there must be more real numbers between 0 and 1 than there are natural numbers.

Upheaval in Mathematics

In this section, we learn about how mathematics was shaken up by discoveries such as non-Euclidean geometries and Cantor's work.

Upheaval in Mathematics

• At the turn of the 19th century, Lobashevsky and Gauss discovered non-Euclidean geometries which prompted mathematicians to examine more closely their field's foundations.

• A huge debate broke out among mathematicians at the end of the 1800s. On one side were the intuitionists who thought that Cantor's work was nonsense and that infinities like Cantors weren't real.

• On the other side were the formalists who thought that math could be put on absolutely secure logical foundations through Cantor's set theory.

• David Hilbert, a hugely influential mathematician, was convinced that a more formal and rigorous system of mathematical proof based on set theory could solve all the issues that had cropped up in math over the last century.

Russell's Paradox

In this section, we learn about Russell's paradox and how it challenged Cantor's set theory.

Russell's Paradox

• Bertrand Russell pointed out a serious problem in Cantor's set theory. If sets can contain anything, they can contain other sets or even themselves.

• This leads straight to a problem. What about r, the set of all sets that don't contain themselves?

• If r doesn't contain itself, then it must contain itself. But if r does contain itself, then by definition it must not contain itself. So r contains itself if and only if it doesn't.

• Russell later explained his paradox using an analogy involving a village populated entirely by grown men with a strange law against beards. The barber must shave all and only those men of the village who do not shave themselves but who shaves him?

The Paradoxes of Self-Reference

This section discusses how the paradoxes of self-reference in mathematics were resolved by restricting the concept of a set.

Resolving Russell's Paradox

• The paradoxes of self-reference in mathematics were resolved by restricting the concept of a set.

• Hilbert and other mathematicians from his school solved the problem by restricting the collection of all sets, so it is not a set anymore, and neither is the collection of all sets that don't contain themselves.

Hao Wang's Tiling Problem

• Mathematician Hao Wang was looking at square tiles with different colors on each side.

• It turns out that for an arbitrary set of these tiles, you can't tell if they will tile the plane or not.

• This problem is undecidable and ultimately comes from self-reference.

Hilbert's Formal System

This section discusses Hilbert's formal system for mathematical proofs.

Systems of Proof

• A system of proof starts with axioms, basic statements assumed to be true.

• Proofs are then constructed from those axioms using rules of inference methods for using existing statements to derive new statements chosen to preserve truth.

Hilbert's Dream

• Hilbert wanted a formal system of proof, a symbolic logical language with rigid manipulation rules for those symbols.

• Hilbert wanted to express the axioms of mathematics as symbolic statements in a formal system and set up the rules of inference as the system's rules for symbol manipulation.

Principia Mathematica

• Russell and Whitehead developed a formal system like this in their three-volume Principia Mathematica published in 1913.

• The notation is dense and exhausting, but it is also exact, unlike ordinary languages.

Hilbert's Three Big Questions

This section discusses Hilbert's three big questions about mathematics.

The Three Big Questions

• There were three big questions that Hilbert wanted answered about mathematics.

• Number one is math complete meaning is there a way to prove every true statement does every true statement have a proof?

• Number two is mathematics consistent meaning is it free of contradictions?

• Number three is math decidable meaning is there an algorithm that can always determine whether a statement follows from the axioms?

Gödel's Incompleteness Theorem

• Kurt Gödel explained that he had found the answer to the first of Hilbert's three big questions about completeness, and the answer was no.

• By showing that any formal system capable of expressing basic arithmetic cannot be both consistent and complete, Gödel proved his incompleteness theorem.

Gödel's Proof

In this section, we learn about Gödel's proof and how he used logic and mathematics to answer questions about the system of logic and mathematics. We also learn about the concept of Gödel numbers, which are assigned to each symbol in a mathematical system.

Assigning Numbers to Symbols

• Gödel assigned a number to each basic symbol in a mathematical system.

• This is known as the symbol's Gödel number.

• For example, the symbol for "not" gets the number one, while "or" gets the number two.

• Zero gets its own Gödel number six, and if you want to write one, you just put the successor symbol next to it.

Creating Equations with Gödel Numbers

• We can create equations using Gödel numbers for all symbols and numbers we might want to use.

• To represent an equation like zero equals zero, we take prime numbers starting at 2 and raise each one to the power of the corresponding symbol's Gödel number.

• The resulting product is a unique Gödel number that represents that equation.

Proving Statements with Axioms

• To prove statements in this system, we need axioms that also have their own unique Gödel numbers.

• We can substitute values into these axioms to create proofs for statements like "one does not equal zero."

• However, there will always be true statements within this system that have no proof or are unprovable. This is known as Gödel's incompleteness theorem.

Gödel's Incompleteness Theorem

This section discusses Gödel's incompleteness theorem and its implications for mathematics.

Gödel's Incompleteness Theorem

• Truth and provability are not the same thing.

• Any consistent formal system of math cannot prove its own consistency.

• The best you can hope for is a consistent yet incomplete system of math.

• Mathematics decidable - is there an algorithm that can always determine whether a statement follows from the axioms?

Turing Machines

This section discusses Alan Turing's invention of the modern computer, which he called a Turing machine.

Turing Machines

• A mechanical computer that takes as input an infinitely long tape of square cells each containing a zero or a one.

• A set of internal instructions tells the machine what to do based on the digit it reads and its internal state.

• A Turing machine's arbitrarily large memory and program mean it can execute any computable algorithm if given enough time.

Halting Problem

This section discusses the halting problem, which asks whether it is possible to tell beforehand if a program will halt or not on a particular input.

Halting Problem

• If we could find a way to figure out if a Turing machine would halt then it would also be possible to decide if a statement followed from the axioms.

• Turing imagined a machine H that can determine whether any Turing machine will halt or not on a particular input.

• We can modify the H machine by adding additional components to create a new machine called H plus.

Conclusion

This section concludes the video and summarizes the main points discussed.

Conclusion

• The halting problem is unsolvable, which means there are some problems in mathematics that cannot be solved by an algorithm.

• Alan Turing's work laid the foundation for modern computing and computer science.

The Halting Problem

In this section, we learn about the halting problem and how it relates to Turing machines. We also discover that mathematics is undecidable.

The Behavior of a Machine

• H simulates what H+ would do given its own input.

• If H concludes that H+ never halts, then this makes H+ immediately halt.

• If H thinks H+ will halt, then that necessarily forces H+ to loop.

Undecidability in Mathematics

• There is no way to tell in general if a Turing machine will halt or not on a given input.

• This means mathematics is undecidable; there is no algorithm that can always determine whether a statement is derivable from the axioms.

• Mathematicians proved in 2015 that in general, the spectral gap question (whether a system is gapped or gapless) is undecidable.

Turing Completeness

In this section, we learn about touring completeness and how every touring complete system comes with its own analog of the halting problem.

Touring Completeness

• The best computational systems are those that can do everything a touring machine can; this is called touring completeness.

• Every touring complete system comes with its own analog of the halting problem.

• Examples of touring complete systems include Wang tiles, complex quantum systems, and the game of life.

Programming Languages

• Nearly every programming language in existence is designed to be Turing complete.

• In theory, we only need one programming language because any Turing complete system can program anything at all.

The Legacy of David Hilbert's Dream

In this section, we learn about the legacy of David Hilbert's dream and how it led to modern computational devices.

The Legacy of David Hilbert's Dream

• Kurt Gödel suffered bouts of mental instability later in life convinced that people were trying to poison him.

• Alan Turing put his ideas about computing to practical use in World War II leading the team at Bletchley Park that built real calculating machines to crack Nazi codes for the allies.

• By one estimate, the intelligence Turing and his colleagues gathered from decrypted messages shortened the war by two to four years.

• After the war, Turing and John von Neumann designed the first true programmable electronic computer ENIAC based on touring's designs.

Alan Turing's Life and Legacy

This section covers the life and legacy of Alan Turing, including his conviction for gross indecency, his contributions to computer science, and his ideas about computability.

Conviction and Tragic End

• In 1952, the British government convicted Turing of gross indecency for being gay.

• As a result, he was stripped of his security clearance and forced to take hormones.

• In 1954, he tragically committed suicide.

Contributions to Computer Science

• Turing is widely considered to be the most important founding figure in computer science.

• All modern computers are descended from his designs.

• His ideas about computability came from his concept of the Turing machine.

Computability and Self-reference

• Turing's concept of the Turing machine stemmed from thinking about Hilbert's question: is math decidable?

• Code-breaking machines developed by Turing were based on these concepts.

• All modern computers stem from the weird paradoxes that arise from self-reference.

Infinity and Certainty

• There is a hole at the bottom of math that means we will never know everything with certainty.

• True statements will always exist that cannot be proven.

• This realization transformed the concept of infinity and changed the course of a world war.

Brilliant Sponsorship

• Brilliant is a website full of interactive courses on topics like math, physics, and computer science.

• Their logic course guides you through increasingly sophisticated puzzles.

• Viewers can get 20% off an annual subscription by signing up as one of the first 200 people.