Subsection 3.2.1 Formal Systems
Further, mathematicians had long assumed there were consistent foundational axioms for their discipline. Newly discovered paradoxes challenged this view.
Exploration 3.2.1. Russell’s Paradox.
In a certain town lives a barber who only cuts the hair of all people who do not cut their own hair. Who cuts the barber’s hair?
Two main schools of mathematical philosophy sprung up in the wake of these discoveries. The formalists argued that statements of mathematics and logic are really just about the rules and consequences for manipulating symbols and strings of letters. That is, mathematics does not have a subject matter at all--just empty symbols, which may be given an interpretation in particular situations and thus have meaning.
The response came from the intuitionists . Intuitionism is an approach that considers mathematics to be purely the result of the constructive mental activity of humans rather than the discovery of any principles which we can reasonably claim exist in an objective reality. Thus, in some sense, mathematics is up to whoever is doing the mathematics. To the intuitionists, the formalists were reducing mathematics to a meaningless game with symbols.
Discussion 3.2.2.
What strikes you about the formalist and intuitionist approaches to mathematics? Why?
In 1900, at the second International Congress of Mathematicians in Paris, the esteemed mathematician David Hilbert posed 23 theretofore unanswered problems in mathematics that he thought were important to guide the development of mathematics in the 20th century. Most of Hilbert’s problems have been solved, but three are unresolved, two are thought to be too vague to ever get consensus on what a solution would look like, and one is the subject of much debate.
In an attempt to resolve the issues raised by paradoxes like Russell’s Paradox, Hilbert posed this problem, the second on the list:
But above all I wish to designate the following as the most important among the numerous questions which can be asked with regard to the axioms: To prove that they are not contradictory, that is, that a definite number of logical steps based upon them can never lead to contradictory results….
That is, Hilbert wanted mathematicians to prove that the axioms on which mathematics was founded did not lead to a contradiction. The resolution to this problem is surprising, and to begin to explore its solution, we will turn to the infinite.
Subsection 3.2.2 Infinity and Incompleteness
In
Subsection 3.2.1, we learned about the push from mathematicians in the late 19th/early 20th century were trying to show that the axioms, the very foundations on which mathematics was built, were both
complete (the truth of every sensible statement could be decided via deductions from the axioms) and
consistent (one could never deduce contradictory statements from the axioms).
For reasons which are hopefully clear, we’ll assume that the axioms are consistent, that is, no contradictions will arise from them. (If contradictions can arise, we are in trouble indeed.) But if the axioms are consistent, can it be shown that they’re complete? To answer this question, we dive into the realm of infinity.
Definition 3.2.3.
Let \(S\) and \(T\) be sets, which we may think of as collections of objects. We say that \(S\) and \(T\) have the same cardinality if there is a one-to-one correspondence between the objects of \(S\) and those of \(T\text{,}\) i.e., if each element of \(S\) can be paired up with one and only one unique element of \(T\text{.}\) In this case, we write \(|S| = |T|\text{.}\)
The idea that we can compare sizes of collections of objects by placing them in one-to-one correspondence is known to very young children. However, they are mostly concerned with finite collections. Georg Cantor’s crucial insight in studying the mathematics of the infinite was that one-to-one correspondences could also be used to study infinite collections of numbers. This is widely (though not universally) accepted today, but was the subject of much controversy in the late 19th century when he introduced it.
Activity 3.2.4.
Let \(S = \{1,2,3,4\}\text{,}\) \(T=\{\square,\circ,\bigstar,\triangle\}\text{,}\) and \(U = \{\diamondsuit,\spadesuit,\clubsuit\}\text{.}\)
Can you find a one-to-one correspondence between \(S\) and \(T\text{?}\) Describe it, or explain why none exist.
Can you find a one-to-one correspondence between \(S\) and \(U\text{?}\) Describe it, or explain why none exist.
Can you find a one-to-one correspondence between \(T\) and \(U\text{?}\) Describe it, or explain why none exist.
In order to explore our undecidable statement, we need to set some notation.
Definition 3.2.5.
We define the following sets of numbers.
The natural numbers are given by \(\mathbb{N} = \{1, 2, 3, \ldots\}\text{.}\)
The whole numbers are given by \(\mathbb{W} = \{0,1,2,3,\ldots\}\text{.}\)
The integers are given by \(\mathbb{Z} = \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}\text{.}\)
The even integers are given by \(2\mathbb{Z} = \{\ldots, -6, -4, -2, 0, 2, 4, 6, \ldots\}\text{.}\)
The set of rational numbers is denoted by \(\mathbb{Q}\) and consists of all fractions \(\frac{a}{b}\text{,}\) where \(a,b\) are integers and \(b\ne 0\text{.}\)
The set of real numbers is denoted by \(\mathbb{R}\) and is given by all positive and negative infinite decimals (alternatively, every point on the number line).
Activity 3.2.6.
For the numbers that follow, identify all sets described in
Definition 3.2.5 they live in.
\(\displaystyle 7\)
\(\displaystyle -2\)
\(\displaystyle \pi\)
\(\displaystyle \frac{4}{3}\)
\(\displaystyle 0\)
We now look for some one-to-one correspondences.
Exploration 3.2.7.
For the following pairs of sets, determine whether a one-to-one correspondence between the two sets exists. If it does, describe it. If it does not, give a justification.
\(\mathbb{N}\) and \(\mathbb{W}\)
\(\mathbb{W}\) and \(\mathbb{Z}\)
\(\mathbb{Z}\) and \(2\mathbb{Z}\)
\(\mathbb{N}\) and \(2\mathbb{Z}\)
(Challenge) \(\mathbb{N}\) and \(\mathbb{Q}\)
Exploration 3.2.8.
Let’s explore the relationship between the cardinalities of \(\mathbb{N}\) and \(\mathbb{R}\) by considering the interval \([0,1]\) consisting of all real numbers (points on the number line) \(x\) satisfying \(0 \le x \le 1\text{.}\) We will use the notation \(0.a_1 a_2 a_3 \ldots\) to denote the infinite decimal with tenths place value \(a_1\text{,}\) hundredths \(a_2\text{,}\) and so on.
What is the relationship between \(|\mathbb{R}|\) and \(|[0,1]|\text{?}\)
Suppose we have a one-to-one correspondence between
\(\mathbb{N}\) and
\([0,1]\text{.}\) Explain why this means that we can write
\begin{align*}
1 \amp \leftrightarrow 0.d_{11}d_{12}d_{13}\ldots\\
2 \amp \leftrightarrow 0.d_{21}d_{22}d_{23}\ldots\\
3 \amp \leftrightarrow 0.d_{31}d_{32}d_{33}\ldots\\
\amp \vdots
\end{align*}
where
\(d_{ij}\) is the
\(j\)th decimal digit of the
\(i\)th number on the list.
Define a real number
\(M = 0.e_1 e_2 e_3 \ldots\) where
\(e_j = 2\) if
\(d_{jj} \ge 5\) and
\(e_j = 7\) if
\(d_{jj} \lt 5\text{.}\) Suppose the first three numbers on the list above are
\begin{align*}
\amp 0.4548430426\ldots\\
\amp 0.4607677961\ldots\\
\amp 0.4702962689\ldots
\end{align*}
What is
\(M\) in this case?
In general, is it true that \(0 \le M \le 1\text{?}\)
Where is \(M\) on the list in Question 2?
What does your answer to the previous question suggest about the one-to-one correspondence we wrote down in Question 2?
What does your answer to the previous question suggest about the relationship between \(|\mathbb{N}|\) and \(|[0,1]|\text{?}\) Between \(|\mathbb{N}|\) and \(|\mathbb{R}|\text{?}\)
Discussion 3.2.9.
Given your responses to
Exploration 3.2.7 and
Exploration 3.2.8, do you think there is a set
\(S\) such that
\(|S| \gt |\mathbb{N}|\) and
\(|S| \lt |\mathbb{R}|\text{?}\) Why or why not?
In the early 1930s, the Austrian mathematical logician Kurt Gödel revolutionized mathematical logic with his two
incompleteness theorems. Informally, first incompleteness theorem states that any sufficiently strong, consistent formal system contains undecidable statements. That is, there are sensible statements, such as the one raised in
Discussion 3.2.9, which cannot be proved from within the system. In that case, we may choose to adopt either the statement
or its negation as an additional axiom, and may do so without creating any contradiction.
The question in
Discussion 3.2.9 leads to just such a proposition, namely that no such set
\(S\) exists. This has been known as the
continuum hypothesis. It was first suggested by Cantor in 1878, and was one of Hilbert’s 23 problems. Gödel himself proved in 1940 that its negation, i.e., that such a set
\(S\) does exist, is independent of the usual axioms of set theory. The mathematician Paul Cohen proved in 1963 that the continuum hypothesis itself is independent of the usual axioms of set theory, thus verifying that the hypothesis is undecidable.
