E-Book Content
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, 1951Fundamental 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 2 1
In token of my respect and gratitude this book is dedicated to llonka and Sandor Szasz
This page intentionally left blank
CONTENTS ILLUSTRATIONS PREFACE I.
xi xiii
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
1.
Bases, 157
2.
Linear Maps and Equations, 167
3.
Affine and Projective Geometry, 176
4.
Hyperplanes in Linear Programming, 183
157
5. Time and Speed in Special Relativity, 187 Bibliography, 194 VII.
GRAPHS
1. Trees and Median Graphs, 197 2.
Games, 202
197
CONTENTS
3.
iX
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
IN