---
tag: BQ0AC9QX7E
kind: statement
role: theorem
name: Pol–Inv Galois connection
msc: [08A40, 06A15]
uses: [PTKR703G6A, A0K9EZRM7E, MC25MTN2N7, Q5JHEPRYQ6]
about: [PTKR703G6A, MC25MTN2N7]
sources:
  - url: https://en.wikipedia.org/wiki/Galois_connection
  - url: https://en.wikipedia.org/wiki/Clone_(algebra)
---

## Statement

Let $A$ be a finite nonempty set.
For a set $F$ of finitary operations on $A$, let $\operatorname{Inv}(F)$ be the set of finitary relations on $A$ preserved by every member of $F$.
For a set $\Gamma$ of finitary relations on $A$, let $\operatorname{Pol}(\Gamma)$ be the set of operations that are [[polymorphisms|A0K9EZRM7E]] of all members of $\Gamma$.
Then:

1. $\operatorname{Pol}(\operatorname{Inv}(F))$ is the [[clone|PTKR703G6A]] generated by $F$.
2. $\operatorname{Inv}(\operatorname{Pol}(\Gamma))$ is the [[relational clone|MC25MTN2N7]] generated by $\Gamma$.
3. Consequently, $C \mapsto \operatorname{Inv}(C)$ is an inclusion-reversing bijection from the clones on $A$ to the relational clones on $A$, with inverse $\Gamma \mapsto \operatorname{Pol}(\Gamma)$.

## 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|Q5JHEPRYQ6]]; 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)$.

## Explanations

### L1 human

A family of operations can be described in two ways: by listing operations that generate it, or by listing the relations that all of them respect.
On a finite set, the theorem says that the second description is always possible and exact.
Every clone is the set of all operations that respect some family of relations.
Dually, a family of relations closed under the natural constructions is the set of all relations respected by some operations.

### L2 human

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|GF1RK91VED]] 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|97SRYBF41G]], which bounds the arity of the relations needed for a clone with a near-unanimity operation.