## On the Brink of Paradox

by Rayo

### Instructor Requests

An introduction to awe-inspiring ideas at the brink of paradox: infinities of different sizes, time travel, probability and measure theory, and computability theory.

This book introduces the reader to awe-inspiring issues at the intersection of philosophy and mathematics. It explores ideas at the brink of paradox: infinities of different sizes, time travel, probability and measure theory, computability theory, the Grandfather Paradox, Newcomb's Problem, the Principle of Countable Additivity. The goal is to present some exceptionally beautiful ideas in enough detail to enable readers to understand the ideas themselves (rather than watered-down approximations), but without supplying so much detail that they abandon the effort. The philosophical content requires a mind attuned to subtlety; the most demanding of the mathematical ideas require familiarity with college-level mathematics or mathematical proof.

The book covers Cantor's revolutionary thinking about infinity,
which leads to the result that some infinities are bigger than others; time travel and free will, decision theory, probability, and the Banach-Tarski Theorem, which states that it is possible to decompose a ball into a finite number of pieces and reassemble the pieces so as to get two balls that are each the same size as the original. Its investigation of computability theory leads to a proof of Gödel's Incompleteness Theorem, which yields the amazing result that arithmetic is so complex that no computer could be programmed to output every arithmetical truth and no falsehood. Each chapter is followed by an appendix with answers to exercises. A list of recommended reading points readers to more advanced discussions. The book is based on a popular course (and MOOC) taught by the author at MIT.

Expand/Collapse All
Contents (pg. vii)
Preface (pg. ix)
I. Infinity (pg. 1)
1. Infinite Cardinalities (pg. 3)
1.1 Hilbert’s Hotel (pg. 3)
1.2 Size Comparisons (pg. 8)
1.3 Cantor’s Theorem (pg. 11)
1.4 Further Cardinality Questions (pg. 12)
1.5 Finite Sequences of Natural Numbers (pg. 12)
1.6 The Real Numbers (pg. 13)
1.7 The Power Set of the Natural Numbers (pg. 19)
1.8 Conclusion (pg. 21)
1.9 Further Resources (pg. 22)
Appendix: Answers to Exercises (pg. 23)
2. The Higher Infinite (pg. 31)
2.1 Living Large (pg. 31)
2.2 Ordinals (pg. 33)
2.3 Ordinal Arithmetic (pg. 43)
2.4 Ordinals as Blueprints (pg. 48)
2.6 Conclusion (pg. 54)
2.7 Further Resources (pg. 55)
Appendix: Answers to Exercises (pg. 56)
3.2 Rational Decision-Making (pg. 66)
3.3 Reverse Omega-Sequence Paradoxes (pg. 70)
3.4 Hat Problems (pg. 77)
3.5 Conclusion (pg. 84)
3.6 Further Resources (pg. 85)
Appendix: Answers to Exercises (pg. 86)
II. Decisions, Probabilities, and Measures (pg. 91)
4. Time Travel (pg. 93)
4.1 Time Travel (pg. 93)
4.2 The Grandfather Paradox (pg. 97)
4.3 Time Travel and Physical Law (pg. 99)
4.4 Free Will (pg. 107)
4.5 Conclusion (pg. 115)
4.6 Further Resources (pg. 115)
Appendix: Answers to Exercises (pg. 117)
5. Newcomb’s Problem (pg. 119)
5.1 The Problem (pg. 119)
5.2 Maximizing Expected Value (pg. 121)
5.3 In Defense of Two-Boxing (pg. 126)
5.4 Causal Decision Theory (pg. 130)
5.5 Conclusion (pg. 136)
5.6 Further Resources (pg. 136)
Appendix A: The Prisoner’s Dilemma (pg. 138)
Appendix B: The Tickle Defense (pg. 140)
Appendix C: Answers to Exercises (pg. 143)
6. Probability (pg. 149)
6.1 Probability, Subjective and Objective (pg. 149)
6.2 Subjective Probability (pg. 151)
6.3 Objective Probability (pg. 156)
6.4 The Principle of Countable Additivity (pg. 164)
6.5 Optional: The Two-Envelope Paradox (pg. 168)
6.6 Further Resources (pg. 171)
Appendix: Answers to Exercises (pg. 173)
7. Non-Measurable Sets (pg. 181)
7.1 Measure (pg. 181)
7.2 Non-Measurable Sets (pg. 188)
7.3 Conclusion (pg. 196)
7.4 Further Resources (pg. 196)
Appendix: Answers to Exercises (pg. 197)
8. The Banach-Tarski Theorem (pg. 205)
8.1 Three Warm-Up Cases (pg. 205)
8.2 The Theorem (pg. 212)
8.4 Further Resources (pg. 221)
Appendix: Answers to Exercises (pg. 222)
III. Computability and Gödel’s Theorem (pg. 227)
9. Computability (pg. 229)
9.1 Turing Machines (pg. 229)
9.2 Non-Computable Functions (pg. 237)
9.3 Efficiency (pg. 242)
9.4 Optional: The Big Number Duel (pg. 244)
9.5 Conclusion (pg. 247)
9.6 Further Resources (pg. 247)
Appendix: Answers to Exercises (pg. 248)
10. Gödel’s Theorem (pg. 255)
10.1 Gödel’s Incompleteness Theorem (pg. 255)
10.2 An Arithmetical Language (pg. 256)
10.3 A Proof of Gödel’s Theorem (pg. 261)
10.4 The Philosophical Significance of Gödel’s Theorem (pg. 265)
10.5 Conclusion (pg. 268)
10.6 Further Resources (pg. 269)
Appendix A: Proof of the Lemma (pg. 270)
Appendix B: Answers to Exercises (pg. 281)
Glossary (pg. 283)
Bibliography (pg. 295)
Index (pg. 299)

#### Agustín Rayo

Agustín Rayo is Professor of Philosophy at MIT and the author of The Construction of Logical Space.

Instructors
You must have an instructor account and submit a request to access instructor materials for this book.
 eTextbook Go paperless today! Available online anytime, nothing to download or install. 4 months / \$23.18 12 months / \$32.45