Preliminaries

Robin Hirsch    Department of Computer Science, University College Gower Street, London, WCIE 6BT United Kingdom

Ian Hodkinson    Department of Computing, Imperial College 180 Queen's Gate, London, SW7 2BZ United Kingdom

We do not want to assume any previous knowledge about algebraic logic, although a certain familiarity with mathematical concepts and notation is needed, and a background in formal logic will help. We have included this chapter in order to cover notions from outside algebraic logic that will be useful in later chapters. Most of them are from universal algebra — equational varieties and Birkhoff’s theorem, subdirectly irreducibles, conjugates, and discriminators. We also cover boolean algebras with operators and associated constructions such as atom structures, canonical embedding algebras, and completions. Some model theory will also be used in the book, and most of the later chapters are heavily influenced by model-theoretic ideas, but we use few specific model-theoretic theorems, so we confine ourselves here to the basic concepts and introduce the remaining ones, such as saturation, at the time of use. The chapter is intended to be selective and expository, and not a full or rigorous development of either universal algebra or model theory. References to universal algebra, which has historically been closely related to algebraic logic, include [Grät79, BurSan81, McKeMcN+87]. Standard texts on model theory, not so often seen as related to algebraic logic, include [ChaKei90, Hod93],

The reader who wishes to get straight into algebraic logic and the representation theory might be advised to run quickly through this preliminary chapter, or perhaps skip it altogether, and then refer back to it as the need arises.

2.1 Foundations

We assume a basic knowledge of sets, relations and functions, and other basic mathematical notions. In particular, the following concepts and notations will arise. Many of them are entire fields with many books devoted to them; we only want to give a handy reference for items used later.

Iff We often use ‘iff’ to abbreviate ‘if and only if’; this useful word was invented by Halmos. ‘⇔’ means the same; ‘⇒’ means ‘implies’, and ‘⇐’ means ‘is implied by’.

Sets We work implicitly in ZFC — Zermelo-Fraenkel set theory with the axiom of choice. For sets X,Y,X × Y denotes the set of all ordered pairs (x,y) (x ∈ X,y ∈ Y). (Formally, (x,y) = {{x}, {x,y}}.) For a whole number n ≥ 1, Xn denotes

×X×⋯×X;⏞ntimes

we think of this as the set of sequences {(x0, …, xn − 1): x0, …,xn − 1 ∈ X}. For a set ∪X and x∈Xx denote {y: y ∈ x for some x ∈ X}. For finite sets X, we simplify the notation, so that x∪ y denotes xy, etc. Similar conventions apply to ∩ when X ≠ Ø. The disjoint union of sets Xi (i ∈ I) is formally defined to be Xi×i:i∈I, though normally we think of it as the union of pairwise disjoint copies of the Xi. In the text, ⊆ will denote set or class inclusion (see any standard text on set theory for information about classes), or substructure or subalgebra (see section 2.2.4), as appropriate. ⊂ will be used to indicate that the inclusion is proper: X ⊂ Y iff X ⊆ Y and ≠Y.℘X denotes the power set (set of all subsets) of X. We write X / Y for the set {x ∈ X: x ∉ Y}.

Binary relations These are the main topic of the book; here we confine ourselves to their basic aspects. A binary relation R on a set X is a subset of X × X. Generally, X will be non-empty, but sometimes it is useful to allow empty X. We write R(x,y) or xRy as alternative notations for {x,y) ∈ R. The domain and range of R are {x: (x,y)’) ∈ R} and {y: (x,y) ∈ R}, respectively. R is said to be

reflexive, if xRx for all x ∈ X,

irreflexive, if xRx for no x ∈ X,

symmetric, if xRy implies yRx,

antisymmetric, if xRy and yRx imply x = y,

transitive, if xRy and yRz imply xRz.

The reflexive (or transitive) closure of R (with respect to X) is the smallest reflexive (respectively, transitive) binary relation on X containing R. The reflexive closure of R with respect to X is R ∪ {(x.x): x ∈ X}. Its transitive closure is the set of all pairs (x,y) such that there exist finite n > 0 and x0,…, xn ∈ X with x0 = x, xn = y, x0Rx1, x1Rx2, …, xn − 1 Rxn. That is, it is the intersection of all transitive relations on X containing R — or, the smallest such relation. Similarly, the reflexive transitive closure of R with respect to X is the smallest reflexive transitive relation containing R.

Equivalence relations An equivalence relation on a set X is a reflexive, symmetric, transitive binary relation E on X. An equivalence class of E is a subset of X of the form /E=defy∈X:yEx for some x ∈ X. We write X/E for the set of equivalence classes of E. The equivalence classes of E partition X: i.e., every element of X lies in exactly one of them.

The equivalence relation generated by a binary relation R on X is the smallest equivalence relation on X that contains R.

Orderings A pre-order is a set X endowed with a reflexive transitive binary relation ≤. A partial order or partial ordering is an antisymmetric pre-order. A partial order (X, ≤) is well-founded if every non-empty subset Y ⊆ X has a minimal element (there is y ∈ Y such that if z ∈ Y and z ≤ y then z = y), or equivalently, there is no infinite descending sequence of distinct elements x0 ≥ x1 ≥  in X. (X, ≤) is a linear order if x ≤ y or y ≤ x for all x,y ∈ X, and a well-order if it is well-founded and linear.

An irreflexive partial order on X is an irreflexive binary relation on X, usually written <, whose reflexive closure is a partial order on X. Similar definitions are made for irreflexive linear order, etc. If (X, ≤) is a given partial order, x < y denotes the binary relation on X given by x < y iff x ≤ y and x ≠ y. Then (X, <) is an irreflexive partial order. Conversely, for an irreflexive partial order (X, <), x < y denotes the binary relation on X given by x ≤ y iff x < y or x = y; then, (X, ≤) is a partial order.

Two linear orders are said to be...