Blog Abstract: In mathematics the obvious choice is not always the right one. This applies even to the very definition of “truth”.
Since mathematicians spend all day trying to prove things are true, one would imagine that the definition of “truth” would be unambiguous. But the definition of truth was once hotly debated in mathematics. The classical view, taken since the days of Aristotle, says that a statement is true if it is not false. But another school of thought, known as Intuitionism, says that a statement is true only if we can provide a “witness” of the proposition that creates the objects in question.
To illustrate how these views differ, and what a witness looks like, we’ll explore Euclid’s classic proof that there are infinitely many primes:
Suppose there were only finitely many prime numbers. If we were to multiply all of these numbers together, we will get another number N which is divisible by every prime. But N + 1 cannot be a multiple of any prime, hence N + 1 is prime. But N + 1 is bigger than every number in our list of every prime number. Hence there are not finitely many primes.
This tells us there cannot be finitely many prime numbers, but it doesn’t tell us how to find those primes. But we can tweak the proof a little to get a much stronger result.
If we have a finite list of numbers such that no two numbers in that list share a common factor, then we can grow that list by one element by appending all of the numbers multiplied together, plus one. The numbers in this new list still have no common factors, hence we can get arbitrarily many numbers that don’t share a factor. We can factorise each number in the list to get a list of prime numbers. So we can get a list of arbitrarily many prime numbers by starting with the list containing only the number 2 and repeatedly growing our list.
Both proofs tell us there are infinitely many primes, but the second provides a witness of this fact by describing a method that allows us to compute as many prime numbers as we want. This is called a constructive proof. Because constructive proofs give us stronger results, one may wonder what happens if we use a system of logic that only allows constructive proofs. These are so called “intuitionistic” or “constructive” logics. The properties of these systems are somewhat surprising. The first thing that you notice is that the statement that a proposition is either true or not true, does not necessarily hold. Another common statement, that if a proposition is not false then it is true, also doesn’t hold. This may seem unnecessarily restrictive, but it’s actually a strength. The lack of these statements allows the semantics of intuitionistic logic to become much more intricate than classical logic. Because of this intuitionistic logic arises naturally throughout mathematics and shows up in fields such as topology, category theory, and algebraic geometry.
Isaac Bankier
University of Wollongong
