Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Thanks to a comment of Gerhard Paseman on my answer to this MO questionMO question, I recently learned that the algebras of the Lawvere theory $Fin_{3^-}$ are better known as $3$-valued Post algebras, and there is a similar notion of $n$-valued Post algebra. That gives perhaps a quicker answer to Harrison's question.

Thanks to a comment of Gerhard Paseman on my answer to this MO question, I recently learned that the algebras of the Lawvere theory $Fin_{3^-}$ are better known as $3$-valued Post algebras, and there is a similar notion of $n$-valued Post algebra. That gives perhaps a quicker answer to Harrison's question.

Thanks to a comment of Gerhard Paseman on my answer to this MO question, I recently learned that the algebras of the Lawvere theory $Fin_{3^-}$ are better known as $3$-valued Post algebras, and there is a similar notion of $n$-valued Post algebra. That gives perhaps a quicker answer to Harrison's question.

added 428 characters in body
Source Link
Todd Trimble
  • 53.3k
  • 6
  • 205
  • 322

Thanks to a comment of Gerhard Paseman on my answer to this MO question, I recently learned that the algebras of the Lawvere theory $Fin_{3^-}$ are better known as $3$-valued Post algebras, and there is a similar notion of $n$-valued Post algebra. That gives perhaps a quicker answer to Harrison's question.


Thanks to a comment of Gerhard Paseman on my answer to this MO question, I recently learned that the algebras of the Lawvere theory $Fin_{3^-}$ are better known as $3$-valued Post algebras, and there is a similar notion of $n$-valued Post algebra. That gives perhaps a quicker answer to Harrison's question.

Source Link
Todd Trimble
  • 53.3k
  • 6
  • 205
  • 322

Harrison, I've been meaning to blog a bit about this somewhere, but I might as well put something down here in case it's useful to you.

As you know, there are lots of ways of defining Boolean algebras. I'm going to focus on one (due in large part to Lawvere) that may open one's eyes to some not-too-well-known possibilities. It starts by observing that for any finitary algebraic theory $T$, the category of algebras is equivalent to the category of product-preserving functors

$$Kl(T)^{op} \to Set$$

where $Kl(T)$, aka the Kleisli category, is the category of finitely generated free algebras. (The morphisms here are of course natural transformations.) This is "Lawvere Theories 101" (the Lawvere theory of an algebraic theory or monad $T$ being defined as $Kl(T)^{op}$). In the case we are concerned with, the finitely generated free Boolean algebras are finite Boolean algebras of cardinality $2^{2^n}$, and by a baby form of Stone duality, the opposite of the category of finitely generated free Boolean algebras is equivalent to the category of finite sets having cardinalities of the form $2^n$.

Let's call this category $Fin_{2^{-}}$. Thus the category of Boolean algebras is equivalent to the category of product-preserving functors

$$Fin_{2^{-}} \to Set$$

But we can say it more nicely than that. A functor $F: C \to Set$ extends uniquely (up to isomorphism) to the so-called Cauchy completion of $C$, aka the Karoubi envelope or idempotent-splitting completion of $C$, which I'll denote as $\bar{C}$. Moreover, if $C$ has finite products and $F$ preserves them, then it's an easy exercise that $\bar{C}$ acquires finite products and the extension $\bar{F}: \bar{C} \to Set$ preserves them. In the present case, it is easy to see that the idempotent-splitting completion of $C = Fin_{2^-}$ is the category $Fin$ of all finite sets, basically because any (nonempty) finite set is a retract of a finite set of cardinality $2^n$.

Putting all this together, we obtain what I think is a pretty description of the category of Boolean algebras: it is equivalent to the category of product-preserving functors

$$Fin \to Set$$

(which I believe Lawvere and Schanuel have taken to calling "distributions".) One of the beauties of this description is that it is totally unbiased: there is no special bias toward finite sets of cardinality $2^n$.

In fact, all this shows that we could, if we want, change our bias to, say, finite sets of cardinality $3^n$. In other words, the category of such sets is also a category with finite products, and its Cauchy completion is again $Fin$, and therefore we are within our rights to describe the category of Boolean algebras as equivalent to the category of product-preserving functors of the form

$$Fin_{3^-} \to Set$$

The category $Fin_{3^-}$ a perfectly legitimate single-sorted Lawvere theory $T'$; the generic object is the finite set $3^1$, of which all other objects in $T'$ are finite products. Using this to extract an alternative operations-and-equations presentation of the theory of Boolean algebras is an interesting exercise, but maybe I'll confine myself to some additional remarks that bear a bit on Stone duality.

From Lawvere Theories 101, we know that the free $T'$-algebra on $n$-generators, $F(n)$, is in this case given by the representable (note that representable functors automatically preserve products)

$$Fin_{3^-}(3^n, -) = Fin(3^n, -): Fin_{3^-} \to Set$$

If $A$ is a $T'$-algebra, then the underlying set is naturally identified as

$$U(A) = Set(1, U(A)) \cong T'\text{-Alg}(F(1), A) \cong Nat(Fin(3^1, -), A-)$$

(in the last step identifying $T'$-algebras with product-preserving functors $A$). For example, if $A = F(n) = Fin(3^n, -)$, then we have

$$U(A) \cong Nat(Fin(3^1, -), Fin(3^n, -)) \cong Fin(3^n, 3)$$

by the Yoneda lemma, whence the underlying set of the $T'$-algebra $F(n)$ has $3^{3^n}$ elements, in perfect analogy with the standard description of the free Boolean algebra on $n$ generators having $2^{2^n}$ elements. (Obviously I shouldn't say "the" underlying set; one of the morals here is that there can be many underlying-set functors which are monadic for a given variety of algebras.)

Next, we can analogize baby Stone duality for finite Boolean algebras, which says that homming into the free Boolean algebra on 0 generators (the Boolean algebra with two elements) induces an equivalence

$$Bool_{fp}^{op} \to Fin$$

where $Bool_{fp}$ stands for the category of finitely presented Boolean algebras. Of course, notions like "finitely presented Boolean algebras" and the "free Boolean algebra on 0 generators" have perfectly invariant unbiased descriptions, but if we allow ourselves to be biased toward $T'$-algebras, where the free $T'$-algebra has $3^{3^0} = 3$ elements, then baby Stone duality reads

  • The functor $T'\text{-Alg}(-, 3): T'\text{-Alg}(-, 3): T'\text{-Alg}_{fp}^{op} \to Fin$ is an equivalence.

The other direction of the equivalence is the obvious functor $Fin(-, 3): Fin^{op} \to T'-\text{Alg}_{fp}$, which sends a finite set $X$ to $3^X$, with the pointwise-defined $T'$-algebra operations induced by the $T'$-algebra structure on $3$.

Similarly, an ultrafilter on a set $X$ (or an ultrafilter in a $T'$-algebra $A$) may be defined as a $T'$-algebra map $3^X \to 3$ (a $T'$-algebra map $A \to 3$, resp.). Thus the general Stone duality may be lifted to the context of $T'$-algebras.

These observations (which I discovered for myself only recently, but which are undoubtedly known to people like Lawvere and Schanuel) may help shed some light on an observation made by Lawvere which might be a bit mysterious otherwise. Namely, if we consider the subtheory of $T'$ generated by the unary operations, noticing that unary operations under composition form a monoid which is isomorphic to the monoid of endomorphisms $M = Fin(3, 3)$ (again by the Yoneda lemma), then we get a forgetful functor

$$Bool \simeq T'\text{-Alg} \to Set^M$$

where $Set^M$ denotes the category of sets equipped with an $M$-action, or $M$-sets for short. It turns out that this is a full embedding; in other words, if a function between $T'$-algebras preserves just the unary operations, then it preserves all the $T'$-operations. (This is a nice exercise.) Therefore, we may identify an ultrafilter on a set $X$ as being essentially the same as a homomorphism of $M$-sets

$$3^X \to 3$$

(This doesn't work if $3$ is replaced by $2$!) And similarly if $3$ is replaced by any $n \geq 3$. (Lawvere goes on to say that countably complete ultrafilters may be equivalently defined as functions $\mathbb{N}^X \to \mathbb{N}$ which preserve the evident actions by the monoid of endofunctions on $\mathbb{N}$. Thus, the canonical map

$$prin_X: X \to Set^{End(\mathbb{N})}(\mathbb{N}^X, \mathbb{N})$$

which is the unit of an evident monad

$$Set \stackrel{\mathbb{N}^-}{\to} Set^{End(\mathbb{N})} \stackrel{\hom(-, \mathbb{N})}{\to} Set$$

on $Set$, fails to be an isomorphism if and only if there exists a measurable cardinal.