5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Denis Jan 15 '18 at 14:27
  • $\begingroup$ 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" ? $\endgroup$ – C.P. Jan 15 '18 at 14:33
  • $\begingroup$ Functionally complete. $\endgroup$ – Emil Jeřábek supports Monica Jan 15 '18 at 14:48
  • $\begingroup$ Sounds to be the used name indeed. Thanks a lot. Can you answer the question so I can close it? $\endgroup$ – C.P. Jan 15 '18 at 14:54
  • $\begingroup$ ah sorry my bad misunderstood the definition $\endgroup$ – Denis Jan 15 '18 at 14:55
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.