How to show that an algebra is contained in a clone

My question:

If we have a be the binary operation on 2 = {0, 1}, denoted $\overline{\land}$, defined by

\begin{array}{|c|c|c|} \hline \overline{\land} &0 & 1 \\ \hline 0&1 & 0\\ \hline 1 & 0 &0 \\ \hline \end{array}

How do I prove that $\mathcal{A}$ = {¬, ∧, ∨} ⊆ $\mathcal{C}$ = Clo($(2, \overline{\land})$)?

My thoughts:

The $\mathcal{A}$ is probably some lattice, however, I am confused about what should be the universe here. I understand the operations {¬, ∧, ∨} as inverse, meet and join respectively.

The $\mathcal{C}$ is the clone of term operations. The clone $\mathcal{C}$ on $(2, \overline{\land})$ should be defined a set of operations on $(2, \overline{\land})$ which contains all projections and is closed under composition of functions.

So I think maybe I should just show that any two elements that give 0 or 1 after applying the operations from $\mathcal{A}$ have to automatically give 0 or 1 after applying the operation $\overline{\land}$? But I am not very sure how would I show that if this was the correct process.

Why I am interested in this:

We were assigned this as an exercise in our university course and I am following mostly the book Universal Algebra: Fundamentals and Selected Topics by Clifford Bergman. In the book, there is only similar exercise (4.10.4 in particular), but no solutions.

I would love to learn to work with clones, not only study theorems and proofs, so any advice on this or any learning sources with more exercises are very appreciated.

Solution 1:

Since I got some nice advice in the comments (thank you!), I will try to post an answer myself. Feel free to add anything.

A clone $\mathcal{C}$ is a set of operations on $(2, \overline{\land})$ which contains all projections and is closed under composition of functions.

Denote $\mathcal{A} = (\{0, 1\}, \overline{\land})$.

The unary operation $\neg$ ("not"), and the binary operations $\land$ ("and"), $\lor$ ("or") are operations defined on $\{0,1 \}$. We need to know how the operations $\neg, \land$ and $\lor$ behave to solve the problem. We create Cayley tables to observe how the operations can be generated from one another.

We will show that that all $\neg, \land$ and $\lor$ can be created by projections and compositions of the $\overline{\land}$ operator.

Proof that $\neg \in \mathcal{C}$

The $\neg$ operator is unary operator and therefore the Cayley table has outputs only for $(x,x)$.

$\begin{array}{|c|c|c|} \hline \neg &0 & 1 \\ \hline 0& 1 & -\\ \hline 1 & - & 0 \\ \hline \end{array}$

Observe that $\neg(x,x)$ is the same $x \overline{\land} x$. The $\neg(x,x)$ operator is like the $\overline{\land}$ operator restricted only to one variable instead of two. Hence, $\neg(x,x)$ is a part of the $\mathcal{C} = Clo((2, \overline{\land}))$

Proof that $\land \in \mathcal{C}$

$\begin{array}{|c|c|c|} \hline \land &0 & 1 \\ \hline 0& 0 & 0\\ \hline 1 & 0 &1 \\ \hline \end{array}$

First, I will generate $\land$ from $\lor$ and $\neg$. Then I will express $\lor$ and $\neg$ using $\overline{\land}$ and we are done.

Observe $\neg x \lor \neg y$.

$\begin{array}{|c|c|c|} \hline \neg x \lor \neg y &0 & 1 \\ \hline 0& 1 & 1\\ \hline 1 & 1 &0 \\ \hline \end{array}$

Then, observe that the table above is just negation of the $\land$ operator. Therefore $\land = \neg (\neg x \lor \neg y)$.

$\begin{array}{|c|c|c|} \hline \neg (\neg x \lor \neg y) &0 & 1 \\ \hline 0& 0 & 0\\ \hline 1 & 0 &1 \\ \hline \end{array}$

Since we have already shown that the $\lor$ and $\neg$ operators are in $Clo((2, \overline{\land}))$, it means $\land$ is also in the clone, because it can be created from these operators and therefore from the $\overline{\land}$ operator.

Proof that $\lor \in \mathcal{C}$

$\begin{array}{|c|c|c|} \hline \lor &0 & 1 \\ \hline 0& 0 & 1\\ \hline 1 & 1 &1 \\ \hline \end{array}$

Observe that $x \lor y = \neg(x \overline{\land} y)$ and hence equal to $(x \overline{\land} y) \overline{\land} (x \overline{\land} y)$. It means that it can be made as a composition of $ \overline{\land}$ operators, so it belongs to $\mathcal{C} = Clo((2, \overline{\land}))$.