3
$\begingroup$

A clone on a set $A$ is a collection of $m$-ary functions $A^m \to A$ ($m$ depends on the function) that is closed under composition and includes all projection functions. Clones are significant because for any language of possible operations on $A$, the functions definable from those operations is a clone.

Is it true for all $n \in \mathbb{N}$ that there are only finitely many clones containing all constant functions? That is, for each $a \in A$ the clone contains a function $f: A \to A$, such that $f(x) = a$ for all $x$.

Motivation

The classic case is where $A = \{0,1\}$; a set of functions is "expressively adequate" if it generates the clone of all functions. It is a famous and fundamental result that sets such as $\{\lor, \lnot\}$ and $\{\to, \bot\}$ are expressively adequate. A more powerful and incredibly beautiful result is Post's lattice which completely characterizes ALL countably many possible clones on $\{0,1\}$. Wikipedia states: "the lattice of clones on a three-element (or larger) set [has] the cardinality of the continuum, and a complicated inner structure."

But I have an alternate definition of expressive adequacy in mind where we wish to always allow constants $0$ and $1$. Thus we restrict to those clones containing the constant functions, and we find that there are only finitely many clones on $\{0,1\}$. In fact, there are 7 clones:

  • $UM$, which contains just constant functions and projections
  • $\Lambda$, the set of conjunctive functions
  • $V$, the set of disjunctive functions
  • $U$, the set of essentially unary functions (depend only one one coordinate)
  • $A$, the set of affine functions
  • $M$, the set of monotone functions
  • $\top$, all functions.

Thus I am interested in whether there are still finitely many such clones for a set of size greater than $2$.

$\endgroup$
3
$\begingroup$

The answer to the question in your title is yes.

Ágoston, I.; Demetrovics, J.; Hannák, L. On the number of clones containing all constants (a problem of R. McKenzie). Lectures in universal algebra (Szeged, 1983), 21–25, Colloq. Math. Soc. János Bolyai, 43, North-Holland, Amsterdam, 1986.

''Answering a question raised by McKenzie, the authors prove that over any finite set with at least three elements there are continuously many clones containing all constants. Here a clone over some set A is a set of finitary functions over A containing all projections and closed with respect to composition.''

Images of the article from Google Books:

enter image description here enter image description here enter image description here enter image description here enter image description here

$\endgroup$
  • $\begingroup$ Thanks! Seems like it answers it. I'll try to find the article but leave this up for a while in case there is an available proof. $\endgroup$ – 6005 Aug 3 '17 at 20:57
  • 2
    $\begingroup$ @6005 The entire article is available on Google books. $\endgroup$ – Noah Schweber Aug 3 '17 at 21:23
  • $\begingroup$ @NoahSchweber and it's short :D $\endgroup$ – 6005 Aug 3 '17 at 21:39

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.