Springer Graduate Texts in Philosophy Roman Kossak Mathematical Logic On Numbers, Sets, Structures, and Symmetry Springer Graduate Texts in Philosophy Volume 3 The Springer Graduate Texts in Philosophy offers a series of self-contained textbooks aimed towards the graduate level that covers all areas of philosophy ranging from classical philosophy to contemporary topics in the field. The texts will,ingeneral,includeteachingaids(suchasexercisesandsummaries),andcovers the range from graduate level introductions to advanced topics in the field. The publications in this series offer volumes with a broad overview of theory in core topicsinfieldandvolumeswithcomprehensiveapproachestoasinglekeytopicin thefield.Thus,theseriesofferspublicationsforbothgeneralintroductorycourses aswellascoursesfocusedonasub-disciplinewithinphilosophy. Theseriespublishes: • Allofthephilosophicaltraditions • Includes sourcebooks, lectures notes for advanced level courses, as well as textbookscoveringspecializedtopics • Interdisciplinaryintroductions–wherephilosophyoverlapswithotherscientific orpracticalareas. We aim to make a first decision within 1 month of submission. In the event of a positivefirstdecision,theworkwillbeprovisionallycontracted.Thefinaldecision on publication will depend upon the result of the anonymous peer review of the completed manuscript. We aim to have the complete work peer-reviewed within 3monthsofsubmission.Proposalsshouldinclude: • Ashortsynopsisoftheworkortheintroductionchapter • TheproposedTableofContents • CVoftheleadauthor(s) • Listofcoursesforpossiblecourseadoption The series discourages the submission of manuscripts that are below 65,000 wordsinlength. Moreinformationaboutthisseriesathttp://www.springer.com/series/13799 Roman Kossak Mathematical Logic On Numbers, Sets, Structures, and Symmetry 123 RomanKossak CityUniversityofNewYork NewYork,NY,USA SpringerGraduateTextsinPhilosophy ISBN978-3-319-97297-8 ISBN978-3-319-97298-5 (eBook) https://doi.org/10.1007/978-3-319-97298-5 LibraryofCongressControlNumber:2018953167 ©SpringerInternationalPublishingAG,partofSpringerNature2018 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictional claimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Logicandsermonsneverconvince, Thedampofthenightdrivesdeeperintomysoul. (Onlywhatprovesitselftoeverymanandwomanisso, Onlywhatnobodydeniesisso.) WaltWhitman,LeavesofGrass InWhyIsTherePhilosophyofMathematicsatAll?[8],IanHackingwrites: Yet although most members of our species have some capacity for geometrical and numerical concepts, very few human beings have much capacity for doing or even understandingmathematics.Thisisoftenheldtobetheconsequenceofbadeducation,but althougheducationcansurelyhelp,thereisnoevidencethatvastdisparityoftalent,oreven interestin,mathematics,isaresultofbadpedagogy...Aparadox:wearethemathematical animal. A few of us have made astonishing mathematical discoveries, a few more of us canunderstandthem.Mathematicalapplicationshaveturnedouttobeakeytounlockand discipline nature to conform to some of our wishes. But the subject repels most human beings. It all rings true to anyone who has ever taught the subject. When I teach undergraduates,Isometimessay,“Mathdoesnotmakeanysense,right?”towhich I hear in unison “Right.” My own school experience has not been much different. Even though I was considered “good at math,” it only meant that I could follow instructions and do homework to a satisfying result. Only occasionally I’d have momentsIwasproudof.Inmyfirsthighschoolyear,Ihadamathematicsprofessor aboutwhomlegendsweretold.Everyoneknewthatinordertosurviveinhisclass, one had to understand. At any time you could be called to the blackboard to be askedapenetratingquestion.Wewitnessedhumiliatingmomentswhensomeone’s ignorance was ruthlessly revealed. Once, when the topic was square roots of real numbers,Iwascalledandasked: – Doeseverypositivenumberhaveasquareroot? – Yes. – Whatisthesquarerootoffour? – Two. – Whatisthesquarerootoftwo? – Thesquarerootoftwo. v vi Preface – Good.Whatisthesquarerootofthesquarerootoftwo. – Thesquarerootofthesquarerootoftwo. – Good.Sitdown. The professor smiled. He liked my answers, and I was happy with them too. It seemed I had understood something and that this understanding was somehow complete. The truth was simple, and once you grasped it, there was nothing more toit,justplainsimpletruth.Perhapssuchraresatisfyingmomentswerethereason Idecidedtostudymathematics. In my freshmen year at the University of Warsaw, I took Analysis, Abstract Algebra, Topology, Mathematical Logic, and Introduction to Computer Science. I was completely unprepared for the level of abstraction of these courses. I thought that we would just continue with the kind of mathematics we studied in high school.Iexpectedmoreofthesamebutmorecomplicated.Perhapssomeadvanced formulas for solving algebraic and trigonometric equations and more elaborate constructions in plane and three-dimensional geometry. Instead, the course in analysisbeganwithdefiningrealnumbers.Somethingwetookforgrantedandwe thoughtweknewwellnowneededadefinition!Myanswersattheblackboardthat I had been so proud of turned out to be rather naive. The truth was not so plain andsimpleafterall.Andtomakemattersworse,thecoursefollowedwithaproof of existence and uniqueness of the exponential function f(x) ex, and in the = process, we had to learn about complex numbers and the fundamental theorem of algebra.Insteadofadvancedapplicationsofmathematicswehavealreadylearned, we were going back, asking more and more fundamental questions. It was rather unexpected. The algebra and topology courses were even harder. Instead of the already familiar planes, spheres, cones, and cylinders, now we were exposed to general algebraic systems and topological spaces. Instead of concrete objects one couldtrytovisualize,westudiedinfinitespaceswithsurprisinggeneralproperties expressedintermsofalgebraicsystemsthatwereassociatedwiththem.Ilikedthe prospect of learning all that, and in particular the promise that in the end, after all this high-level abstract stuff got sorted out, there would be a return to more down-to-earth applications. But what was even more attractive was the attempt to gettothebottomofthings,tounderstandcompletelywhatthiselaborateedificeof mathematicswasfoundedupon.Idecidedtospecializeinmathematicallogic. Myfirstencounterswithmathematicallogicweretraumatic.Whilestillinhigh school, I started reading Andrzej Grzegorczyk’s Outline of Mathematical Logic,1 a textbook whose subtitle promised Fundamental Results and Notions Explained withAllDetails.Grzegorczykwasaprominentmathematicianwhomadeimportant contributions to the mathematical theory of computability and later moved to philosophy.ThankstoGoogleBooks,wecannowseealistofthewordsandphrases most frequently used in the book: axiom schema, computable functions, concept, empty domain, existential quantifier, false, finite number, free variable, and many 1AnEnglishtranslationis[17]. Preface vii more. I found this all attractive, but I did not understand any of it, and it was not Grzegorczyk’sfault.Intheintroduction,theauthorwrites: RecentyearshaveseentheappearanceofmanyEnglish-languagehandbooksoflogicand numerous monographs on topical discoveries in the foundations of mathematics. These publications on the foundations of mathematics as a whole are rather difficult for the beginnersorreferthereadertootherhandbooksandvariouspiecemealcontributionsand also sometimes to largely conceived ‘mathematical folklore’ of unpublished results. As distinct from these, the present book is as easy as possible systematic exposition of the now classical results in the foundations of mathematics. Hence the book may be useful especiallyforthosereaderswhowanttohavealltheproofscarriedoutinfullandallthe conceptsexplainedindetail.Inthissensethebookisself-contained.Thereader’sability toguessisnotassumed,andtheauthor’sambitionwastoreducetheuseofsuchwordsas evidentandobviousinproofstoaminimum.Thisiswhythebook,itisbelieved,maybe helpfulinteachingorlearningthefoundationofmathematicsinthosesituationsinwhich thestudentcannotrefertoaparallellectureonthesubject. Now that I know what Grzegorczyk is talking about, I tend to agree. When I was readingthebookthen,Ifounditalmostincomprehensible.Itisnotbadlywritten,it isjustthatthematerial,despiteitsdeceptivesimplicity,ishard. In my freshmen year, Andrzej Zarach, who later became a distinguished set theorist, was finishing his doctoral dissertation and had the rather unusual idea of conductingaseminarforfreshmenonsettheoryandGödel’saxiomofconstructibil- ity. This is an advanced topic that requires solid understanding of formal methods thatcannotbeexpectedfrombeginners.Zarachgaveusafewlecturesonaxiomatic set theory, and then each of us was given an assignment for a class presentation. Mine was the Löwenheim-Skolem theorem. The Löwenheim-Skolem theorem is one of the early results in model theory. Model theory is what I list now as my researchspecialty.Fortheseminar,myjobwastopresenttheproofasgiveninthe thenrecentlypublishedbookConstructibleSetswithApplications[23],byanother prominentPolishlogicianAndrzejMostowski.Thetheoremisnotdifficulttoprove. Incoursesinmodeltheory,aproofisusuallygivenearly,asitdoesnotrequiremuch preparation.InMostowski’sbook,theprooftakesaboutone-thirdofthepage.Iwas reading it and reading it, and then reading it again, and I did not understand. Not onlydidInotunderstandtheideaoftheproof;asfarasIcanrecallnow,Ididnot understandasinglesentenceinit.Eventually,Imemorizedtheproofandreproduced itattheseminarinthewaythatclearlyexposedmyignorance.Itwasahumiliating experience. I brought up my early learning experiences here for just one reason: I really know what it is not to understand. I am familiar with not understanding. At the same time, I am also familiar with those extremely satisfying moments when one does finally understand. It is a very individual and private process. Sometimes momentsofunderstandingcomewhensmallpieceseventuallyadduptothepoint when one grasps a general idea. Sometimes, it works the other way around. An understandingofageneralconceptcancomefirst,andthenitshedsbrightlighton an array of smaller related issues. There are no simple recipes for understanding. In mathematics, sometimes the only good advice is study, study, study..., but this is not what I recommend for reading this book. There are attractive areas of viii Preface mathematicsanditsapplicationsthatcannotbefullyunderstoodwithoutsufficient technicalknowledge.Itishard,forexample,tounderstandmodernphysicswithout asolidgraspofmanyareasofmathematicalanalysis,topology,andalgebra.HereI willtrytodosomethingdifferent.Mygoalistotrytoexplainacertainapproachto thetheoryofmathematicalstructures.Thismaterialisalsotechnical,butitsnature isdifferent.Therearenoprerequisites,otherthansomegenuinecuriosityaboutthe subject.Nopriormathematicalexperienceisnecessary.Somewhatparadoxically,to followthelineofthought,itmaybehelpfultoforgetsomemathematicsonelearns in school. Everything will be built up from scratch, but this is not to say that the subjectiseasy. Muchofthematerialinthisbookwasdevelopedinconversationswithmywife, Wanda,andfriends,whoarenotmathematicians,butwerekindandcuriousenough tolistentomyexplanationsofwhatIdoforaliving.Ihopeitwillshedsomelight onsomeareasofmodernmathematics,butexplainingmathematicsisnottheonly goal.Iwanttopresentamethodologicalframeworkthatpotentiallycouldbeapplied outside mathematics, the closest areas I can think of being architecture and visual arts.Afterall,everythingisorhasastructure. I am very grateful to Beth Caspar, Andrew McInerney, Philip Ording, Robert Tragesser,TonyWeaver,JimSchmerl,andJanZwickywhohavereadpreliminary versionsofthisbookandhaveprovidedinvaluableadviceandeditorialhelp. About theContent The central topic of this book is first-order logic, the logical formalism that has broughtmuchclarityintothestudyofclassicalmathematicalnumbersystemsand is essential in the modern axiomatic approach to mathematics. There are many books that concentrate on the material leading to Gödel’s famous incompleteness theorems, and on results about decidability and undecidability of formal systems. The approach in this book is different. We will see how first-order logic serves asalanguageinwhichsalientfeaturesofclassicalmathematicalstructurescanbe describedandhowstructurescanbecategorizedwithrespecttotheircomplexity,or lackthereof,thatcanbemeasuredbythecomplexityoftheirfirst-orderdescriptions. Allkindsofgeometric,combinatorial,andalgebraicobjectsarecalledstructures, but for us the word “structure” will have a strict meaning determined by a formal definition.PartIofthebookpresentsaframeworkinwhichsuchformaldefinitions can be given. The exposition in this part is written for the reader for whom this material is entirely new. All necessary background is provided, sometimes in a repetitivefashion. The role of exercises is to give the reader a chance to revisit the main ideas presented in each chapter. Newly learned concepts become meaningful only after we “internalize” them. Only then, can one question their soundness, look for alternatives, and think of examples and situations when they can be applied, and, sometimesmoreimportantly,whentheycannot.Internalizingtakestime,soonehas Preface ix tobepatient.Exercisesshouldhelp.Tothereaderwhohasnopriorpreparationin abstract mathematics or mathematical logic, the exercises may look intimidating, but they are different, and much easier, than in a mathematics textbook. Most of themonlyrequirecheckingappropriatedefinitionsandfacts,andmostofthemhave pointersandhints.Theexercisesthataremarkedbyasterisksareformoreadvanced readers. All instructors will have their own way of introducing the material covered in PartI.AselectionfromChapters1through6canbechosenforindividualreading, andexercisescanbeassignedbasedonhowadvancedthestudentsintheclassare. My suggestion is to not skip Chapter 2, where the idea of logical seeing is first introduced. That term is often used in the second part of the book. I would also recommendnottoskipthedevelopmentofaxiomaticsettheory,whichisdiscussed in Chapter 6. It is done there rigorously but in a less technical fashion than one usuallyseesintextbooksonmathematicallogic. HereisabriefoverviewofthechaptersinPartI.Allchaptersinbothpartshave moreextensiveintroductions: • Chapter 1 begins with a detailed discussion of a formalization of the statement “there are infinitely many prime numbers,” followed by an introduction of the fullsyntaxoffirst-orderlogicandAlfredTarski’sdefinitionoftruth. • Chapter2introducesthemodel-theoreticconceptofsymmetry(automorphism) usingsimplefinitegraphsasexamples.Theideaof“logicalseeing”isdiscussed. • ShortChapter3isdevotedtotheelusiveconceptofnaturalnumber. • InChapter4,buildinguponthestructureofthenaturalnumbers,adetailedformal reconstruction of the arithmetic structures of the integers (whole numbers) and therationalnumbers(fractions)intermsoffirst-orderlogicisgiven.Thischapter isimportantforfurtherdevelopments. • Chapter 5 provides motivation for grounding the rest of the discussion in axiomatic set theory. It addresses important questions: What is a real number, andhowcanacontinuousreallinebemadeofpoints? • Chapter6isashortintroductiontotheaxiomsofZermelo-Fraenkelsettheory. PartIIismoreadvanced.Itsaimistogiveagentleintroductiontomodeltheory andtoexplainsomeclassicalandsomerecentresultsontheclassificationoffirst- orderstructures.Afewdetailedproofsareincluded.Undoubtedly,thispartwillbe morechallengingforthereaderwhohasnopriorknowledgeofmathematicallogic; nevertheless,itiswrittenwithsuchareaderinmind. • Chapter 7 formally introduces ordered pairs, Cartesian products, relations, and first-orderdefinability.Itconcludeswithanexampleofavarietyofstructureson aone-elementdomainandanimportantstructurewithatwo-elementdomain. • Chapter 8 is devoted to a detailed discussion of definable elements and, in particular,definabilityofnumbersinthefieldofrealnumbers. • In Chapter 9, types and symmetries are defined for arbitrary structures. The concepts of minimality and order-minimality are illustrated by examples of orderingrelationsonsetsofnumbers.