Clarification of the definition of a clone I've begun studying boolean algebra in mathematical logic, after studying a course on abstract algebra which ended with the definition of boolean lattices, so I'm familiar with some algebraic structures. But now that I've begun studying boolean algebra in mathematical logic, and I've come across the concept of a 'functionally complete' set. I understand it intuitively through digital circuits and combinational logic, and through algebraic manipulation too. But I was looking for a formal definition of a 'functionally complete' set for a notebook glossary. That's when I arrived at the concept of a 'clone'... and it's created a spectrum of questions that I haven't been able to find the answer of.

*

*Is a clone anything more than a magma whose set is a set of functions, and operation is the superposition operation?

*Does a clone require a 'basis' that it was generated from?

*What does it mean for the set of functions to be a projections? (is a projection just a generalization of a truth table)?

 A: The Wikipedia article on clones explains this.
In contrast to that article, which defines
general clones so that they are single-sorted and later
defines abstract clones so that they are multisorted,
I view clones as multisorted structures always:
$$
{\mathbf C}=
\langle C_0, C_1, C_2, \ldots; \{\textrm{comp}^m_k\;|\;m,k\geq 0\}, \{\pi_i^k\;|\;1\leq i\leq k\}\rangle.
$$
Here $C_0, C_1, C_2, \ldots$ are sets.
For a clone of operations on a set $A$,
the set $C_n$ is a set of $n$-ary
operations on $A$. (An $n$-ary operation
on $A$ is a function $f\colon A^n\to A$.)
For an abstract clone,
each $C_n$ is just a set. I typically consider the
$C_n$'s to be pairwise disjoint sets.
Some people disallow the $0$-ary sort $C_0$.
The $(m+1)$-ary clone operation
$\textrm{comp}^m_k$ is composition of
one $m$-ary element with $m$ $k$-ary elements. For a
clone of operations on a set $A$, this composition operation
is defined so that
$$
\textrm{comp}^m_k(f,g_1,\ldots,g_m) = f(g_1,\ldots,g_m).
$$
The $0$-ary clone operation
$\pi_i^k\in C_k$ is called
the $k$-ary projection onto the $i$th variable.
For a clone of operations on a set $A$, this
projection is defined so that
$
\pi_i^k(x_1,\ldots,x_k)=x_i.
$
That is, $\pi_i^k\colon A^k\to A$ is the function
$(a_1,\ldots,a_k)\mapsto a_i$ that accepts as input an element of $A^k$
and returns as output its $i$th coordinate.
The axioms for abstract clones are

*

* (Axioms of Projection) ${\rm comp}_n^n(f,\pi_1^n, \ldots, \pi_n^n) = f$
  and ${\rm comp}_n^m(\pi_i^m,f_1,\ldots,f_m) = f_i$.
  

* (Associative Laws) ${\rm comp}_{m}^p\big(f,{\rm comp}_{m}^n(g_1,
  h_1,\ldots, h_n), \ldots, {\rm comp}_{m}^n(g_p,
  h_1,\ldots, h_n)\big) = {\rm comp}_{m}^n\big({\rm
    comp}_n^p(f,g_1, \ldots, g_p), h_1,\ldots, h_n\big)$.


These axioms generalize the axioms for monoids.
Together, they allow one to prove a Cayley-type theorem
stating that every abstract clone is isomorphic to a concrete
clone of operations on some set.

Now I answer the questions:

*

* Is a clone anything more than a magma whose set is a set of functions, and operation is the superposition operation?
It is awkward to think of superposition as a binary operation only,
although it would be possible to develop clones this way if you also had operations for variable manipulation of clone elements. I would say instead that a clone is a multisorted set and superposition is a family of operations of different arities.


* Does a clone require a 'basis' that it was generated from?
No. 


*What does it mean for the set of functions to be a projections? (is a projection just a generalization of a truth table)?

A projection is not a generalization of a truth table.


*What does it mean to be functionally complete?

A set $F$ of operations on a set $A$ is functionally complete if the clone
on $A$ generated by $F$ is the clone of all operations on $A$. An algebra defined on a set $A$ is called functionally complete if its clone of polynomial operations is the clone of all operations on $A$. (The polynomial operations are those generated by the term operations and the constant operations on $A$.)


Example.
The clone of the additive group of real numbers
$\textrm{Clo}(\langle {\mathbb R}; +, -, 0\rangle)$ has sorts:
$C_0 = \{0\}$.
$C_1 = \{mx_1\;|\;m\in\mathbb Z\}$,      $\pi_1^1 = x_1$
$C_2 = \{mx_1+nx_2\;|\;m,n\in\mathbb Z\}$,      $\pi_1^2 = x_1$,   $\pi_2^2 = x_2$
$C_3 = \{mx_1+nx_2+px_3\;|\;m,n,p\in\mathbb Z\}$,    $\pi_1^3 = x_1$,   $\pi_2^3 = x_2$,  $\pi_3^3 = x_3$
ETC
Here $mx_1 = x_1+x_1+\cdots+x_1$ ($m$ $x_1$s).
Also, I am informally writing $x_i$ for $\pi_i^k$. This leaves me with a copy of $x_i$ in each $C_k$, $k\geq i$.
If $f(x_1,x_2)=x_1+x_2\in C_2$, then
$\textrm{comp}^2_2(f,f,f) = f(f,f) = (x_1+x_2)+(x_1+x_2)=2x_1+2x_2\in C_2$.

Keeping $f=x_1+x_2\in C_2$, note that
$\textrm{comp}^2_4(f,\pi_1^4,\pi_2^4) = f(\pi_1^4,\pi_2^4) = x_1+x_2 \in C_4$,
and
$\textrm{comp}^2_4(f,\pi_3^4,\pi_4^4) = f(\pi_3^4,\pi_4^4) = x_3+x_4 \in C_4$,
Hence
$\textrm{comp}^2_4(f,f(\pi_1^4,\pi_2^4), f(\pi_3^4,\pi_4^4))=
(x_1+x_2)+(x_3+x_4) \in C_4$. This looks like $\textrm{comp}(f,f,f)$ again, but we need to watch out for superscripts and subscripts and projections.
