Sur un ensemble A, un clone est un ensemble C d'opérations finies (de cardinalité finie d'arguments) sur A contenant toutes les projections et fermé par composition (substitution) : composer des opérations de C (avec arités compatibles) donne une opération dans C. Abstraitement, les clones codent toutes les opérations de termes définissables à partir d'une signature sur le même support.

Principe

Les propriétés de fermeture par composition et la présence des projections sont définitoires : les projections fournissent les variables, la composition réalise la substitution de termes, et ensemble elles décrivent exactement les opérations obtenues par formation finie de termes.

Démonstration

Pour une algèbre booléenne, l'ensemble de toutes les fonctions booléennes (sur {0,1}) est un clone ; des exemples plus fins sont les clones des opérations polynomiales d'une algèbre donnée (toutes les opérations exprimables par des termes de l'algèbre). Le clone engendré par un ensemble d'opérations de base est le plus petit clone les contenant et se décrit par compositions itérées et projections.

Mauvaise application

Appeler 'clone' tout ensemble d'opérations sans vérifier les conditions de fermeture, ou confondre clones et monoïdes de transformations (qui peuvent ne pas contenir de projections ni permettre des arités variées), ou supposer une fermeture pour des compositions infinitaires alors que seules les compositions finitaires sont permises.

Conséquence

Les clones servent d'invariants algébriques pour les théories équationnelles : le clone des opérations de termes détermine la théorie équationnelle d'une structure et classe les opérations définissables. L'étude des clones conduit à des classifications (lattice de Post en cas booléen) et relie descriptions syntaxiques et fermetures sémantiques.

Inversion

Une famille d'opérations qui n'est pas fermée par composition ou qui omet les projections n'est pas un clone ; supprimer les projections ou la fermeture par composition rompt le lien avec la formation de termes et donne des objets algébriques plus faibles (ensembles d'opérations ou opérades avec d'autres axiomes).

Limite

Les clones concernent les opérations finies sur un support fixé ; ils excluent les opérations infinitaires ou les relations, et exigent la présence de toutes les projections. D'autres cadres emploient des notions proches (opérades, monoïdes de transformations) avec des contraintes d'arité ou de symétrie différentes.

Tension sémantique

Tension fréquente entre clone et opérade ou monoïde de transformations : les opérades insistent sur la composition indexée par l'arité souvent sans projections, les monoïdes de transformations se concentrent sur les compositions unaires. Les clones se situent entre ces notions, en soulignant la substitution et la formation de termes multi-arité.

Synthèse

Un clone d'opérations sur un ensemble est la fermeture, par substitution et en incluant les projections variables, d'une famille d'opérations finies ; il capture exactement les opérations réalisables en formant des termes à partir de primitives données et encode ainsi le pouvoir expressif équationnel de l'algèbre.