The logic of categories of partial functions and its applications

Adam Obtułowicz

  • Publisher: Instytut Matematyczny Polskiej Akademi Nauk(Warszawa), 1986

Abstract

top
CONTENTS0. Introduction.......................................................................................................................................................................................51. Preliminaries.....................................................................................................................................................................................92. Relations and functional relations in a category.............................................................................................................................13 2.1. The concept of a regular category.............................................................................................................................................13 2.2. Relations in a category and their composition............................................................................................................................14 2.3. Functional relations in a category...............................................................................................................................................15 2.4. Certain generalization of the concept of a category of functional relations................................................................................203. The category P f n A as a category with ordered hom-sets.........................................................................................................23 3.1. The concept of an ordered category..........................................................................................................................................23 3.2. The concept of a domain classifier w.r.t. partial ordering............................................................................................................24 3.3. The concept of a product w.r.t. partial ordering and domain classifier........................................................................................264. The category P f n A as a category with additional equational structure.....................................................................................29 4.1. The concept of a category with ordered precartesian structure.................................................................................................29 4.2. The concepts of an equoidal category and a semilogical category............................................................................................35 4.3. The notion of the category associated to a category with ordered strict precartesian structure.................................................41 4.4. Functors between categories with ordered strict precartesian structure and the notion of quasi-natural transformation...........475. Functional relations in an elementary topos...................................................................................................................................54 5.1. The notion of an elementary topos.............................................................................................................................................54 5.2. Higher-order types of functionality in P f n E ...........................................................................................................................59 5.3. The notion of a doctrine of functional relations..........................................................................................................................64 5.4. The interpretation of logical connectives in an equoidal category with types and in a doctrine of functional relations...............72 5.5. Undefined elements and upper bounds......................................................................................................................................806. Axiom of infinity. programmability. and recursiveness.....................................................................................................................88 6.1. Axiom of infinity and the notion of an arithmetical doctrine of functional relations......................................................................88 6.2. Programmability in doctrines of functional relations...................................................................................................................96 6.3. Recursiveness and doctrines of functional relations................................................................................................................1027. Applications to Universal Algebra; theories classifying partial algebras........................................................................................105 7.1. The formulation of P-equational logic.......................................................................................................................................105 7.2. The presentation of p-theories by categories...........................................................................................................................111 7.3. The representations of partial algebras by functors.................................................................................................................115 7.4. Categories of partial algebras; p-algebraic categories and p-algebraic functors......................................................................119 7.5. Properties of p-algebraic categories and p-algebraic functors.................................................................................................124 7.6. Characterization of p-algebraic categories...............................................................................................................................131 7.7. Applications in linguistics..........................................................................................................................................................138 7.8. Graphical algebras...................................................................................................................................................................141Appendix A.......................................................................................................................................................................................148Appendix B.......................................................................................................................................................................................149Appendix C.......................................................................................................................................................................................155References.......................................................................................................................................................................................157Index.................................................................................................................................................................................................160Index of symbols...............................................................................................................................................................................163

How to cite

top

Adam Obtułowicz. The logic of categories of partial functions and its applications. Warszawa: Instytut Matematyczny Polskiej Akademi Nauk, 1986. <http://eudml.org/doc/268404>.

@book{AdamObtułowicz1986,
abstract = {CONTENTS0. Introduction.......................................................................................................................................................................................51. Preliminaries.....................................................................................................................................................................................92. Relations and functional relations in a category.............................................................................................................................13 2.1. The concept of a regular category.............................................................................................................................................13 2.2. Relations in a category and their composition............................................................................................................................14 2.3. Functional relations in a category...............................................................................................................................................15 2.4. Certain generalization of the concept of a category of functional relations................................................................................203. The category $Pfn_A$ as a category with ordered hom-sets.........................................................................................................23 3.1. The concept of an ordered category..........................................................................................................................................23 3.2. The concept of a domain classifier w.r.t. partial ordering............................................................................................................24 3.3. The concept of a product w.r.t. partial ordering and domain classifier........................................................................................264. The category $Pfn_A$ as a category with additional equational structure.....................................................................................29 4.1. The concept of a category with ordered precartesian structure.................................................................................................29 4.2. The concepts of an equoidal category and a semilogical category............................................................................................35 4.3. The notion of the category associated to a category with ordered strict precartesian structure.................................................41 4.4. Functors between categories with ordered strict precartesian structure and the notion of quasi-natural transformation...........475. Functional relations in an elementary topos...................................................................................................................................54 5.1. The notion of an elementary topos.............................................................................................................................................54 5.2. Higher-order types of functionality in $Pfn_E$...........................................................................................................................59 5.3. The notion of a doctrine of functional relations..........................................................................................................................64 5.4. The interpretation of logical connectives in an equoidal category with types and in a doctrine of functional relations...............72 5.5. Undefined elements and upper bounds......................................................................................................................................806. Axiom of infinity. programmability. and recursiveness.....................................................................................................................88 6.1. Axiom of infinity and the notion of an arithmetical doctrine of functional relations......................................................................88 6.2. Programmability in doctrines of functional relations...................................................................................................................96 6.3. Recursiveness and doctrines of functional relations................................................................................................................1027. Applications to Universal Algebra; theories classifying partial algebras........................................................................................105 7.1. The formulation of P-equational logic.......................................................................................................................................105 7.2. The presentation of p-theories by categories...........................................................................................................................111 7.3. The representations of partial algebras by functors.................................................................................................................115 7.4. Categories of partial algebras; p-algebraic categories and p-algebraic functors......................................................................119 7.5. Properties of p-algebraic categories and p-algebraic functors.................................................................................................124 7.6. Characterization of p-algebraic categories...............................................................................................................................131 7.7. Applications in linguistics..........................................................................................................................................................138 7.8. Graphical algebras...................................................................................................................................................................141Appendix A.......................................................................................................................................................................................148Appendix B.......................................................................................................................................................................................149Appendix C.......................................................................................................................................................................................155References.......................................................................................................................................................................................157Index.................................................................................................................................................................................................160Index of symbols...............................................................................................................................................................................163},
author = {Adam Obtułowicz},
keywords = {computation theory; universal algebra; categories of partial functions; elementary toposes; doctrine of functional relations; adjunction; natural numbers object; programmability; recursive functions; categories of partial algebras},
language = {eng},
location = {Warszawa},
publisher = {Instytut Matematyczny Polskiej Akademi Nauk},
title = {The logic of categories of partial functions and its applications},
url = {http://eudml.org/doc/268404},
year = {1986},
}

TY - BOOK
AU - Adam Obtułowicz
TI - The logic of categories of partial functions and its applications
PY - 1986
CY - Warszawa
PB - Instytut Matematyczny Polskiej Akademi Nauk
AB - CONTENTS0. Introduction.......................................................................................................................................................................................51. Preliminaries.....................................................................................................................................................................................92. Relations and functional relations in a category.............................................................................................................................13 2.1. The concept of a regular category.............................................................................................................................................13 2.2. Relations in a category and their composition............................................................................................................................14 2.3. Functional relations in a category...............................................................................................................................................15 2.4. Certain generalization of the concept of a category of functional relations................................................................................203. The category $Pfn_A$ as a category with ordered hom-sets.........................................................................................................23 3.1. The concept of an ordered category..........................................................................................................................................23 3.2. The concept of a domain classifier w.r.t. partial ordering............................................................................................................24 3.3. The concept of a product w.r.t. partial ordering and domain classifier........................................................................................264. The category $Pfn_A$ as a category with additional equational structure.....................................................................................29 4.1. The concept of a category with ordered precartesian structure.................................................................................................29 4.2. The concepts of an equoidal category and a semilogical category............................................................................................35 4.3. The notion of the category associated to a category with ordered strict precartesian structure.................................................41 4.4. Functors between categories with ordered strict precartesian structure and the notion of quasi-natural transformation...........475. Functional relations in an elementary topos...................................................................................................................................54 5.1. The notion of an elementary topos.............................................................................................................................................54 5.2. Higher-order types of functionality in $Pfn_E$...........................................................................................................................59 5.3. The notion of a doctrine of functional relations..........................................................................................................................64 5.4. The interpretation of logical connectives in an equoidal category with types and in a doctrine of functional relations...............72 5.5. Undefined elements and upper bounds......................................................................................................................................806. Axiom of infinity. programmability. and recursiveness.....................................................................................................................88 6.1. Axiom of infinity and the notion of an arithmetical doctrine of functional relations......................................................................88 6.2. Programmability in doctrines of functional relations...................................................................................................................96 6.3. Recursiveness and doctrines of functional relations................................................................................................................1027. Applications to Universal Algebra; theories classifying partial algebras........................................................................................105 7.1. The formulation of P-equational logic.......................................................................................................................................105 7.2. The presentation of p-theories by categories...........................................................................................................................111 7.3. The representations of partial algebras by functors.................................................................................................................115 7.4. Categories of partial algebras; p-algebraic categories and p-algebraic functors......................................................................119 7.5. Properties of p-algebraic categories and p-algebraic functors.................................................................................................124 7.6. Characterization of p-algebraic categories...............................................................................................................................131 7.7. Applications in linguistics..........................................................................................................................................................138 7.8. Graphical algebras...................................................................................................................................................................141Appendix A.......................................................................................................................................................................................148Appendix B.......................................................................................................................................................................................149Appendix C.......................................................................................................................................................................................155References.......................................................................................................................................................................................157Index.................................................................................................................................................................................................160Index of symbols...............................................................................................................................................................................163
LA - eng
KW - computation theory; universal algebra; categories of partial functions; elementary toposes; doctrine of functional relations; adjunction; natural numbers object; programmability; recursive functions; categories of partial algebras
UR - http://eudml.org/doc/268404
ER -

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.