Pol–Inv Galois connection

Remarks

The maps $\operatorname{Pol}$ and $\operatorname{Inv}$ come from the relation "$f$ preserves $R$" between operations and relations, so they always form a Galois connection; the theorem identifies its closed sets. For part 1, take an $n$-ary $f \in \operatorname{Pol}(\operatorname{Inv}(F))$ and the relation $R$ of arity $\abs{A}^n$ formed by the columns of all $n$-ary operations in the clone generated by $F$. This $R$ is preserved by $F$ and contains the columns of the $n$ projections. So $f$ applied to these columns gives the column of $f$, which lies in $R$, and $f$ is in the clone. Part 2 is proved in a similar way, with a relation built from $\operatorname{Pol}(\Gamma)$ and a primitive positive definition of it from $\Gamma$. The result is due to Geiger and, independently, to Bodnarčuk, Kalužnin, Kotov and Romov. For example, on $\set{0, 1}$ the clone of monotone operations is $\operatorname{Pol}(\set{\le})$. Finiteness of $A$ is needed: on an infinite set, the closed sets are clones that are locally closed, and some clones are not of the form $\operatorname{Pol}(\Gamma)$.

Going deeper

For a student

The theorem turns questions about clones into questions about relations, which are often easier to handle. Maximal clones, for example, are of the form $\operatorname{Pol}(\set{\rho})$ for a single relation $\rho$, and Rosenberg's classification lists those relations. In constraint satisfaction, adding a primitive positive definable relation to a template does not change the complexity. So the complexity of a finite template depends only on its polymorphism clone. The same reasoning underlies the Baker–Pixley theorem, which bounds the arity of the relations needed for a clone with a near-unanimity operation.