C S. Burris And H.P. Sankappanavar - Mathematics

2y ago
26 Views
2 Downloads
4.21 MB
290 Pages
Last View : 2m ago
Last Download : 2m ago
Upload by : Cade Thielen
Transcription

iic S. Burris and H.P. SankappanavarAll Rights ReservedISBN 978-0-9880552-0-9The authors permit this PDF file of our book to be freely copied, distributedand printed, for non-commercial educational purposes, by anyone, anywhere,including educational institutions and libraries.

iiiThis book is dedicated to our childrenKurosh Phillip BurrisVeena and Geeta and Sanjay Sankappanavar

Preface to the Millennium Edition— 2012 UpdateThe original 1981 edition of A Course in Universal Algebra has now beenLaTeXed, so the authors could make the out-of-print Springer-Verlag Graduate Texts in Mathematics edition available once again, with corrections.The subject of Universal Algebra has flourished mightily since 1981, andwe still believe that A Course in Universal Algebra offers an excellentintroduction to the subject.Special thanks go to Lis D’Alessio for the superb job of LaTeXing thisedition, and to NSERC for their support which has made this work possible.An update to the online edition in 2009 corrected the errors that hadbeen found—details were given in the (separate) errata sheet. Unfortunatelylatexing the new file produced some changes in the page numbering.To solve the problem with shifting page numbers, the 2012 update hasbeen reformatted so that the main body of the book (pages 1–256) agreespage-by-page (but not always line-by-line) with the original 1981 Springeredition. The few errors that have been found in the original edition, as wellas those introduced when LaTeXing the original edition to create the onlineversion, have been corrected. Any further errors that are discovered in thisonline version will be cited in an online errata sheet.iv

Acknowledgments[From the original 1981 edition]First we would like to express gratitude to our colleagues who have added so muchvitality to the subject of Universal Algebra during the past twenty years. One of theoriginal reasons for writing this book was to make readily available the beautifulwork on sheaves and discriminator varieties which we had learned from, and laterdeveloped with H. Werner. Recent work of, and with, R. McKenzie on structureand decidability theory has added to our excitement, and conviction, concerningthe directions emphasized in this book.In the late stages of polishing the manuscript we received valuable suggestionsfrom M. Valeriote, W. Taylor, and the reviewer for Springer-Verlag. For helpin proof-reading we also thank A. Adamson, M. Albert, D. Higgs, H. Kommel,G. Krishnan, and H. Riedel. A great deal of credit for the existence of the finalproduct goes to Sandy Tamowski whose enthusiastic typing has been a constantinspiration. The Natural Sciences and Engineering Research Council of Canadahas generously funded both the research which has provided much of the impetusfor writing this book as well as the preparation of the manuscript through NSERCGrant No. A7256. Also thanks go to the Pure Mathematics Department of theUniversity of Waterloo for their kind hospitality during the several visits of thesecond author, and to the Institute of Mathematics, Federal University of Bahia,for their generous cooperation in this venture.The second author would most of all like to express his affectionate gratitudeand appreciation to his wife—Nalinaxi—who, over the past four years has patientlyendured the many trips between South and North America which were necessaryfor this project. For her understanding and encouragement he will always beindebted.[2012 addendum]We are indebted to the following fans of universal algebra for pointing out errorsin the previous online version: Agostinho Almeida, Rob Arthan, Emidio Barsanti,Jonathan Cohen, Isabel Ferreirim, Marcel Jackson, Greg Lavender and MauroPadellini.v

Preface[From the original 1981 edition]Universal algebra has enjoyed a particularly explosive growth in the last twentyyears, and a student entering the subject now will find a bewildering amount ofmaterial to digest.This text is not intended to be encyclopedic; rather, a few themes central touniversal algebra have been developed sufficiently to bring the reader to the brink ofcurrent research. The choice of topics most certainly reflects the authors’ interests.Chapter I contains a brief but substantial introduction to lattices, and to theclose connection between complete lattices and closure operators. In particular,everything necessary for the subsequent study of congruence lattices is included.Chapter II develops the most general and fundamental notions of universalalgebra—these include the results that apply to all types of algebras, such asthe homomorphism and isomorphism theorems. Free algebras are discussed ingreat detail—we use them to derive the existence of simple algebras, the rules ofequational logic, and the important Mal’cev conditions. We introduce the notionof classifying a variety by properties of (the lattices of) congruences on membersof the variety. Also, the center of an algebra is defined and used to characterizemodules (up to polynomial equivalence).In Chapter III we show how neatly two famous results—the refutation of Euler’sconjecture on orthogonal Latin squares and Kleene’s characterization of languagesaccepted by finite automata—can be presented using universal algebra. We predictthat such “applied universal algebra” will become much more prominent.}The symbol markspage breaks inthe 1981 edition.Chapter IV starts with a careful development of Boolean algebras, includingStone duality, which is subsequently used in our study of Boolean sheaf representations; however, the cumbersome formulation of general }vi

viisheaf theory has been replaced by the considerably simpler definition of a Booleanproduct. First we look at Boolean powers, a beautiful tool for transferring resultsabout Boolean algebras to other varieties as well as for providing a structure theoryfor certain varieties. The highlight of the chapter is the study of discriminatorvarieties. These varieties have played a remarkable role in the study of spectra,model companions, decidability, and Boolean product representations. Probablyno other class of varieties is so well-behaved yet so fascinating.The final chapter gives the reader a leisurely introduction to some basic concepts, tools, and results of model theory. In particular, we use the ultraproductconstruction to derive the compactness theorem and to prove fundamental preservation theorems. Principal congruence formulas are a favorite model-theoretic toolof universal algebraists, and we use them in the study of the sizes of subdirectlyirreducible algebras. Next we prove three general results on the existence of a finitebasis for an equational theory. The last topic is semantic embeddings, a populartechnique for proving undecidability results. This technique is essentially algebraicin nature, requiring no familiarity whatsoever with the theory of algorithms. (Thestudy of decidability has given surprisingly deep insight into the limitations ofBoolean product representations.)At the end of several sections the reader will find selected references to sourcematerial plus state of the art texts or papers relevant to that section, and at the endof the book one finds a brief survey of recent developments and several outstandingproblems.The material in this book divides naturally into two parts. One part can bedescribed as “what every mathematician (or at least every algebraist) should knowabout universal algebra.” It would form a short introductory course to universalalgebra, and would consist of Chapter I; Chapter II except for §4, §12, §13, andthe last parts of §11, §14; Chapter IV §1–4; and Chapter V §1 and the part of §2leading to the compactness theorem. The remaining material is more specializedand more intimately connected with current research in universal algebra.Chapters are numbered in Roman numerals I through V, the sections in a chapterare given by Arabic numerals, §1, §2, etc. Thus II§6.18 refers to item 18, whichhappens to be a theorem, in Section 6 of Chapter II. A citation within Chapter IIwould simply refer to this item as 6.18. For the exercises we use numbering such asII§5 Exercise 4, meaning the fourth exercise in §5 of Chapter II. The bibliographyis divided into two parts, the first containing books and survey articles, and thesecond research papers. The books and survey articles are referred to by number,e.g., G. Birkhoff [3], and the research papers by year, e.g., R. McKenzie [1978].

viiiDiagram of PrerequisitesPreface

ContentsPreface to the Millennium itions of Lattices . . . . . . . . . . . . . . . . . . . . . . . .3§2Isomorphic Lattices, and Sublattices . . . . . . . . . . . . . . . .8§3Distributive and Modular Lattices . . . . . . . . . . . . . . . . . 10§4Complete Lattices, Equivalence Relations, and Algebraic Lattices§5Closure Operators . . . . . . . . . . . . . . . . . . . . . . . . . . 18II The Elements1422§1Definition and Examples of Algebras . . . . . . . . . . . . . . . . 22§2Isomorphic Algebras, and Subalgebras . . . . . . . . . . . . . . . 28§3Algebraic Lattices and Subuniverses . . . . . . . . . . . . . . . . 30§4The Irredundant Basis Theorem . . . . . . . . . . . . . . . . . . 32§5Congruences and Quotient Algebras . . . . . . . . . . . . . . . . 35§6Homomorphisms and the Homomorphism and Isomorphism Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42§7Direct Products, Factor Congruences, and Directly Indecomposable Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . .51§8Subdirect Products, Subdirectly Irreducible Algebras, and SimpleAlgebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56§9Class Operators and Varieties . . . . . . . . . . . . . . . . . . . . 60§10 Terms, Term Algebras, and Free Algebras . . . . . . . . . . . . . 62§11 Identities, Free Algebras, and Birkhoff’s Theorem . . . . . . . . .71§12 Mal’cev Conditions . . . . . . . . . . . . . . . . . . . . . . . . .77§13 The Center of an Algebra . . . . . . . . . . . . . . . . . . . . . . 82§14 Equational Logic and Fully Invariant Congruences . . . . . . . . 89ix

xCONTENTSIII Selected Topics99§1Steiner Triple Systems, Squags, and Sloops . . . . . . . . . . . . 99§2Quasigroups, Loops, and Latin Squares . . . . . . . . . . . . . . 102§3Orthogonal Latin Squares . . . . . . . . . . . . . . . . . . . . . . 103§4Finite State Acceptors . . . . . . . . . . . . . . . . . . . . . . . . 107IV Starting from Boolean Algebras116§1Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . 116§2Boolean Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122§3Filters and Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . 127§4Stone Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135§5Boolean Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 141§6Ultraproducts and Congruence-distributive Varieties . . . . . . . . 145§7Primal Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . 150§8Boolean Products . . . . . . . . . . . . . . . . . . . . . . . . . . 154§9Discriminator Varieties . . . . . . . . . . . . . . . . . . . . . . . 164§10 Quasiprimal Algebras . . . . . . . . . . . . . . . . . . . . . . . . 169§11 Functionally Complete Algebras and Skew-free Algebras . . . . . 176§12 Semisimple Varieties . . . . . . . . . . . . . . . . . . . . . . . . 183§13 Directly Representable Varieties . . . . . . . . . . . . . . . . . . 187V Connections with Model Theory191§1First-order Languages, First-order Structures, and Satisfaction . . 191§2Reduced Products and Ultraproducts . . . . . . . . . . . . . . . . 205§3Principal Congruence Formulas . . . . . . . . . . . . . . . . . . 221§4Three Finite Basis Theorems . . . . . . . . . . . . . . . . . . . . 227§5Semantic Embeddings and Undecidability . . . . . . . . . . . . . 237Recent Developments and Open Problems249§1The Commutator and the Center . . . . . . . . . . . . . . . . . . 249§2The Classification of Varieties . . . . . . . . . . . . . . . . . . . 250§3Decidability Questions . . . . . . . . . . . . . . . . . . . . . . . 251§4Boolean Constructions . . . . . . . . . . . . . . . . . . . . . . . 253§5Structure Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 254§6Applications to Computer Science . . . . . . . . . . . . . . . . . 255§7Applications to Model Theory . . . . . . . . . . . . . . . . . . . 255§8Finite Basis Theorems . . . . . . . . . . . . . . . . . . . . . . . 256§9Subdirectly Irreducible Algebras . . . . . . . . . . . . . . . . . . 256Bibliography§1257Books and Survey Articles . . . . . . . . . . . . . . . . . . . . . 257

CONTENTS§2xiResearch Papers and Monographs . . . . . . . . . . . . . . . . . 258Name Index267Subject Index269

Notation IndexpAi qiPIP, Ø, , Y, X, xx1 , . . . , xn yA B iPIrAi , AIf :AÑBf paq, f af 1g f, A , g.l.b., infl.u.b., supQP (as a poset)I pLqLpP qM5 , N5JpLq ,r1 r2EqpAq , , A , AΠpAqθ pπ qa{θ, A{θLCFfAA xA, F y E pX qSgpX qSubpAqSubpAqCn pX qIrBA{θCon AΘCon AΘp X qxii 11111111222224, 284555910101114141515151616161823, 1912323283030313132333636373738Θpa1 , a2 qCEPαpAqα 1 pAqkerpαqφ{ θBθθæBra, bsA1 A2πiIA iPI Aiθa,bI, S, H, P, PSVT pX qpATpX qΦK pX qθK pX qFK pX qp ppx1 , . . . , xn q ù*IdpX q, IdK pX qp qM p ΣqZ p AqAAΘ F I pS qCon F I pAqDpΣq LpAq LBæ aSupX q1, 2BbRbI pX q, F pX qB X1 Y X2 , X1 Y X2ArBs ArBs 3842434344474848495151, 5353535960616263646666676771, 138141142

NOTATION INDEXrr ssθU iPI Ai {UPU p K qarbSpec ASpec pV q2Lθ1 θnL, RA xA, Lyf A , rALpX qLAA B, S p qθFSpec φP R pK qiPI Ai {Fa{FThpK qTh@Th@HAæLDVF SI-K pc1 , . . . , cn qsemÝsemÝÑxiii143, 207145146, 210147, 6213215218220221233238238244

xivNOTATION INDEX

PreliminariesWe have attempted to keep our notation and conventions in agreement with those of theclosely related subject of model theory, especially as presented in Chang and Keisler’sModel Theory [8]. The reader needs only a modest exposure to classical algebra; forexample he should know what groups and rings are.We will assume a familiarity with the most basic notions of set theory. Actually,we use classes as well as sets. A class of sets is frequently called a family of sets. Thenotations, Ai , i P I, and pAi qiPI refer to a family of sets indexed by a set I. A naive theoryof sets and classes is sufficient for our purposes. We assume the reader is familiar withmembership pPq, the empty set Ø, set-builder notation pt—:—uq, subset p q, union pYq,intersectionpXq, difference p q, ordered n-tuples pxx1 , . . . , xn yq, (direct) products of setspA B, iPI Ai q, and (direct) powers of sets pAI q. Also, it is most useful to know that(a) concerning relations:(i) an n-ary relation on a set A is a subset of An ;(ii) if n 2 it is called a binary relation on A;(iii) the inverse r of a binary relation r on A is specified by xa, byxb, ay P r;P r iff(iv) the relational product r s of two binary relations r, s on A is given by:xa, by P r s iff for some c, xa, cy P r, xc, by P s;(b) concerning functions:(i) a function f from a set A to a set B, written f : A Ñ B, is a subset of A Bsuch that for each a P A there is exactly one b P B with xa, by P f ; in thiscase we write f paq b or f : a ÞÑ b; for a simple expression a we oftenwrite f a instead of f paq;(ii) the set of all functions from A to B is denoted by B A ;(iii) the function fa2 ;P B A is injective (or one-to-one) if f pa1 q f pa2 q ñ a1 (iv) the function f P B A is surjective (or onto) if for every ba P A with f paq b;P B there is an1

2PreliminariesP B A is bijective if it is both injective and surjective;for f P B A and X A, f pX q tb P B : f paq b for some a P X u;for f P B A and Y B, f 1 pY q ta P A : f paq P Y u;for f : A Ñ B and g : B Ñ C, let g f : A Ñ C be the function definedby pg f qpaq g pf paqq. [This does not agree with the relational product(v) the function f(vi)(vii)(viii)defined above—but the ambiguity causes no problem in practice.]; (c) given a family F of sets, the union of F, F, is defined by a Psome A P F (define the intersection of F, F, dually);(d) a chain of sets C is a family of sets such that for each A, BB A; F iff a P A forP C either A B or(e) Zorn’s lemma says that if F is a nonempty family of sets such that for each chainC of members of F there is a member of F containing C (i.e., C has an upperbound in F ) then F has a maximal member M (i.e., M P F and M A P Fimplies M A);(f) concerning ordinals:(i) the ordinals are generated from the empty set using the operations ofsuccessor px x Y txuq and union;(ii) 0 , 1 0 , 2 1 , etc.; the finite ordinals are 0, 1, . . . ; and n t0, 1, . . . , n 1u; the natural numbers are 1, 2, 3 . . . , the nonzero finiteordinals;(iii) the first infinite ordinal is ω t0, 1, 2, . . . u;(iv) the ordinals are well-ordered by the relation P, also called;(g) concerning cardinality:(i) two sets A and B have the same cardinality if there is a bijection from A toB;(ii) the cardinals are those ordinals κ such that no earlier ordinal has the samecardinality as κ. The finite cardinals are 0, 1, 2, . . . ; and ω is the smallestinfinite cardinal;(iii) the cardinality of a set A, written A , is that (unique) cardinal κ such that Aand κ have the same cardinality;(iv) A B A B r maxp A , B q if either is infinite and A, B s .A X B ñ A B A Y B r maxp A , B q if either is infinites;(h) one usually recognizes that a class is not a set by noting that it is too big to be putin one-to-one-correspondence with a cardinal (for example, the class of all groups).In Chapter IV the reader needs to know the basic definitions from point set topology,namely what a topological space, a closed (open) set, a subbasis (basis) for a topologicalspace, a closed (open) neighborhood of a point, a Hausdorff space, a continuous function,etc., are.The symbol “ ” is used to express the fact that both sides name the same object,whereas “ ” is used to build equations which may or may not be true of particularelements. (A careful study of is given in Chapter II.)

Chapter ILatticesIn the study of the properties common to all algebraic structures (such as groups,rings, etc.) and even some of the properties that distinguish one class of algebrasfrom another, lattices enter in an essential and natural way. In particular, congruence lattices play an important role. Furthermore, lattices, like groups or rings,are an important class of algebras in their own right, and in fact one of the mostbeautiful theorems in universal algebra, Baker’s finite basis theorem, was inspiredby McKenzie’s finite basis theorem for lattices. In view of this dual role of latticesin relation to universal algebra, it is appropriate that we start with a brief study ofthem. In this chapter the reader is acquainted with those concepts and results fromlattice theory which are important in later chapters. Our notation in this chapteris less formal than that used in subsequent chapters. We would like the reader tohave a casual introduction to the subject of lattice theory.The origin of the lattice concept can be traced back to Boole’s analysis ofthought and Dedekind’s study of divisibility. Peirce and Schröder were alsopioneers at the end of the last century. The subject started to gain momentum inthe 1930’s and was greatly promoted by Birkhoff’s book, Lattice Theory, in the1940’s.§1Definitions of LatticesThere are two standard ways of defining lattices—one puts them on the same(algebraic) footing as groups or rings, and the other, based on the notion of order,offers geometric insight.3

4I LatticesDefinition 1.1. A nonempty set L together with two binary operations and (read “join” and “meet” respectively) on L is called a lattice if it satisfies thefollowing identities

about Boolean algebras to other varieties as well as for providing a structure theory for certain varieties. The highlight of the chapter is the study of discriminator varieties. These varieties have played a remarkable role in the study of spectra, model companions, decidability, and Boolean product representations. Probably

Related Documents:

These Burris 1-4x riflescopes require 30mm rings. We recommend using high-quality rings and bases, like the Burris Xtreme Tactical Rings and Xtreme Tactical Bases. Quality components ensure that your scope will remain safely and securely mounted, and will provide the maximum accuracy. Use c

LAW OFFICES OF JOHN L. BURRIS 7677 Oakport Street, Suite 1120 Oakland, California 94621 Telephone: (510) 839-5200 -3882 john.burris@johnburrislaw.com adante.pointer@johnburrisalaw.com melissa.nold@johnburrislaw.com Attorneys for Plaintiff ADRIAN BURRELL JASON ROSS, Esq. SBN 2829

from Burris. Double Spring-Tension Internal Assemblies. RT-6s are built to withstand the harshest shooting environments and hold zero round after round. Index-Matched, Hi-Lume Multi-Coated Lenses. Enhanced low-light performance and glare elimination, making more shots possible and increasing your success rate. 2 1File Size: 2MB

VOLUME L NUMBER 12 719 Dr. Kravitz Dr. Burris Dr. Butler Dr. Dabney Dr. Kravitz is an Associate Editor of the Journal of Clinical Orthodontics and in the private practice of orthodontics at 25055 Riding Plaza, Suite 110, South Riding, VA 20152; e-mail: nealkravitz@gmail.com. Dr. Burris is an expert adviser for SmileDirectClub and in the private practice of gen-

within the Burris Laboratory School building. Burris is the state's only laboratory school operated by a public university and serves over 640 students from kindergarten to 12th grade from the local community. The Academy serves roughly 330 juniors and seniors from across the state. Both schools are

County Sanitation Districts of Los Angeles County Lancaster and Palmdale Project Schedules 9 April 2007 0053956 M. Kenneth Burris Jr. Environmental Resources Management 7106 Crossroads Boulevard, Suite 228 Brentwood, Tennessee 37027 (615) 324-1012 / Fax (615) 373-2392 E-mail: ken.burris@erm.com

Mr. Robert J. Bukovac & Mrs. Sandra L. Bukovac Mr. Peter Buksa & Mrs. Irena Buksa Mr. David Burge & Mrs. Julie Burge Mr. Patrick Burris & Mrs. Kathy Burris Mr. Robert W. Burruss & Mrs. Maureen J. Burruss Mrs. Atha Cahalan Ms. Mary Ann Caissie Mr. Salvador J. Caldaron & Mrs. Martha A. Caldaron Mr. John Calvarese & Mrs. Jeannie Calvarese

Dr. Robert Korsgaard- Muncie Burris High School Dr. Korsgaard coached Muncie Burris swimming from 1953 to 1964. He was a “pioneer” to Indiana high school swimming in that he, along with 12 other high schools, began high school competitive swimming. His teams traveled the length of the