Some Final Thoughts on the Limits of Proof
During this course we’ve learned some of the basic methods and concepts used by mathematicians.
In particular, we’ve learned how to use proofs to demonstrate the truth of statements about mathe-
matical 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 (such as Cantor’s)
caused a foundational crisis in mathematics. If a concept as basic as set is self-contradictory, how
are we to have faith in any mathematical conclusion?! The response to this crisis was an effort to
formulate a list of reasonable axioms from which all mathematics could be derived using basic logical
reasoning. Such an axiomatic foundation would ideally satisfy two conditions:
• Consistency: No contradiction can be derived from the axioms.
• Completeness: All true mathematical statements could be derived from the axioms.
Any hope for such a foundation was crushed in 1931, when Kurt G
¨
odel published his famous Incom-
pleteness Theorems, showing that no such axiomatic system could exist. Very roughly, G
¨
odel showed
that in any consistent axiomatic system strong enough to produce some basic arithmetic, there are
undecideable statements; neither deducible 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. The most pop-
ular approach is to base all of mathematics on set theory—as your studies progress, you’ll see that
many of the objects you study can be formalized as sets together with functions and relations be-
tween them. We’ve started this work already: Chapter 7 says that functions and relations are them-
selves sets! Numbers like 0, 1, 2,
12
19
or even π = 3.14 . . . can be thought of as sets if one so desires.
In turn, set theory is often axiomatized using the ZFC axioms (short for Zermelo–Fraenkel set theory
with the Axiom of Choice).
While the ZFC system remains subject to G
¨
odel’s limitations,
58
it has proven able to formalize most
of the mathematics actually used by current mathematicians, and has not (thus far!) produced any
inconsistencies. While there is plenty of fun to be had exploring set theory, its history and its quirks,
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))
58
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