FUNDAMENTAL STRUCTURES OF ALGEBRA AND DISCRETE MATHEMATICS This page intentionally left blank FUNDAMENTAL STRUCTURES OF ALGEBRA AND DISCRETE MATHEMATICS STEPHAN FOLDES A Wiley-lnterscience Publication JOHN WILEY & SONS, INC. New York / Chichester / Brisbane / Toronto / Singapore This text is printed on acid-free paper. Copyright ©1994 by John Wiley & Sons, Inc. All rights reserved. Published simultaneously in Canada. Reproduction or translation of any part of this work beyond that permitted by Section 107 or 108 of the 1976 United States Copyright Act without the permission of the copyright owner is unlawful. Requests for permission or further information should be addressed to the Permissions Department, John Wiley & Sons, Inc. Library of Congress Cataloging in Publication Data: Foldes, Stephan, 1951- Fundamental structures of algebra and discrete mathematicsrt>y Stephan Foldes. p. cm. "A Wiley-Interscicncc publication." Includes bibliographical references and index. ISBN 0-471-57180-6 (cloth) 1. Algebra. I. Title. QA155.F65 1993 512'.02-dc20 93-8787 10 9 8 7 6 5 4 3 21 In token of my respect and gratitude this book is dedicated to llonka and Sandor Szasz This page intentionally left blank CONTENTS ILLUSTRATIONS xi PREFACE xiii I. SETS 1 1. Elementary Constructions and Axioms, 1 2. Cardinal and Ordinal Numbers, 11 3. Intersections, 21 Bibliography, 28 II. ORDERED SETS 31 1. Relations, Orders, and Zorn's Lemma, 31 2. Lattices and Closures, 43 3. Covering Relations, 49 4. Intersecting Convex Sets, 54 Bibliography, 56 vii Vill CONTENTS III. GROUPS 59 1. Binary Operations, Homomorphisms, and Congruences, 59 2. Permutation Groups, 68 3. Integers and Cyclic Groups, 75 4. Alternating Groups, 82 Bibliography, 90 IV. RINGS 93 1. Ideals, 93 2. Polynomials, 104 3. Factorization and the Euclidean Algorithm, 111 Bibliography, 123 V. FIELDS 125 1. Rational and Real Numbers, 125 2. Galois Groups and Imaginary Roots, 137 Bibliography, 154 VI. VECTOR SPACES 157 1. Bases, 157 2. Linear Maps and Equations, 167 3. Affine and Projective Geometry, 176 4. Hyperplanes in Linear Programming, 183 5. Time and Speed in Special Relativity, 187 Bibliography, 194 VII. GRAPHS 197 1. Trees and Median Graphs, 197 2. Games, 202 CONTENTS iX 3. Chromatic Polynomials, 207 Bibliography, 210 VIII. LATTICES 213 1. Complements and Distributivity, 213 2. Boolean Algebra, 230 3. Modular and Geometric Lattices, 237 Bibliography, 242 IX. MATROIDS 245 1. Linear and Abstract Independence, 245 2. Minors and Tutte Polynomials, 252 3. Greedy Optimization Procedures, 262 Bibliography, 268 X. TOPOLOGICAL SPACES 269 1. Filters, 269 2. Closure, Convergence, and Continuity, 272 3. Distances and Entourages, 281 Bibliography, 288 XI. UNIVERSAL ALGEBRAS 291 1. Homomorphisms and Congruences, 291 2. Algebra of Syntax, 295 3. Truth and Formal Proof, 300 Bibliography, 308 XII. CATEGORIES 311 Bibliography, 324 INDEX OF DEFINITIONS 327 INDEX OF NOTATION 339 INDEX OF THEOREMS 343