Clone (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.

[modifier] Clone

[modifier] 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, 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.

[modifier] 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 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.