You are currently browsing the category archive for the ‘Abstract Algebra’ category.

In this post, I’d like to move from abstract, general considerations of Boolean algebras to more concrete ones, by analyzing what happens in the finite case. A rather thorough analysis can be performed, and we will get our first taste of a simple categorical duality, the finite case of Stone duality which we call “baby Stone duality”.

Since I have just mentioned the “c-word” (categories), I should say that a strong need for some very basic category theory makes itself felt right about now. It is true that Marshall Stone stated his results before the language of categories was invented, but it’s also true (as Stone himself recognized, after categories were invented) that the most concise and compelling and convenient way of stating them is in the language of categories, and it would be crazy to deny ourselves that luxury.

I’ll begin with a relatively elementary but very useful fact discovered by Stone himself — in retrospect, it seems incredible that it was found only after decades of study of Boolean algebras. It says that Boolean algebras are essentially the same things as what are called Boolean rings:

Definition: A Boolean ring is a commutative ring (with identity $1$) in which every element $x$ is idempotent, i.e., satisfies $x^2 = x$.

Before I explain the equivalence between Boolean algebras and Boolean rings, let me tease out a few consequences of this definition.

Proposition 1: For every element $x$ in a Boolean ring, $2x = 0$.

Proof: By idempotence, we have $x + 1 = (x+1)^2 = x^2 + 2x + 1$. Since $x = x^2$, we may additively cancel in the ring to conclude $0 = 2x$. $\Box$

This proposition implies that the underlying additive group of a Boolean ring is a vector space over the field $\mathbb{Z}_2$ consisting of two elements. I won’t go into details about this, only that it follows readily from the proposition if we define a vector space over $\mathbb{Z}_2$ to be an abelian group $V$ together with a ring homomorphism $\mathbb{Z}_2 \to Hom(V, V)$ to the ring of abelian group homomorphisms from $V$ to itself (where such homomorphisms are “multiplied” by composing them; the idea is that this ring homomorphism takes an element $r = 0, 1$ to scalar-multiplication $r \cdot (-): V \to V$).

Anyway, the point is that we can now apply some linear algebra to study this $\mathbb{Z}_2$-vector space; in particular, a finite Boolean ring $B$ is a finite-dimensional vector space over $\mathbb{Z}_2$. By choosing a basis, we see that $B$ is vector-space isomorphic to $\mathbb{Z}_{2}^{n}$ where $n$ is the dimension. So the cardinality of a finite Boolean ring must be of the form $2^n$. Hold that thought!

Now, the claim is that Boolean algebras and Boolean rings are essentially the same objects. Let me make this more precise: given a Boolean ring $B$, we may construct a corresponding Boolean algebra structure on the underlying set of $B$, uniquely determined by the stipulation that the multiplication $x \cdot y$ of the Boolean ring match the meet operation $x \wedge y$ of the Boolean algebra. Conversely, given a Boolean algebra $B$, we may construct a corresponding Boolean ring structure on $B$, and this construction is inverse to the previous one.

In one direction, suppose $B$ is a Boolean ring. We know from before that a binary operation on a set $B$ that is commutative, associative, unital [has a unit or identity] and idempotent — here, the multiplication of $B$ — can be identified with the meet operation of a meet-semilattice structure on $B$, uniquely specified by taking its partial order to be defined by: $x \leq y$ iff $x = x \cdot y$. It immediately follows from this definition that the additive identity $0 \in B$ satisfies $0 \leq y$ for all $y$ (is the bottom element), and the multiplicative identity $1 \in B$ satisfies $x \leq 1$ for all $x$ (is the top element).

Notice also that $x \wedge (1-x) = x (1-x) = 0$, by idempotence. This leads one to suspect that $1-x$ will be the complement of $x$ in the Boolean algebra we are trying to construct; we are partly encouraged in this by noting $x = 1 - (1 - x)$, i.e., $x$ is equal to its putative double negation.

Proposition 2: $x \mapsto 1-x$ is order-reversing.

Proof: Looking at the definition of the order, this says that if $x = x y$, then $1-y = (1-x)(1-y)$. This is immediate. $\Box$

So, $x \mapsto 1 - x$ is an order-reversing map $B \to B$ (an order-preserving map $B \to B^{op}$) which is a bijection (since it is its own inverse). We conclude that $B \to B^{op}: x \mapsto 1-x$ is a poset isomorphism. Since $B$ has meets and $B \cong B^{op}$, $B^{op}$ also has meets (and the isomorphism preserves them). But meets in $B^{op}$ are joins in $B$. Hence $B$ has both meets and joins, i.e., is a lattice. More exactly, we are saying that the function $f(x) = 1 - x$ takes meets in $B$ to joins in $B$; that is,

$f(x \wedge y) = 1 - x y = f(x) \vee f(y) = (1 - x) \vee (1 - y)$

or, replacing $x$ by $1-x$ and $y$ by $1-y$,

$1 - (1-x)(1-y) = x \vee y$

whence $x \vee y = x + y - x y = x + y + xy$, using the proposition 1 above.

Proposition 3: $1 - x$ is the complement of $x$.

Proof: We already saw $x \wedge (1-x) = x(1-x) = 0$. Also

$x \vee (1-x) = x + (1 - x) + x(1-x) = x + (1-x) + 0 = 1,$

using the formula for join we just computed. This completes the proof. $\Box$

So the lattice is complemented; the only thing left to check is distributivity. Following the definitions, we have $(x \vee y) \wedge z = (x + y + xy)z = xz + yz + xyz$. On the other hand, $(x \wedge z) \vee (y \wedge z) = xz + yz + (xz)(yz) = xz + yz + xyz$, using idempotence once again. So the distributive law for the lattice is satisfied, and therefore we get a Boolean algebra from a Boolean ring.

Naturally, we want to invert the process: starting with a Boolean algebra structure on a set $B$, construct a corresponding Boolean ring structure on $B$ whose multiplication is the meet of the Boolean algebra (and also show the two processes are inverse to one another). One has to construct an appropriate addition operation for the ring. The calculations above indicate that the addition should satisfy $x \vee y = x + y + x \wedge y$, so that $x \vee y = x + y$ if $x \wedge y = 0$ (i.e., if $x$ and $y$ are disjoint): this gives a partial definition of addition. Continuing this thought, if we express $x \vee y = x + y + x \wedge y$ as a disjoint sum of some element $a$ and $x \wedge y$, we then conclude $x \vee y = a + x \wedge y$, whence $a = x + y$ by cancellation. In the case where the Boolean algebra is a power set $PX$, this element $a$ is the symmetric difference of $x$ and $y$. This generalizes: if we define the addition by the symmetric difference formula $x + y := (\neg x \wedge y) \vee (x \wedge \neg y)$, then $x + y$ is disjoint from $x \wedge y$, so that

$(x + y) + x \wedge y$

$= (x + y) \vee (x \wedge y) = (\neg x \wedge y) \vee (x \wedge \neg y) \vee (x \wedge y) = x \vee y$

after a short calculation using the complementation and distributivity axioms. After more work, one shows that $x + y$ is the addition operation for an abelian group, and that multiplication distributes over addition, so that one gets a Boolean ring.

Exercise: Verify this last assertion.

However, the assertion of equivalence between Boolean rings and Boolean algebras has a little more to it: recall for example our earlier result that sup-lattices “are” inf-lattices, or that frames “are” complete Heyting algebras. Those results came with caveats: that while e.g. sup-lattices are extensionally the same as inf-lattices, their morphisms (i.e., structure-preserving maps) are different. That is to say, the category of sup-lattices cannot be considered “the same as” or equivalent to the category of inf-lattices, even if they have the same objects.

Whereas here, in asserting Boolean algebras “are” Boolean rings, we are making the stronger statement that the category of Boolean rings is the same as (is isomorphic to) the category of Boolean algebras. In one direction, given a ring homomorphism $f: B \to C$ between Boolean rings, it is clear that $f$ preserves the meet $x \cdot y$ and join $x + y + x y$ of any two elements $x, y$ [since it preserves multiplication and addition] and of course also the complement $1 + x$ of any $x$; therefore $f$ is a map of the corresponding Boolean algebras. Conversely, a map $f: B \to C$ of Boolean algebras preserves meet, join, and complementation (or negation), and therefore preserves the product $x \wedge y$ and sum $(\neg x \wedge y) \vee (x \wedge \neg y)$ in the corresponding Boolean ring. In short, the operations of Boolean rings and Boolean algebras are equationally interdefinable (in the official parlance, they are simply different ways of presenting of the same underlying Lawvere algebraic theory). In summary,

Theorem 1: The above processes define functors $F: \mbox{BoolRing} \to \mbox{BoolAlg}$, $G: \mbox{BoolAlg} \to \mbox{BoolRing}$, which are mutually inverse, between the category of Boolean rings and the category of Boolean algebras.

• Remark: I am taking some liberties here in assuming that the reader is already familiar with, or is willing to read up on, the basic notion of category, and of functor (= structure-preserving map between categories, preserving identity morphisms and composites of morphisms). I will be introducing other categorical concepts piece by piece as the need arises, in a sort of apprentice-like fashion.

Let us put this theorem to work. We have already observed that a finite Boolean ring (or Boolean algebra) has cardinality $2^n$ — the same as the cardinality of the power set Boolean algebra $PX$ if $X$ has cardinality $n$. The suspicion arises that all finite Boolean algebras arise in just this way: as power sets of finite sets. That is indeed a theorem: every finite Boolean algebra $B$ is naturally isomorphic to one of the form $PX$; one of our tasks is to describe $X$ in terms of $B$ in a “natural” (or rather, functorial) way. From the Boolean ring perspective, $X$ is a basis of the underlying $\mathbb{Z}_2$-vector space of $B$; to pin it down exactly, we use the full ring structure.

$X$ is naturally a basis of $PX$; more precisely, under the embedding $i: X \to PX$ defined by $x \mapsto \{x\}$, every subset $S \subseteq X$ is uniquely a disjoint sum of finitely many elements of $i(X)$: $S = \sum_{x \in X} a_x(S) \{x\}$ where $a_x(S) \in \{0, 1\} = \mathbb{Z}_2$: naturally, $a_x(S) = 1$ iff $x \in S$. For each $S$, we can treat the coefficient $a_x(S)$ as a function of $x$ valued in $\mathbb{Z}_2$. Let $\hom(X, \mathbb{Z}_2)$ denote the set of functions $X \to \mathbb{Z}_2$; this becomes a Boolean ring under the obvious pointwise definitions $(f + g)(x) := f(x) + g(x)$ and $(f g)(x) = f(x) g(x)$. The function $PX \to \hom(X, \mathbb{Z}_2)$ which takes $S \in PX$ to the coefficient function $a_{(-)}(S)$ is a Boolean ring map which is one-to-one and onto, i.e., is a Boolean ring isomorphism. (Exercise: verify this fact.)

Or, we can turn this around: for each $x \in X$, we get a Boolean ring map $PX \to \mathbb{Z}_2$ which takes $S$ to $a_x(S)$. Let $\mbox{Bool}(PX, \mathbb{Z}_2)$ denote the set of Boolean ring maps $PX \to \mathbb{Z}_2$.

Proposition 4: For a finite set $X$, the function $X \to \mbox{Bool}(PX, \mathbb{Z}_2)$ that sends $x$ to $a_x(-)$ is a bijection (in other words, an isomorphism).

Proof: We must show that for every Boolean ring map $\phi: PX \to \mathbb{Z}_2$, there exists a unique $x \in X$ such that $\phi = a_x(-)$, i.e., such that $\phi(T) = a_x(T)$ for all $T \in PX$. So let $\phi$ be given, and let $S$ be the intersection (or Boolean ring product) of all $T \in PX$ for which $\phi(T) = 1$. Then

$\phi(S) = \phi(\prod_{T: \phi(T) = 1} T) = \prod_{T: \phi(T) = 1} \phi(T) = 1$.

I claim that $S$ must be a singleton $\{x\}$ for some (evidently unique) $x \in X$. For $1 = \phi(S) = \phi(\sum_{x \in S} \{x\}) = \sum_{x \in S} \phi(\{x\})$, forcing $\phi(\{x\}) = 1$ for some $x \in S$. But then $S \subseteq \{x\}$ according to how $S$ was defined, and so $S = \{x\}$. To finish, I now claim $\phi(T) = a_x(T)$ for all $T \in PX$. But $\phi(T) = 1$ iff $S \subseteq T$ iff $x \in T$ iff $a_x(T) = 1$. This completes the proof. $\Box$

This proposition is a vital clue, for if $B$ is to be isomorphic to a power set $PX$ (equivalently, to $\hom(X, \mathbb{Z}_2)$), the proposition says that the $X$ in question can be retrieved reciprocally (up to isomorphism) as $\mbox{Bool}(B, \mathbb{Z}_2)$.

With this in mind, our first claim is that there is a canonical Boolean ring homomorphism

$B \to \hom(\mbox{Bool}(B, \mathbb{Z}_2), \mathbb{Z}_2)$

which sends $b \in B$ to the function $eval_b$ which maps $\phi \in \mbox{Bool}(B, \mathbb{Z}_2)$ to $\phi(b)$ (i.e., evaluates $\phi$ at $b$). That this is a Boolean ring map is almost a tautology; for instance, that it preserves addition amounts to the claim that $eval_{b+c}(\phi) = eval_b(\phi) + eval_c(\phi)$ for all $\phi \in \mbox{Bool}(B, \mathbb{Z}_2)$. But by definition, this is the equation $\phi(b+c) = \phi(b) + \phi(c)$, which holds since $\phi$ is a Boolean ring map. Preservation of multiplication is proved in exactly the same manner.

Theorem 2: If $B$ is a finite Boolean ring, then the Boolean ring map

$eval: B \to \hom(\mbox{Bool}(B, \mathbb{Z}_2), \mathbb{Z}_2)$

is an isomorphism. (So, there is a natural isomorphism $B \cong P(\mbox{Bool}(B, \mathbb{Z}_2)$.)

Proof: First we prove injectivity: suppose $b \in B$ is nonzero. Then $\neg b \neq 1$, so the ideal $(\neg b) = \{a \cdot \neg b: a \in B\} = \{x \in B: x \leq \neg b\}$ is a proper ideal. Let $I$ be a maximal proper ideal containing $\neg b$, so that $B/I$ is both a field and a Boolean ring. Then $B/I \cong \mathbb{Z}_2$ (otherwise any element $x \in B/I$ not equal to $0, 1 \in B/I$ would be a zero divisor on account of $x(1-x) = 0$). The evident composite

$B \to B/I \cong \mathbb{Z}_2$

yields a homomorphism $\phi: B \to \mathbb{Z}_2$ for which $\phi(\neg b) = \phi(1-b) = 0$, so $\phi(b) = eval_b(\phi) = 1$. Therefore $eval_b$ is nonzero, as desired.

Now we prove surjectivity. A function $g: \mbox{Bool}(B, \mathbb{Z}_2) \to \mathbb{Z}_2$ is determined by the set of elements $\phi$ mapping to $1$ under $g$, and each such homomorphism $\phi: B \to \mathbb{Z}_2$, being surjective, is uniquely determined by its kernel, which is a maximal ideal. Let $J$ be the intersection of these maximal ideals; it is an ideal. Notice that an ideal is closed under joins in the Boolean algebra, since if $x, y$ belong to $J$, then so does $x \vee y = x + y + x y$. Let $j$ be the join of the finitely many elements of $J$; notice $J = \{x \in B: x \leq j\} = (j)$ (actually, this proves that every ideal of a finite Boolean ring $B$ is principal). In fact, writing $k_\phi$ for the unique element such that $\ker(\phi) = (k_\phi)$, we have

$j = \bigwedge_{\phi: g(\phi) = 1} k_\phi$

(certainly $j \leq k_\phi$ for all such $\phi$, since $J \subseteq \ker(\phi) = \{x \in B: x \leq k_\phi\}$, but also $\bigwedge_{g(\phi) = 1} k_\phi$ belongs to the intersection of these kernels and hence to $J = \{x \in B: x \leq j\}$, whence $\bigwedge_{g(\phi) = 1} k_\phi \leq j$).

Now let $b = 1- j$; I claim that $g = eval_b$, proving surjectivity. We need to show $g(\phi) = eval_b(\phi) = \phi(b)$ for all $\phi \in \mbox{Bool}(B, \mathbb{Z}_2)$. In one direction, we already know from the above that if $g(\phi) = 1$, then $j$ belongs to the kernel of $\phi$, so $\phi(j) = 0$, whence $\phi(b) = \phi(1-j) = 1$.

For the other direction, suppose $\psi(b) = 1$, or that $\psi(j) = 0$. Now the kernel of $\psi$ is principal, say $(k)$ for some $k \neq 1$. We have $j \leq k$, so

$k = k \vee j = k \vee \bigwedge_{g(\phi) = 1} k_\phi = \bigwedge_{g(\phi) = 1} k \vee k_\phi$

from which it follows that $k \vee k_\phi \neq 1$ for some $\phi \in g^{-1}(1)$. But then $(k \vee k_\phi)$ is a proper ideal containing the maximal ideals $(k)$ and $(k_\phi)$; by maximality it follows that $(k) = (k \vee k_\phi) = (k_\phi)$. Since $\psi$ and $\phi$ have the same kernels, they are equal. And therefore $g(\psi) = g(\phi) = 1$. We have now proven both directions of the statement ($\psi(b) = 1$ if and only if $g(\psi) = 1$), and the proof is now complete. $\Box$

• Remark: In proving both injectivity and surjectivity, we had in each case to pass back and forth between certain elements $b$ and their negations, in order to take advantage of some ring theory (kernels, principal ideals, etc.). In the usual treatments of Boolean algebra theory, one circumvents this passage back-and-forth by introducing the notion of a filter of a Boolean algebra, dual to the notion of ideal. Thus, whereas an ideal is a subset $I \subseteq B$ closed under joins and such that $x \wedge y \in I$ for $x \in B, y \in I$, a filter is (by definition) a subset $F$ closed under meets and such that $x \vee y \in F$ whenever $x \in B, y \in F$ (this second condition is equivalent to upward-closure: $y \in F$ and $y \leq x$ implies $x \in F$). There are also notions of principal filter and maximal filter, or ultrafilter as it is usually called. Notice that if $I$ is an ideal, then the set of negations $\{\neg x: x \in I\}$ is a filter, by the De Morgan laws, and vice-versa. So via negation, there is a bijective correspondence between ideals and filters, and between maximal ideals and ultrafilters. Also, if $f: B \to C$ is a Boolean algebra map, then the inverse image $f^{-1}(1)$ is a filter, just as the inverse image $f^{-1}(0)$ is an ideal. Anyway, the point is that had we already had the language of filters, the proof of theorem 2 could have been written entirely in that language by straightforward dualization (and would have saved us a little time by not going back and forth with negation). In the sequel we will feel free to use the language of filters, when desired.

For those who know some category theory: what is really going on here is that we have a power set functor

$P(-) = \hom(-, \mathbb{Z}_2): \mbox{FinSet}^{op} \to \mbox{FinBool}$

(taking a function $f: X \to Y$ between finite sets to the inverse image map $f^{-1}: PY \to PX$, which is a map between finite Boolean algebras) and a functor

$Q(-) = \mbox{Bool}(-, \mathbb{Z}_2): \mbox{FinBool}^{op} \to \mbox{FinSet}$

which we could replace by its opposite $Q(-)^{op}: \mbox{FinBool} \to \mbox{FinSet}^{op}$, and the canonical maps of proposition 4 and theorem 2,

$X \to \mbox{Bool}(\hom(X, \mathbb{Z}_2), \mathbb{Z}_2),$

$B \to \hom(\mbox{Bool}(B, \mathbb{Z}_2), \mathbb{Z}_2),$

are components (at $X$ and $B$) of the counit and unit for an adjunction $Q(-)^{op} \dashv P(-)$. The actual statements of proposition 4 and theorem 2 imply that the counit and unit are natural isomorphisms, and therefore we have defined an adjoint equivalence between the categories $\mbox{FinSet}^{op}$ and $\mbox{FinBool}$. This is the proper categorical statement of Stone duality in the finite case, or what we are calling “baby Stone duality”. I will make some time soon to explain what these terms mean.

The study of binary algebraic structures (or binary structures) and isomorphisms is a basic (and fundamental) one in the study of abstract algebra, and in some sense, the connection between these two concepts is similar to (in fact, extends) the one between sets and bijection. This post explores that connection.

Recall, two sets $A$ and $B$ have the same “size”, or have an equal number of elements, if there exists a bijection (or bijective function) $f: A \to B$, i.e. $f$ is a mapping that is both one-to-one and onto. If $A$ and $B$ are both finite sets, then it is easy to prove if there exists a bijection between the two. However, if $A$ and $B$ are infinite sets, then it is usually a non-trivial task proving the existence of a bijection (if there exists one!) between the two sets.

One way of looking at this is by viewing the “structure” of sets as an “obstruction.” So, for instance, we could ask, what could obstruct two sets $A$ and $B$ from having a bijection $f: A\to B$? Answer: if they have different cardinalities (which may be viewed as a structural property). Okay, I admit the answer is somewhat circular, but we will stick with this for now. Now, is cardinality the only obstruction to the existence of a bijection between any two sets? It turns out the answer is yes. In other words, two sets have the same cardinality if and only if there exists a bijection between the two. Now, let’s extend this further to binary algebraic structures and isomorphisms.

Let’s quickly go through some definitions, first.

1) A binary operation $\, *$ on a set $S$ is a function mapping $S \mbox{x} S$ into $S$.

2) A binary algebraic structure $$ is a set $S$ together with a binary operation $\, *$ on $S$.

3) Let $$ and $$ be binary algebraic structures. An isomorphism of $S$ with $S'$ is a one-to-one and onto function $\phi: S \to S'$ such that

$\phi (x * y) = \phi (x)*' \phi (y) \quad \forall x, y \in S$.

We note above that the notion of isomorphism between binary algebraic structures “extends” the notion of bijection between sets, in the sense that isomorphism tells us how similar two binary structures are. Just as the existence of a bijection between sets $A$ and $B$ tells us they have the same cardinality (which may be considered a structural property), the existence of an isomorphism between binary structures also tells us how similar they are “structurally.”

Now, just as we asked, earlier, what possible obstructions there might be to the existence of a bijection between two sets, we may ask in a similar vein, what possible obstructions might there be to the existence of an isomorphism between two binary structures $$ and $$? Answer: there is more than one. Let us take a look at some of those obstructions.

1) Cardinality of the sets $S$ and $S'$.

If $S$ and $S'$ have different cardinalities, then it is easy to prove that there does not exist an isomorphism $\phi: S \to S'$, i.e. $$ and $$ are not isomorphic. For example, $<\mathbb{Q}, +>$ and $< \mathbb{R}, +>$ (where $+$ is the usual addition) are not isomorphic because $\mathbb{Q}$ has cardinality $\aleph_{0}$ while $|\mathbb{R}| \ne \aleph_{0}$. Note that it is not enough to say that $\mathbb{Q}$ is subset of $\mathbb{R}$. For example, $<2\mathbb{Z}, +>$ is isomorphic to $<\mathbb{Z}, +>$ (where $+$ is the usual addition) even though $2\mathbb{Z}$ is a subset of $\mathbb{Z}$. (Here, $2\mathbb{Z} = \{ 2n \mid n \in \mathbb{Z} \}$.)

(More to come …)

• 371,445 hits