Tai Lieu Chat Luong In the last fifty years, the use of the notion of 'category' has led to a remarkable unification and simplification of mathematics. Written by two of the best-known participants in this development, Conceptual mathe- matics is the first book to apply categories to the most elementary mathe- matics. It thus serves two purposes: to provide a skeleton key to mathematics for the general reader or beginning student; and to furnish an introduction to categories for computer scientists, logicians, physicists, linguists, etc. who want to gain some familiarity with the categorical method.
Everyone who wants to follow the applications of mathematics to twenty-first century science should know the ideas and techniques explained in this book. Conceptual Mathematics Conceptual Mathematics A first introduction to categories F. WILLIAM LAWVERE State University of New York at Buffalo STEPHEN H. SCHANUEL State University of New York at Buffalo CAMBRIDGE UNIVERSITY PRESS PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE The Pitt Building, Trumpington Street, Cambridge CB2 1RP, United Kingdom CAMBRIDGE UNIVERSITY PRESS The Edinburgh Building, Cambridge CB2 2RU, United Kingdom 40 West 20th Street, New York, NY 10011-4211, USA 10 Stamford Road, Oakleigh, Melbourne 3166, Australia C Buffalo Workshop Press 1991 Italian translation C) Franco Muzzio &c.
editore spa 1994 This edition C Cambridge University Press 1997 This book is 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 1997 Printed in the United Kingdom at the University Press, Cambridge A catalogue record for this book is available from the British Library Library of Congress Cataloguing in Publication data Lawvere, F. Conceptual mathematics : a first introduction to categories / F.
William Lawvere and Stephen H.3–dc20 95-44725 CIP ISBN 0 521 47249 0 hardback ISBN 0 521 47817 0 paperback Contents Please read this xiii Note to the reader xv Acknowledgements xvi Preview Session 1 Galileo and multiplication of objects 3 1 Introduction 3 2 Galileo and the flight of a bird 3 3 Other examples of multiplication of objects 7 Part I The category of sets Article I Sets, maps, composition 13 1 Guide 20 Summary: Definition of category 21 Session 2 Sets, maps, and composition 22 1 Review of Article I 22 2 An example of different rules for a map 27 3 External diagrams 28 4 Problems on the number of maps from one set to another 29 Session 3 Composing maps and counting maps 31 Part II The algebra of composition Article II Isomorphisms 39 1 Isomorphisms 39 2 General division problems: Determination and choice 45 3 Retractions, sections, and idempotents 49 4 Isomorphisms and automorphisms 54 5 Guide 58 Summary: Special properties a map may have 59 viii Contents Session 4 Division of maps: Isomorphisms 60 1 Division of maps versus dilision of numbers 60 2 Inverses versus reciprocals 61 3 Isomorphisms as 'divisors' 63 4 A small zoo of isomorphisms in other categories 64 Session 5 Division of maps: Sections and retractions 68 1 Determination problems 68 2 A special case: Constant maps 70 3 Choice problems 71 4 Two special cases of division: Sections and retractions 72 5 Stacking or sorting 74 6 Stacking in a Chinese restaurant 76 Session 6 Two general aspects or uses of maps 81 1 Sorting of the domain by a property 81 2 Naming or sampling of the codomain 82 3 Philosophical explanation of the two aspects 84 Session 7 Isomorphisms and coordinates 86 1 One use of isomorphisms: Coordinate systems 86 2 Two abuses of isomorphisms 89 Session 8 Pictures of a map making its features evident 91 Session 9 Retracts and idempotents 99 1 Retracts and comparisons 99 2 Idempotents as records of retracts 100 3 A puzzle 102 4 Three kinds of retract problems 103 5 Comparing infinite sets 106 Quiz 108 How to solve the quiz problems 109 Composition of opposed maps 114 Summary/quiz on pairs of 'opposed' maps 116 Summary: On the equation poj =1A 117 Review of 'I-words' 118 Test 1 119 Session 10 Brouwer's theorems 120 1 Balls, spheres, fixed points, and retractions 120 2 Digression on the contrapositive rule 124 3 Brouwer's proof 124 Contents ix 4 Relation between fi)*1 point and retraction theorems 126 5 How to understand a proof: The objectification and `mapification' of concepts 127 6 The eye of the storm 130 7 Using maps to formulate guesses 131 Part III Categories of structured sets Article III Examples of categories 135 1 The category .50 of endomaps of sets 136 2 Typical applications of .50 137 3 Two subcategories of S° 138 4 Categories of endomaps 138 5 Irreflexive graphs 141 6 Endomaps as special graphs 143 7 The simpler category S1-: Objects are just maps of sets 144 8 Reflexive graphs 145 9 Summary of the examples and their general significance 146 10 Retractions and injectivity 146 11 Types of structure 149 12 Guide 151 Session 11 Ascending to categories of richer structures 152 1 A category of richer structures: Endomaps of sets 152 2 Two subcategories: Idempotents and automorphisms 155 3 The category of graphs 156 Session 12 Categories of diagrams 161 1 Dynamical systems or automata 161 2 Family trees 162 3 Dynamical systems revisited 163 Session 13 Monoids 166 Session 14 Maps preserve positive properties 170 1 Positive properties versus negative properties 173 Session 15 Objectification of properties in dynamical systems 175 1 Structure-preserving maps from a cycle to another endomap 175 2 Naming elements that have a given period by maps 176 3 Naming arbitrary elements 177 4 The philosophical role of N 180 5 Presentations of dynamical systems 182 x Contents Session 16 Idempotents, involutions, and graphs 187 1 Solving exercises on idempotents and involutions 187 2 Solving exercises on maps of graphs 189 Session 17 Some uses of graphs 196 1 Paths 196 2 Graphs as diagram shapes 200 3 Commuting diagrams 201 4 Is a diagram a map? 203 Test 2 204 Session 18 Review of Test 2 205 Part IV Elementary universal mapping properties Article IV Universal mapping properties 213 1 Terminal objects 213 2 Separating 215 3 Initial object 215 4 Products 216 5 Commutative, associative, and identity laws for multiplication of objects 220 6 Sums 222 7 Distributive laws 222 8 Guide 223 Session 19 Terminal objects 225 Session 20 Points of an object 230 Session 21 Products in categories 236 Session 22 Universal mapping properties and incidence relations 245 1 A special property of the category of sets 245 2 A similar property in the category of endomaps of sets 246 3 Incidence relations 249 4 Basic figure-types, singular figures, and incidence, in the category of graphs 250 Session 23 More on universal mapping properties 254 1 A category of pairs of maps 255 2 How to calculate products 256 Contents xi Session 24 Uniqueness of products and definition of sum 261 1 The terminal object as an identity for multiplication 261 2 The uniqueness theorem for products 263 3 Sum of two objects in a category 265 Session 25 Labelings and products of graphs 269 1 Detecting the structure of a graph by means of labelings 270 2 Calculating the graphs A x Y 273 3 The distributive law 275 Session 26 Distributive categories and linear categories 276 1 The standard map Ax B 1 + A X B2 -> A x (B 1 + B2 ) 276 2 Matrix multiplication in linear categories 279 3 Sum of maps in a linear category 279 4 The associative law for sums and products 281 Session 27 Examples of universal constructions 284 1 Universal constructions 284 2 Can objects have negatives? 287 3 Idempotent objects 289 4 Solving equations and picturing maps 292 Session 28 The category of pointed sets 295 1 An example of a non-distributive category 295 Test 3 299 Test 4 300 Test 5 301 Session 29 Binary operations and diagonal arguments 302 1 Binary operations and actions 302 2 Cantor's diagonal argument 303 Part V Higher universal mapping properties Article V Map objects 313 1 Definition of map object 313 2 Distributivity 315 3 Map objects and the Diagonal Argument 316 4 Universal properties and `observables' 316 5 Guide 319 Session 30 Exponentiation 320 1 Map objects, or function spaces 320 xii Contents 2 A fundamental example of the transformation of map objects 323 3 Laws of exponents 324 4 The distributive law in cartesian closed categories 327 Session 31 Map object versus product 328 1 Definition of map object versus definition of product 329 2 Calculating map objects 331 Session 32 Subobjects, logic, and truth 335 1 Subobjects 335 2 Truth 338 3 The truth value object 340 Session 33 Parts of an object: Toposes 344 1 Parts and inclusions 344 2 Toposes and logic 348 Index 353 Please read this We all begin gathering mathematical ideas in early childhood, when we discover that our two hands match, and later when we learn that other children also have grand- mothers, so that this is an abstract relationship that a child might bear to an older person, and then that 'uncle' and 'cousin' are of this type also; when we tire of losing at tic-tac-toe and work it all out, never to lose again; when we first try to decide why things look bigger as they get nearer, or whether there is an end to counting. As the reader goes through it, this book may add some treasures to the collection, but that is not its goal. Rather we hope to show how to put the vast storehouse in order, and to find the appropriate tool when it is needed, so that the new ideas and methods collected and developed as one goes through life can find their appropriate places as well. There are in these pages general concepts that cut across the artificial boundaries dividing arithmetic, logic, algebra, geometry, calculus, etc.
There will be little discussion about how to do specialized calculations, but much about the ana- lysis that goes into deciding what calculations need to be done, and in what order. Anyone who has struggled with a genuine problem without having been taught an explicit method knows that this is the hardest part. This book could not have been written fifty years ago; the precise language of concepts it uses was just being developed. True, the ideas we'll study have been employed for thousands of years, but they first appeared only as dimly perceived analogies between subjects.
Since 1945, when the notion of 'category' was first pre- cisely formulated, these analogies have been sharpened and have become explicit ways in which one subject is transformed into another. It has been the good fortune of the authors to live in these interesting times, and to see how the fundamental insight of categories has led to clearer understanding, thereby better organizing, and sometimes directing, the growth of mathematical knowledge and its applications. Preliminary versions of this book have been used by high school and university classes, graduate seminars, and individual professionals in several countries. The response has reinforced our conviction that people of widely varying backgrounds can master these important ideas.
Note to the reader The Articles cover the essentials; the Sessions, tables, and exercises are to aid in gaining mastery. The first time we taught this course, the Articles were the written material given to the students, while Emilio Faro's rough notes of the actual class discussions grew into the Sessions, which therefore often review material previously covered. Our students found it helpful to go over the same ground from different viewpoints, with many examples, and readers who have difficulty with some of the exercises in the Articles may wish to try again after studying the ensuing Sessions. Also, Session 10 is intended to give the reader a taste of more sophisticated applica- tions; mastery of it is not essential for the rest of the book.