## On Definability of Functions of Several Variables

##### Couceiro, Miguel (2006)

Couceiro, Miguel

Tampere University Press

2006

Matematiikka - Mathematics

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

##### Väitöspäivä

2006-09-16**Julkaisun pysyvä osoite on**

http://urn.fi/urn:isbn:951-44-6704-3

##### Tiivistelmä

In this research work, we focused on functions of several variables over a set $A$ and valued in a possibly different set $B$. We studied function properties which can be expressed by means of functional equations and by means of relational constraints $(R,S)$ (where $R$ and $S$ are relations of the same arity on $A$ and $B$, respectively), taking into account the syntax of equations and the type of relations allowed in constraints.

We started by studying the Boolean case, and considered characterizations of Boolean function classes, as studied by Ekin, Foldes, Hammer and Hellerstein, but by means of functional equations written in the additive language of Boolean rings, i.e. by means of the so-called linear equations. We showed that a class of Boolean functions has a linear theory if and only if it is stable under right and left composition with the clone of constant-preserving linear functions. These classes were equivalently described within a Galois setting, more stringent than that considered by Pippenger, in which classes are defined by means of affine constraints, showing that definability by linear equations is equivalent to definability by affine constraints, since these two approaches specify exactly the same Boolean function classes. The dual question of describing the sets of affine constraints which are characterized by Boolean functions was also addressed and answered.

Then, we studied the general case, and extended Pippenger's Galois theory by removing the finiteness restriction on the underlying sets $A$ and $B$. We showed that the classes of functions definable by constraints are exactly those locally closed classes which are stable under right composition with the smallest clone on $A$, containing only projection maps, and that the sets of relational constraints characterized by functions are essentially those locally closed sets of constraints which are closed under combining families of constraints into new constraints by means of (possibly infinitary) existential first-order schemes similar to those described by Szab\'o. Furthermore, we showed how these results can be used to derive the characterizations of the closed systems associated with the well-known Galois correspondence between operations and relations.

This basic Galois correspondence between functions and constraints was specialized and generalized in several ways in this research work. We studied Galois connections arising from the restriction of the primal objects (functions) and dual objects (relational constraints) to fixed arities, and presented descriptions of the Galois closure systems by means of parametrized analogues of the closures given in the previous joint work with Stephan Foldes. Furthermore, we provided factorizations of the Galois maps in terms of operators associated with these closures.

Also, we considered the more general notion of \emph{multivalued functions}, i.e. mappings of the form $A^n\rightarrow \mathcal{P}(B)$, where $\mathcal{P}(B)$ denotes the set of all subsets of $B$, which generalize the notions of total and partial functions. These different notions were studied in a unifying Galois framework arising from the natural extension of the relation ``satisfies" to multivalued functions and relational constraints (whose ``consequents" are still defined as relations on $B$, and not on $\mathcal{P}(B)$). We described the Galois closed sets by means of necessary and sufficient conditions which specialize to those given in the total single-valued case, and presented factorizations of the associated Galois maps in terms of simpler closure operators. Moreover, we considered further Galois connections by imposing algebraic restrictions on the sets of dual objects: the relations $R$ and $S$ in the constraints were required to be invariant under given clones $\mathcal{C}_1$ and $\mathcal{C}_2$ on $A$ and $B$, respectively. Within this framework, function classes are defined by sets of these invariant constraints, and characterized in terms of stability under left and right composition with $\mathcal{C}_2$ and $\mathcal{C}_1$. This general Galois framework subsumes, in particular, the Galois settings described by Pippenger, and those developed in previous joint work with Stephan Foldes. The notion of functional equation was adjusted to the general case of arbitrary underlying sets. This formulation facilitated a general correspondence between definability by functional equations and by relational constraints. The proof was based on a construction which revealed general criteria by which further correspondences between equations of specific algebraic syntax, and relational constraints satisfying certain invariance conditions, can be established. As examples, we considered certain noteworthy classes of field-valued functions of Boolean variables, and proved existence and non-existence of linear characterizations of these classes, in terms of the characteristic of the underlying field. Explicit equational characterizations were also given, accordingly. As further applications, we considered classes of affine operations on finite fields, with a bounded number of essential variables. We established a general correspondence between linear equations and affine constraints, which we used to show that these classes do not have linear theories. By making use of well-known facts from linear algebra over finite fields, we obtained characterizations of each of these classes, by means of (non-linear) functional equations.

We started by studying the Boolean case, and considered characterizations of Boolean function classes, as studied by Ekin, Foldes, Hammer and Hellerstein, but by means of functional equations written in the additive language of Boolean rings, i.e. by means of the so-called linear equations. We showed that a class of Boolean functions has a linear theory if and only if it is stable under right and left composition with the clone of constant-preserving linear functions. These classes were equivalently described within a Galois setting, more stringent than that considered by Pippenger, in which classes are defined by means of affine constraints, showing that definability by linear equations is equivalent to definability by affine constraints, since these two approaches specify exactly the same Boolean function classes. The dual question of describing the sets of affine constraints which are characterized by Boolean functions was also addressed and answered.

Then, we studied the general case, and extended Pippenger's Galois theory by removing the finiteness restriction on the underlying sets $A$ and $B$. We showed that the classes of functions definable by constraints are exactly those locally closed classes which are stable under right composition with the smallest clone on $A$, containing only projection maps, and that the sets of relational constraints characterized by functions are essentially those locally closed sets of constraints which are closed under combining families of constraints into new constraints by means of (possibly infinitary) existential first-order schemes similar to those described by Szab\'o. Furthermore, we showed how these results can be used to derive the characterizations of the closed systems associated with the well-known Galois correspondence between operations and relations.

This basic Galois correspondence between functions and constraints was specialized and generalized in several ways in this research work. We studied Galois connections arising from the restriction of the primal objects (functions) and dual objects (relational constraints) to fixed arities, and presented descriptions of the Galois closure systems by means of parametrized analogues of the closures given in the previous joint work with Stephan Foldes. Furthermore, we provided factorizations of the Galois maps in terms of operators associated with these closures.

Also, we considered the more general notion of \emph{multivalued functions}, i.e. mappings of the form $A^n\rightarrow \mathcal{P}(B)$, where $\mathcal{P}(B)$ denotes the set of all subsets of $B$, which generalize the notions of total and partial functions. These different notions were studied in a unifying Galois framework arising from the natural extension of the relation ``satisfies" to multivalued functions and relational constraints (whose ``consequents" are still defined as relations on $B$, and not on $\mathcal{P}(B)$). We described the Galois closed sets by means of necessary and sufficient conditions which specialize to those given in the total single-valued case, and presented factorizations of the associated Galois maps in terms of simpler closure operators. Moreover, we considered further Galois connections by imposing algebraic restrictions on the sets of dual objects: the relations $R$ and $S$ in the constraints were required to be invariant under given clones $\mathcal{C}_1$ and $\mathcal{C}_2$ on $A$ and $B$, respectively. Within this framework, function classes are defined by sets of these invariant constraints, and characterized in terms of stability under left and right composition with $\mathcal{C}_2$ and $\mathcal{C}_1$. This general Galois framework subsumes, in particular, the Galois settings described by Pippenger, and those developed in previous joint work with Stephan Foldes. The notion of functional equation was adjusted to the general case of arbitrary underlying sets. This formulation facilitated a general correspondence between definability by functional equations and by relational constraints. The proof was based on a construction which revealed general criteria by which further correspondences between equations of specific algebraic syntax, and relational constraints satisfying certain invariance conditions, can be established. As examples, we considered certain noteworthy classes of field-valued functions of Boolean variables, and proved existence and non-existence of linear characterizations of these classes, in terms of the characteristic of the underlying field. Explicit equational characterizations were also given, accordingly. As further applications, we considered classes of affine operations on finite fields, with a bounded number of essential variables. We established a general correspondence between linear equations and affine constraints, which we used to show that these classes do not have linear theories. By making use of well-known facts from linear algebra over finite fields, we obtained characterizations of each of these classes, by means of (non-linear) functional equations.

##### Kokoelmat

- Väitöskirjat [2301]