Categories with families and first-order logic with dependent sorts

被引:4
|
作者
Palmgren, Erik [1 ]
机构
[1] Stockholm Univ, Dept Math, Stockholm, Sweden
基金
瑞典研究理事会;
关键词
Intuitionistic first-order logic; Dependent types; Categorical logic; Models of type theory; FOUNDATION;
D O I
10.1016/j.apal.2019.102715
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
First-order logic with dependent sorts, such as Makkai's first-order logic with dependent sorts (FOLDS), or Aczel's and Belo's dependently typed (intuitionistic) first-order logic (DFOL), may be regarded as logic enriched dependent type theories. Categories with families (cwfs) is an established semantical structure for dependent type theories, such as Martin-Lig type theory. We introduce in this article a notion of hyperdoctrine over a cwf, and show how FOLDS and DFOL fit in this semantical framework. A soundness and completeness theorem is proved for DFOL. The semantics is functorial in the sense of Lawvere, and uses a dependent version of the Lindenbaum-Tarski algebra for a DFOL theory. Agreement with standard first-order semantics is established. Applications of DFOL to constructive mathematics and categorical foundations are given. A key feature is a local propositions-as-types principle. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页数:75
相关论文
共 50 条
  • [1] First-order logic with dependent types
    Rabe, Florian
    AUTOMATED REASONING, PROCEEDINGS, 2006, 4130 : 377 - 391
  • [2] THE FIRST-ORDER LOGIC OF CZF IS INTUITIONISTIC FIRST-ORDER LOGIC
    Passmann, Robert
    JOURNAL OF SYMBOLIC LOGIC, 2024, 89 (01) : 308 - 330
  • [3] First-Order Logic and First-Order Functions
    Freire, Rodrigo A.
    LOGICA UNIVERSALIS, 2015, 9 (03) : 281 - 329
  • [4] Non-cyclic Sorts for First-Order Satisfiability
    Korovin, Konstantin
    FRONTIERS OF COMBINING SYSTEMS (FROCOS 2013), 2013, 8152 : 214 - 228
  • [5] A First-Order Logic with Frames
    Murali, Adithya
    Pena, Lucas
    Loeding, Christof
    Madhusudan, P.
    PROGRAMMING LANGUAGES AND SYSTEMS ( ESOP 2020): 29TH EUROPEAN SYMPOSIUM ON PROGRAMMING, 2020, 12075 : 515 - 543
  • [6] Extended First-Order Logic
    Brown, Chad E.
    Smolka, Gert
    THEOREM PROVING IN HIGHER ORDER LOGICS, PROCEEDINGS, 2009, 5674 : 164 - 179
  • [7] FIRST-ORDER HOMOTOPICAL LOGIC
    Helfer, Joseph
    JOURNAL OF SYMBOLIC LOGIC, 2023,
  • [8] First-Order Logic with Adverbs
    Haze, Tristan Grotvedt
    LOGIC AND LOGICAL PHILOSOPHY, 2024, 33 (02) : 289 - 324
  • [9] GEOMETRISATION OF FIRST-ORDER LOGIC
    Dyckhoff, Roy
    Negri, Sara
    BULLETIN OF SYMBOLIC LOGIC, 2015, 21 (02) : 123 - 163
  • [10] First-Order Logic of Change
    Swietorzecka, Kordula
    LOGIC JOURNAL OF THE IGPL, 2024, 32 (01) : 35 - 46