© in this Web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information Already published 2 K. Petersen Ergodic theory 3 P.T. Johnstone Stone spaces 5 J.-P. Kahane Some random series of functions, 2nd Edition 7 J. Lambek & P.J. Scott Introduction to higher-order categorical logic 8 H. Matsumura Commutative ring theory 10 M. Aschbacher Finite group theory, 2nd edition 11 J.L. Alperin Local Representation Theory 12 P. Koosis The logarithmic integral I 14 S.J. Patterson An introduction to the theory of the Riemann zeta-function 15 H.J. Baues Algebraic homotopy 16 V.S. Varadarajan Introduction to harmonic analysis on semisimple Lie groups 17 W. Dicks & M. Dunwoody Groups acting on graphs 19 R. Fritsch & R. Piccinini Cellular structures in topology 20 H. Klingen Introductory lectures on Siegel modular forms 21 P. Koosis The logarithmic integral II 22 M.J. Collins Representations and characters of finite groups 24 H. Kunita Stochastic flows and stochastic differential equations 25 P. Wojtaszczyk Banach spaces for analysts 26 J.E. Gilbert & M.A.M. Murray Clifford algebras and Dirac operators in harmonic analysis 27 A. Frohlich & M.J. Taylor Algebraic number theory 28 K. Goebel & W.A. Kirk Topics in metric fixed point theory 29 J.F. Humphreys Reflection groups and Coxeter groups 30 D.J. Benson Representations and cohomology I 31 D.J. Benson Representations and cohomology II 32 C. Allday & V. Puppe Cohomological methods in transformation groups 33 C. Soule et al. Lectures on Arakelov geometry 34 A. Ambrosetti & G. Prodi A primer of nonlinear analysis 35 J. Palis & F. Takens Hyperbolicity, stability and chaos at homoclinic bifurcations 37 Y. Meyer Wavelets and operators 1 38 C. Weibel, An introduction to homological algebra 39 W. Bruns & J. Herzog Cohen-Macaulay rings 40 V. Snaith Explicit Brauer induction 41 G. Laumon Cohomology of Drinfeld modular varieties I 42 E.B. Davies Spectral theory and differential operators 43 J. Diestel, H. Jarchow, & A. Tonge Absolutely summing operators 44 P. Mattila Geometry of sets and measures in Euclidean spaces 45 R. Pinsky Positive harmonic functions and diffusion 46 G. Tenenbaum Introduction to analytic and probabilistic number theory 47 C. Peskine An algebraic introduction to complex projective geometry 48 Y. Meyer & R. Coifman Wavelets 49 R. Stanley Enumerative combinatorics I 50 I. Porteous Clifford algebras and the classical groups 51 M. Audin Spinning tops 52 V. Jurdjevic Geometric control theory 53 H. Volklein Groups as Galois groups 54 J. Le Potier Lectures on vector bundles 55 D. Bump Automorphic forms and representations 56 G. Laumon Cohomology of Drinfeld modular varieties II 57 D.M. Clark & B.A. Davey Natural dualities for the working algebraist 58 J. McCleary A user's guide to spectral sequences II 59 P. Taylor Practical foundations of mathematics 60 M.P. Brodmann & R.Y. Sharp Local cohomology 61 J.D. Dixon et al. Analytic pro-P groups 62 R. Stanley Enumerative combinatorics II 63 R.M. Dudley Uniform Central Limit Theorems 64 J. Jost & X. Li-Jost Calculus of variations 65 A.J. Berrick & M.E. Keating An introduction to rings and modules 66 S. Morosawa Holomorphic dynamics 67 A.J. Berrick & M.E. Keating Categories and modules with K-theory in view 68 K. Sato Levy processes and infinitely divisible distributions 69 H. Hida Modular forms and Galois cohomology 70 R. Iorio & V. Iorio Fourier analysis and partial differential equations 71 R. Blei Analysis in integer and fractional dimensions 72 F. Borceaux & G. Janelidze Galois theories 73 B. Bollobas Random graphs

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information LECTURES IN LOGIC AND SET THEORY Volume 2: Set Theory GEORGE TOURLAKIS York University

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

cambridge university press Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sгo Paulo, Delhi, Dubai, Tokyo, Mexico City

Cambridge University Press The Edinburgh Building, Cambridge cb2 8ru, UK

Published in the United States of America by Cambridge University Press, New York

www.cambridge.org Information on this title: www.cambridge.org/9780521168489

© George Tourlakis 2003

This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press.

First published 2003 First paperback edition 2010

A catalogue record for this publication is available from the British Library

British LIBRARY CATALOGuing in Publication Data

Tourlakis, George J.

Lectures in logic and set theory / George Tourlakis.

p. cm. (Cambridge studies in advanced mathematics)

Includes bibliographical references and index.

Contents: v. 1. Mathematical logic v. 2. Set theory.

ISBN 0-521-75373-2 (v. 1) ISBN 0-521-75374-0 (v. 2)

1. Logic, Symbolic and mathematical. 2. Set theory. I. Title. II. Series.

QA9.2 .T68 2003

511.3 dc21

2002073308

isbn 978-0-521-75374-6 Hardback isbn 978-0-521-16848-9 Paperback

Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information To the memory of my parents

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information Contents

Preface I A Bit of Logic: A User's Toolbox I.1 First Order Languages I.2 A Digression into the Metatheory: Informal Induction and Recursion I.3 Axioms and Rules of Inference I.4 Basic Metatheorems I.5 Semantics I.6 Defined Symbols I.7 Formalizing Interpretations I.8 The Incompleteness Theorems I.9 Exercises II The Set-Theoretic Universe, NaЁively II.1 The "Real Sets" II.2 A NaЁive Look at Russell's Paradox II.3 The Language of Axiomatic Set Theory II.4 On Names III The Axioms of Set Theory III.1 Extensionality III.2 Set Terms; Comprehension; Separation III.3 The Set of All Urelements; the Empty Set III.4 Class Terms and Classes III.5 Axiom of Pairing III.6 Axiom of Union III.7 Axiom of Foundation III.8 Axiom of Collection III.9 Axiom of Power Set vii © in this web service Cambridge University Press

page xi 1 7 20 29 43 53 66 77 87 94 99 99 105 106 110 114 114 119 130 134 145 149 156 160 178 www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

viii

Contents

III.10 Pairing Functions and Products

182

III.11 Relations and Functions

193

III.12 Exercises

210

IV The Axiom of Choice

215

IV.1 Introduction

215

IV.2 More Justification for AC; the "Constructible"

Universe Viewpoint

218

IV.3 Exercises

229

V The Natural Numbers; Transitive Closure

232

V.1 The Natural Numbers

232

V.2 Algebra of Relations; Transitive Closure

253

V.3 Algebra of Functions

272

V.4 Equivalence Relations

276

V.5 Exercises

281

VI Order

284

VI.1 PO Classes, LO Classes, and WO Classes

284

VI.2 Induction and Inductive Definitions

293

VI.3 Comparing Orders

316

VI.4 Ordinals

323

VI.5 The Transfinite Sequence of Ordinals

340

VI.6 The von Neumann Universe

358

VI.7 A Pairing Function on the Ordinals

373

VI.8 Absoluteness

377

VI.9 The Constructible Universe

395

VI.10 Arithmetic on the Ordinals

410

VI.11 Exercises

426

VII Cardinality

430

VII.1 Finite vs. Infinite

431

VII.2 Enumerable Sets

442

VII.3 Diagonalization; Uncountable Sets

451

VII.4 Cardinals

457

VII.5 Arithmetic on Cardinals

470

VII.6 Cofinality; More Cardinal Arithmetic;

Inaccessible Cardinals

478

VII.7 Inductively Defined Sets Revisited;

Relative Consistency of GCH

494

VII.8 Exercises

512

VIII Forcing

518

VIII.1 PO Sets, Filters, and Generic Sets

520

VIII.2 Constructing Generic Extensions

524

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

Contents

ix

VIII.3 Weak Forcing

528

VIII.4 Strong Forcing

532

VIII.5 Strong vs. Weak Forcing

543

VIII.6 M[G] Is a CTM of ZFC If M Is

544

VIII.7 Applications

549

VIII.8 Exercises

558

Bibliography

560

List of Symbols

563

Index

567

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information Preface

This volume contains the basics of Zermelo-Fraenkel axiomatic set theory. It is situated between two opposite poles: On one hand there are elementary texts that familiarize the reader with the vocabulary of set theory and build set-theoretic tools for use in courses in analysis, topology, or algebra but do not get into metamathematical issues. On the other hand are those texts that explore issues of current research interest, developing and applying tools (constructibility, absoluteness, forcing, etc.) that are aimed to analyze the inability of the axioms to settle certain set-theoretic questions. Much of this volume just "does set theory", thoroughly developing the theory of ordinals and cardinals along with their arithmetic, incorporating a careful discussion of diagonalization and a thorough exposition of induction and inductive (recursive) definitions. Thus it serves well those who simply want tools to apply to other branches of mathematics or mathematical sciences in general (e.g., Theoretical Computer Science), but also want to find out about some of the subtler results of modern set theory. Moreover, a fair amount is included towards preparing the advanced reader to read the research literature. For example, we pay two visits to GoЁdel's constructible universe, the second of which concludes with a proof of the relative consistency of the axiom of choice and of the generalized continuum hypothesis with ZF. As such a program requires, I also include a thorough discussion of formal interpretations and absoluteness. The lectures conclude with a short but detailed study of Cohen forcing and a proof of the non-provability in ZF of the continuum hypothesis. The level of exposition is designed to fit a spectrum of mathematical sophistication, from third-year undergraduate to junior graduate level (each group will find here its favourite chapters or sections that serve its interests and level of preparation). xi

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

xii

Preface

The volume is self-contained. Whatever tools one needs from mathematical logic have been included in Chapter I. Thus, a reader equipped with a combination of sufficient mathematical maturity and patience should be able to read it and understand it. There is a trade-off: the less the maturity at hand, the more the supply of patience must be. To pinpoint this "maturity": At least two courses from among calculus, linear algebra, and discrete mathematics at the junior level should have exposed the reader to sufficient diversity of mathematical issues and proof culture to enable him or her to proceed with reasonable ease.

A word on approach. I use the Zermelo-Fraenkel axiom system with the axiom of choice (AC). This is the system known as ZFC. As many other authors do, I simplify nomenclature by allowing "proper classes" in our discussions as part of our metalanguage, but not in the formal language. I said earlier that this volume contains the "basics". I mean this characterisation in two ways: One, that all the fundamental tools of set theory as needed elsewhere in the mathematical sciences are included in detailed exposition. Two, that I do not present any applications of set theory to other parts of mathematics, because space considerations, along with a decision to include certain advanced relative consistency results, have prohibited this. "Basics" also entails that I do not attempt to bring the reader up to speed with respect to current research issues. However, a reader who has mastered the advanced metamathematical tools contained here will be able to read the literature on such issues. The title of the book reflects two things: One, that all good short titles are taken. Two, more importantly, it advertises my conscious effort to present the material in a conversational, user-friendly lecture style. I deliberately employ classroom mannerisms (such as "pauses" and parenthetical "why"s, "what if"s, and attention-grabbing devices for passages that I feel are important). This aims at creating a friendly atmosphere for the reader, especially one who has decided to study the topic without the guidance of an instructor. Friendliness also means steering clear of the terse axiom-definition-theorem recipe, and explaining how some concepts were arrived at in their present form. In other words, what makes things tick. Thus, I approach the development of the key concepts of ordinals and cardinals, initially and tentatively, in the manner they were originally introduced by Georg Cantor (paradox-laden and all). Not only does this afford the reader an understanding of why the modern (von Neumann) approach is superior (and contradiction-free), but it also shows what it tries to accomplish. In the same vein, Russell's paradox is visited no less than three

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

Preface

xiii

times, leaving us in the end with a firm understanding that it has nothing to do with the "truth" or otherwise of the much-maligned statement "x x" but it is just the result of a diagonalization of the type Cantor originally taught us.

A word on coverage. Chapter I is our "Chapter 0". It contains the tools needed to enable us do our job properly a bit of mathematical logic, certainly no more than necessary. Chapter II informally outlines what we are about to describe axiomatically: the universe of all the "real" sets and other "objects" of our intuition, a caricature of the von Neumann "universe". It is explained that the whole fuss about axiomatic set theory is to have a formal theory derive true statements about the von Neumann sets, thus enabling us to get to know the nature and structure of this universe. If this is to succeed, the chosen axioms must be seen to be "true" in the universe we are describing. To this end I ensure via informal discussions that every axiom that is introduced is seen to "follow" from the principle of the formation of sets by stages, or from some similarly plausible principle devised to keep paradoxes away. In this manner the reader is constantly made aware that we are building a meaningful set theory that has relevance to mathematical intuition and expectations (the "real" mathematics), and is not just an artificial choice of a contradiction-free set of axioms followed by the mechanical derivation of a few theorems. With this in mind, I even make a case for the plausibility of the axiom of choice, based on a popularization of GoЁdel's constructible universe argument. This occurs in Chapter IV and is informal.

The set theory we do allows atoms (or Urelemente), just like Zermelo's.

The re-emergence of atoms has been defended aptly by Jon Barwise (1975) and

others on technical merit, especially when one does "restricted set theories"

(e.g., theory of admissible sets).

Our own motivation is not technical; rather it is philosophical and ped-

agogical. We find it extremely counterintuitive, especially when addressing

undergraduate audiences, to tell them that all their familiar mathematical

objects the "stuff of mathematics" in Barwise's words are just perverse

"box-in-a-box-in-a-box . . . " formations built from an infinite supply of empty

boxes. For example, should I be telling my undergraduate students that their

familiar number "2" really is justa short name for something like "

"?

And what will I tell them about " 2 "?

O.K., maybe not the whole fuss. Axiomatics also allow us to meaningfully ask, and attempt to answer, metamathematical questions of derivability, consistency, relative consistency, indepen- dence. But in this volume much of the fuss is indeed about learning set theory. Allows, but does not insist that there are any.

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

xiv

Preface

Some mathematicians have said that set theory (without atoms) speaks only of sets and it chooses not to speak about objects such as cows or fish (colourful terms for urelements). Well, it does too! Such ("atomless") set theory is known to be perfectly capable of constructing "artificial " cows and fish, and can then proceed to talk about such animals as much as it pleases. While atomless ZFC has the ability to construct or codify all the familiar mathematical objects in it, it does this so well that it betrays the prime directive of the axiomatic method, which is to have a theory that applies to diverse concrete (meta i.e., outside the theory and in the realm of "everyday math") mathematical systems. Group theory and projective geometry, for example, fulfill the directive. In atomless ZFC the opposite appears to be happening: One is asked to embed the known mathematics into the formal system. We prefer a set theory that allows both artificial and real cows and fish, so that when we want to illustrate a point in an example utilizing, say, the everyday set of integers, Z, we can say things like "let the atoms (be interpreted to) include the members of Z . . . ". But how about technical convenience? Is it not hard to include atoms in a formal set theory? In fact, not at all! A word on exposition devices. I freely use a pedagogical feature that, I believe, originated in Bourbaki's books that is, marking an important or difficult topic by placing a "winding road" sign in the margin next to it. I am using here the same symbol that Knuth employed in his TEXbook, namely, , marking with it the beginning and end of an important passage. Topics that are advanced, or of the "read at your own risk" type, can be omitted without loss of continuity. They are delimited by a double sign, . Most chapters end with several exercises. I have stopped making attempts to sort exercises between "hard" and "just about right", as such classifications are rather subjective. In the end, I'll pass on to you the advice one of my professors at the University of Toronto used to offer: "Attempt all the problems. Those you can do, don't do. Do the ones you cannot". What to read. Just as in the advice above, I suggest that you read everything that you do not already know if time is no object. In a class environment the coverage will depend on class length and level, and I defer to the preferences of the instructor. I suppose that a fourth-year undergraduate audience ought to see the informal construction of the constructible universe in Chapter IV, whereas a graduate audience would rather want to see the formal version in Chapter VI. The latter group will probably also want to be exposed to Cohen forcing.

© in this web service Cambridge University Press

www.cambridge.org

Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information

Preface

xv

Acknowledgments. I wish to thank all those who taught me, a group that is too large to enumerate, in which I must acknowledge the presence and influence of my parents, my students, and the writings of Shoenfield (in particular, 1967, 1978, 1971). The staff at Cambridge University Press provided friendly and expert support, and I thank them. I am particularly grateful for the encouragement received from Lauren Cowles and Caitlin Doggart at the initial (submission and refereeing) and advanced stages (production) of the publication cycle respectively. I also wish to record my appreciation to Zach Dorsey of TechBooks and his team. In both volumes they tamed my English and LATEX, fitting them to Cambridge specifications, and doing so with professionalism and flexibility. This has been a long project that would have not been successful without the support and understanding for my long leaves of absence in front of a computer screen that only one's family knows how to provide. I finally wish to thank Donald Knuth and Leslie Lamport for their typesetting systems TEX and LATEX that make technical writing fun (and also empower authors to load the pages with and other signs).

George Tourlakis Toronto, March 2002

© in this web service Cambridge University Press

www.cambridge.org

doc.uments.com

About Us :: Privacy Policies :: Terms of Service :: Feedback :: Copyright :: Contact Us :: DMCA Policy

Copyright © 2018 doc.uments.com