The aim of this book is to explain set theory interacts with logic, and both begin to affect mainstream mathematics.Editorial, sales, and customer service officeA K Peters, Ltd5 Commonwealth road, Suite 2CNatick, Ma 01760www.akpeters.comCopyright c 2010 by a K Peters, LtdAll rights reserved. No part of the material protected by this copy.right notice may be reproduced or utilized in any form, electronic ormechanical, including photocopying, recording, or by any informationstorage and retrieval system, without written permission from the copy-right owner.Library of Congress Cataloging-in-Publication DataStillwell, JoRoads to infinity: the mathematics of truth and proof John Stillwellp. cm.Includes bibliographical references and indexISBN978-1-56881-4667(alk. paper)1. Set theory. 2. Intinite. 3. Logic, Symbolic and mathematical. I. TitleQA248.S7782010511.3′22-dc222010014077Cover images C Andreas Guskos and Bob Keefer, 2010Usedunderlicensefromshutterstock.comPrinted in the united states of america141312111010987654321TO elaineCONTENTSPREFACE1 THE DIAGONAL ARGUMENT1.1 Counting and Countabilit1.2 Does one infinite size fit all?41.3 Cantor's Diagonal Argument61.4 Transcendental Numbers1.5 Other Uncountability proofs1.6 Rates of growth141.7 The Cardinality of the Continuum1.8 Historical Background192 ORDINAls292.1 Counting P302.2 The Countable ordinals332.3 The Axiom of choice372. 4 The Continuum Hypoth402.5 Induction422.6 Cantor Normal Form2.7 Goodstein,s Theorem472.9 Historical Background p2.8 Hercules and the hydr3 COMPUTABILITY AND PROOF673.1 Formal Systems683. 2 Post's Approach to Incomplete3.3 Godel's First Incompleteness Theorem3. 4 Godel's Second Incompleteness The803.5 Formalization of Computability823.6 The halting problem853.7 The Entscheidungsproblem873.8 Historical Background89VIIICoNTENTS4 LOGIC4.1 Propositional logic4.2 A Classical System4.3 A Cut-Free System for propositional Logl(1004.4 Happy Endings1054.5 Predicate le1064.6 Completeness, Consistency, Happy Endings11047 Historical background1125 ARITHMETIC1195.1 How Might We prove consistency?1205.2 Formal arithmetic1215.3 The Systems PA and PA5.4Embedding pa in Pa81245.5 Cut Elimination in Pa1275.6 The Height of This great Argument1305.7 Roads to Infinity1335.8 Historical background1356 NATURAL UNPROVABLE SENTENCES1396.1 A Generalized goodstein theorem1406.2 Countable ordinals via Natural Numbers1416.3 From Generalized Goodstein to Well-Ordering1446.4 Generalized and Ordinary Goodstein1466.5 Provably Computable Functions1476.6 Complete Disorder Is Impossible6.7 The Hardest Theorem in graph theory1511546. 8 Historical background157Z AXIOMS OF INFINITY7.1 Set Theory without Infinity1657.2 Inaccessible Cardinals1687. 3 The Axiom of Determinacy1707.4 Largeness Axioms for Arithm1727.5 Large Cardinals and Finite Mathematics1737. 6 Historical Background77BIBLIOGRAPHY183NDEX189PREFACEit is hard to bc finite upon an infinite subject, and all subjects arc infinite.-Herman Melville(1850), P 1170Mathematics and science as we know them are very much the result oftrying to grasp infinity with our finite minds. The German mathemati-cian richard dedekind said as much in 1854(see Ewald(1996),pp 755as the work of man, science is subject to his arbitrariness and toall the imperfections of his mental powers There would essentiallbe no more science for a man gifted with an unbounded understandinga man for whom the final conclusions, which we attain througha long chain of inferences, would be immediately evident truthsDedekind's words reflect the growing awareness of infinity in 19thcentury mathematics, as reasoning about infinite processes(calculus)bcame an indispensable tool of science and engineering. He wrote at thedawn of an era in which infinity and logic were viewed as mathemati-cal concepts for the first time. This led to advances(some of them dueto Dedekind himself) that made all previous knowledge of these topicsseem almost childishly simpleMany popular books have been written on the advances in our understanding of infinity sparked by the set theory of georg Cantor in the1870s, and incompleteness theorems of Kurt Godel in the 1930s. How-ever, such books generally dwell on a single aspect of either set theoryor logic. I believe it has not been made clear that the results of Cantorand Godel form a seamless whole. The aim of this book is to explain thewhole, in which set theory interacts with logic, and both begin to affectmainstream mathematics(the latter quite a recent development, not yetgiven much space in popular accounts)In particular, I have taken some pains to tell the story of two neglectedfigures in the history of logic, Emil Post and Gerhard Gentzen. Postdiscovered incompleteness before Godel, though he did not publish hisproof until later. However, his proof makes clear (more so than Godel'sPREFACEdid) the origin of incompleteness in Cantor's set theory and its connections with the theory of computation. gentzen in the light of godels the-orem that the consistency of number theory depends on an assumptionrom outside number theory, found the minimum such assumption-onethat grows out of Cantor's theory of ordinal numbers--paving the wayfor new insights into unprovability in number theory and combinatoricsThis book can be viewed as a sequel to my Yearning for the Impossible,the main message of which was that many parts of mathematics demandthat we accept some form of infinity. The present book explores the consequences of accepting infinity, which are rich and surprising. There aremany levels of infinity, ascending to heights that almost defy belief, yeteven the highest levels have"observable" effects at the level of finite objects, such as the natural numbers 1, 2, 3,.... Thus, infinity may be moredown-to-earth than certain parts of theoretical physics! In keeping withthis claim, I have assumed very little beyond high school mathematicsexcept a willingness to grapple with alien ideas. If the notation of symolic logic proves too alien, it is possible to skip the notation-heavy partsand still get the gist of the story.I have tried to ease the reader into the technicalities of set theory andlogic by tracing a single thread in each chapter, beginning with a natural mathematical question and following a sequence of historic responsesto it. Each response typically leads to new questions, and from themnew concepts and theorems emerge. At the end of the chapter there islongish section called Historical Background, which attempts to situatethe thread in a bigger picture of mathematics and its history. My inten-tion is to present key ideas in closeup first, then to revisit and reinforcethem by showing a wider view. But this is not the only way to read thebook. Some readers may be impatient to get to the core theorems, andwill skip the historical background sections, at least at first reading Oth-ers, in search of a big picture from the beginning, may begin by readinthe historical background and then come back to fill in detailsThe book has been developing in my unconscious since the 1960s,when i was an undergraduate at the university of melbourne and agraduate student at MIT. Set theory and logic were then my passions inmathematics, but it took a long time for me to see them in perspectiveapologize to my teachers for the late return on their investment! I particu-larly want to thank Bruce Craven of Melbourne for indulging my interestin a field outside his specialty, and my MIT teachers Hartley Rogers jrand Gerald Sacks for widening my horizons in logic and set theoryIn recent times I have to thank jeremy Avigad for bringing me up todate, and cameron freer for a very detailed criticism of an earlier draftof this book. John Dawson also made very helpful comments. If errorsremain, they are entirely my fault. The University of San Francisco andPREFACEMonash university provided valuable support and facilities while i waswriting and researchingi also want to thanke Shenitzer for his perenniwith proofreading, and my sons Michael and robert for sharing this onerous task. Finally, I thank my wife Elaine, as alwaysJohn StillwellUniversity of San Francisco and Monash UniversityMarch 2010CHAPTER 1THE DIAGONAL ARGUMENTPREVIEWInfinity is the lifeblood of mathematics because there is no end to eventhe simplest mathematical objects-the positive integers 1,2,3,4,5, 6,7,.... One of the oldest and best arguments about infinity is euclidsproof that the prime numbers 2,3, 5,7,11, 13,... form an infinite sequence. Euclid succeeds despite knowing virtually nothing about thesequence, by showing instead that any finite sequence of primes is in-complete. That is, he shows how to find a prime p different from anygiven primes p1,p2…pna set like the prime numbers is called countably infinite because wecan order its members in a list with a first member, second memberthird member and so on. As Euclid showed the list is infinite but eachmember appears at some finite position, and hence gets"countedCountably infinite sets have always been with us, and indeed it ishard to grasp infinity in any way other than by counting. But in 1874 theGerman mathematician Georg Cantor showed that infinity is more complicated than previously thought, by showing that the set of real numbersis uncountable. He did this in a way reminiscent of Euclid's proof but onelevel higher, by showing that any countably infinite list of real numbersis incomplete.Cantor's method finds a real number x different from any on a givencountable list x1, x2,3,... by what is now called the diagonal argumentfor reasons that will become clear below. The diagonal argument (whichcomes in several variations) is logically the simplest way to prove theexistence of uncountable sets. It is the first " road to infinity "of our titleso we devote this chapter to it. a second road--via the ordinals--was alsodiscovered by Cantor, and it will be discussed in Chapter 2