<TITLE: On Definability of Functions of Several Variables
ACADEMIC DOMAIN: natural sciences
DISCIPLINE: mathematics
EVENT TYPE: doctoral defence presentation
FILE ID: UDEFP120
NOTES: continued in UDEFD120

RECORDING DURATION: 21 min 31 sec

RECORDING DATE: 16.9.2006

NUMBER OF PARTICIPANTS: circa 30

NUMBER OF SPEAKERS: 1

S2: NATIVE-SPEAKER STATUS: Portuguese; ACADEMIC ROLE: junior staff; GENDER: male; AGE: 24-30>


<S2> well first of all i i would like to welcome you to the the public defence of my doctoral erm dissertation , well in this erm in this short talk erm i will will try to to explain and and expose erm several erm or some aspects of the research work which was presented in this doctoral er in this doctoral thesis , well to start with erm in this doctoral work erm we were interested in functions that is maps which take objects from one set to objects of another another set , now these functions have properties and these properties can be expressed or specified er in several ways so in this doctoral work we we studied erm ways or mechanisms for for specifying erm sets of functions having certain properties in common and which we call classes , and i will try to to illustrate er this study by means of some concrete <COUGH> concrete examples . so let us consider first the identity function that is the function that maps each point to itself now this function has two immediate properties well first of all it is increasing since the greater are the o- the objects the greater is the value of the function and it constitutes a linear an a linear function and this can be seen erm since this function erm is represented by a line passing through the (object) but of course not every er increasing function constitutes a linear function and not every linear function constitutes an increasing function so for example for example the cubic function er constitutes an increasing function but this function is non- er linear well s- conversely er the negation which is the which is the function that maps er each object to which maps each object to itself er to to to its negative er constitutes a linear function which is decreasing , now this er <TRYING TO MOVE MARKERBOARDS, P:05> (i must) , how do i (remove) it . well there are several erm this these these properties can be expressed in in several ways . for example the property of being increasing can be expressed by means of relations er namely by means of the less or equal relation because the increasing functions are exactly those which map each each er e- each pair of points satisfying this relation to pairs of points still satisfying the same relation , well similarly we see that the property of being decreasing can be specified er by means of pairs of relations well and another way another common way of expressing function properties is by means of equations for example the property of being linear can be expressed by an equation which er simply tell us that the linear functions are exactly those which preserve addition , now as we are going to see erm each one of these properties can be specified by means of equations and by means of pairs of relations but only the first and the last can be erm only the first property and the last can be expressed by means of sets of single relations and this is because the the properties which are known to be expressible by means of relation er are known to be closed under functional compositions and the property of being decreasing does not fulfil this condition well in the end if we compose the negation er with itself we obtain the identity function which constitutes an increasing function and thus in particular it constitutes a non-decreasing function , well and these examples basically er illustrate er part of the research programme er which was carried out in this doctoral work so in one side we have functions and their properties and on the other side we have ways or mechanisms for specifying these properties so the question is to determine which erm which function properties can be expressed by given defining mechanisms and conversely er which defining mechanisms can er specify given function properties , well in this doctoral work we we focused essentially on two approaches to functional classifiability , well one by means of equations and the other by means of pairs of relations which we call relational constraints , so in the sequel i i will focus erm mostly on the the latter approach and i will try to present in a a little more formal way erm the origins motivations as well as give you little taste of our results , so i start by introducing some basic notions and terminology , well in this doctoral work the functions that we were interested in are the so-called B-valued functions on A because these functions are maps taking tuples over a set A to elements of erm possibly different set B so for example the the displayed function constitutes a real-valued function on the positive integers since this function maps pairs of positive integers to real numbers , now in the particular case that the two underlying sets are the same erm then we refer to these er functions as operations on A well and furthermore if if the underlying sets A erm is the two-element set zero one then these these operations are usually known known as er boolean functions , well typical examples of operations are the the projections er which are maps taking tuples erm to fixed components and the the usual binary addition and binary er and the binary er product X-1 times X- X-2 and we express this operation by juxtaposition , now next we <COUGH> we defined the notion of er functional composition so the composition of a of a N-ary function F with M-ary er functions G-1 to GN is defined as the function obtained from from F by substituting each of its variables by the corresponding G function so for example the the composition of our function F with the addition and the product is the function obtained from F by substituting the variable X-1 by the addition X-1 plus X-2 and by substituting the variable X-2 by the product X-1 times X-2 , now this notion of functional composition er is naturally extended to classes by defining the composition of a class A with a class B as the set of all (those well-) defined er defined compositions or functions in A with functions in (xx) , so with this terminology we can define a clone on a set A as a class of operations which contains all projections and which is stable under composition with itself now typical examples of clones are the erm are the class B which contains all projections which constitutes a clone er since the composition of projections with projections is still a projection and the class L of er linear operations that is operations which are the sum of weighted variables and which er this class also constitutes a clone since er projections are a particular case of linear erm of linear operations and if we substitute any of these variables by a sum of weighted variables we still obtain the sum of weighted variables that is we still obtain a linear function now clones er constitute a closure system with respect to class composition and thus er clones can each clone can be can be specified by by a set of operations which we call generators in the sense that each operation in the clone can be expressed by as compositions of these generating functions but there are other ways of er specifying clones and in one of such ways or a- or approaches to specify clones clones appear as er closure systems induced by galois connection , so what is a galois connection , well a galois connection between a set er P of primal objects and a set D of dual objects er is simply a pair of markings V and W which establish a two-way correspondence between er sets of primal objects and sets of dual objects erm and which are usually induced by binary relations between the primal and the dual objects , now one of the main features <COUGH> of galois connections is that two compositions are V with W and W with V constitute closure operators on the primal and dual objects that is they induce closure systems on both primal and dual objects in such a way that the two mappings V and W constitute two-way translations between these two induced erm closure systems , well and these erm and these er properties of of galois connections er reveal their usefulness well through these mappings properties of primal objects can be described in terms of dual objects and conversely properties of dual objects can be described in terms of primal objects , well in this approach erm , this approach to define clones er was exactly erm er to to erm th- this approach based on galois connections was exactly the method used by by geiger erm and independently by erm bodnarchuk kaluznin kotov and romov who in the late 60s introduced the galois or established the galois connection in which clones are described by means of relations , so formally an M-ary relation on a set A is simply a set of M-tuples over A but in order to to simplify our exposition we are going to consider these relations as classes of unary maps defined on the first M positive integers and valued in A so in this sense we say that an operation stu- er preserves a relation R if er the operation composed with the relation is still contained in the relation now this notion of er relational preservation induces erm a fairly well-known er galois connection between between er operations and relations which is denoted by pol and inv where pol which stands for polymorphisms denotes the map which takes each each set Q of relations to the class of all those operations preserving each member of Q and where inv <COUGH> which stands for invariance denotes the mapping which takes each class C of operations to the set of all those relations preserved by each member of the class now it is known that erm the the properties or the the classes which can be defined in this way that is which constitutes erm which constitutes er sets of polymorphisms for a given set of relations these these er these classes erm are exactly the clones of operations on the other line set so for example the clone of constant preserving linear operations on a given field can be described as the set of polymorphisms for the affined subspaces over the same underlying field well but erm concerning erm the definability of function properties well this er this framework has some limitations , well first of all erm it's it can only be applied to to operations but even in this case it fails to to to specify several natural properties of operations such as that of being decreasing because erm because these these er these these properties do not constitute clones and therefore they cannot be specified by means of relations so to overcome these diff- these limitations er pippenger introduced a galois framework in which er function properties are specified by means of erm pairs of relations which we call relational constraints , so formally an M-ary A to B relational constraints is a couple RS of M-ary relations on A and on B which are called the antecedent and consequent of the constraint , now in this setting er a function is set to satisfy one of such constraints if the function composed with the antecedent is contained on the consequent , now as in in the erm in the case of operations er this er this er notion of er constraint satisfaction induces a a galois connection between functions and relational constraints which we denote by FSC and CSF where FSC denotes the mapping taking each set T of relational constraints to the class of all those functions satisfying each member of T and where er CSF erm denotes the mapping which takes each class K of of erm each class K of functions to the set of all those relational constraints satisfied by every member of the class now looking at er the definition of erm at at the notion er of er constraint satisfaction we see that this notion er reduces the relational preservation by taking the antecedent and consequent to be the same relation that is to say that erm clones constitute a particular case of classes which can be defined by means of relational constraints , well but as we have seen erm there are classes of functions which do not constitute clones but still they can be defined by means of relational constraints well and this observation erm er raises the question which classes of functions can be specified by means of relational constraints , well in the finite case erm pippenger noticed that if a class satis- if a class K satisfies a constraint RS then also the composition of K with the smallest clone containing all projections also satisfies the same the same er constraint RS that is to say that if a class is satisfied is is defined by means of relational constraints then this class must be closed under simple variable substitutions that is this class must be stable under right composition with the smallest clone of projections , well in the finite case er pippenger showed that <COUGH> this condition er closure under simple variable substitutions also suffices to characterise or to describe those classes which can be defined by means of er relational constraints but in the fi- in the the infinite case erm this this is not er well this is not the case because erm if erm if a function is affine on a a infinite domain then constraint satisfaction can only be verified on finite restrictions of the function building and thus if a class is defined by means of relational constraints then the class must contain every function which can be interpolated on every finite restriction of its domain by some member of the class , and classes fulfilling this condition are said to be locally closed , well in the finite case erm in the finite case er this condition is is trivially satisfied but in over er infinite er sets this is not this is not the case and in the example of a class which is not locally closed is the class of all polynomials erm which is not locally closed because every function er can be interpolated on every finite restriction of its domain by some polynomial but of course not every function is polynom , now together with er with this additional condition er <NAME> and and myself we showed that the classes which can be defined in general the the classes which can be defined by means of relational constraints are exactly those locally closed classes which are closed under simple variable substitutions well the the description or the the dual question er of which er of which classes or which sets of relational constraints can be er specified by means of functions was also addressed in this in this doctoral in this doctoral work and it was answering the same in the same style by means of necessary and sufficient conditions but now involving erm the combination of sets of relational constraints into into new constraints by means of possibly infinitary er formula schemes and also involving erm a notion of local closure which expresses a sort of compactness on the antecedents of relational constraints well in this <COUGH> in this er in this doctoral work erm we we specialised this er this basic galois connection between functions and relational constraints erm , we specialised and also generalised this ba- er basic galois connection between functions and relational constraints in several ways well first we considered arity restrictions on both function classes and sets of relational constraints well this er this setting allow us to focus on erm special types of mappings between special types of relational of relational structures for example the the automorphisms between graphs appear in the setting as unary functions satisfying binary constraints , well also we extended this er this basic er galois connection between functions and relational constraints by generalising the notion of function to multi-valued functions and in this way we were capable of considering in a in a unified <COUGH> in a unified galois setting several generalised notions er which appear and are used erm both in mathematics and in in computer science to describe for example er functional inverses er partiality and non-determinism and moreover we consider er we considered further galois connections by imposing invariants' conditions on the defining sets of relational constraints well and this erm and this study er provided tools which were used in the equational approach to functional class definability by establishing general correspondences between equations and relational constraints in terms of their expressive power and i would like to i would like to <COUGH> to conclude my presentation by illustrating erm by illustrating these points , well in the beginning of erm of our joint research er research work with er <NAME> we were interested in equational definability of function properties but taking into account the language in which the equations are written , well in particular we were interested in the so-called erm linear equations which are which are er expressions er written in the language of in the additive language of rings so for example the the clone of linear operations er or the equation defining the clone of linear operations constitutes erm a linear a linear equation but er the equation which is known to define the class of decreasing functions does not er constitute er a linear equation because this equation is written in the (xx) language of of (xx) so erm well to describe the erm the classes which ca- which have linear series that is which can be de- er which can be described by means of of erm of linear equations well we first noticed that erm the classes definable by means of linear equations are exactly those which can be defined by means of affine constraints that is constraints in which both the antecedent and the consequent constitute er affined subspaces well and then erm by noticing that er these constraints are exactly those in which the antecedent and consequent are closed are erm invariant under the under the the clones of constant preserving linear operations we showed that the the classes which can be defined by means of linear equations are exactly those which are stable under both right and left composition with the clones of constant-preserving linear operations , well and i i ask you professor er <NAME S3> as er as my my opponent ap- er appointed by the faculty er of information science to make comments on my dissertation which you which you may find er pertinent </S2>
