On Galois connections between external operations and relational constraints
by
Miguel Couceiro
Department of Mathematics, Statistics and Philosophy, University of Tampere, Finland

Let A and B be arbitrary non empty sets. An external operation on A to B (or simply, function on A to B) is a map f: Aⁿ --> B, n >= 1. By an A-to-B relational constraint we mean a couple (R, S) where R and S are relations (of same arity) on A and B, respectively. A function f:Aⁿ --> B, is said to satisfy an A-to-B constraint (R, S) if fR is contained in S.

The polarity " satisfies " induces a Galois connection between external operations and relational constraints. For finite underlying sets A and B, Pippenger described simple closure conditions for the classes of finite functions definable by the constraints which they satisfy, and for the sets of relational constraints characterized by the functions satisfying them. This was extended to the general case of arbitrary underlying sets in a joint work with Stephan Foldes.

For A=B this correspondence specializes to the well-known Galois connection Pol-Inv by restricting the set of dual objects to relational constraints of the form (R, R), and for which constraint satisfaction reduces to preservation of relations.

We shall consider further Galois correspondences induced by arity restrictions on functions and constraints, and by generalizations of the notion of external operation, e.g. to partial functions (i.e. p:D --> B, where D is a subset of Aⁿ) and multivalued functions (i.e. g:Aⁿ --> P(B), where P(B) denotes the set of all subsets of B).

Date received: April 29, 2004