Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Cover of the book
Tytuł książki

The logic of categories of partial functions and its applications

Seria
Rozprawy Matematyczne tom/nr w serii: 241 wydano: 1986
Zawartość
Warianty tytułu
Abstrakty
EN

CONTENTS
0. Introduction.......................................................................................................................................................................................5
1. Preliminaries.....................................................................................................................................................................................9
2. 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................................................................................20
3. 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........................................................................................26
4. 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...........47
5. 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......................................................................................................................................80
6. 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................................................................................................................102
7. 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...................................................................................................................................................................141
Appendix A.......................................................................................................................................................................................148
Appendix B.......................................................................................................................................................................................149
Appendix C.......................................................................................................................................................................................155
References.......................................................................................................................................................................................157
Index.................................................................................................................................................................................................160
Index of symbols...............................................................................................................................................................................163
Słowa kluczowe
Tematy
Miejsce publikacji
Warszawa
Copyright
Seria
Rozprawy Matematyczne tom/nr w serii: 241
Liczba stron
165
Liczba rozdzia³ów
Opis fizyczny
Dissertationes Mathematicae, Tom CCXLI
Daty
wydano
1986
Twórcy
Bibliografia
  • [1] H. Andreka and I. Nemeti, Generalization of the concept of variety and quasivariety to partial algebras through category theory, Dissertationes Math. 204. 1983.
  • [2] L. Banachowski. et al., An Introduction to Algorithmic Logic, Mathematical Investigations in the Theory of Programs, in Mathematical Foundations of Computer Science, ed. A. Mazurkiewicz and Z. Pawlak, Banach Center Publications 2, Warszawa 1977, pp. 7-100.
  • [3] E. Bishop, Foundations of Constructive Analysis, New York 1967.
  • [4] B. Blanc, Langages du premier ordre sur graphes et théorie sur catégorie, Cahiers Math. Montpellier, decembre 1975.
  • [5] A. Boileau, Types vs topos, Université de Montréal, mimeographed 1975.
  • [6] W. S. Brainerd and L. H. Landweber, Theory of Computation, New York 1974.
  • [7] T. Brook, Order and recursion in topoi, Notes on Pure Math. 9 (1977), Australian National University, Canberra.
  • [8] P. Burmeister, Partial algebras - survey of unifying approach towards a two-valued model theory for partial algebras, Algebra Universalis 15 (1982). pp. 306-358.
  • [9] M. Bunge, Topos theory and Souslin's hypothesis, J. Pure Appl. Algebra 4 (1974), pp. 159-187.
  • [10] A. Burroni, Algèbres graphiques, Cahiers Topologic Géom. Différentielle 22 (3) (1981), pp. 249-265.
  • [11] R. L. Constable and D. R. Zlatin. The Type Theory of PL/CV3, in Logics of Programs, ed. D. Kozen, Lecture Notes in Comput Sci. 131, New York 1982, pp. 72-93.
  • [12] M-F. Coste-Roy, M. Coste, and L. Mache, Contribution to the study of the natural number object in elementary topoi. J. Pure Appl. Algebra 17 (1980). pp. 35-68.
  • [13] M. Coste, Une approche logique des théories definissables par limites projectives finies, in Séminaire De Théorie Des Catégories Dirigé par Jean Benabou, preprint of Centre Scientifique et Polytechnique, Université Paris Nord Paris 1976.
  • [14] J. Diller and A. S. Troelstra, Realizability and Intuitionistic Logic, Report 82-12, Dept. of Math. University of Amsterdam 1982.
  • [15] H. Ehrig, W. Kühnel and M. Pfender, Diagram-characterization of recursion, in Category theory applied to computation and control, ed. E. G. Manes, Lecture Notes in Comput. Sci. 25, New York 1975.
  • [16] S. Eilenberg and C. C. Elgot, Recursiveness, New York 1970.
  • [17] M. Eytan, Engeler Algorithms in a Topos, in Fundamentals of Computation Theory FCT'79, ed. L. Budach. Berlin 1979. pp. 128-137.
  • [18] R. Fittler, Direct limits of models, Z. Math. Logik Grundlag. Math. 16 (1970), pp. 377-384.
  • [19] M. P. Fourman, The logic of topoi, in Handbook of Mathematical Logic, ed. J. Barwise, Amsterdam 1977, pp. 1053-1090.
  • [20] P. Freyd. Aspects of topoi, Bull. Austral. Math. Soc. 7 (1972), pp. 1-76.
  • [21] P. Gabriel and F. Ulmer, Lokal presentierbaren Kategorien, Lecture Notes in Math. 221, Berlin 1971.
  • [22] J. A. Goguen, et al., A Junction between Computer Science and Category Theory I: Basic Concepts and Examples (Part 2). I.B.M. Research Report RC 5908, 3/18/76. Yorktown Heights 1976.
  • [23] J. A. Goguen et al. Initial Algebra Semantics and Continuous Algebras, J. Assoc. Comput. Mach. 26, (1) (1977), pp. 68-95.
  • [24] R. Goldblatt, Topoi, the categorical analysis of logic, Amsterdam 1979.
  • [25] G. Grätzer, Universal Algebra, New York 1979, second edition.
  • [26] P. A. Grillet, Regular categories, in Exact categories and categories of sheaves, ed. M. Barr, Lecture Notes in Math. 236, Berlin 1971, pp. 121-222.
  • [27] A. Grzegorczyk, Recursive objects in all finite types. Fund. Math. 54 (1964), pp. 73-93.
  • [28] R. Guitart, Qu'est que la logique dans une catégorie?, Cahiers Topologie Géom. Différentielle 33 (3) (1982), pp. 115-148.
  • [29] H. Herrlich and G. E. Strecker, Category Theory. Boston 1973.
  • [30] R. Hindley and G. Mitschke, Some remarks about the connections between combinatory logic and axiomatic recursion theory, Arch. math. Logic 18 (1977), pp. 99-103.
  • [31] H-J. Hoehnke, On partial algebras, in Universal Algebra, ed. B. Csákany, et al. Colloquia Mathematica Societatis Janos Bolyai 29, Amsterdam 1982. pp. 373-412.
  • [32] J. M. E. Hyland, P.T. Johnstone, and A. M. Pitts, Tripos Theory, Math. Proc. Camb. Phil. Soc. 88 (1980), pp. 205-232.
  • [33] J. M. E. Hyland, The Effective Topos, notes, Cambridge University 1982.
  • [34] T. M. V. Janssen, Foundations and Applications of Montague Grammars, dissertation, Mathematisch Centrum, Amsterdam 1983.
  • [35] P. T. Johnstone, Topos Theory, New York 1977.
  • [36] O. Keane, Abstract Horn Theories, in Model Theory and Topoi, ed. F. W . Lawvere, Lecture Notes in Math. 445, Berlin 1975, pp. 15-50.
  • [37] A. Kock and G. C. Wraith, Elementary Toposes, Lecture Notes Series No. 30, September 1971, Mathematisk Institut, Aarhus Universitet.
  • [38] A. Kock and G. E. Reyes, Doctrines in categorical logic, in Handbook of Mathematical Logic, ed. J. Barwise. Amsterdam 1977. pp. 283-313.
  • [39] J. Lambek, Deductive systems and categories III, in Toposes, Algebraic Geometry and Logic, ed. F. W. Lawvere, Lecture Notes in Math. 274, Berlin 1972, pp. 57-82.
  • [40] J. Lambek, Functional completeness of cartesian categories, Ann. Math. Logic 6 (1974), pp. 259-292.
  • [41] J. Lambek, From types to sets, Advances in Mathematics Vol. 36, No. 2 (1982), pp. 113-164.
  • [42] J. Lambek, Toposes are monadic over categories, in Category Theory, ed. K. H. Kamps, et al. in Lecture Notes Math 962, Berlin 1982, pp. 153-166.
  • [43] J. Lambek, and P. J. Scott, Intuitionistic type theory and the free topos, J. Pure Appl. Algebra 19 (1980), pp. 215-257.
  • [44] F. W. Lawvere, Functorial semantics of algebraic theories, Proc. N.A.S. 50, 1963, pp. 869-872.
  • [45] F. W. Lawvere, Functorial semantics of elementary theories, J. Symbolic Logic 32 (1967), p. 562.
  • [46] F. W. Lawvere, Adjointness in Foundations, Dialectica 23, No. 3/4 (1969), pp. 281-296.
  • [47] S. Mac Lane, Categories for the Working Mathematician, Berlin-New York 1971.
  • [48] Z. Manna, Mathemtical Theory of Computation, New York 1974.
  • [49] P. Martin-Löf Constructive Mathematics and Computer Programming, in Proc. of The 6-th International Congress of Logic, Method. Phil. of Science, Hannover 1979, ed. L. J. Cohen, et al., Amsterdam 1982, pp. 153-175.
  • [50] S. Mazur, Computable analysis, Rozprawy Matematyczne Vol. 33 (1963).
  • [51] C. J. Mikkelsen, Lattice theoretic and logical aspects of elementary topoi. Various Publications Series No. 25, Mathematisk Institut, Aarhus Universitet, March 1976.
  • [52] G. Mirkowska, On formalized Systems of Algorithmic Logic, Bull. Acad. Polon. Sci., Ser. Sci. Math. Astronom. Phys., 19 (1971), pp. 421-428.
  • [53] R. Montague, Universal grammar, Theoria 36 (1970) pp. 371-398.
  • [54] A. Obtułowicz, A characterization of categories of partial functions its applications to universal algebra, in Abstracts of the Sussex Category Meeting held at The Isle of Thorns, July 11 - July 16, 1982, ed. Ch. Mulvey, Sussex Univ. 1982.
  • [55] A. Obtułowicz, P-equational logic, in Proc. of the third workshop-meeting on "Categorical and Algebraic Methods in Computer Science and System Theory" Nov. 3-7 1980. ed. G. Dittrich and W. Merzenich. Dortmundt Universität Forschungsbericht Nr. 114, 1981, pp. 75-80.
  • [56] H. Rasiowa and R. Sikorski, The Mathematics of Metamathematics. Monografie Matematyczne Tom 41, third edition, Warsaw 1970.
  • [57] H. Reichel, Algebraic specifications of abstract data types, in Algebra and its Applications, ed. T. Traczyk, Banach Center Publications Vol. 9, Warsaw 1982.
  • [58] G. E. Reyes, From sheaves to logic, in M.A.A. Studies in Mathematics Vol. 9. ed. A. Daigneault, Math. Assoc. Am. New York 1974, pp. 143-204.
  • [59] D. I. Schlomiuk, Logique des Topos, Seminaire de Mathématiques Superieures Université de Montréal 53, Montréal 1977.
  • [60] H. Schubert, Categories. Berlin 1972.
  • [61] R. A. G. Seely, Locally Cartesian Closed Categories and Type Theory, Math. Proc. Camb. Phil. Soc. 95 (1984), pp. 33-48.
  • [62] J. Słomiński, A theory of extensions of quasi-algebra to algebras. Dissertationes Math. 40, 1964.
  • [63] I. Sols, Programming in topoi, Cahiers Topologie Géom. Différentielle XVI, 3 (1975). pp. 312-319.
  • [64] M. E. Szabo, Algebra of Proofs, Amsterdam 1978.
  • [65] A. Tarski, Equational logic and equational theories of algebras, in Contributions to Mathematical Logic, ed. H. A. Schmidt, Amsterdam 1968, pp. 275-288.
  • [66] M-F. Thibault, Pre-recursive categories, J. Pure Appl. Algebra 24 (19823. pp. 79-93.
  • [67] P. Tichy, Foundations of partial type theory, Rep. Math. Logic 14 (1982), pp. 59-72
  • [68] A. S. Troelstra, Aspects of constructive mathematics, in Handbook of Mathematical Logic, ed. J. Barwise, Amsterdam, pp. 973-1052.
  • [69] H. Volger, Completeness theorem for logical categories, in Model Theory and Topoi, ed. F. W. Lawvere, Lecture Notes in Math. Vol. 445, Berlin 1975, pp. 51-86.
  • [70] H. Volger, Logical categories, semantical categories and topoi, Lecture Notes in Math. Vol. 445, Berlin 1975, pp. 87-100.
  • [71] J. Winkowski, An algebraic description of system behaviours, Theoretical Computer Science 21 (19823. pp. 315-340.
  • [72] A. Wiweger, Pre-adjunctions and lambda-algebraic theories, Colloq. Math. 48 (2) (1984), pp. 153-165.
  • [73] G. C. Wraith, Lectures on Elementary Topoi, in Model Theory and topoi, ed. F. W. Lawvere, Lecture Notes in Math. 445, Berlin 1975, pp. 114-206.
  • [63a] T. Świrszcz and A. Wiweger, Monads and Generalized Linton Alqebras, Bull. Acad. Polon. Sci. Sér. Sci. Math. 29. No. 5-6 (1981), pp. 205-211.
Języki publikacji
EN
Uwagi
Identyfikator YADDA
bwmeta1.element.zamlynska-0ca8970d-4c92-4740-aa1f-95f0b5c048f0
Identyfikatory
ISBN
83-01-064544
ISSN
0012-3862
Kolekcja
DML-PL
Zawartość książki

rozwiń roczniki

JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.