Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A Boolean lattice has a number of rather nice properties which give it a central role in many parts of combinatorics. For instance, it's a lattice, it can be augmented with a ring structure, it can also be augmented with an associative algebra structure, it has a complementation operation, it can be "identified" in different ways with things like the hypercube or a powerset, it satisfies the Stone representability theorem, etc.

It's kind of obvious that Boolean lattices are pretty closely related to the number 2. Like, they have a duality, finite ones all have order a power of 2, etc. One way to see this is to look at a (finite) Boolean lattice as the set of all functions from a set $S \rightarrow \{0, 1\}$, with the lattice and complementation structures acting pointwise.

To what extent can you get an analogue of Boolean lattices (or even posets) with some other natural number k taking the place of 2? You could consider the set of all functions from $S \rightarrow \{0, 1, ..., k-1\}$, which again gives you a poset with a lattice structure, but we don't get a complementation map (although I guess we do get some sort of "k-ality.")

There are a number of questions that this raises: Is this the proper generalization of Boolean lattices in this direction? Does some weird analogue of the Stone theorem hold? What's true for Boolean lattices but isn't true for these guys? What are the right notions to replace "hypercube" and "power set?" Etc.

share|improve this question
    
Sort of the driving question here, FWIW, is the relationship between extremal combinatorics of set systems and Ramsey theory, in particular (and most concretely) the point of view in which we take (density) Hales-Jewett to be a generalization of Sperner's theorem. –  Harrison Brown Nov 23 '09 at 6:58
    
I also don't understand what you mean by an analogue of Stone's theorem. What part of it do you care about? –  Qiaochu Yuan Nov 23 '09 at 23:28
    
I guess I really don't care that much about it, since I'm really mostly concerned with finite sets. It would be interesting to know if there's some way of looking at these things as sets of a topological space, though. –  Harrison Brown Nov 24 '09 at 2:55
add comment

7 Answers

A standard extention is to the lattice of subspaces of an n dimensional space over a field with q elements. Many nice properties of the Boolean lattice extend while others do not. Many extremal combinatorics result extend and some are even simpler.

share|improve this answer
    
Hm, interesting. Is there a name for this other than just "lattice of subspaces?" –  Harrison Brown Nov 24 '09 at 2:59
1  
Here is a link to a paper springerlink.com/content/v141451p51820482 which studies simultaneuosly a basic questions regarding ranks of incidence matrices for the Boolean lattice and for the lattice of subspaces over a field with q elements. –  Gil Kalai Nov 24 '09 at 15:28
    
This lattice coincides with the (incidence geometry) of the building of type $A_{n-1}$ over the field $\mathbb{F}_q$. The points of this geometry are the 1-dimensional subspaces, the lines the 2-dimensional subspaces etc. Buildings in general are indeed known to admit a rich theory and countless deep and beautiful properties, applications and interpretations, in many fields of mathematics, such as (finite and infinite) group theory, representation theory, combinatorics, geometry, ... –  Max Horn Jul 1 '11 at 8:44
add comment

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.


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.

share|improve this answer
add comment

One can consider the set of functions $S \to P$ where $P$ is any poset with $k$ elements. The reason the Boolean lattice is special is that the "truth poset" happens to lie at the intersection of a lot of important ideas (logic, set theory, universal algebra, etc.) and I don't think the same can be said about just any old poset.

If you want to generalize most of the important properties of the Boolean lattices I'm not convinced cardinality is the right think to be looking at.

share|improve this answer
    
Well, you'd probably be right, except that I have a well-defined goal in mind, and cardinality's gotta come into play somehow... –  Harrison Brown Nov 23 '09 at 23:16
add comment

The generalization you seek exists when k itself is a power of 2 (but gives no additional examples). This is because, as Q Yuan points out, the important properties of 2 that you seem to require are that is it a "truth" poset 2={false,true}, and when k=2^m, then there is a Boolean algebra of size k that can serve a similar purpose.

That is, the suggestion is that you should replace 2 with an arbitrary Boolean algebra B. For example, if you look at functions f:S to B, you can still perform lattice operations and complements pointwise. Perhaps this is the generalization you seek.

But you won't get any new examples this way, since they will still just be (larger) Boolean algebras.

share|improve this answer
    
What he said. ☼ –  Jon Awbrey Dec 18 '09 at 13:02
add comment

I think you could look at MV-algebras. They were introduced in the 50's by Chang in order to prove completness of the Lukasziewicz propositional many valued (MV) logic. From what I know, this class of algebras is the most special proper generalization of Boolean algebras that makes sense.

Every MV-algebra is a subdirect product of totally ordered MV-algebras; this is a direct generalization of the algebraic version of Stone's theorem. In the finite case, this reduces to the fact that every finite MV-algebra is isomorphic to a direct product of finite chains and vice versa. Even some of the more elaborate parts of the theory of Boolean algebras, like the Loomis-Sikorski theorem have their MV-algebraic versions.

As proved by Mundici in the 80's, MV-algebras are categorically equivalent to lattice ordered abelian groups with strong order unit.

The standard reference book for MV-algebras is this one.

share|improve this answer
add comment

Alfred Foster worked on "n-ality" in some structures. While not quite a generalization of Boolean algebras, he did work on structures with a notion that generalized duality. In one of his papers, he found (something like, I am operating with faulty memory here) a substructure that resembled a ring of idempotents that helped carry the notion. He was also interested in generalizations of the Chinese Remainder Theorem for structures.

That and n-valued logics are the closest I can think of toward the "n" part of your question.

Gerhard "Ask Me About System Design" Paseman, 2010.03.01

share|improve this answer
add comment

Just to answer the question with a few more questions:

  • What is the definition of generalization that you have in mind here?

  • Can you think of other definitions of generalization that are commonly used?

  • For example, is working over $\mathbb{R}$ more general or less general than working over $\mathbb{B}$?

Addendum

There are many ways of defining an order of generalization, one of them being to align it with an order of abstraction. There are in fact several different kinds of abstraction, but the simplest among them is probably the idea that concrete things have many properties and abstraction is a process of "abstracting away" from the many toward the few.

In that light, the real domain $\mathbb{R}$ appears more concrete and more special while the boolean domain $\mathbb{B} = \lbrace 0, 1 \rbrace$ appears more abstract and more general.

share|improve this answer
13  
Jon, this answer is totally useless. Please refrain. -1 –  Scott Morrison Nov 23 '09 at 19:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.