Restriction categories and the semantics of partiality

Relatore
Prof. Robin Cockett - Department of Computer Science, University of Calgary

Data e ora
giovedì 4 dicembre 2008 alle ore 16.30 - Caffe' e pasticcini alle 16.15

Luogo
Ca' Vignal 3 - Piramide, Piano 0, Sala Verde

Referente
Gianluigi Bellin

Referente esterno

Data pubblicazione
28 novembre 2008

Dipartimento
 

Riassunto

Partial functions are absolutely fundamental in mathematics.  They arises,
for example, in elementary calculus.  In fact, Karl Menger in his freshman
calculus text (Menger 1955) already saw the need for a rigorous abstract
theory of partiality.  He and his students Bert Schweitzer and Abe Sklar 
subsequently developed an axiomatic theory for semigroups of partial 
functions (Menger 1959, Schweitzer and Sklar 1961,1967).  Over the next 
fifty years this axiomatization was reinvented several more times both 
within semigroup theory and elsewhere. 

Motivated by the work of Robert Di Paola and Alex Heller 
(Di Paolo and Heller 1987) , Pino Rosolini and Edmund Robinson (Rosolini 
and Robinson 1988), and Aurelio Carboni (Carboni 1987), and completely 
unaware of the volume of work mentioned above Steve Lack and I provided 
(Cockett and Lack  2002) a categorical axiomatization of partiality which 
was almost identical to the above.  In fact, even the name we chose, 
{\em restriction\/} categories, had precedents in that literature. 
However, approaching the subject with categorical tools in hand allowed a 
much more perspicuous development of the subject than was hitherto 
possible. 

In this talk I wish to introduce the basic theory of restriction 
categories. In particular, I will outline the completeness and 
representation theorems for these categories and discuss some (unlikely)  
examples. I will argue that restriction categories provide the cleanest 
basis, so far, for studying partiality. I will end by discussing some more 
recent developments. In particular, I would like to introduce Turing 
categories and the revamping of the theory of computability, which  
Pieter Hofstra and I are undertaking ... and why it is necessary.
ornamento
Inizio pagina