You are currently browsing the category archive for the ‘Uncategorized’ 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.

[Update: Look for another (slicker) solution I found after coming up with the first one.]

My friend, John, asked me today if I had a solution to the following (well-known) problem which may be found, among other sources, in Chapter Zero (!) of the very famous book, Mathematical Circles (Russian Experience).

Three tablespoons of milk from a glass of milk are poured into a glass of tea, and the liquid is thoroughly mixed. Then three tablespoons of this mixture are poured back into the glass of milk. Which is greater now: the percentage of milk in the tea or the percentage of tea in the milk?

Note that there is nothing special about transferring three tablespoons of milk and/or tea from one glass to another – the problem doesn’t really change if we transfer one tablespoon of milk/tea instead, and that there is nothing special about transferring “volumes” – we could instead keep a count of, say, the number of molecules transferred.  We may, therefore, pose ourselves the following analogous “discrete” problem whose solution provides more “insight” into what’s really going on.

Jar W contains $n$ white objects (and no other objects) and jar B contains $n$ black objects (and no other objects.) We transfer $k$ objects from jar W to jar B. We then thoroughly mix –  in fact, we don’t have to – the contents of jar B, following which we transfer $k$ objects, this time, from jar B to jar W. Which is greater now: the percentage of black objects in jar W or the percentage of white objects in jar B?

Solution 1: Let us keep track of the number of black and white objects in both the jars before and after the transfers of $k$ objects from one jar to another. So, initially, in jar W,

# of white objects = $n$, and # of black objects = $0 \,$.

Also, in jar B,

# of white objects = $0 \,$, and # of black objects = $n$.

Now, we transfer $k$ objects from jar W to jar B. So, in jar W,

# of white objects = $n-k$, and # of black objects = $0 \,$.

Also, in jar B,

# of white objects = $k$, and # of black objects = $n$.

Finally, we transfer $k$ objects from jar B to jar W. Let the number of white objects out of those $k$ objects be $k_1$. Then, the number of black objects transferred equals $k-k_1$. Therefore, now, in jar W,

# of white objects = $n-k + k_1$, and # of black objects = $k-k_1$.

Also, in jar B,

# of white objects = $k-k_1$, and # of black objects = $n - (k-k_1)$.

From here, it is easy to see that the percentage of black objects in jar W is the same as the percentage of white objects in jar B! And, we are done.

Solution 2: (I think this is a slicker one, and I found it after pondering a little over the first solution I wrote above!) This one uses the idea of invariants, and there are, in fact, two of ‘em in this problem! Note that at any given time,

# of white objects = # of black objects = $n$.

The above is the first invariant.

Also, note that after we transfer $k$ objects from jar W to jar B and then $k$ objects from jar B to jar W, the number of objects in each jar is also $n$. This is the second invariant. And, now the problem is almost solved!

Suppose, after we do the transfers of $k$ objects from jar W to jar B and then from jar B to jar W, the # of white objects in jar W is $k$. Then it is easy to see that the # of black objects in jar W is $n-k$ (using the second invariant mentioned above.) Similarly, using the first invariant, the # of white objects in jar B = $n-k$. Therefore, using the second invariant again, the # of black objects in jar B = $n - (n-k) = k$. And, from this the conclusion immediately follows!

Last time in this series on Stone duality, we introduced the concept of lattice and various cousins (e.g., inf-lattice, sup-lattice). We said a lattice is a poset with finite meets and joins, and that inf-lattices and sup-lattices have arbitrary meets and joins (meaning that every subset, not just every finite one, has an inf and sup). Examples include the poset $PX$ of all subsets of a set $X$, and the poset $Sub(V)$ of all subspaces of a vector space $V$.

I take it that most readers are already familiar with many of the properties of the poset $PX$; there is for example the distributive law $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$, and De Morgan laws, and so on — we’ll be exploring more of that in depth soon. The poset $Sub(V)$, as a lattice, is a much different animal: if we think of meets and joins as modeling the logical operations “and” and “or”, then the logic internal to $Sub(V)$ is a weird one — it’s actually much closer to what is sometimes called “quantum logic”, as developed by von Neumann, Mackey, and many others. Our primary interest in this series will be in the direction of more familiar forms of logic, classical logic if you will (where “classical” here is meant more in a physicist’s sense than a logician’s).

To get a sense of the weirdness of $Sub(V)$, take for example a 2-dimensional vector space $V$. The bottom element is the zero space $\{0\}$, the top element is $V$, and the rest of the elements of $Sub(V)$ are 1-dimensional: lines through the origin. For 1-dimensional spaces $x, y$, there is no relation $x \leq y$ unless $x$ and $y$ coincide. So we can picture the lattice as having three levels according to dimension, with lines drawn to indicate the partial order:

V = 1
/ | \
/   |   \
x    y    z
\   |   /
\ | /
0

Observe that for distinct elements $x, y, z$ in the middle level, we have for example $x \wedge y = 0 = x \wedge z$ (0 is the largest element contained in both $x$ and $y$), and also for example $y \vee z = 1$ (1 is the smallest element containing $y$ and $z$). It follows that $x \wedge (y \vee z) = x \wedge 1 = x$, whereas $(x \wedge y) \vee (x \wedge z) = 0 \vee 0 = 0$. The distributive law fails in $Sub(V)$!

Definition: A lattice is distributive if $x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)$ for all $x, y, z$. That is to say, a lattice $X$ is distributive if the map $x \wedge -: X \to X$, taking an element $y$ to $x \wedge y$, is a morphism of join-semilattices.

1. Exercise: Show that in a meet-semilattice, $x \wedge -: X \to X$ is a poset map. Is it also a morphism of meet-semilattices? If $X$ has a bottom element, show that the map $x \wedge -$ preserves it.
2. Exercise: Show that in any lattice, we at least have $(x \wedge y) \vee (x \wedge z) \leq x \wedge (y \vee z)$ for all elements $x, y, z$.

Here is an interesting theorem, which illustrates some of the properties of lattices we’ve developed so far:

Theorem: The notion of distributive lattice is self-dual.

Proof: The notion of lattice is self-dual, so all we have to do is show that the dual of the distributivity axiom, $x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)$, follows from the distributive lattice axioms.

Expand the right side to $((x \vee y) \wedge x) \vee ((x \vee y) \wedge z)$, by distributivity. This reduces to $x \vee [(x \vee y) \wedge z]$, by an absorption law. Expand this again, by distributivity, to $x \vee (x \wedge z) \vee (y \wedge z)$. This reduces to $x \vee (y \wedge z)$, by the other absorption law. This completes the proof. $\Box$

Distributive lattices are important, but perhaps even more important in mathematics are lattices where we have not just finitary, but infinitary distributivity as well:

Definition: A frame is a sup-lattice for which $x \wedge -: X \to X$ is a morphism of sup-lattices, for every $x \in X$. In other words, for every subset $S \subseteq X$, we have $\sup(\{x \wedge s: s \in S\}) = x \wedge \sup(S)$, or, as is often written,

$\bigvee_{s \in S} x \wedge s = x \wedge \bigvee_{s \in S} s.$

Example: A power set $PX$, as always partially ordered by inclusion, is a frame. In this case, it means that for any subset $A$ and any collection of subsets $\{B_i: i \in I\}$, we have

$A \cap (\bigcup_{i \in I} B_i) = \bigcup_{i \in I} A \cap B_i$

This is a well-known fact from naive set theory, but soon we will see an alternative proof, thematically closer to the point of view of these notes.

Example: If $X$ is a set, a topology on $X$ is a subset $\mathbf{T} \subseteq PX$ of the power set, partially ordered by inclusion as $PX$ is, which is closed under finite meets and arbitrary sups. This means the empty sup or bottom element $\emptyset$ and the empty meet or top element $X$ of $PX$ are elements of $\mathbf{T}$, and also:

1. If $U, V$ are elements of $\mathbf{T}$, then so is $U \cap V$.
2. If $\{U_i: i \in I\}$ is a collection of elements of $\mathbf{T}$, then $\bigcup_{i \in I} U_i$ is an element of $\mathbf{T}$.

A topological space is a set $X$ which is equipped with a topology $\mathbf{T}$; the elements of the topology are called open subsets of the space. Topologies provide a primary source of examples of frames; because the sups and meets in a topology are constructed the same way as in $PX$ (unions and finite intersections), it is clear that the requisite infinite distributivity law holds in a topology.

The concept of topology was originally rooted in analysis, where it arose by contemplating very generally what one means by a “continuous function”. I imagine many readers who come to a blog titled “Topological Musings” will already have had a course in general topology! but just to be on the safe side I’ll give now one example of a topological space, with a promise of more to come later. Let $X$ be the set $\mathbb{R}^n$ of $n$-tuples of real numbers. First, define the open ball in $\mathbb{R}^n$ centered at a point $x \in \mathbb{R}^n$ and of radius $r > 0$ to be the set $\{y \in \mathbb{R}: ||x - y||$ < $r\}$. Then, define a subset $U \subseteq \mathbb{R}^n$ to be open if it can be expressed as the union of a collection, finite or infinite, of (possibly overlapping) open balls; the topology is by definition the collection of open sets.

It’s clear from the definition that the collection of open sets is indeed closed under arbitrary unions. To see it is closed under finite intersections, the crucial lemma needed is that the intersection of two overlapping open balls is itself a union of smaller open balls. A precise proof makes essential use of the triangle inequality. (Exercise?)

Topology is a huge field in its own right; much of our interest here will be in its interplay with logic. To that end, I want to bring in, in addition to the connectives “and” and “or” we’ve discussed so far, the implication connective in logic. Most readers probably know that in ordinary logic, the formula $p \Rightarrow q$ (“$p$ implies $q$“) is equivalent to “either not $p$ or $q$” — symbolically, we could define $p \Rightarrow q$ as $\neg p \vee q$. That much is true — in ordinary Boolean logic. But instead of committing ourselves to this reductionistic habit of defining implication in this way, or otherwise relying on Boolean algebra as a crutch, I want to take a fresh look at material implication and what we really ask of it.

The main property we ask of implication is modus ponens: given $p$ and $p \Rightarrow q$, we may infer $q$. In symbols, writing the inference or entailment relation as $\leq$, this is expressed as $p \wedge (p \Rightarrow q) \leq q$. And, we ask that implication be the weakest possible such assumption, i.e., that material implication $p \Rightarrow q$ be the weakest $a$ whose presence in conjunction with $p$ entails $q$. In other words, for given $p$ and $q$, we now define implication $p \Rightarrow q$ by the property

$(a \wedge p \leq q)$ if and only if $(a \leq p \Rightarrow q).$

As a very easy exercise, show by Yoneda that an implication $p \Rightarrow q$ is uniquely determined when it exists. As the next theorem shows, not all lattices admit an implication operator; in order to have one, it is necessary that distributivity holds:

Theorem:

• (1) If $X$ is a meet-semilattice which admits an implication operator, then for every element $p$, the operator $p \wedge -: X \to X$ preserves any sups which happen to exist in $X$.
• (2) If $X$ is a frame, then $X$ admits an implication operator.

Proof: (1) Suppose $S \subseteq X$ has a sup in $X$, here denoted $\bigvee_{s \in S} s$. We have

$(\bigvee_{s \in S} s) \wedge p \leq q$ if and only if

$\bigvee_{s \in S} s \leq p \Rightarrow q$ if and only if

for all $s \in S, (s \leq p \Rightarrow q)$ if and only if

for all $s \in S, (s \wedge p \leq q)$ if and only if

$\bigvee_{s \in S} (s \wedge p) \leq q$.

Since this is true for all $q$, the (dual of the) Yoneda principle tells us that $(\bigvee_{s \in S} s) \wedge p = \bigvee_{s \in S} (s \wedge p)$, as desired. (We don’t need to add the hypothesis that the sup on the right side exists, for the first four lines after “We have” show that $(\bigvee_{s \in S} s) \wedge p$ satisfies the defining property of that sup.)

(2) Suppose $p, q$ are elements of a frame $X$. Define $p \Rightarrow q$ to be $\sup(\{a \in X: a \wedge p \leq q\})$. By definition, if $a \wedge p \leq q$, then $a \leq p \Rightarrow q$. Conversely, if $a \leq p \Rightarrow q$, then

$a \wedge p \leq \sup\{x: x \wedge p \leq q\} \wedge p = \sup\{x \wedge p: x \wedge p \leq q\},$

where the equality holds because of the infinitary distributive law in a frame, and this last sup is clearly bounded above by $q$ (according to the defining property of sups). Hence $a \wedge p \leq q$, as desired. $\Box$

Incidentally, part (1) this theorem gives an alternative proof of the infinitary distributive law for Boolean algebras such as $PX$, so long as we trust that $p \Rightarrow q := \neg p \vee q$ really does what we ask of implication. We’ll come to that point again later.

Part (2) has some interesting consequences vis à vis topologies: we know that topologies provide examples of frames; therefore by part (2) they admit implication operators. It is instructive to work out exactly what these implication operators look like. So, let $U, V$ be open sets in a topology. According to our prescription, we define $U \Rightarrow V$ as the sup (the union) of all open sets $W$ with the property that $W \cap U \subseteq V$. We can think of this inclusion as living in the power set $PX$. Then, assuming our formula $U^c \cup V$ for implication in the Boolean algebra $PX$ (where $U^c$ denotes the complement of $U$), we would have $W \subseteq U^c \cup V$. And thus, our implication $U \Rightarrow V$ in the topology is the union of all open sets $W$ contained in the (usually non-open) set $U^c \cup V$. That is to say, $U \Rightarrow V$ is the largest open contained in $U^c \cup V$, otherwise known as the interior of $U^c \cup V$. Hence our formula:

$U \Rightarrow V$ = int$(U^c \cup V).$

Definition: A Heyting algebra is a lattice $H$ which admits an implication $p \Rightarrow q$ for any two elements $p, q \in H$. A complete Heyting algebra is a complete lattice which admits an implication for any two elements.

Again, our theorem above says that frames are (extensionally) the same thing as complete Heyting algebras. But, as in the case of inf-lattices and sup-lattices, we make intensional distinctions when we consider the appropriate notions of morphism for these concepts. In particular, a morphism of frames is a poset map which preserves finite meets and arbitrary sups. A morphism of Heyting algebras preserves all structure in sight (i.e., all implied in the definition of Heyting algebra — meets, joins, and implication). A morphism of complete Heyting algebras also preserves all structure in sight (sups, infs, and implication).

Heyting algebras are usually not Boolean algebras. For example, it is rare that a topology is a Boolean lattice. We’ll be speaking more about that next time soon, but for now I’ll remark that Heyting algebra is the algebra which underlies intuitionistic propositional calculus.

Exercise: Show that $(0 \Rightarrow 0) = 1$ in a Heyting algebra.

Exercise: (For those who know some general topology.) In a Heyting algebra, we define the negation $\neg x$ to be $x \Rightarrow 0$. For the Heyting algebra given by a topology, what can you say about $\neg U$ when $U$ is open and dense?

[Update: Firefox 3 Beta 5 is out - the last beta version! And it is supposedly the fastest browser out there. So, far it's been using memory not more than 150 200 Mb!]

I have been wanting to respond to some of the comments I’ve received over the past week but haven’t had enough time to do so. I will certainly respond some time soon.

For now, I just wish to point out to folks who use Firefox 2 that Firefox 3 Beta 4 has been released. Well, it is only meant for developers and testers for now, but having installed and used it over the past several days, I can say it’s  a much better version of the Firefox browser. The biggest problem (I’ve had) with the current version of Firefox is it uses an enormous amount of memory mostly due to memory leaks. Keep it running for several days – I hardly log off – and the browser takes up as much as 700-800Mb of memory, sometimes even consuming a gigabyte, which is plain insane! Due to this, I had seriolusly considered switching to Flock or IE altogether. But, now I am very satisfied with the new beta version. It mostly uses around 150Mb of memory while never exceeding 200Mb 250Mb, which really shows that the Firefox team has had been working hard on the new version.

Go ahead and download/install the new beta version and test it yourself. I haven’t had any problems thus far. The only downside of using the beta version is your add-ons will not work, but that is hardly an issue, at least to me, for now.

This post is non-mathematical in nature, and yet, I felt I should write about a very important essay written by Kant, for the rational thought expressed in the essay is very close to my heart!

In 1784, Immanuel Kant wrote an essay titled, Answer to the Question: What is Enlightenment?

He answers that question in the first paragraph of his essay:

Enlightenment is man’s emergence from his self-imposed immaturity. Immaturity is the inability to use one’s understanding without guidance from another. This immaturity is self-imposed when its cause lies not in lack of understanding, but in lack of resolve and courage to use it without guidance from another. Sapere Aude! [dare to know] “Have courage to use your own understanding!”–that is the motto of enlightenment.

And, the part that I really like is contained in the second paragraph, and it reads,

If I have a book to serve as my understanding, a pastor to serve as my conscience, a physician to determine my diet for me, and so on, I need not exert myself at all. I need not think, if only I can pay: others will readily undertake the irksome work for me. The guardians who have so benevolently taken over the supervision of men have carefully seen to it that the far greatest part of them (including the entire fair sex) regard taking the step to maturity as very dangerous, not to mention difficult. Having first made their domestic livestock dumb, and having carefully made sure that these docile creatures will not take a single step without the go-cart to which they are harnessed, these guardians then show them the danger that threatens them, should they attempt to walk alone.

When the mathematician proposed to his girlfriend, why did she turn him down?

Because he offered her a ring but she wanted a field!

(Sarah Brown)

Less than a couple of months ago, we heard of the (untimely) death of Bobby Fischer, undoubtedly the greatest chess player who ever lived on earth. For a lot of people, in his later years he was a raving arrogant “lunatic.” But few people knew/know about his human side, which was brought out in a moving eulogy on Fischer, by Dick Cavett, titled Was It Only a Game? written for The New York Times. The accompanying video in that article shows how “normal” Fischer was, just like you and me.

Here is a wonderful video of Fischer as a 15-yr old kid appearing in a game show I’ve Got a Secret.

The following is a casual interview in which Fischer smiles and laughs as never seen before.

And here is a short documentary on Fischer’s world championship match with Boris Spassky in 1972 and how he beat the gargantuan Soviet chess machine.

Ok, this one looks like it’s from XKCD but I am not entirely sure. If you do happen to know the source, I will greatly appreciate if you would tell me about it, so that I can properly cite it.

[ Thanks to Dr Armstrong for providing the correct link. ]

There is immense joy and thrill in discovering that one of the world’s greatest mathematicians (and probably many more like him) got interested in mathematics, just as I did as a kid, after reading one of Yakov I. Perelman‘s popular science books. Physics for Entertainment is the book and Grisha Perelman is the mathematician I am referring to!

Yakov I. Perelman’s books on physics, mathematics and astronomy were written in a style that brought out many of the aspects of the aforesaid subjects in the most enjoyable way. He breathed life into every page of his books and made mathematics and physics accessible to any kid in a way that brought sheer joy to the soul! At the same time, his writings provided a glimpse of the amazing way that physics helps us understand and study the nature around us. Physics Can Be Fun, Mathematics Can be Fun and Astronomy for Entertainment are the titles of some of his other books that were immensely popular among young students who read them. The credit for my long-lasting interest/passion in physics and mathematics solely goes to him.

I think all twelve-year olds should be given copies of his books as birthday gifts instead of toys! Surprisingly, there is an online copy of Physics For Entertainment here. I am not sure if any copyright laws will be violated if you download the online version but it seems that the site is a “genuine” one.