Birkhoffconst PDF

NOTES ON THE
BIRKHOFF CONSTRUCTION OF FREE ALGEBRAS
RALPH FREESE
This is an explanation of the Birkhoff construction of the free algebra [3].

It borrows heavily from Berman’s survey article [2] but uses slight different
notation.
Let X be a set an A and algebra. A map v : X → A (so v ∈ AX ) is
called a valuation or an X–labelling. Note: not all elements of A get labels
and some can get more than one label. Let A(v) denote the subalgebra
generated by v(X). Let u : X → B be a labelling of an algebra B. A
homomorphism ϕ : A → B respects the labellings if ϕ(v(x)) = u(x), for
x ∈ X. This can be visualized with the following commutative diagram.
(There really should just be one X; but diagonal arrows require a picture
environment.)
id
X −−−−→ X
 
vy
 u
y
A(v) −−−−→ B(u)
ϕ
Let K be a set of algebras of the same similarity type and let V = H SPK
be the variety generated by K. First consider the case K = {A} consists of
a single algebra. We form the direct product of the algebras A(v), v ∈ AX .
This is an X–labelled algebra under the labelling
Y
x 7→ x̄ ∈ A(v) where x̄v = v(x)
v∈AX
so x̄ is the vector whose v th component is v(x). Viewing elements of a

product as funtions on the
Q index set, we can write this as x̄(v) = v(x). Let
F be the subalgebra of v∈AX A(v) generated by {x̄ : x ∈ X}. F has the
universal mapping property over X for K: if u : X → A then the restriction
of the projection homomorphism πu to F followed by the embedding of A(u)
into A is a homomorphsim of F to A extending u.
Now if U has the universal mapping property for K, it has the universal
mapping property for H K, SK and PK. Thus F has the universal mapping
property for V and, since F ∈ V, it is the free algebra FV (X).
In the case K is a set of algebras, we form the direct product
Y Y
A(v)
A∈K v∈AX
1
2 RALPH FREESE
As before X is naturally embedded into this product and the subalgebra

generated by the image of X is the Birkhoff construction of the free algebra
FV (X).
Two corollaries of this construction:
Corollary 1. FV (X) is a subdirect product of subalgebras of members of K.

In particular FV (X) ∈ SP K.
X
Corollary 2. FV(A) (X) is the subalgebra of AA generated by {x̄ : x ∈ X}.
In particular, if |X| = k and |A| = n, then
k
|FV(A) (X)| ≤ nn .
1. Thinning the coordinates

Under the Birkhoff representation of the free algebra each element is a
vector of length |A||X| , which can be rather large. For Lyndon’s 7 element
nonfinitely based groupoid this means every element of the free algebra on
6 generators, which turns out to have only 1, 957 elements, is a vector of
length 76 = 117, 649 so every multiplication in FV (A) (X) becomes 117, 649
multiplications in A. Often not all of the coordinates are necessary.
Let πv be the projection homomorphism of the Birkhoff represenation of
FV (A) (X) onto A(v) and let ηv ∈ Con (FV (A) (X)) be its kernel. Also let πv0
be the projection homomorphism onto allVcoordinates except the v th coordi-
nate. And let ηv0 be its kernel. Of course v∈AX ηv = 0 in Con (FV (A) (X)).
If I ⊆ AX such that v∈I ηv = 0 then the natural map that maps each
V
vector of FV (A) (X) to just the I th coordinates is an isomorphism. In fact

if two vectors in the Birkhoff representation agree on I, they are equal.
V While in most cases it would be difficult to find a minimal set I such that
v∈I ηv = 0, we can at least eliminate some of the v’s. If ηv ≤ ηu then
clearly
^
ηu0 = ηv = 0
v∈AX
v6=u
and so u can be eliminated. The following lemma helps.
Lemma 3. ηv ≤ ηu if and only if there is a homomorphism ϕ : A(v) → A(u)

respecting the labelling.
Proof. First suppose there is a label-respecting homomorphism ϕ : A(v) →

A(u) and suppose ā ηv b̄ for some ā, b̄ ∈ FV (A) (X). Since F := FV (A) (X)
X
is the subalgebra of AA generated by the x̄’s, there are terms t and s such
that
(1) ā = tF (x̄1 , . . . , x̄k ) and b̄ = sF (x̄1 , . . . , x̄k );

THE BIRKHOFF CONSTRUCTION 3
see Theorem 10.3(c) of [4]. Applying πv to these we get
av = πv (ā) = tA(v) (v(x1 ), . . . , v(xk ))

bv = πv (b̄) = sA(v) (v(x1 ), . . . , v(xk ))
Since av = bv ,
tA(v) (v(x1 ), . . . , v(xk )) = sA(v) (v(x1 ), . . . , v(xk )).
Applying ϕ to this, and using that ϕ(v(x)) = u(x) gives
tA(u) (u(x1 ), . . . , u(xk )) = sA(u) (u(x1 ), . . . , u(xk )).
Using this and (1)
au = πu (ā) = πu (tF (x̄1 , . . . , x̄k )

= tA(u) (u(x1 ), . . . , u(xk ))
= sA(u) (u(x1 ), . . . , u(xk ))
= πu (sF (x̄1 , . . . , x̄k ) = πu (b̄) = bu
showing ā ηu b̄. This proves one direction. For the other, we need to assume
ηv ≤ ηu and show that the map v(x) 7→ u(x) extends to a homomorphism
ϕ : A(v) → A(u). We leave this as an exercise.
In the Lyndon groupoid we can use this thinning to reduced the number
of coordinates from 117, 649 down to 22, 526.
We can extend Lemma 3 to test if ηu ∧ ηv ≤ ηw . This will be the case
if and only if there is a homomorphsim respecting X from the subagebra
of A(u) × A(v) generated by {(u(x), v(x)) : x ∈ X} onto A(w). However,
this is usually too expensive since it involves looking at all 3 element subsets
of AX .
Exercises
1. Let N5 be the 5 element nonmodular lattice. Using the thinning
process described above show that when |X| = 3, the 125 coordinates
NX
of FN5 (X) ≤ N5 5 are thinned down to 18 coordinates. And find
the sizes of the N5 (v) that remain.
2. Show that when |X| = 4 the proceedure thins the 625 coordinates
down to 132 and find the sizes of the N5 (v) that remain.
3. Show that when |X| ≥ 5 the N5 (v)’s that remain after thinning all
have size 4 or 5.
4 RALPH FREESE
Subdirect Decompositions. While it is difficult to find all subdirectly

irreducible homomorphic images of an algebra A, one can find a subdirect
decomposition into subdirectly irreducibles in polynomial time: First find
the principal congruence of A (this can be done in polynomial time by [5]).
Then find the subset of join irreducibles and the atoms. For each atom find
a meet irreducible congruence not above it by joining principles.
We can apply this to each of our A(v)’s. In Con (FV (A) (X)) we are re-
placing ηv with a set {ψv,i } of meet irreducibles which meet to ηv . This seems
counter-productive since it actually makes the vectors longer but the thining
process applied to the ψv,i is usually able to produce a smaller set of coor-
dinates. In the Lyndon algebra it reduces the number of coordinates down
to 11, 582. This process works particularly well for congruence distributive
algebras where it produces the unique minimal subdirect representation into
subdirectly irreducibles. The next example illustrates this.
Example. Consider FV (A) (x, y, z), where A = N5 is the five element non-
modular lattice. N5 has several sublattices isomorphic to 3, the three el-
ement chain. If u and v ∈ AX , X = {x, y, z}, are labellings such that
z < y < x in both, then there is an isomorphism A(u) → A(v) respect-
ing the labelling. So ηu = ηv and the thinning can eliminate most of this
projections. But this still leaves 6 projections onto the three element chain
corresponding the the 6 orderings of X. Since there is no homomorphism of
N5 or of 2 × 2 onto 3, all 6 of these coordinates will be retained in our thin-
ning process. In fact the thinning process leaves 18 of the 125 projections.
But it is easy to see that if A(v) is the two element lattice, then there is a
labelling u such that A(u) ∼= N5 and there is a homomorphism A(u) → A(v)
respecting the labelling. These arguments show that using the subdirect
decomposition method described above, all projections except the 6 where
A(v) ∼= N5 can be eliminated. You can play with this using the Univesal Al-
gebra Calculator (at www.uacalc.org). Choose the built-in algebra n5, and
form the free algebra on 3 generators, one time choosing “thin coords” and
one time choosing “decompose and thin”. We summarize our observation
about N5 .
Theorem 4. For |X| ≥ 3, FV(N5 ) (X) is a subdirect product of copies of
N5 .
In the case |X| = 4, FV (N5 ) (X) is a subdirect product of 84 copies of N5 .
The size of the free algebra is 540, 792, 672, as Berman and Wolk showed [1].
This is too big for the Calculator to construct. But for M3 it can construct
the free algebra on 4 generators. It is a subdirect product of 14 copies of
M3 and 14 copies of 2 and has 19, 982 elements.
THE BIRKHOFF CONSTRUCTION 5
2. Birkhoff Basis
In testing if there is a homomorphism from A(v) onto A(u) respecting
the labelling we first check if the map ϕ : v(x) 7→ u(x) is well defined. (This
can fail if, say, v(x) = v(y) but u(x) 6= u(y).) If ϕ is well defined, we try
to extend it to all of A(v). We build A(v) ≤ A by closing the image of v
under the operations in the usual way and try to extend ϕ as we go.
So if a and b have been generated and f is a binary operation, we form
e = f (a, b). If this element is not in the closure we have so far, we add it
and we extend ϕ by setting ϕ(e) = f (ϕ(a), ϕ(b)). On the other hand if e is
already in the closure so ϕ(e) is already defined, we check if the existing ϕ(e)
is equal to f (ϕ(a), ϕ(b)). If this fails, we stop: there is no homomorphism
A(v) → A(u) respecting the labelling. Otherwise we continue.
Let V = V Q (A) and let F := FV (X) be the Birkhoff construction as the
subalgebra of v∈AX A(v) generated by {x̄ : x ∈ X}, x̄v = v(x). Using ideas
similar to the last paragraph, when closing {x̄ : x ∈ X} we can associate to
each element a of the closure a term ta in the variables X such that tF a = a.
Namely the term of x̄ is x and if c first appears as f (a, b) then tc = f (ta , tb ).
Now suppose g is an r-ary operation symbol, a1 , . . . , ar ∈ F and b =
g F (a1 , . . . , ar ). Then the equation
(2) tb ≈ g(ta1 , . . . , tar )
is true in A. Indeed, a substitution of the variables X into A is an element
v ∈ AX . If x1 , . . . xk are the variables occuring in the equation, then by the
way the terms ta were defined, the relation
tF F F F
b (x1 , . . . , xk ) = g (ta1 (x1 , . . . , xk ), . . . , tar (x1 , . . . , xk ))
holds in F. Now just apply πv to show that (2) holds in A under this
substitution.
The set of all equations of the form (2) for all basic operations g and
all r-tuples a1 , . . . , ar , r the arity of g, is called the Birkhoff basis for the
equations of A in the variables X. Recall that we have associated with each
element a of F a term ta ) with variables in X. One can use the Birkhoff
basis to transform an arbitrary term in X, t(x1 , . . . , xk ), xi ∈ X into the
term ta , where a = tF (x1 , . . . , xk ). Then, if s and t are terms in X, we can
decide if s ≈ t holds in V by transforming both s and t as above and seeing
if the results are equal. The details are left as an exercise.
By Corollary 2 if A is finite then the Birkhoff basis is finite. So we have
the following corollary.
Corollary 5. If A is a finite algebra, then the k-variable equations of A
are finitely based, for each finite k.
As we mentioned before, there are finite algebras with only finitely many
basic operations that do not have a finite equational basis for their identities.
Finally we mention that all of the above could be done for a set K of
algebras in place of the single algebra A.
6 RALPH FREESE
References
[1] J. Berman and B. Wolk, Free lattices in some small varieties, Algebra Universalis 10
(1980), 269–289.
[2] Joel Berman, The structure of free algebras, Structural theory of automata, semigroups,
and universal algebra, NATO Sci. Ser. II Math. Phys. Chem., vol. 207, Springer,
Dordrecht, 2005, pp. 47–76.
[3] G. Birkhoff, On the structure of abstract algebras, Proc. Cambridge Phil. Soc. 31
(1935), 433–454.
[4] S. Burris and H. P. Sankappanavar, A course in universal algebra, Springer-Verlag,
New York, 1981.
[5] Ralph Freese, Computing congruences efficiently, Algebra Uni-
versalis 59 (2009), 337–343, Online manuscript available at:
http://www.math.hawaii.edu/∼ralph/papers.html.
(Ralph Freese) Department of Mathematics, University of Hawaii, Honolulu,

Hawaii, 96822 USA
E-mail address, Ralph Freese: ralph@math.hawaii.edu

Birkhoffconst PDF

Uploaded by

Copyright:

Available Formats

Birkhoffconst PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Birkhoffconst PDF

Uploaded by

Copyright:

Available Formats

NOTES ON THE

BIRKHOFF CONSTRUCTION OF FREE ALGEBRAS

This is an explanation of the Birkhoff construction of the free algebra [3].

so x̄ is the vector whose v th component is v(x). Viewing elements of a

As before X is naturally embedded into this product and the subalgebra

Corollary 1. FV (X) is a subdirect product of subalgebras of members of K.

1. Thinning the coordinates

vector of FV (A) (X) to just the I th coordinates is an isomorphism. In fact

and so u can be eliminated. The following lemma helps.

Lemma 3. ηv ≤ ηu if and only if there is a homomorphism ϕ : A(v) → A(u)

Proof. First suppose there is a label-respecting homomorphism ϕ : A(v) →

(1) ā = tF (x̄1 , . . . , x̄k ) and b̄ = sF (x̄1 , . . . , x̄k );

see Theorem 10.3(c) of [4]. Applying πv to these we get

av = πv (ā) = tA(v) (v(x1 ), . . . , v(xk ))

tA(v) (v(x1 ), . . . , v(xk )) = sA(v) (v(x1 ), . . . , v(xk )).

Applying ϕ to this, and using that ϕ(v(x)) = u(x) gives

tA(u) (u(x1 ), . . . , u(xk )) = sA(u) (u(x1 ), . . . , u(xk )).

Using this and (1)

au = πu (ā) = πu (tF (x̄1 , . . . , x̄k )

Subdirect Decompositions. While it is difficult to find all subdirectly

(Ralph Freese) Department of Mathematics, University of Hawaii, Honolulu,

You might also like