On closed sets of relational constraints and classes of functions closed under variable substitutions (Q2577758)

Let \(A\) and \(B\) be arbitrary non-empty sets. If \(\ell\) is a map from (ordinal) \(n\) to (ordinal) \(m\) then the \(m\)-ary function \(g:A^m\to B\) defined by \(g(\underline a)=f(\underline a\circ\ell)\) for every \(m\)-tuple \(\underline a\in A^m\) is said to be obtained from the \(n\)-ary function \(f:A^n\to B\) by simple variable substitution. A class \({\mathcal K}\) of functions of several variables is said to be closed under simple variable substitution if each function obtained from a function \(f\in{\mathcal K}\) by simple variable substitution is also in \({\mathcal K}\). Further, under an \(m\)-ary \(A\)-to-\(B\) relational constraint is understood an ordered pair \((R,S)\) where \(R\subseteq A^m\) and \(S\subseteq B^m\). A function \(f:A^n\to B\), \(n\geq 1\), is said to satisfy a constraint \((R,S)\) if \(fR\subseteq S\). A class \({\mathcal K}\subseteq\bigcup_{n\geq 1}B^{A^n}\) of \(B\)-valued functions on \(A\) is said to be definable by a set \({\mathcal S}\) of \(A\)-to-\(B\) constraints if \({\mathcal K}\) is the class of all functions that satisfy every member of \({\mathcal S}\). Galois theory of finite functions and relational constraints developed by \textit{N. Pippenger} [``Galois theory for minors of finite functions'', Discrete Math. 254, 405--419 (2002; Zbl 1010.06012)] is extended to the infinite case. It is proved in particular that a class \({\mathcal K}\) is locally closed and is closed under simple variable substitutions iff \({\mathcal K}\) is definable by some set of \(A\)-to-\(B\) constraints (Theorem 2.1).