Cambridge studies in advanced mathematics

Tags: Cambridge University Press, Set Theory, George Tourlakis, web service, constructible universe, mathematical objects, atoms, Set Theory George Tourlakis Frontmatter, mathematical sciences, Lectures, relative consistency, Algebraic number theory, Cardinals, J. Le Potier Lectures, P. Mattila Geometry, logarithmic integral, Finite group theory, formal logic, proof techniques, Inaccessible Cardinals, Cardinal Arithmetic, Topics in metric fixed point theory, A. Ambrosetti, Scott Introduction, Alperin Local representation theory, P. SARNAK Lectures, York University of Ontario., Jon Barwise, mathematical intuition, mathematical logic, George J. Lectures, information Contents, York University, information cambridge university press Cambridge, New York, von Neumann, admissible sets, Y. Meyer Wavelets, Introductory lectures on Siegel modular forms, Lectures on Arakelov geometry, Caitlin Doggart, expert support, Lauren Cowles, Donald Knuth, Y. Meyer
Content: Cambridge University Press 978-0-521-16848-9 - Lectures in Logic and Set Theory: Volume 2: Set Theory George Tourlakis Frontmatter More information Cambridge Studies IN ADVANCED MATHEMATICS Editorial Board B. BOLLOBAS, W. FULTON, A. KATOK, F. KIRWAN, P. SARNAK Lectures in Logic and Set Theory Volume 2 This two-volume work bridges the gap between introductory expositions of logic or set theory on one hand, and the research literature on the other. It can be used as a text in an advanced undergraduate or beginning graduate course in mathematics, Computer Science, or philosophy. The volumes are written in a user-friendly conversational lecture style that makes them equally effective for self-study or class use. Volume 2, on formal (ZFC) set theory, incorporates a self-contained "Chapter 0" on proof techniques so that it is based on formal logic, in the style of Bourbaki. The emphasis on basic techniques will provide the reader with a solid foundation in set theory and sets a context for the presentation of advanced topics such as absoluteness, relative consistency results, two expositions of GoЁdel's constructible universe, numerous ways of viewing recursion, and a chapter on Cohen forcing. George Tourlakis is Professor of Computer Science at York University of Ontario.
© 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

File: cambridge-studies-in-advanced-mathematics.pdf
Title: 0521753740pre
Author: Administrator
Published: Mon Sep 12 15:23:16 2011
Pages: 15
File size: 0.14 Mb


CONSUMER PRICE INDICES, 1 pages, 0.15 Mb

, pages, 0 Mb

LITERATURE PDF, 2 pages, 0.05 Mb
Copyright © 2018 doc.uments.com