### Table of Contents

**The Diagonal Argument**

Counting and Countability

Does One Infinite Size Fit All?

Cantor’s Diagonal Argument

Transcendental Numbers

Other Uncountability Proofs

Rates of Growth

The Cardinality of the Continuum

Historical Background

**Ordinals**

Counting Past Infinity

The Countable Ordinals

The Axiom of Choice

The Continuum Hypothesis

Induction

Cantor Normal Form

Goodstein’s Theorem

Hercules and the Hydra

Historical Background

Computability and Proof

Formal Systems

Post’s Approach to Incompleteness

Gödel’s First Incompleteness Theorem

Gödel’s Second Incompleteness Theorem

Formalization of Computability

The Halting Problem

The Entscheidungs problem

Historical Background

**Logic**

Propositional Logic

A Classical System

A Cut-Free System for Propositional Logic

Happy Endings

Predicate Logic

Completeness, Consistency, Happy Endings

Historical Background

**Arithmetic**

How Might We Prove Consistency?

Formal Arithmetic

The Systems PA and PAω

Embedding PA in PAω

Cut Elimination in PAω

The Height of This Great Argument

Roads to Infinity

Historical Background

**Natural Unprovable Sentences**

A Generalized Goodstein Theorem

Countable Ordinals via Natural Numbers

From Generalized Goodstein to Well-Ordering

Generalized and Ordinary Goodstein

Provably Computable Functions

Complete Disorder Is Impossible

The Hardest Theorem in Graph Theory

Historical Background

**Axioms of Infinity**

Set Theory without Infinity

Inaccessible Cardinals

The Axiom of Determinacy

Largeness Axioms for Arithmetic

Large Cardinals and Finite Mathematics

Historical Background

### Author(s) Bio

John Stillwell was born in Melbourne, Australia in 1942 and educated at Melbourne High School, the University of Melbourne (M.Sc. 1965), and MIT (Ph.D. 1970). From 1970 to 2001 he taught at Monash University in Melbourne, and since 2002 he has been Professor of Mathematics at the University of San Francisco. He has been an invited speaker at several international conferences, including the International Congress of Mathematicians in Zurich 1994. His works cover a wide spectrum of mathematics, from translations of classics by Dirichlet, Dedekind, Poincare, and Dehn to books on algebra, geometry, topology, number theory, and their history. For his expository writing he was awarded the Chauvenet Prize of the Mathematical Association of America in 2005, and the AJCU National Book Award in 2009. Recent titles by Stillwell include Yearning for the Impossible, Mathematics and Its History, The Four Pillars of Geometry, and Geometry of Surfaces.

### Reviews

"The text is nicely presented, with many illuminating and/or entertaining quotes and diagrams. … The wide scope of the work and the way that the author manages to show the connections between the different topics are the main strength of the book, making it a good place to start if you have some interest in logic, set theory, or just challenging ideas in general."

—Yann Peresse, *London Mathematical Society Newsletter*, June 2013

"The book follows essentially two roads to infinity: Cantor’s diagonal argument and Cantor’s construction of the ordinals. Stillwell shows how these two themes intertwine and influence a wide range of mathematical questions … The scope of this book is breathtaking, but Stillwell has masterfully presented and developed a wide range of mathematics as a coherent narrative. … He is able to pack a lot of information and ideas into a few well-chosen paragraphs without sacrificing clarity. Stillwell is an accomplished historian of mathematics who doesn’t limit himself to the work of the well-known. I appreciated the appearance of some of the lesser known contributors to the study of the infinite. … It is well-conceived and well-written, and covers a large amount of material on logic, transfinite set theory, provability, combinatorics, and the histories of these fields."

—James V. Rauff, *Mathematics and Computer Education*, Winter 2012

"Stillwell is a master expositor and does a very good job explaining and weaving together many core issues in mathematical logic and foundational studies. … Stillwell’s book is highly commendable, very informative and well organized. It is very carefully produced."

—José Ferreirós, *American Mathematical Monthly*, February 2012

"I highly recommend it for undergraduates in mathematics and other young mathematicians who are looking for historical context or a different angle to their studies. Readers who have experience with theoretical analysis or a foundation in abstract mathematics will find the examples wonderfully illustrative. For these readers, Stillwell’s words will flow smoothly, almost like a novel."

—Joyance Meechai, *Mathematics Teacher*, October 2011

"Stillwell has produced an excellent book on infinity for the motivated lay reader. … The author does a masterful job of painting a historical portrait of logic, set theory, incompleteness, computable functions, and many associated foundational questions. His lively style and clear exposition of the relationship between proof and truth will engage both the novice and the expert. Although there are numerous books on the topic of infinity, Stillwell tells a story which motivates the ideas he introduces. This is a book that anyone with an interest in mathematics should have in their library. Highly recommended."

—R.L. Pour, *CHOICE*, March 2011

"This book is an accessible, but also a scholarly and extremely well-written introduction to the great ideas of modern logic. While the central results are the famed proofs of Gödel, Stillwell does a masterful job of relating that work not only to Gödel’s contemporaries, such as Post, Turing, Church, Tarski, Gentzen, and von Neumann, but also to modern researchers in the foundations of mathematics (Friedman, Woodin, and others). Chapter 6 on natural unprovable sentences is a gem … Stillwell’s book is worthwhile reading for anyone interested in the development of mathematical logic in the 20th century and learning about the possible directions of the field in the 21st."

—Stan Wagon, *The College Mathematics Journal*, March 2011

"In 1963, Edwin E. Moise published *Elementary Geometry from an Advanced Standpoint* and his book became a classic. … [this book] deserves the same outcome. … One of the most enjoyable features is Stillwell’s use of techniques of logic and set theory to solve real mathematical problems … Another enjoyable feature is Stillwell’s uniform coverage of unprovability, undecidability and non-computability … suitable for self-study … it is excellent background material for computer scientists and mathematicians in other fields. The historical notes alone are worth perusing by anyone who is interested in the development of mathematical ideas."

—Phill Schultz, *Gazette of the Australian Mathematical Society*, March 2011

"… a clear and succinct guide. … One interesting feature of the book is the careful treatment of two of the less famous contributors in this area—Emil Post and Gerhard Gentzen …"

—*CMS Notes*, Vol. 43, No. 1, February 2011

"… excellent book … the investment the reader makes—be he an intellectually curious adult or a math grad student with extra time on her hands—pays off with an increased understanding of the fascinating world of mathematical logic. The author’s thorough, well-researched historical comments are particularly valuable, as well as the philosophical quotations from the important players in this game. There is a very complete bibliography. What the reader might appreciate most is the ability of the author to share his deep insights into what is important and what it all means in the most profound sense. … it is clear that the book received excellent proofreading before publication. …"

—*Mathematical Reviews*, Issue 2011f

"This is an interesting book on infinity. The author combines set theory and logic to face the most basic and fruitful aspects of infinity."

—Claudi Alsina, *Zentralblatt MATH* 1196

"Featuring chapters dedicated to the diagonal argument, ordinals, computability and proof, logic, arithmetic, natural unprovable sentences, and axioms, as well as being enhanced with the inclusion of a lengthy bibliography and a comprehensive index, **Roads to Infinity: The Mathematics of Truth and Proof** is highly recommended reading for students, scholars, and non-specialist general readers with an interest in the history and contemporary issues of mathematics today."

—Able Greenspan, *Midwest Book Review*

"I love reading anything by John Stillwell. If you've ever been tantalized by the puzzles of infinity, set theory, and logic, and want to understand what's really going on, this is the book for you. It's an exceptionally fine piece of mathematical exposition."

—Steven Strogatz, Cornell University, author of *The Calculus of Friendship*