How to create multiplication table ("Cayley table") for an algebra or class of algebras?

Question

I am studying universal algebra and getting familiar with the concept of variety of algebra.

As far as I understand, a variety is just a class of all algebras satisfying given set of identities. Also, a variety is always closed under homomorphic images, subalgebras and direct products of its members.

I am also familiar with definition of free algebra.

However, I dont know how to start with this exercise from Bergman´s Fundamentals of Universal Algebra.

Exercise 5 (b) from Exercise set 4.34

Let $\mathcal{V}$ be the variety of algebras $(A, ·)$ satisfying the identities

$x \ast x \approx x$ and $(x \ast y) \ast z \approx (z \ast y) \ast x.$

Let $\mathcal{W}$ be the subvariety of V defined by the additional identity $y \ast (x \ast y) \approx x$.

Determine $\textbf{F}_\mathcal{W}(x, y)$. Write out a Cayley table.

My thoughts

I would just create a multiplication table with x, y, z and start generating the entries according to the operations.

My attempt is this:

$$\begin{array}{|c|c|c|c|} \hline *& x & y & z\\ \hline x & x & ? & ?\\ \hline y & ? & y & ?\\ \hline z & ? & ? & z\\ \hline \end{array}$$

The problem is, I dont know, how to proceed, when I have identity with three different elements, but on the table, I can only combine two (one on row, on on column).

But even if I generate the complete table, I dont know, how to proceed with the free algebra generated by this. (The $\textbf{F}_\mathcal{W}(x, y)$).

I appreciate any advice in this problem or even how to determine a free algebra generaly.

Thank you!

Answer 1

To save typing, I'll write $x\cdot y$ and $xy$ and $\approx$ as $=$.

You left out some important information here: Bergman gives in part (a) a list of identities which follow from the defining identities of $\mathcal{V}$. These identities are very helpful in solving part (b)!

1. $(x y) (z w)= (x z) (y w)$
2. $x (y z) = (x y) (x z)$
3. $(y z) x= (y x) (z x)$
4. $y (x y)= (y x) y$
5. $(y x) x = x y$

For completeness, I'll give proofs of these five identities inside the spoiler blocks.

1. $(xy)(zw) = ((zw)y)x = ((yw)z)x = (xz)(yw)$

2. $x(yz) = (xx)(yz) = (xy)(xz)$

3. $(yz)x = (yz)(xx) = (yx)(zx)$

4. $y(xy) = (yx)(yy) = (yx)y$

5. $(yx)x = (xx)y = xy$

Ok, now we add the additional defining identity of $\mathcal{W}$: 6. $y(xy) = x$. Note that in conjunction with identity 4 above, we also have 7. $(yx)y = x$.

Our task is to understand $\mathbf{F}_{\mathcal{W}}(a,b)$, the free algebra in $\mathcal{W}$ on two generators $a$ and $b$. I'm using $a$ and $b$ for the generators so as not to be confused with the variables $x$ and $y$ used in the identities above. Let's try to find all its elements.

Recall that every element of the free algebra $\mathbf{F}_{\mathcal{W}}(a,b)$ is an equivalence class of terms in the generators $a$ and $b$. The terms can be built up in levels, where the terms at Level $0$ are the generators and the terms at Level $(n+1)$ are the generators and the products of two terms at Level $(\leq n)$.

Level $0$: $a$, $b$.

Level $1$: $a$, $b$, $aa$, $ab$, $ba$, and $bb$.

Note that we can eliminate $aa$ and $bb$ since they are redundant: $aa = a$ and $bb = b$.

Now it turns out that any term at Level 2 (any product of $a$, $b$, $ab$, and $ba$) can be shown to be equivalent to a term at Level 1, using the identities above. They multiply according to the following Cayley table: \begin{array}{c|cccc} & a & b & ab & ba\\ \hline a & a & ab & ba & b \\ b & ba & b & a & ab \\ ab & b & ba & ab & a \\ ba & ab & a & b & ba \end{array}

I've hidden the derivations in the spoiler blocks below.

$a(ab) = a((aa)b) = a((ba)a) = ba$ by 6. Similarly, $b(ba) = ab$.

$b(ab) = a$ by 6. Similarly, $a(ba) = b$.

$(ab)a = b$ by 7. Similarly, $(ba)b = a$.

$(ab)b = ba$ by 5. Similarly, $(ba)a = ab$.

$(ab)(ab) = ab$. Similarly, $(ba)(ba) = ba$.

$(ab)(ba) = ((ab)b)((ab)a) = (ba)b = a$ by 2, 5, and 7. Similarly, $(ba)(ab) = b$.

It follows that if the terms $a$, $b$, $ab$, and $ba$ are distinct in the free algebra $\mathbf{F}_{\mathcal{W}}(a,b)$, then the table above is its Cayley table. To prove that the terms are distinct, it suffices to show that there is any algebra in $\mathcal{W}$ with generators $a$ and $b$ such that these four terms are distinct. One way to do this is to check that the Cayley table above actually describes an algebra in $\mathcal{W}$, i.e., that all three defining identities are satisfied. This is mechanical, but tedious.

Answer 2

You should do Part (a) of the problem before you try to do Part (b).

In Part (a), Bergman asks you to derive a number of identities from the defining identities for $\mathcal W$, and these identities help to show that the universe of $\mathbf F_{\mathcal W}(x,y)$ is $\{x, y, (x\cdot y), (y\cdot x)\}$. More precisely, Bergman's identities help to show that every word in $x$ and $y$ reduces to one of $x, y, (x\cdot y)$, or $(y\cdot x)$. To show that no further reductions are possible, it suffices to observe that if $\mathbb F_4=\mathbb F_2[\alpha]$ for $\alpha$ satisfying $x^2+x+1=0$, then the operation $x\cdot y:=\alpha x+(1-\alpha)y$ acting on the set $\mathbb F_4$ satisfies all the defining identities of $\mathcal W$, and the four words $x, y, x\cdot y$, and $y\cdot x$ have distinct interpretations on $\mathbb F_4$.

To show that every word in $x$ and $y$ reduces to some word in the set $\{x, y, (x\cdot y), (y\cdot x)\}$ one must show that the product of any two words in this set reduces to a word in this set.

For example, the product of $x$ and $(x\cdot y)$ (I mean the product $x\cdot (x\cdot y)$) reduces to $(y\cdot x)$. To see this, substitute $Y=x, X=(y\cdot x)$ in the defining identity $Y\cdot (X\cdot Y) = X$ to obtain $$\tag{E} x\cdot ((\underline{y}\cdot x)\cdot \underline{x})=(y\cdot x).$$ Now swap the underlined characters using the defining identity $(\underline{X}\cdot Y)\cdot \underline{Z} = (\underline{Z}\cdot Y)\cdot \underline{X}$ to obtain from (E) that $x\cdot ((x\cdot x)\cdot y)=(y\cdot x)$ holds. Now apply the defining identity $X\cdot X=X$ to reduce this to $x\cdot (x\cdot y)=(y\cdot x)$. This verifies the first sentence of this paragraph.