<p>Such algebras are called <em>functionally complete</em>. Also, what you call <em>terms</em> are actually called <em>polynomials</em>. 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 <em>primal</em>. See e.g. Burris&amp;Sankappanavar, <a href="https://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html" rel="noreferrer"><em>A Course in Universal Algebra</em></a>.</p>

CC BY-SA 3.0
2018-01-15T15:02:44.287Z
2018-01-15T15:02:44.287Z
Emil Jeřábek
<p>I am looking for the name of something that may have one.</p>

<p>A <em>finite algebra</em> $\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).</p>

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

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

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

<p><strong><em>Terminology question:</em></strong> 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$?</p>

<p>Famous example:
 $$(\{0, 1\}, \{\land, \lor, \lnot\})$$</p>

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

CC BY-SA 3.0
2018-01-15T14:27:27.357Z
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
CC BY-SA 3.0
2018-01-15T14:33:19.843Z
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.
CC BY-SA 3.0
2018-01-15T14:48:56.997Z
Functionally complete.
Emil Jeřábek
CC BY-SA 3.0
2018-01-15T14:54:12.307Z
Sounds to be the used name indeed. Thanks a lot. Can you answer the question so I can close it?
C.P.
CC BY-SA 3.0
2018-01-15T14:55:22.727Z
ah sorry my bad misunderstood the definition
Denis
<terminology><algebra><universal-computation>
Terminology about computation and Finite algebra
C.P.
# Terminology about computation and Finite algebra

(Asked by: username_0 on 2018-01-15)

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\})$$

**Tags:** terminology, algebra, universal-computation

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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" ?  
> **username_2**: Functionally complete.  
> **username_0**: Sounds to be the used name indeed. Thanks a lot. Can you answer the question so I can close it?  
> **username_1**: ah sorry my bad misunderstood the definition  

---

## 1 answers

### Answer by username_2 on 2018-01-15. Score: 7 | Accepted answer

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*](https://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html).


---

