In the 19th century, mathematicians sought to re-found all the ancient disciplines of mathematics (geometry, arithmetic) as well as the newer disciplines (calculus, complex analysis, topology) on a firm foundation, expressed in a single abstraction: sets. A set is described as a "collection of elements". The term "collection" is meant only to build intuition, because in reality, sets are "undefined terms", like the points and lines of Euclidean geometry. The undefined terms are only made meaningful through a set of axioms. Axioms are statements that are assumed to be true, for the sake of argument. The axioms of set theory (Zermelo-Fraenkel set theory) are:
Axioms of ZF Set theory
- Axiom of Extensionality: Two sets are equal if they have the same elements.
- Axiom of Regularity (or Foundation): Every non-empty set A contains an element that is disjoint from A.
- Axiom of Pairing: For any two sets, there is a set that contains them as elements.
- Axiom of Union: For any set of sets, there is a set that contains all the elements of those sets.
- Axiom of Infinity: There exists a set that contains the empty set and is closed under the operation of forming the union of a set with its singleton.
- Axiom of Power Set: For any set, there is a set of all its subsets.
- Axiom of Replacement: If a class function is defined on all elements of a set, then its range is also a set.
There is another axiom that is sometimes used, but it's not without it's controversy, that's the Axiom of Choice:
Axiom of Choice
For any set of non-empty sets, there exists a choice function that selects one element from each set in the collection.
Georg Cantor and the infinite
Georg Cantor was a prophet. He's widely known as a mathematician who first developed axiomatic set theory and the theory of infinity (Transfinite Numbers), but I call him a prophet because of what motivated him to study the infinite with such rigor and intensity.
From Georg Cantor: The Personal Matrix of His Mathematics:
From Georg Cantor: The Personal Matrix of His Mathematics:
The religious dimension which Cantor attributed to his transfinite numbers should not be discounted as an aberration. Nor should it be forgotten or separated from his existence as a mathematician. The theological side of Cantor's set theory, though perhaps irrelevant for understanding its mathematical content, is nevertheless essential for the full understanding of his theory and why it developed in its early stages as it did.
Of the many unbelievable things Cantor proved, he proved that there were multiple sizes of infinity. Before we get there, we have to revisit something posted above, 5. Axiom of Infinity. This axiom states that there exists a set that contains the empty set, and which is closed under the operation of forming a union of a set with its singleton.
In set theory notation:
$$\exists A : \emptyset \in A \text{ and } x \in A \implies \{x\} \in A$$
This can be interpreted as saying there is at least one infinite set. We know that the empty set is in the set A, and if anything is in A, then we can construct another set, which is the singleton containing it, then by definition that's in A too. We can recursively take this singleton and then make a singleton out of that, and so on... infinitely many times. All are contained in A, so A is infinite.
Since the Axiom of Infinity is an axiom, it is assumed and not proven. Because proofs have to take a finite number of steps, the only way we can prove anything about the infinite is by setting up axioms like this as a starting point. So, how do we go from 5. Axiom of Infinity to multiple sizes of infinity?
Diagonalization
The Axiom of Infinity doesn't really need to be assumed if you believe that integers exist. You can encode the integers like this:
$$\begin{align*} \emptyset &= 0 \\ \{ \emptyset \} &= 1 \\ \{\{ \emptyset \}\} &= 2 \\ ... & \\ \end{align*}$$
Then, consider the set (0,1) of all real numbers strictly between 0 and 1. This includes rationals, irrationals, transcendentals, all of them. They are all real numbers greater than 0 and less than 1. Cantor proves that the set (0,1) is larger than the whole infinite set of integers from 0 up! That is, Cantor's Diagonalization Theorem proves that $$|\{0,1,2,3,4,....\} | < |(0,1)|$$
The proof uses the method of Proof by Contradiction:
Note: "the continuum" refers to the continuous interval of real numbers (0,1)
$$\begin{align*} \emptyset &= 0 \\ \{ \emptyset \} &= 1 \\ \{\{ \emptyset \}\} &= 2 \\ ... & \\ \end{align*}$$
Then, consider the set (0,1) of all real numbers strictly between 0 and 1. This includes rationals, irrationals, transcendentals, all of them. They are all real numbers greater than 0 and less than 1. Cantor proves that the set (0,1) is larger than the whole infinite set of integers from 0 up! That is, Cantor's Diagonalization Theorem proves that $$|\{0,1,2,3,4,....\} | < |(0,1)|$$
The proof uses the method of Proof by Contradiction:
Note: "the continuum" refers to the continuous interval of real numbers (0,1)
Proof:
Suppose that there exists a 1-to-1 correspondence between the integers and the continuum.
Then you can write a table like this:
$$\begin{align*} r_1 &\leftrightarrow 0.123456789\ldots \\ r_2 &\leftrightarrow 0.234567890\ldots \\ r_3 &\leftrightarrow 0.345678901\ldots \\ &\vdots \end{align*}$$
Now, take the first digit of r₁, increment it by 1, then the second digit of r₂, increment it by 1, etc. (and if any are 9, just roll around to 0). Do this all the way down the list. You will have constructed a number, a real number, between 0 and 1, which is not in the original list. This ability to generically construct an element that's not in the set is the thing that contradicts the setup of the proof. The assumption that there exists such a 1-to-1 correspondence leads to this contradiction where we can trivially find a number in one set that simply isn't matched by an integer. This is the reductio ad absurdum. There are simply more real numbers in (0,1) than all integers.
The legendary mathematician David Hilbert once said:
$$\begin{align*} r_1 &\leftrightarrow 0.123456789\ldots \\ r_2 &\leftrightarrow 0.234567890\ldots \\ r_3 &\leftrightarrow 0.345678901\ldots \\ &\vdots \end{align*}$$
Now, take the first digit of r₁, increment it by 1, then the second digit of r₂, increment it by 1, etc. (and if any are 9, just roll around to 0). Do this all the way down the list. You will have constructed a number, a real number, between 0 and 1, which is not in the original list. This ability to generically construct an element that's not in the set is the thing that contradicts the setup of the proof. The assumption that there exists such a 1-to-1 correspondence leads to this contradiction where we can trivially find a number in one set that simply isn't matched by an integer. This is the reductio ad absurdum. There are simply more real numbers in (0,1) than all integers.
The legendary mathematician David Hilbert once said:
No one shall expel us from the Paradise that Cantor has created.
This world of set theory and infinite numbers is larger than anything our earthly minds can conceive of. It has the mathematical precision that would satisfy most scientists, but it begins with an act of faith, the commitment to an axiom, which would be more familiar to theologians. The infinite is something which can be quantified, but which still embodies the essential mystery of the universe in that it can never be fully known. It can only be grasped through proofs, starting from axioms accepted on faith, like the axiom of infinity. We have to believe that at least one infinite set exists, but when we do, we can prove that there are infinite sets that are strictly larger than the one we chose to believe in. There are either no infinities or infinitely many, and this is something about which we can be certain.