×

The logic of structures. (English) Zbl 0763.18001

“Proof-theoretic” properties of various categories of accessible categories (Cartesian closure, normal forms, links with linear logic) are investigated. The connection of accessible categories with sketches is used (accessible categories being the categories of models of a small sketch). The author works in ZFC + the axiom of universes. The following topics are studied in detail: \(\beta\)-accessible categories and \(\beta\)- continuous functors (with a regular cardinal); Cartesian closed categories of accessible categories; some linear features (in the sense of Girard’s linear logic) of the theory of \(\alpha\)-presentable categories.

MSC:

18A15 Foundations, relations to logic and deductive systems
68Q55 Semantics in the theory of computing
03F05 Cut-elimination and normal-form theorems
18A35 Categories admitting limits (complete categories), functors preserving limits, completions
03C65 Models of other mathematical theories
18A10 Graphs, diagram schemes, precategories
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ageron, P., Les catégories localement (multi)présentables comme domaines de Sott, Diagrammes, 21, A1-A5 (1989)
[2] Barr, M., \(^∗\)-Autonomous Categories, (Lecture Notes in Mathematics, 752 (1979), Springer: Springer Berlin) · Zbl 0217.07003
[3] Barr, M.; Wells, C., Toposes, Triples and Theories (1985), Springer: Springer Berlin · Zbl 0567.18001
[4] Coquand, T., Categories of embeddings, Theoret. Comput. Sci., 68, 221-237 (1989) · Zbl 0688.18004
[5] Diers, Y., Catégories localement multiprésentables, Arch. Math., 34, 344-356 (1980) · Zbl 0432.18006
[6] Ehresmann, C., Esquisses et types des structures algébriques, Bul. Inst. Politehn. Iasi Sect. I, XIV, 1-14 (1968) · Zbl 0196.03102
[7] Gabriel, P.; Ulmer, F., Lokal präsentierbare Kategorien, (Lecture Notes in Mathematics, 221 (1971), Springer: Springer Berlin) · Zbl 0225.18004
[8] Girard, J.-Y., Linear logic, Theoret. Comput. Sci., 50, 1-102 (1987) · Zbl 0625.03037
[9] Girard, J.-Y., Normal functors, power series and lambda calculus, Ann. Pure Appl. Logic, 37, 129-177 (1988) · Zbl 0646.03056
[10] Girard, J.-Y.; Lafont, Y.; Taylor, P., Proofs and Types (1989), Cambridge University Press: Cambridge University Press Cambridge
[11] Gray, J., The category of sketches as a model for algebraic semantics, (Gray, J.; Scedrov, A., Categories in Computer Science and Logic. Categories in Computer Science and Logic, Contemporary Mathematics, 92 (1989), Amer. Mathematical Soc: Amer. Mathematical Soc Providence, RI) · Zbl 0688.68077
[12] Grothendieck, A.; Verdier, J.-L., Préfaisceaux, (Théorie des Topos et Cohomologie Étale des Schémas (SGA4). Théorie des Topos et Cohomologie Étale des Schémas (SGA4), Lecture Notes in Mathematics, 269 (1972), Springer: Springer Berlin) · Zbl 0249.18021
[13] Guitart, R., On the geometry of computations, (II) Cahiers Topologie Géom. Différentielle Catégoriques, XXIX, 297-326 (1988) · Zbl 0668.18009
[14] Guitart, R.; Lair, C., Calcul syntaxique des modèles et calcul des formules internes, Diagrammes, 4, 1-106 (1980) · Zbl 0508.03030
[15] Guitart, R.; Lair, C., Existence de diagrammes localement libres, (II) Diagrammes, 7, RGCL1-RGCL4 (1982) · Zbl 0518.18005
[16] Guitart, R.; Lair, C., Limites et colimites pour représenter les formules, Diagrammes, 7, GL1-GL24 (1982) · Zbl 0535.03013
[17] Jung, A., Cartesian closed categories of algebraic CPO’s, Theoret. Comput. Sci., 70, 223-250 (1990)
[18] Lair, C., Catégories modelables et catégories esquissables, Diagrammes, 7, L1-L20 (1981) · Zbl 0522.18008
[19] Lair, C., Diagrammes localement libres, extensions de corps et théorie de Galois, Diagrammes, 10, L1-L17 (1983) · Zbl 0569.18001
[20] Lair, C., Catégories qualifiables et catégories esquissables, Diagrammes, 17, 1-153 (1987) · Zbl 0624.18003
[21] Lamarche, F., Modelling polymorphism with categories, (Thesis (1988), McGill University: McGill University Montréal)
[22] Makkai, M.; Paré, R., Accessible Categories: The Foundations of Categorical Model Theory, (Contemporary Mathematics, 104 (1989), Amer. Mathematical Soc: Amer. Mathematical Soc Providence, RI) · Zbl 0703.03042
[23] Seely, R., Linear categories, \(^∗\)-autonomous categories and cofree coalgebras, (Gray, J.; Scedrov, A., Categories in Computer Science and Logic. Categories in Computer Science and Logic, Contemporary Mathematics, 92 (1989), Amer. Mathematical Soc: Amer. Mathematical Soc Providence, RI) · Zbl 0674.03007
[24] Taylor, P.; Pitt, D., Quantitative domains, groupoids and linear logic, Category Theory and Computer Science. Category Theory and Computer Science, Lecture Notes in Computer Science, 389, 155-181 (1989), Springer · Zbl 07572041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.