## On closed sets of relational constraints and classes of functions closed under variable substitutions.(English)Zbl 1095.08002

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 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).

### MSC:

 08A02 Relational systems, laws of composition 06A15 Galois correspondences, closure operators (in relation to ordered sets)

### Keywords:

Galois connections

Zbl 1010.06012
Full Text: