Some Final Thoughts on the Limits of Proof
Throughout this course we’ve learned about some of the basic methods and concepts used by math-
ematicians. In particular, we’ve learned how to use proofs to demonstrate the truth of statements
about mathematical objects. As we finish, it makes sense to reflect on the limits of our methods.
By the early 20
th
century, the discovery of various paradoxes and contradictions (like Cantor’s) led
to a foundational crisis in mathematics. If a concept as basic as set is contradictory, how can we
have faith in any mathematical conclusion?! The result of this crisis was an effort to place all of
mathematics on a rigorous axiomatic basis by formulating a list of reasonable axioms from which all
of mathematics could be derived using basic logical reasoning. Such an axiomatic foundation ideally
would satisfy two conditions:
• Consistency: No contradiction could be derived from the axioms.
• Completeness: All true mathematical statements could be derived from the axioms.
All hope for such a foundation was crushed in 1931, when Kurt G
¨
odel published his famous In-
completeness Theorems which showed that no such axiomatic system could exist. Essentially, G
¨
odel
showed that any consistent axiomatic system strong enough to produce some basic arithmetic, there
are undecideable statements; neither derivable nor refutable from the axioms. Perhaps even worse, no
such system can prove its own consistency.
While the strongest aims of early 20
th
axiomatics cannot be accomplished, contemporary research
was able to provide a foundation that most modern mathematicians deem adequate for current
work. Perhaps the most popular approach is to base all of mathematics on set theory—as your stud-
ies progress, you’ll see that many of the objects you study can be formalized as sets together with
functions and relations between sets. We’ve started this work already: Chapter 7 says that func-
tions and relations are themselves sets! Numbers like 0, 1, 2,
12
19
or even π = 3.14 . . . can be thought
of as sets if one desires. In turn, set theory is often axiomatized using the ZFC axioms (short for
Zermelo–Fraenkel set theory with the Axiom of Choice).
While ZFC is subject to the limitations imposed by G
¨
odel’s theorems,
59
they have proven able to
formalize most of the mathematics actually used by current mathematicians, and have not (thus
far!) produced any inconsistencies. While there is plenty of fun to be had exploring set theory,most
modern mathematicians feel little need to dwell on the foundational issues of last century!
Exercises 8.2. A reading quiz and practice question can be found online.
1. Decide the cardinality of each set. No working is necessary.
(a) N
≤12
(b) Z
≤12
(c) ( 0, 5] (d) [2, π] ∩Q (e) P
{R}
(f)
T
x∈R
+
[3 −
1
x
, 3 +
1
x
)
2. Find explicit bijections (thus showing that the given intervals have the same cardinality):
(a) f : [2, 3) → [1, 5) (b) g : [2, 3) → (1, 5] (c) h : (−3, 2) → R (d) j : R → (1, ∞)
(Hint: The proof of Corollary 8.13 should provide some inspiration—be creative)
3. Let B = [3, 5) ∪(6, 10). Use the Cantor–Schr
¨
oder–Bernstein Theorem to prove that
|
B
|
= c.
(Hint: State injective functions f : (0, 1) → B and g : B → (0, 1))
59
Perhaps the most famous undecidable statement in ZFC is relevant to our recent discussion: the continuum hypothesis is
the claim that no set has cardinality strictly between ℵ
0
and c; that intervals are the simplest (‘smallest’) uncountable sets.
119