Clone (mathématiques)

Définition

Soit A un ensemble, et F(A) l'ensemble de toutes les constantes de A et de toutes les fonctions finitaires sur A. Un clone sur A est un sous-ensemble X de F(A) tel que

1. X est clos par composition ;
2. X contient toutes les projections ;
3. si une constante c est dans X, toutes les fonctions finitaires à valeur constante c sont dans X
4. si une fonction finitaire à valeur constante c est dans X et X contient au moins une constante, alors la valeur constante c est dans X.

Tout sous-ensemble X de F (A) est contenu dans un plus petit clone sur A, que l'on appelle le clone engendré par X.

Le clone engendré par les opérations fondamentales d'une algèbre A est appelé le clone de A.

Exemple

Considérons l'ensemble à 2 éléments 0,1. Le clone engendré par les constantes 0,1 et les opérations binaires min et max est celui des fonctions croissantes, c’est-à-dire telles que ${\displaystyle f(x_{1},...x_{k-1},0,x_{k+1},...x_{n})\leq f(x_{1},...x_{k-1},1,x_{k+1},...x_{n})}$

Emil Post a publié en 1921 une étude exhaustive et passionnante des clones sur les algèbres à deux éléments.