# Terminology about computation and Finite algebra

I am looking for the name of something that may have one.

A finite algebra $\mathcal{A} = (E, \{f_1, f_2, \ldots, f_k\})$ is a non-empty set $E$ together with some functions $f_i$ from $E^{r_i} \to E$ where $r_i$ is a fixed integer (arity).

An $n$-term is a term on $n$ variables $x_1, \ldots, x_n$ over a finite algebra $\mathcal A$. A term is defined as usual by induction:

• Any element of $E$ and the variables $x_1,\ldots, x_n$ are terms
• If $t_1, \ldots, t_{r_i}$ are terms, then $f_i(t_1,\ldots, t_{r_i})$ is also a term.

An $n$-term $t$ computes a function $[t]\colon E^n \to E$ in an obvious way.

Terminology question: How do we call finite algebras such that for every function $f\colon E^n\to E$, there exists a term $t$ such that $[t] = f$?

Famous example: $$(\{0, 1\}, \{\land, \lor, \lnot\})$$

Famous co-example: $$(\{0, 1\}, \{\land, \lor\})$$

• why is the first an example ? what about projection to the first (resp. second) component ? Also you probably want to add "for every n smaller than some bound" in your definition. – Denis Jan 15 '18 at 14:27
• The first one is an example thanks to the (logic) completeness of $\land, \lor,\lnot$. I don't get why you want to have "n smaller than some bound" ? – C.P. Jan 15 '18 at 14:33
• Functionally complete. – Emil Jeřábek Jan 15 '18 at 14:48
• Sounds to be the used name indeed. Thanks a lot. Can you answer the question so I can close it? – C.P. Jan 15 '18 at 14:54
• ah sorry my bad misunderstood the definition – Denis Jan 15 '18 at 14:55

Such algebras are called functionally complete. Also, what you call terms are actually called polynomials. In standard terminology, term operations have a more restricted definition that allows variables and the basic operations $f_i$, but not constants from $E$. Algebras that satisfy the stronger condition that every operation is represented by this kind of a term are called primal. See e.g. Burris&Sankappanavar, A Course in Universal Algebra.