Closed classes of functions, generalized constraints, and clusters (Q607451)

For a fixed base set \(A\), the maps \(f : A^n \rightarrow A\) can also be regarded as operations on \(A\). Let \({\mathcal O}_A\) be the set of all operations on \(A\). Mal'tsev introduced five types of operations on the set \({\mathcal O}_A\): two kinds of permutation of variables (denoted \(\zeta\), \(\tau\)), identification of variables or diagonalization (denoted \(\Delta\)), addition of a dummy variable or cylindrification (denoted \(\nabla\)) and composition (\(*\)). The algebra \(({\mathcal O}_A, \{\zeta, \tau, \Delta, \nabla, * \})\) is called the full iterative algebra on \(A\); its subalgebras are called iterative algebras on \(A\). Clones are iterative algebras that contain all projections. The ``preservation'' relation between operations and relations on \(A\) induces a Galois connection whose closed operations are exactly the clones of \(A\). The first part of this paper presents existing results on classes of functions that are closed under only some of the iterative algebra operations, and on a Galois theory developed for these variants to describe the closed classes in terms of a ``preservation'' relation between functions and some ``dual'' objects which in this case are more general than relations. In addition, the authors describe the classes of operations on arbitrary nonempty sets \(A\) that are closed under the iterative algebra operations except for the identification of variables. They show that the classes of operations on \(A\) that contain all projections and are closed under this subset of operations are precisely the closed classes of the Galois connection induced by the ``preservation'' relation between operations and clusters (downward closed sets of multisets of \(m\)-tuples on \(A\)). They also describe the Galois closed classes of clusters as classes that are closed under certain operators (conjunctive mirrors, unions, quotients, dividends).