#
Roads to Infinity

The Mathematics of Truth and Proof

## Preview

## Book Description

Winner of a CHOICE Outstanding Academic Title Award for 2011!

This book offers an introduction to modern ideas about infinity and their implications for mathematics. It unifies ideas from set theory and mathematical logic, and traces their effects on mainstream mathematical topics of today, such as number theory and combinatorics. The treatment is historical and partly informal, but with due attention to the subtleties of the subject.

Ideas are shown to evolve from natural mathematical questions about the nature of infinity and the nature of proof, set against a background of broader questions and developments in mathematics. A particular aim of the book is to acknowledge some important but neglected figures in the history of infinity, such as Post and Gentzen, alongside the recognized giants Cantor and Gödel.

## 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)

### Biography

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 Standpointand 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 MATH1196"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 Proofis 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 ofThe Calculus of Friendship