This is a question from a "demo exam" a few years ago at out university course.
The question: How would you compute the free algebra for $\mathcal{A}$ over $X = \{x, y \}$, where $\mathcal{A} = \{ \{ 0, 1, 2 \}, \ast \}$?
The operation $\ast$ is defined:
\begin{array}{ |c|c|c|c| }
\hline
∗& 0& 1& 2 \\
\hline
0 &0 &1& 1\\
\hline
1 &1& 0&0\\
\hline
2 & 0&0& 1\\
\hline
\end{array}
My thoughts:
If I simply start with definitions, an algebra $\mathcal{F}$ is free for $\mathcal{A}$ over $X$ iff $X \in \mathcal{F}$ and for every $A$ from $\mathcal{A}$ and every $h: X \rightarrow A$, there exists a $\overline{h}: \mathcal{F} \rightarrow A$ such that $h$ is the restriction of $\overline{h}$ on $X$.
But then, I am stuck. Maybe we should take an arbitrary $X$ from $\mathcal{A}$, for example $\{0, 1 \}$, and an arbitrary map $h: \{x, y \} \rightarrow \{0, 1 \}$ that maps $x$ to $0$ and $y$ to $1$. And then find the $\overline{h}$ that "extends" the $h$ somehow?
But honestly, I have no idea, how to construct a free algebra just from this information. Any help would be appreciated.
Best Answer
The question is asking for the free algebra over $X=\{x,y\}$ in the variety $\sf V = {\sf H}{\sf S}{\sf P}(\mathcal A)$. This free algebra has 130 elements, so I doubt you are expected to actually construct it. Rather, it seems likely that they only want you to explain the procedure for constructing it.
One standard construction for ${\mathcal F}_{\sf V}(\{x,y\})$ is as a subalgebra of the algebra ${\mathcal A}^{{\mathcal A}^2}$. The $\underline{\textrm{set}}$ $A^{A^2}$ consists of all functions $f\colon A^2\to A$. We may regard $x$ and $y$ as elements of this set of functions by identifying $x$ with binary first-coordinate projection ($x(u,v) = u$) and $y$ with binary second-coordinate projection ($y(u,v)=v$). The $\underline{\textrm{algebra}}$ ${\mathcal A}^{{\mathcal A}^2}$ is this set of functions under pointwise operations from $\mathcal A$. One construction of ${\mathcal F}_{\sf V}(\{x,y\})$ is as the subalgebra of ${\mathcal A}^{{\mathcal A}^2}$ generated by the subset $\{x,y\}$.
More concretely, order the elements of $A^2$ lexicographically as $$\langle (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)\rangle.$$ These 9 elements can be taken as indices of coordinates of tuples for elements of $A^{A^2}$. With this representation, the function table for first projection $x$ may be represented as $[x]:=\langle 0,0,0,1,1,1,2,2,2\rangle\in A^9$, and the function table for the second projection $y$ may be represented as $[y]:=\langle 0,1,2,0,1,2,0,1,2\rangle\in A^9$. To get ${\mathcal F}_{\sf V}(\{x,y\})$, generate a subalgebra of ${\mathcal A}^{9}$ with $[x], [y]$. This means, start with $[x]=\langle 0,0,0,1,1,1,2,2,2\rangle, [y]=\langle 0,1,2,0,1,2,0,1,2\rangle\in A^9$ and close under coordinatewise multiplication.
EDIT 1/8/22.
In response to a comment, I will explain why the $2$-generated free algebra in the variety generated by ${\mathcal A}$ has size $130$. Moreover I will explain how to $*$-multiply any two elements of this $130$-element set.
In order to avoid writing too many bracketed variables, I will use the letter $a$ to denote $[x]$ from above, and the letter $b$ to denote $[y]$ from above.
Observe that
In particular, $B=\{0,1\}$ is the underlying set of a subalgebra of $\mathcal A$ and the algebra structure on $B$ is equivalent to that of a $2$-element group, or equivalent to that of a $1$-dimensional vector space over $\mathbb F_2$.
These facts mean that the subalgebra $\mathcal F$ of ${\mathcal A}^9$ that is generated by $a = \langle 0,0,0,1,1,1,2,2,2\rangle$ and $b=\langle 0,1,2,0,1,2,0,1,2\rangle$ has the property that the product of any two elements lies in $B^9 = \{0,1\}^9$, which is a $9$-dimensional vector space over $\mathbb F_2$ under the $*$-operation. Hence the underlying set of $\mathcal F$ must have the form $\{a,b\}\cup V$ for some $\mathbb F_2$-subspace $V\leq B^9$. I claim that this $V$ is a $7$-dimensional subspace, and I will tell you which one it is.
Write a typical element of $A^9$ as $z = \langle z_1,z_2,z_3,z_4,z_5,z_6,z_7,z_8,z_9\rangle$. Observe that if $z$ is one of the generators of $\mathcal F$, $a = \langle 0,0,0,1,1,1,2,2,2\rangle$ or $b=\langle 0,1,2,0,1,2,0,1,2\rangle$, the following hold:
The relations are preserved under the $*$-operation acting coordinatewise. (Reason: the generators have coordinates $z_1, z_2, z_4, z_5\in B$, so the projection of $\mathcal F$ onto these coordinates is a vector subspace of $B^4$ with respect to $*$ and this vector space is generated by vectors $\langle a_1,a_2,a_4,a_5\rangle = \langle 0, 0, 1, 1\rangle$ and $\langle b_1,b_2,b_4,b_5\rangle = \langle 0, 1, 0, 1\rangle$, which satisfy these linear relations.) This implies that the underlying set of $\mathcal F$ is $\{a, b\}\cup V$ where in every $z\in V$ we have $z_1=0$ and $z_2+z_4+z_5=0$. The two linear relations guarantee that $V$ has codimension at least $2$ in the $9$-dimensional space $B^9$, so $V$ is at most $7$-dimensional. But $V$ is exactly $7$-dimensional, since I can exhibit $7$ independent vectors in $V$, namely:
(In the products on the left of the equal signs I am abbreviating $*$-products $p*q$ by $pq$.) Altogether, this shows that the underlying set of $\mathcal F$ is $\{a, b\}\cup V$ where $V\leq B^9$ is the $7$-dimensional subspace of all $z = \langle z_1,z_2,z_3,z_4,z_5,z_6,z_7,z_8,z_9\rangle$ satisfying $z_1=0$ and $z_2+z_4+z_5=0$. This allows us to determine the size of $\mathcal F$: it is $2+|V|=2+2^7 = 130$.
We can do more than determine the size of this algebra, we can even determine how the $*$-operation interprets on the set $\{a,b\}\cup V$. One may verify that:
This explains how to $*$-multiply one element of $\{a,b\}$ times another. One may also verify that if $z\in B^9$ then
Here I am writing primes on variables to mean: swap $0$ and $1$ (that is, $0'=1, 1'=0$). These four rules explain how to $*$-multiply an element of $\{a,b\}$ times an element $z\in V$. Finally, we already know how to $*$-multiply two elements $z, w\in V$ since $*$ is addition modulo $2$ coordinatewise on $V$.
Altogether this identifies the $130$ tuples comprised by the subalgebra of ${\mathcal A}^9$ generated by $\{a,b\}$, and how the $*$-algebra acts on these $130$ tuples. Usually it is hard to give this much detail without the use of a computer, but we were lucky here that ${\mathcal A}$ is close to being a $1$-dimensional $\mathbb F_2$-vector space.