Hu’s Primal Algebra Theorem Revisited

Hans–E. Porst

Abstract It is shown how Lawvere’s one-to-one translation between Birkhoff’s description of varieties and the categorical one (see [6]) turns Hu’s theorem on varieties generated by a primal algebra (see [4, 5]) into a simple reformulation of the classical representation theorem of finite Boolean algebras as powerset algebras.

Mathematics Subject Classification (1991): Primary 06D25, 06B20 Secondary 18C05.

Keywords: Lawvere theory, equivalence between varieties, Hu’s Theorem, primal algebra, Post algebras.

Hu’s theorem [4, 5] characterizes the varieties (in Birkhoff’s sense) equivalent to the variety Bool of Boolean algebras as those varieties which are generated by some primal algebra. The original proof made use of Stone duality; later proofs ([3], [7]) were of a purely algebraic nature, but certainly not straightforward. Since the variety Post_{n} of Post algebras of order n (n ∈ ℕ, n ≥ 2) is generated by a primal n-element algebra (the n–chain) Post_{n} is equivalent to Bool — a fact which also can be proved directly (see e.g. [1]). Until the recent paper [8] it was unclear whether there are varieties different from Post_{n} with this property.

In this note we are going to show how all these results — plus a complete description of all the varieties equivalent to Bool — can be obtained in the most simple manner using instead of Birkhoff’s description of varieties the categorical one due to Lawvere [6]. Our analysis moreover shows that what is needed substantially to obtain these results (besides the appropriate language) is only the elementary fact that finite Boolean algebras are powersets or, more precisely, that the contravariant powerset functor is a dual equivalence between the categories of finite sets and finite Boolean algebras (we refer to this as “restricted Stone duality”).

To make this a selfcontained paper we start recalling briefly the fundamentals of Lawvere’s approach to varieties as far as they are needed here. As a first application we obtain descriptions of primality of an algebra and of the variety generated by an algebra in this language, which are obvious but seem not to have appeared in print yet.

1 Definitions A (Lawvere) theory is a category 𝕋 with countably many objects T_{0}, T_{1}, T_{2}, … and, for each n ∈ ℕ, a distinguished family (π_{i}^{n}: T_{n} ⟶ T_{1})_{1≤i≤n} of morphisms making T_{n} an n–fold power of T_{1}.

A functor Φ: 𝕊 ⟶ 𝕋 between theories is a theory morphism provided Φ preserves the distinguished product families.

A 𝕋–model is a product–preserving functor from 𝕋 into the category Set of sets and mappings. Mod𝕋 denotes the category of all 𝕋–models considered as a full subcategory of the category of all functors from 𝕋 to Set.

2 Definitions Given concrete categories (K, U) and (L, V), a functor F: K → L is called concrete functor provided VF = U^{1}.

Concrete categories (K, U) and (L, V) are called concretely equivalent (or concretely isomorphic) provided there exists a concrete functor F: (K, U) → (L, V) which is an equivalence (an isomorphism, respectively) as a functor.

3 Facts ([6], [2, Chapter 3]) The category Mod𝕋 is concrete by means of the underlying functor “evaluation at T_{1}”, i.e., the functor ev_{T_{1}} : Mod𝕋 ⟶ Set mapping a model G to G(T_{1}) and a natural transformation λ to its T_{1}–component λ_{T_{1}}.

The fundamental observation leading to the concepts introduced above is the following. For any variety V one can construct a theory ThV, called the theory of V, as follows: objects of ThV are the finite powers (F ω)^{n}, n ≥ 0, of the free V–algebra F ω on a countable set of generators^{2}; morphisms (F ω)^{m} ⟶ F ω are all m-ary term operations of F ω and morphisms (F ω)^{m} ⟶ (F ω)^{n} are all maps t: = ⟨t_{1}, …, t_{n}⟩ where the i-th component t_{i} of t is an m-ary term operation. Note that the theory just described is nothing but the clone of F ω extended by the maps ⟨t_{1}, …, t_{n}⟩ and that, what often is called clone composition, becomes ordinary composition in this category.

Now any V–algebra A determines a ThV–model, denoted by A, mapping (F ω)^{n} to A^{n} and an m-ary term (operation of F ω) to its interpretation on A. Then a homomorphism f: A → B determines a natural transformation f : A → B with f_{(F ω)^{n}} = f^{n} = f ×…×f. This construction yields a concrete equivalence between V and the category of models of ThV.

Conversely, for every Lawvere theory 𝕋 there exists a variety V_{𝕋} — called the variety determined by 𝕋 — such that Mod𝕋 and V_{𝕋} are concretely equivalent. Moreover, the correspondence between varieties and Lawvere theories established above is essentially bijective, (and functorial) i.e.,

1. every variety V is concretely isomorphic to the variety V_{ThV} determined by ThV;

2. every Lawvere theory 𝕋 is isomorphic to the theory ThV_{𝕋} of the variety V_{𝕋} determined by 𝕋; 3. every theory morphism Φ: 𝕊 ⟶ 𝕋 determines a functor Φ^{∗}: Mod𝕋 ⟶

1Concrete functors between varieties are often called interpretations.

2We do not distinguish notationally between an algebra and its underlying set.

Mod𝕊 given by Φ^{∗}(H ⟶^{λ} K) = HΦ ⟶^{λΦ} KΦ which is concrete;

4. every concrete functor F: Mod𝕋 ⟶ Mod𝕊 is F = Φ^{∗} for a unique theory morphism Φ: 𝕊 ⟶ 𝕋.

4 Examples Each algebra A in a variety V with gives rise to two different theories as follows:

a) The theory of A, denoted by 𝔸, is simply the image of A: ThV ⟶ Set. Thus 𝔸 is the clone of the algebra A together with the additional maps

A^{n} ⟶^{⟨t_{i}^{A}⟩} A^{m} induced by families of (t_{1}^{A}, …, t_{m}^{A}) of n–ary derived operations. Note that, for A = F ω, 𝔸 = ThV.

b) The theory generated by A, denoted by Th_{V}(A) is the dual of the full subcategory of V spanned by all finite copowers m · A, m ∈ ℕ. Explicitely: Th_{V}(A) has objects T_{i} = i · A (the i–fold copower of A in V) and morphism sets hom_{Th_{V}(A)}(T_{i}, T_{j}) = hom_{V}(j · A, i · A) and chosen coproduct injections μ_{i}^{n}: A ⟶ n · A (i = 1, …, n). Note that Th_{V}(F 1) is isomorphic to ThV.

For each algebra A the functor A factors, in the notation above, as

ThV ⟶^{A} Set = ThV ⟶^{Φ_{A}} 𝔸 ⟶^{E_{A}} Set

where E_{A} is the embedding of the subcategory 𝔸 into Set. Φ_{A} clearly is a theory– morphism which is surjective (on objects and morphisms). Note that in general 𝔸 is not a full subcategory of Set. This being the case means that each map A^{n} → A is a derived operation of the algebra A. A then is called a primal algebra (provided A is finite with more than one element). Thus we have shown the first the following propositions.

5 Proposition Let A be a finite algebra in V having more than one element. Then A is primal if and only if A is full.

6 Proposition For any algebra A in a variety V the following hold:

1. 𝔸 is the theory of HSP(A), the variety generated by A.

2. V = HSP(A) if and only if A is faithful.

Proof Statement 1 is equivalent to the following lemma which — in the language of universal algebra — states that the variety determined by 𝔸 is the smallest subvariety of V containing A^{3}. The second statement is an immediate consequence of the first one: Φ_{A}: ThV ⟶ 𝔸 is an isomorphism iff A is a faithful model; thus, in this case V and HSP (A) coincide by 1. and bijectivity of the correspondence between theories and varieties. ◇

3A somewhat informal way of proving this is the following: an algebra B is in HSP (A) iff B satisfies all equations which are valid in A. The 𝕋-model B “is” an 𝔸–model iff B factors over Φ_{A} iff the algebra B satisfies all equations of A.

7 Lemma Let 𝕊 be a theory and E: Mod𝕊 ⟶ Mod𝕋 be a full concrete embedding. Assume that the 𝕋-model A is E(A′) for some 𝕊–model A′. Then there exists a full concrete embedding Mod𝔸 ↪ Mod𝕊.

Proof Let E be Φ^{∗} for Φ: 𝕋 ⟶ 𝕊. Then A = A′ ∘ Φ and therefore Φ_{A} = Φ_{A′} · Φ: 𝕋 ⟶ 𝔸. Then Φ_{A′} is surjective since Φ_{A} is. Now apply the following lemma, the proof of which is an easy exercise. ◇

8 Lemma If Φ: 𝕊 ⟶ 𝕋 is a surjective theory morphism, then the functor Φ^{∗}: Mod𝕋 ⟶ Mod𝕊 is a full embedding.

It is well known that different varieties might be equivalent as categories as, e.g., the varieties of left modules over Morita–equivalent rings or the varieties of Post algebras of the various fixed (finite) orders. In order to describe the varieties W equivalent to a given variety V the following notion is crucial:

9 Definition An algebra G in a variety V is called a varietal generator^{4}, provided G is a retract of some finitely generated free V–algebra F n and the free algebra F 1 on one generator is a retract of some finite copower of G.

10 Fact ([6], [8]) Let V be a variety with theory 𝕋. A variety W with theory 𝕊 is equivalent to V iff 𝕊 is (isomorphic to) some theory Th_{V}(G) where G is a varietal generator in V.

11 Example Let V be the variety Bool of Boolean algebras. The varietal generators of Bool are (up to isomorphism) precisely the powerset algebras 2^{n}, n ∈ ℕ, n ≥ 2. This is clear since each retract of a finitely generated free Boolean algebra (which is finite) is finite, thus 2^{n} for some n ∈ ℕ due to restricted Stone duality. Moreover 2^{2} is a retract of 2^{n} iff n ≥ 2 (again by restricted Stone duality).

It is easy to describe the theory generated by 2^{n}: the contravariant powerset functor, restricted to the full subcategory 𝕋_{n} of Set spanned by the finite powers of the n–element set n = {0, 1, …, n − 1} provides a theory–isomorphism 𝕋_{n} ≃ Th_{Bool}(2^{n}).

As a consequence of the above a proof of the following sharpening of Hu’s theorem ([4, 5]) becomes nearly trivial, making thereby clear in addition that this theorem is essentially—up to the well known categorical result stated as Fact 10 above—a reformulation of restricted Stone duality.

4In categorical terms, this is equivalent to saying that G is an extremally projective, finitely presentable extremal generator (see e.g. [8]).

12 Theorem The following are equivalent for a variety V:

(i) V is equivalent to Bool, the variety of Boolean algebras.

(ii) V is generated by a primal algebra.

(iii) ThV ≃ 𝕋_{n} for some n ∈ ℕ, n ≥ 2.

Proof By Fact 10 and Example 11 V is equivalent to Bool iff ThV ≃ 𝕋_{n} for some n ≥ 2.

By Propositions 5 and 6 one gets: V = HSP(A) with an n-element primal algebra A iff A is a ) full and faithful ThV–model, iff ThV ≃ 𝕋_{n}. (Note that 𝕋_{n} has a full and faithful n–element model trivially: its embedding into Set). ◇

13 Remark Since the the correspondence between varieties and Lawvere theories is essentially bijective the above theorem shows in particular that, for each n ∈ ℕ, n ≥ 2, there is (up to concrete isomorphism) precisely one variety which is generated by an n–element primal algebra, namely the variety V_{𝕋_{n}} determined by the theory 𝕋_{n}, and that any variety equivalent to Bool has to be one of those (again up to concrete isomorphism). Now the variety V_{𝕋_{n}} is easily identified as the variety Post_{n} of Post algebras of order n since it is well known (see e.g. [1]) that the latter is equivalent to Bool and generated by an n–element primal algebra. For a more categorical argument see [8].

References

[1] R. Balbes and Ph. Dwinger. Distributive Lattices. University of Missouri Press, 1974. Missouri.

[2] F. Borceux. Handbook of categorical algebra Vol. 2. Cambridge University Press, 1994. Cambridge.

[3] B.A. Davey and H. Werner. Dualities and equivalences for varieties of algebras. In A. P. Huhn and E. T. Schmidt, editors, Contributions to Lattice Theory (Proc. Conf. Szeged 1980), volume 33 of Coll. Math. Soc. János Bolyai, pages 101–275. North-Holland, 1983.

[4] T.K. Hu. Stone Duality for Primal Algebra Theory. Math. Z., 110:180–198, 1969.

[5] T.K. Hu. On the Topological Duality for Primal Algebra Theory. Algebra Universalis, 1:152–154, 1971.

[6] F.W. Lawvere. Functorial semantics of algebraic theories. PhD thesis, Columbia University, 1963.

[7] R. McKenzie. An algebraic version of categorical equivalence for varieties and more general algebraic theories. In A. Ursini and P. Agliano, editors, Logic and Algebra, volume 180 of Lecture Notes in Pure and Appl. Mathematics, pages 211–243. Marcel Dekker, 1996.

[8] H.-E. Porst. Equivalence for Varieties in General and for Bool in Particular. To appear in Algebra Universalis.

Department of Mathematics, University of Bremen, 28359 Bremen, Germany

porst@math.uni-bremen.de