Roads to Infinity: The Mathematics of Truth and Pr

文件名称: Roads to Infinity: The Mathematics of Truth and Proof

所属分类: 讲义

开发工具:

文件大小: 1mb

下载次数: 0

上传时间: 2019-04-20

提供者: cn***

下载 (1mb)

不能下载？报告错误

详细说明：这是一本优秀的数学书，专注于探讨理清一些数学底层概念的来历ROADS TO INFINITY THE MATHEMATICS OF TRUTH AND PROOF JOHN STILLWELL A K PETERS, LTD NATICK, MASSACHUSETTS Editorial, sales, and customer service office A K Peters, Ltd 5 Commonwealth road, Suite 2C Natick, Ma 01760 www.akpeters.com Copyright c 2010 by a K Peters, Ltd All rights reserved. No part of the material protected by this copy. right notice may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copy- right owner. Library of Congress Cataloging-in-Publication Data Stillwell, Jo Roads to infinity: the mathematics of truth and proof John Stillwell p. cm. Includes bibliographical references and index ISBN978-1-56881-4667(alk. paper) 1. Set theory. 2. Intinite. 3. Logic, Symbolic and mathematical. I. Title QA248.S7782010 511.3′22-dc22 2010014077 Cover images C Andreas Guskos and Bob Keefer, 2010 Usedunderlicensefromshutterstock.com Printed in the united states of america 1413121110 10987654321 TO elaine CONTENTS PREFACE 1 THE DIAGONAL ARGUMENT 1.1 Counting and Countabilit 1.2 Does one infinite size fit all? 4 1.3 Cantor's Diagonal Argument 6 1.4 Transcendental Numbers 1.5 Other Uncountability proofs 1.6 Rates of growth 14 1.7 The Cardinality of the Continuum 1.8 Historical Background 19 2 ORDINAls 29 2.1 Counting P 30 2.2 The Countable ordinals 33 2.3 The Axiom of choice 37 2. 4 The Continuum Hypoth 40 2.5 Induction 42 2.6 Cantor Normal Form 2.7 Goodstein,s Theorem 47 2.9 Historical Background p 2.8 Hercules and the hydr 3 COMPUTABILITY AND PROOF 67 3.1 Formal Systems 68 3. 2 Post's Approach to Incomplete 3.3 Godel's First Incompleteness Theorem 3. 4 Godel's Second Incompleteness The 80 3.5 Formalization of Computability 82 3.6 The halting problem 85 3.7 The Entscheidungsproblem 87 3.8 Historical Background 89 VIII CoNTENTS 4 LOGIC 4.1 Propositional logic 4.2 A Classical System 4.3 A Cut-Free System for propositional Logl( 100 4.4 Happy Endings 105 4.5 Predicate le 106 4.6 Completeness, Consistency, Happy Endings 110 47 Historical background 112 5 ARITHMETIC 119 5.1 How Might We prove consistency? 120 5.2 Formal arithmetic 121 5.3 The Systems PA and PA 5.4 Embedding pa in Pa 8 124 5.5 Cut Elimination in Pa 127 5.6 The Height of This great Argument 130 5.7 Roads to Infinity 133 5.8 Historical background 135 6 NATURAL UNPROVABLE SENTENCES 139 6.1 A Generalized goodstein theorem 140 6.2 Countable ordinals via Natural Numbers 141 6.3 From Generalized Goodstein to Well-Ordering 144 6.4 Generalized and Ordinary Goodstein 146 6.5 Provably Computable Functions 147 6.6 Complete Disorder Is Impossible 6.7 The Hardest Theorem in graph theory 151 154 6. 8 Historical background 157 Z AXIOMS OF INFINITY 7.1 Set Theory without Infinity 165 7.2 Inaccessible Cardinals 168 7. 3 The Axiom of Determinacy 170 7.4 Largeness Axioms for Arithm 172 7.5 Large Cardinals and Finite Mathematics 173 7. 6 Historical Background 77 BIBLIOGRAPHY 183 NDEX 189 PREFACE it is hard to bc finite upon an infinite subject, and all subjects arc infinite. -Herman Melville(1850), P 1170 Mathematics and science as we know them are very much the result of trying to grasp infinity with our finite minds. The German mathemati- cian richard dedekind said as much in 1854(see Ewald(1996),pp 755 as the work of man, science is subject to his arbitrariness and to all the imperfections of his mental powers There would essentiall be no more science for a man gifted with an unbounded understand inga man for whom the final conclusions, which we attain through a long chain of inferences, would be immediately evident truths Dedekind's words reflect the growing awareness of infinity in 19th century mathematics, as reasoning about infinite processes(calculus)b came an indispensable tool of science and engineering. He wrote at the dawn 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 due to Dedekind himself) that made all previous knowledge of these topics seem almost childishly simple Many popular books have been written on the advances in our un derstanding of infinity sparked by the set theory of georg Cantor in the 1870s, and incompleteness theorems of Kurt Godel in the 1930s. How- ever, such books generally dwell on a single aspect of either set theory or logic. I believe it has not been made clear that the results of Cantor and Godel form a seamless whole. The aim of this book is to explain the whole, in which set theory interacts with logic, and both begin to affect mainstream mathematics(the latter quite a recent development, not yet given much space in popular accounts) In particular, I have taken some pains to tell the story of two neglected figures in the history of logic, Emil Post and Gerhard Gentzen. Post discovered incompleteness before Godel, though he did not publish his proof until later. However, his proof makes clear (more so than Godel's PREFACE did) the origin of incompleteness in Cantor's set theory and its connec tions with the theory of computation. gentzen in the light of godels the- orem that the consistency of number theory depends on an assumption rom outside number theory, found the minimum such assumption-one that grows out of Cantor's theory of ordinal numbers--paving the way for new insights into unprovability in number theory and combinatorics This book can be viewed as a sequel to my Yearning for the Impossible, the main message of which was that many parts of mathematics demand that we accept some form of infinity. The present book explores the con sequences of accepting infinity, which are rich and surprising. There are many levels of infinity, ascending to heights that almost defy belief, yet even the highest levels have"observable" effects at the level of finite ob jects, such as the natural numbers 1, 2, 3,.... Thus, infinity may be more down-to-earth than certain parts of theoretical physics! In keeping with this claim, I have assumed very little beyond high school mathematics except a willingness to grapple with alien ideas. If the notation of sym olic logic proves too alien, it is possible to skip the notation-heavy parts and still get the gist of the story. I have tried to ease the reader into the technicalities of set theory and logic by tracing a single thread in each chapter, beginning with a natu ral mathematical question and following a sequence of historic responses to it. Each response typically leads to new questions, and from them new concepts and theorems emerge. At the end of the chapter there is longish section called Historical Background, which attempts to situate the 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 reinforce them by showing a wider view. But this is not the only way to read the book. Some readers may be impatient to get to the core theorems, and will skip the historical background sections, at least at first reading Oth- ers, in search of a big picture from the beginning, may begin by readin the historical background and then come back to fill in details The book has been developing in my unconscious since the 1960s, when i was an undergraduate at the university of melbourne and a graduate student at MIT. Set theory and logic were then my passions in mathematics, but it took a long time for me to see them in perspective apologize to my teachers for the late return on their investment! I particu- larly want to thank Bruce Craven of Melbourne for indulging my interest in a field outside his specialty, and my MIT teachers Hartley Rogers jr and Gerald Sacks for widening my horizons in logic and set theory In recent times I have to thank jeremy Avigad for bringing me up to date, and cameron freer for a very detailed criticism of an earlier draft of this book. John Dawson also made very helpful comments. If errors remain, they are entirely my fault. The University of San Francisco and

(系统自动生成,下载前可以参看下载内容)