301

Mathematics

PURE AND APPLIED MATHEMATICS
A SERIES OF MONOGRAPHS AND TEXTBOOKS

The first part of the book focuses on core components, including subalgebras,
congruences, lattices, direct and subdirect products, isomorphism theorems,
a clone of operations, terms, free algebras, Birkhoff’s theorem, and standard
Maltsev conditions. The second part covers topics that demonstrate the
power and breadth of the subject. The author discusses the consequences of
Jónsson’s lemma, finitely and nonfinitely based algebras, definable principal
congruences, and the work of Foster and Pixley on primal and quasiprimal
algebras. He also includes a proof of Murski’s theorem on primal algebras and
presents McKenzie’s characterization of directly representable varieties, which
clearly shows the power of the universal algebraic toolbox. The last chapter
covers the rudiments of tame congruence theory.
Throughout the text, a series of examples illustrates concepts as they are
introduced and helps readers understand how universal algebra sheds
light on topics they have already studied, such as Abelian groups and
commutative rings. The book also includes carefully selected exercises
that reinforce the concepts and help readers reach a deeper understanding
of the theorems and techniques.

Universal Algebra

Starting with the most basic notions, Universal Algebra: Fundamentals
and Selected Topics introduces the key elements needed to read and
understand current research in this field. Suitable for newcomers to the field,
the text prepares readers for research work by providing a solid grounding

in the fundamental constructions and concepts of universal algebra and by
introducing a variety of recent research topics.

Universal Algebra
Fundamentals and Selected Topics

Bergman

K12346

Clifford Bergman


Universal Algebra
Fundamentals and Selected Topics

K12346_FM.indd 1

8/17/11 9:59 AM


PURE AND APPLIED MATHEMATICS
A Program of Monographs, Textbooks, and Lecture Notes

EXECUTIVE EDITORS
Earl J. Taft
Rutgers University
Piscataway, New Jersey

Zuhair Nashed

University of Central Florida
Orlando, Florida

EDITORIAL BOARD
M. S. Baouendi Anil Nerode
University of California, Cornell University
San Diego Freddy van Oystaeyen
Jane Cronin University of Antwerp,
Rutgers University Belgium
Jack K. Hale Donald Passman
Georgia Institute of Technology University of Wisconsin,
S. Kobayashi Madison
University of California, Fred S. Roberts
Berkeley Rutgers University
Marvin Marcus David L. Russell
University of California, Virginia Polytechnic Institute
Santa Barbara and State University
W. S. Massey Walter Schempp
Yale University Universität Siegen

K12346_FM.indd 2

8/17/11 9:59 AM


MONOGRAPHS AND TEXTBOOKS IN
PURE AND APPLIED MATHEMATICS
Recent Titles
Sergio Macías, Topics on Continua (2005)
Mircea Sofonea, Weimin Han, and Meir Shillor, Analysis and Approximation of Contact

Problems with Adhesion or Damage (2006)
Marwan Moubachir and Jean-Paul Zolésio, Moving Shape Analysis and Control:
Applications to Fluid Structure Interactions (2006)
Alfred Geroldinger and Franz Halter-Koch, Non-Unique Factorizations: Algebraic,
Combinatorial and Analytic Theory (2006)
Kevin J. Hastings, Introduction to the Mathematics of Operations Research
with Mathematica®, Second Edition (2006)
Robert Carlson, A Concrete Introduction to Real Analysis (2006)
John Dauns and Yiqiang Zhou, Classes of Modules (2006)
N. K. Govil, H. N. Mhaskar, Ram N. Mohapatra, Zuhair Nashed, and J. Szabados,
Frontiers in Interpolation and Approximation (2006)
Luca Lorenzi and Marcello Bertoldi, Analytical Methods for Markov Semigroups (2006)
M. A. Al-Gwaiz and S. A. Elsanousi, Elements of Real Analysis (2006)
Theodore G. Faticoni, Direct Sum Decompositions of Torsion-Free Finite
Rank Groups (2007)
R. Sivaramakrishnan, Certain Number-Theoretic Episodes in Algebra (2006)
Aderemi Kuku, Representation Theory and Higher Algebraic K-Theory (2006)
Robert Piziak and P. L. Odell, Matrix Theory: From Generalized Inverses to
Jordan Form (2007)
Norman L. Johnson, Vikram Jha, and Mauro Biliotti, Handbook of Finite
Translation Planes (2007)
Lieven Le Bruyn, Noncommutative Geometry and Cayley-smooth Orders (2008)
Fritz Schwarz, Algorithmic Lie Theory for Solving Ordinary Differential Equations (2008)
Jane Cronin, Ordinary Differential Equations: Introduction and Qualitative Theory,
Third Edition (2008)
Su Gao, Invariant Descriptive Set Theory (2009)
Christopher Apelian and Steve Surace, Real and Complex Analysis (2010)
Norman L. Johnson, Combinatorics of Spreads and Parallelisms (2010)
Lawrence Narici and Edward Beckenstein, Topological Vector Spaces, Second Edition (2010)
Moshe Sniedovich, Dynamic Programming: Foundations and Principles, Second Edition (2010)

Drumi D. Bainov and Snezhana G. Hristova, Differential Equations with Maxima (2011)
Willi Freeden, Metaharmonic Lattice Point Theory (2011)
Murray R. Bremner, Lattice Basis Reduction: An Introduction to the LLL Algorithm and
Its Applications (2011)
Clifford Bergman, Universal Algebra: Fundamentals and Selected Topics (2011)

K12346_FM.indd 3

8/17/11 9:59 AM


This page intentionally left blank


Universal Algebra
Fundamentals and Selected Topics

Clifford Bergman
Iowa State University
Ames, USA

K12346_FM.indd 5

8/17/11 9:59 AM


CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742

© 2012 by Taylor & Francis Group, LLC
CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Version Date: 2011928
International Standard Book Number-13: 978-1-4398-5130-2 (eBook - PDF)
This book contains information obtained from authentic and highly regarded sources. Reasonable
efforts have been made to publish reliable data and information, but the author and publisher cannot
assume responsibility for the validity of all materials or the consequences of their use. The authors and
publishers have attempted to trace the copyright holders of all material reproduced in this publication
and apologize to copyright holders if permission to publish in this form has not been obtained. If any
copyright material has not been acknowledged please write and let us know so we may rectify in any
future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced,
transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or
hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.
For permission to photocopy or use material electronically from this work, please access www.copyright.com ( or contact the Copyright Clearance Center, Inc. (CCC), 222
Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are
used only for identification and explanation without intent to infringe.
Visit the Taylor & Francis Web site at

and the CRC Press Web site at



Dedicated to Ralph McKenzie
on the occasion of his 70th birthday


This page intentionally left blank



Contents

Preface

ix

I

1

Fundamentals of Universal Algebra

1 Algebras
1.1 Operations . . . . . . . . . . . . .
1.2 Examples . . . . . . . . . . . . . .
1.3 More about subs, homs and prods
1.4 Generating subalgebras . . . . . .
1.5 Congruences and quotient algebras

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

3
3
4
7
10
13

2 Lattices
2.1 Ordered sets . . . . . . . . . . . . . . .
2.2 Distributive and modular lattices . . .
2.3 Complete lattices . . . . . . . . . . . .
2.4 Closure operators and algebraic lattices
2.5 Galois connections . . . . . . . . . . . .
2.6 Ideals in lattices . . . . . . . . . . . . .

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.

.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

21
21
24
30
34
38
40

Nuts and Bolts of Universal Algebra
The isomorphism theorems . . . . . . . .
Direct products . . . . . . . . . . . . . .
Subdirect products . . . . . . . . . . . .

Case studies . . . . . . . . . . . . . . . .
Varieties and other classes of algebras . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

47
47
52
55
60
71

.
.
.
.
.
.
. .
. .

.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.


79
79
88
94
104
111
117
121
130

3 The
3.1
3.2
3.3
3.4
3.5

.
.
.
.
.

.
.
.
.
.


4 Clones, Terms, and Equational Classes
4.1 Clones . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Invariant relations . . . . . . . . . . . . . . . . . .
4.3 Terms and free algebras . . . . . . . . . . . . . . .
4.4 Identities and Birkhoff’s theorem . . . . . . . . . .
4.5 The lattice of subvarieties . . . . . . . . . . . . . .
4.6 Equational theories and fully invariant congruences
4.7 Maltsev conditions . . . . . . . . . . . . . . . . . .
4.8 Interpretations . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.

vii


viii

II

Selected Topics

135

5 Congruence Distributive Varieties
5.1 Ultrafilters and ultraproducts . . . . . . . . .
5.2 J´onsson’s lemma . . . . . . . . . . . . . . . .

5.3 Model theory . . . . . . . . . . . . . . . . . .
5.4 Finitely based and nonfinitely based algebras
5.5 Definable principal (sub)congruences . . . .

.
.
.
.
.

139
139
145
149
156
160

6 Arithmetical Varieties
6.1 Large clones . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 How rare are primal algebras? . . . . . . . . . . . . . . . . .

169
169
178

7 Maltsev Varieties
7.1 Directly representable varieties . . . . .
7.2 The centralizer congruence . . . . . . .
7.3 Abelian varieties . . . . . . . . . . . . .
7.4 Commutators . . . . . . . . . . . . . .

7.5 Directly representable varieties revisited
7.6 Minimal varieties . . . . . . . . . . . .
7.7 Functionally complete algebras . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.

.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.


.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.

.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.

.
.
.

.
.
.
.
.
.
.

189
189
197
205
216
224
233
239

8 Finite Algebras and Locally Finite Varieties
8.1 Minimal algebras . . . . . . . . . . . . . . .
8.2 Localization and induced algebras . . . . . .
8.3 Centralizers again! . . . . . . . . . . . . . . .
8.4 Applications . . . . . . . . . . . . . . . . . .

.
.
.

.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.

.

.
.
.
.

.
.
.
.

245
245
252
263
274

.
.
.
.
.
.
.

.
.
.
.

.
.
.

Bibliography

291

Index of Notation

299

Index

303


Preface

This text is based on the two-semester course that I have taught over the years
at Iowa State University. In the writing, as in my course, I attempt to convey
my enthusiasm for the subject and my feelings that it is a worthy object of
study for both graduate students and professional mathematicians.
In choosing the level of detail, I have taken my inspiration more from
the tradition of first-year algebra texts such as van der Waerden, Lang, and
Dummit and Foote, than from a typical research monograph. The book is
addressed to newcomers to the field, whom I do not wish to overwhelm, more
than to veterans seeking an encyclopedic reference work.
It is the job of the author to decide what to omit. One rule of thumb that
I have always used in my classes is to introduce a tool only if it will be applied

later in the course. As a teacher, I have always found it frustrating to expend a
lot of effort and class time developing some construction and then not be able
to demonstrate its importance. Thus, for example, in Chapter 7, the basics
of commutator theory are developed in the context of congruence-permutable
varieties and applied to the characterization of directly representable varieties.
The more involved development in the congruence-modular case is omitted
since it isn’t needed for this application.
As I have matured as a teacher, I have come to incorporate many more
examples into all of my classes. I have applied that philosophy to the writing
of this book. Throughout the text a series of examples is developed that
can be used repeatedly to illustrate new concepts as they are introduced.
Whenever possible I work with objects that are already familiar to students,
such as Abelian groups and commutative rings. Of course, part of the fun
of the subject is the introduction of new sorts of structures (quasigroups,
pseudocomplemented distributive lattices, implication algebras) but especially
by working with familiar structures, students will understand how this new
subject of universal algebra is related to topics they have already studied.
I have also put a great deal of effort into the exercises. Working problems is
still the best way to reinforce new concepts in a student’s mind. The number of
exercises is not huge, and most of them are not hard. Rather, they have been
carefully selected to complement the text and push the reader to a deeper
understanding of the theorems and techniques presented in each section. I
encourage the ambitious student to do every single one.
The book is divided into two parts. Part I consists of the core components
that I think every student of the subject must master. There is a brief first
ix


x


Preface

chapter that introduces the central concepts of operation, algebra and homomorphism. This should be an easy conceptual step for anyone with a modest
background in abstract algebra. The discussion of the set of subalgebras and
congruences provides natural motivation for the second chapter on lattices.
The emphasis in Chapter 2 is on complete and algebraic lattices. We do
include a brief diversion into distributivity and modularity, but the primary
focus is on lattices that arise from closure operators, including Galois connections.
Chapter 3 covers direct and subdirect products and the isomorphism theorems. It is at this point that we begin to develop some of our primary
examples. We characterize subdirectly irreducible Abelian groups, commutative rings that satisfy xn ≈ 1, distributive lattices, and pseudocomplemented
distributive lattices. We then use these characterizations to study the lattices
of subvarieties of each of these classes of algebras.
In Chapter 4 we introduce the definition of a clone of operations. From this
point on we take every opportunity to discuss concepts from a clone-theoretic
point of view. Terms and term algebras are covered as the natural analog of
term operations and clones. I know from experience that free algebras are
difficult for students to grasp, so we devote several pages to examples. Of
course, the whole point is to prove Birkhoff’s result that the notions of variety
and equational class coincide. Part I concludes with a derivation of the most
familiar Maltsev conditions, which seems to fit nicely with our discussion of
terms and free algebras.
Part II is, as billed, a selection of topics that I feel illustrate the power
and breadth of the subject. These seemed to divide up naturally according to
the properties of congruence lattices, but the chapter titles shouldn’t be taken
too religiously. Chapter 5 covers the consequences of J´onsson’s lemma and
Baker’s theorem on finitely based algebras. While we are at it, we provide an
example of a nonfinitely based algebra and a discussion of definable principal
congruences.
Chapter 6 treats the work of Foster and Pixley on primal and quasiprimal
algebras. It also includes a proof of Murski˘ı’s theorem that almost every

finite algebra is primal. Many instructors will probably choose to skip this
proof because of its length and nature, relying as it does, on asymptotics. I
was anxious to include this result for several reasons. First, because everyone
finds the theorem to be counterintuitive upon first learning it. Second, because
this particular proof, largely due to Bob Quackenbush, is really quite nice; and
third, because the only published proof in English is a translation from the
original Russian that is very hard to follow.
The goal in Chapter 7 is Ralph McKenzie’s characterization of directly
representable varieties. To my mind, this theorem is the single best illustration
of the power of the universal algebraic toolbox. In order to give a complete
proof, it is necessary to develop the commutator operation on congruences as
well as provide a complete characterization of congruence-permutable Abelian
varieties.


Preface

xi

Finally, Chapter 8 covers the rudiments of tame congruence theory. It
is certainly not a complete treatment. But I hope it goes far enough to
introduce the reader to these new ideas, and also, despite how different these
constructions seem, that they grow naturally out of the considerations in
Chapters 1–7. As always, I have included several illustrations of the use of
the new tools, including the characterization of idempotent varieties omitting
type 1 via “Taylor terms.”
Since the book largely parallels the course that I have taught, one can
simply start at the beginning and progress as far as is possible in the time
allotted. In one semester it should be possible to cover almost all of Part I,
at least through Birkhoff’s theorem in Section 4.4. If the instructor feels the

need to omit something, the “case studies” are a likely candidate, as are the
examples that compose Section 4.4. A one-semester course need not cover the
section on interpretations.
For a two-semester course, I would encourage the instructor to cover everything in Part I and then choose some of the sections in Part II. There are
several very long proofs that one might choose to skip. These are Baker’s Theorem (5.39), Murski˘ı’s Theorem (all of Section 6.2, although one might omit
only the proof of Lemma 6.22), and two theorems used in the characterization
of directly representable varieties, 7.55 and 7.56.
A very recent development is the discovery that the tools of universal
algebra can be brought to bear on constraint satisfaction problems. A reader
specifically interested in this line of research could, after reading most of Part I,
concentrate on Sections 7.2–7.4 and then move on to Chapter 8.
I cringe a bit at the amount of specialized notation that appears in these
pages. I have done what I can to help the reader by providing an index of
symbols, alphabetized to the degree it is possible. In mathematical writing,
there is always a trade-off between precision and readability. While one never
wants to leave a reader guessing about the exact meaning of any assertion, it is
equally true that an author should not become a slave to his notation. Thus,
when I feel that the context allows, I omit superscript or subscript qualifiers
and closure under isomorphism.
I am greatly indebted to my students and colleagues in the universal algebraic community for all of the ideas, suggestions and criticisms that they
supplied. Libor Barto, Keith Kearnes, Ralph McKenzie, George McNulty,
Bob Quackenbush, Jonathan Smith and Ross Willard all very patiently answered my many questions on the fine points of the subject. The treatment
in Chapter 8 relies very heavily on some notes of Matt Valeriote. And I
very gratefully acknowledge both Joel Berman and David Failing for their
painstaking reading of portions of the manuscript.
This text is obviously influenced by the books that have come before,
especially those of Burris and Sankappanavar [BS81] and McKenzie, McNulty
and Taylor [MMT87], both of which are undeservedly out of print. My copies
of each are dog-eared and marked up. I fondly hope that the book you are
now holding will meet the same fate.



This page intentionally left blank


Part I

Fundamentals of Universal
Algebra


This page intentionally left blank


Chapter 1
Algebras

This first, short, chapter sets the stage for the entire text. Many of the
fundamental notions and several central examples are introduced. This will
allow us to provide examples and motivation for the deeper ideas we encounter
in the later chapters.

1.1

Operations

Let A be a set and n a positive integer. We define An to be the set of all
n-tuples of elements of A, and A0 = {∅}.
Remark. More generally, for any two sets A and B, AB denotes the set
of all functions from B to A. How do you reconcile this with the definition of

An just given? In particular, what about A0 ? What does the definition tell
us about the case A = ∅?
For any A and n as above, we call a function An → A an n-ary operation
on A. The natural number n is called the rank of the operation. Operations
of rank 1 and 2 are usually called unary and binary operations, respectively.
Notice that an operation of rank 0 is a function c : {∅} → A. Such a function
is completely determined by the value c(∅) ∈ A. Thus, for all intents and
purposes, nullary operations (as those of rank 0 are often called) are just the
elements of A. They are frequently called constants.
A bit more notation before we proceed. We denote by ω the set of natural
numbers, {0, 1, 2, . . . }. For any set X, Sb(X) denotes the set of all subsets
of X (i.e., the power set). We write Y ⊆ω X to indicate that Y is a finite
subset of X. Finally Sbω (X) = { Y : Y ⊆ω X }. The symbols Z, Q and R
are used to represent the sets of integers, rational numbers and real numbers,
respectively.
Definition 1.1. An algebra is a pair A, F in which A is a nonempty set and
F = fi : i ∈ I is a family of operations on A, indexed by some set I. The
set A is called the universe of the algebra, and the fi are the fundamental or
basic operations.
Let A = A, F be an algebra, with F = fi : i ∈ I . The function
ρ : I → ω which assigns to each i ∈ I the rank of fi is called the similarity
3


4

1. Algebras

type of A. Two algebras are called similar if they have the same similarity
type. It is common to write “type” in lieu of “similarity type” when we feel

we can get away with it.
Definition 1.2. Let A = A, F and B = B, G be algebras of the same
similarity type ρ : I → ω.
(1) We call B a subalgebra of A if B ⊆ A and for every i ∈ I, gi = fi ↾B ρ(i) .
(2) A function h : B → A is called a homomorphism if for every i ∈ I, and
every b1 , b2 , . . . , bn ∈ B, h(gi (b1 , . . . , bn )) = fi (h(b1 ), . . . , h(bn )). (Here,
n = ρ(i).)
Algebras in which every basic operation is unary are called unary algebras.
An algebra with a single basic operation which is binary is called a binar.

1.2

Examples

Here are a few examples just to whet your appetite and give you an idea of
how we use the notation and terminology. We will introduce more examples
as we go.
Definition 1.3. A semigroup is an algebra S, · satisfying the associative law
x · (y · z) ≈ (x · y) · z.

(1–1)

A monoid is an algebra M, ·, e satisfying the associative law and the identities
x · e ≈ x and e · x ≈ x.

(1–2)

Of course, we should really be specifying the ranks of the basic operations of
our algebras. It is hard to imagine a scenario in which a multiplication-like
symbol such as “·” could be anything but binary. The operation “e” here is

nullary. Monoids are often referred to as “semigroups with identity.”
Examples of semigroups and monoids abound in mathematics. Z, + and
ω, + are semigroups, with the latter being a subalgebra of the former. ω, ·
is a semigroup, although not a subalgebra of Z, + . Each of these three can
be made into a monoid by including the appropriate nullary operation. For
any nonempty set A, AA forms a semigroup (in fact, a monoid) under function
composition, called the semigroup of self-maps of A.
Why are we using “squiggly equals” instead of the usual equals sign in
Definition 1.3? The short answer is that (1–1) and (1–2) are not equalities
but identities, since they assert the equality of the left- and right-hand sides
for each choice of the variables (in this case x, y and z). The study of the


2. Examples

5

identities satisfied by an algebra is one of the core areas of universal algebra.
It is formally introduced in Chapter 4. Until then, don’t obsess about it. You
can use an equals sign if you want.
Definition 1.4. A group is an algebra G, ·, −1 , e of type 2, 1, 0 such that
G, ·, e is a monoid and satisfying
x · x−1 ≈ x−1 · x ≈ e.
A ring is an algebra R, +, ·, −, 0 such that R, +, −, 0 is a group, R, · is a
semigroup and such that the identities
x + y ≈ y + x,
x · (y + z) ≈ (x · y) + (x · z),

(y + z) · x ≈ (y · x) + (z · x)
hold.


Definition 1.5. Let R be a fixed ring. A (left) R-module is an algebra
M, +, −, 0, λr : r ∈ R
such that M, +, −, 0 is an Abelian group, and satisfying, for each r, s ∈ R
the laws
λr (x + y) ≈ λr (x) + λr (y),
λr+s (x) ≈ λr (x) + λs (x),

λr (λs (x)) ≈ λrs (x).

Notice that the similarity type of a module depends upon the ring. If the ring
is infinite, so is the similarity type. And notice also that we have employed
yet another device to indicate the basic operations on this algebra.
Definition 1.6. A quasigroup is an algebra Q, ·, /, \ with three binary operations satisfying the laws
x\(x · y) ≈ y, (x · y)/y ≈ x,

x · (x\y) ≈ y, (x/y) · y ≈ x.

Every group can be made into a quasigroup by taking x/y = x · y −1 and
x\y = x−1 · y. Quasigroups provide a generalization of the notion of a group
obtained by dropping the associative law. (Exercise: a quasigroup in which
“·” is associative is a group.) A loop is a quasigroup with an identity element.
The expression x\y (“x under y”) can be thought of as left-division by x.
Dually, x/y (“x over y”) is right-division by y.
Much as with groups, quasigroups are often thought of as algebras of
type 2 with a “special” binary operation. Specifically, if Q = Q, ·, /, \


6


1. Algebras

is a quasigroup as defined above, then the Cayley table of Q, · is a Latin
square, that is, a table in which each entry appears exactly once in each row
and column. (This way of thinking makes the most sense for a finite table.)
Conversely, each Latin square Q, · can be expanded to a quasigroup in a
unique way. Motivated by this, we define a Latin square to be a binar Q, ·
such that for every a, b ∈ Q the equations
a · x = b and y · a = b
have unique solutions. In a quasigroup, the element x in the above pair of
equations is equal to a\b and y is equal to b/a.
Examples of quasigroups. As we just observed, every group can be transformed into a quasigroup. The set Z of integers forms a Latin square under
the binary operation of subtraction. This is an example of a quasigroup that
is not a group. As a more exotic example, define, for points P and Q in the
plane, P · Q to be the midpoint of the line segment from P to Q. Then R2 , ·
forms a Latin square. Examples 6.11 and 7.59 exhibit Cayley tables of finite
Latin squares that are not associative, so of course, are not groups.
Definition 1.7. A lattice is an algebra L, ∧, ∨ with two binary operations
satisfying the identities
(a∧ )
(i∧ )
(c∧ )

x ∧ (y ∧ z) ≈ (x ∧ y) ∧ z
x∧x≈x
x∧y ≈y∧x

(p∧ ) x ∧ (x ∨ y) ≈ x

(a∨ )

(i∨ )
(c∨ )

x ∨ (y ∨ z) ≈ (x ∨ y) ∨ z
x∨x≈x
x∨y ≈ y∨x

(p∨ ) x ∨ (x ∧ y) ≈ x.

A binary operation satisfying i∧ is called idempotent. The identities p∧ and
p∨ are called the absorption laws.
The expression x ∧ y is pronounced “x meet y,” and x ∨ y is “x join y.”
One will sometimes see the symbols “·” and “+” used in place of “∧” and
“∨.”
A semilattice is an algebra S, ∨ satisfying identities a∨ , i∨ , and c∨ from
the above set. In other words, a semilattice is a commutative, idempotent
semigroup.
We will study lattices in some detail in Chapter 2. Among the familiar
examples are Z, min, max , where min and max denote the minimum and
maximum of two numbers; Z+ , gcd, lcm , where Z+ denotes the set of positive integers and gcd, lcm denote greatest common divisor and least common
multiple respectively; and Sb(X), ∩, ∪ for any set X. For any vector space
V, the set of subspaces of V forms a lattice under the operations of intersection and sum.
A note on idempotence. The word “idempotent” is used in several related,
but distinct, ways in algebra. (1) An element, a, of an algebra is called
idempotent if, for every basic operation f , f (a, a, . . . , a) = a. (2) For n > 1,


3. More about subs, homs and prods

7


an n-ary operation, f , is called idempotent if, for all x, f (x, x, . . . , x) = x.
Finally, (3) a unary operation f is idempotent if f ◦ f = f .
Notice that (3) is really a special case of (1). For a unary operation can be
considered an element in the semigroup of self-maps. The condition f ◦ f = f
is precisely that f is an idempotent element of that semigroup. By contrast,
condition (2) applied to a unary operation would assert that for every x,
f (x) = x, i.e., f is the identity map.

1.3

More about subalgebras, homomorphisms and direct
products

99.9% of the time, when we refer to several algebras in the same breath
they will all be of the same similarity type. In fact, we frequently neglect to
state that hypothesis explicitly. From this perspective it is logical to fix a
similarity type and then consider algebras of that type.
Thus, instead of I, let us take for an index set a family F of operation
symbols, and let ρ : F → ω. Then by an algebra A of type ρ we mean a set
A together with, for each operation symbol f ∈ F, an operation f A of rank
ρ(f ). Thus
A = A, F A

where F A = f A : f ∈ F .

For example, if we wanted to discuss groups, we might start with operations symbols m, j and e of ranks 2, 1, and 0 respectively. Then, if A denotes
a particular group, the product of a and b would be denoted mA (a, b) and
the inverse of a as j A (a). (Of course in real life, we prefer to use the “infix”
symbol ‘·’ instead of a prefix symbol like m. So we might be writing a ·A b

instead of mA (a, b). Obviously, we leave off the superscript whenever we can
get away with it.)
Sometimes it is useful to throw away operations. For example, we may
want to discuss the additive structure of a ring, or view a group as being
merely a monoid. If A = A, F is an algebra and G is a subsequence of
F , then the algebra B = A, G is called a reduct of A, and A is called an
expansion of B.
It is frequently useful to take intersections of subalgebras of an algebra.
But there are two technical problems with this. First, strictly speaking, subalgebras are not sets, so we must intersect their respective universes. Second,
it is possible for two subalgebras to have disjoint universes, but we are not
allowing empty algebras. To cope with these two technicalities, we introduce
the following definition.


8

1. Algebras

Definition 1.8. Let A be an algebra. A subset U of A is called a subuniverse
of A if, for every basic operation f of A, with n = rank(f ),
u1 , u2 , . . . , un ∈ U =⇒ f (u1 , u2 , . . . , un ) ∈ U.

(1–3)

In common parlance, subuniverses are the subsets that are “closed under the operations” of A. Note that if B is a subalgebra of A, then B is a
nonempty subuniverse of A, and conversely, every nonempty subuniverse is
the universe of a subalgebra of A. However, the empty set may be a subuniverse of A, but it is never the universe of a subalgebra. In fact, the empty set
is a subuniverse of A if and only if A has no nullary basic operations. (Think
about this last statement. It is a good exercise for developing an understanding of the boundary case in an implication like (1–3).) The set of subuniverses
of A is denoted Sub(A).

An injective (i.e., one-to-one) homomorphism is often called an embedding.
If h : A → B is a surjective homomorphism, then B is called a homomorphic
image of A. And if h is bijective, then A and B are called isomorphic. We
write A ∼
= B in this latter case. An algebra is called trivial if its universe
has cardinality 1. Notice that, up to isomorphism, there is exactly one trivial
algebra of each similarity type.
g
h
As you can easily check, if A → B → C are homomorphisms, then h ◦ g is
a homomorphism as well. It follows that the set of all endomorphisms of A,
(that is, homomorphisms from A to itself) forms a monoid under the binary
operation of composition. And, together with Exercise 1.11.2, we see that
the set Aut(A) of automorphisms of A can be made into a group. The corresponding algebra Aut(A), ◦, −1 , ιA should be denoted Aut(A), although
we often cheat a bit on the boldfacing. The algebra A is called rigid if its
automorphism group is trivial.
Definition 1.9. Let S = Si : i ∈ I be a sequence of sets. The direct, or
Cartesian product of S is the set
i∈I

Si = f : I →

i∈I

Si (∀i ∈ I) f (i) ∈ Si .

The elements of the direct product are often called choice functions since each
such function chooses an element from each Si .
Now let A = Ai : i ∈ I be a sequence of algebras (all of the same
similarity type). The direct product of this sequence is the algebra B with

universe B = i∈I Ai and such that for every (n-ary) basic operation symbol
g and f1 , . . . , fn ∈ B
g B (f1 , . . . , fn ) (i) = g Ai f1 (i), . . . , fn (i) ,

for all i ∈ I.

When I is infinite, direct products are quite difficult to comprehend and
work with. (But necessary, nonetheless.) In the finite case, things are not so


3. More about subs, homs and prods

9

bad. The product A1 × A2 is the algebra whose universe is the set of ordered
pairs (a1 , a2 ) (with ai ∈ Ai , for i = 1, 2) and with operations computed
“coordinatewise.” In other words, for an n-ary operation f ,
f A1 ×A2 (a11 , a21 ), (a12 , a22 ), . . . , (a1n , a2n ) =
f A1 (a11 , . . . , a1n ), f A2 (a21 , . . . , a2n ) .
Now, you need to extend this to a direct product of k factors and, more
importantly, understand how your definition is a special case of the official
definition above. You also ought to think about what happens when I = ∅.
In the special case that all of the algebras Ai are equal to the same algebra
A, we obtain the direct power algebra AI with universe AI of all functions
from I to A and with operations acting coordinatewise. The direct power
construction is familiar from calculus. We treat the collection of all functions
from the reals to itself as a ring, with (f + g)(x) = f (x) + g(x) and (f · g)(x) =
f (x) · g(x). In our notation, this ring is R, +, −, ·, 0 R .
Definition 1.10. Let K be a class of similar algebras. We write
H(K )

S(K )
P(K )

for the class of all homomorphic images of members of K
for the class of all algebras isomorphic to a subalgebra of
a member of K
for the class of all algebras isomorphic to a direct product
of members of K .

We say that K is closed under the formation of homomorphic images if
H(K ) ⊆ K , and similarly for subalgebras and products. Notice that all three
of these “class operators” are designed so that for any class K , H(K ), S(K )
and P(K ) are closed under isomorphic images. On those rare occasions that
we need it, we can write I(K ) for the class of algebras isomorphic to a member
of K .
Finally, we call K a variety if it is closed under each of H, S and P.
Varieties have been the primary objects of study in universal algebra since
the 1970s. They will increasingly become the focus of the text in the later
chapters.
Exercise Set 1.11.
1. Let h : A → B be a homomorphism. Prove that h(A) is a subuniverse
of B. By h(A) we mean { h(a) : a ∈ A }.
2. Let h : A → B be an isomorphism. Prove that the inverse function h−1
is a homomorphism (consequently an isomorphism) from B to A.
3. Let A and B be similar algebras, and h : A → B be a function. View h
as a set of ordered pairs. Prove that h is a subuniverse of A × B if and
only if h is a homomorphism.


10


1. Algebras
4. Let G be a fixed group. Recall from your first-year algebra text, the
idea of G acting on a set S. Let us call such a set S a G-set. Describe
the class of G-sets as a class of algebraic structures in the sense of
Definition 1.1, and describe the identities that must hold.
5. Prove that every group is isomorphic to Aut(A) for some unary algebra
A. (Hint: use the previous exercise.)
6. Let Ai : i ∈ I be a sequence of similar algebras.
(a) Prove that for each j ∈ I, the mapping pj :
f → f (j) is a surjective homomorphism.

Ai → Aj such that

(b) Let B be an algebra similar to the Ai . Suppose that for each
i ∈ I, we are given a homomorphism hi : B → Ai . Prove that
¯ : B → Ai such that for
there exists a unique homomorphism h
¯ = hi .
all i ∈ I, pi ◦ h
Aj
oo7 ? ?
o
o
o 
hj ooo 
o

o
o

o
 pj
o

o
oo
oooh¯ /
Ai
B OO
OOO i∈I
OOO
?
OOO ??? pk
O
OOO ??
hk
OOO??
O' 
Ak
7. A quick game of scattergories, anyone? Fill in the first column of the table in Figure 1.1 with examples of classes of algebras exhibiting closure
under the required operators. On “game day,” the class will go through
everyone’s lists. You get one point for each correct example that is different from anybody else’s. The instructor will award one point for the
example (in each row) that (s)he thinks is the most interesting mathematically.

1.4

Generating subalgebras

Proposition 1.12. Let A be any algebra, and let S be any nonempty collection of subuniverses of A. Then S is a subuniverse of A.
By S we mean the intersection of all the sets in the collection S. One

could write S = { Si : i ∈ I } and then i∈I Si for the intersection, but that