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 条
  • [21] Sperner spaces and first-order logic
    Blass, A
    Pambuccian, V
    MATHEMATICAL LOGIC QUARTERLY, 2003, 49 (02) : 111 - 114
  • [22] First-order conditional logic revisited
    Friedman, N
    Halpern, JY
    Koller, D
    PROCEEDINGS OF THE THIRTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE EIGHTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE, VOLS 1 AND 2, 1996, : 1305 - 1312
  • [23] DATALOG VS FIRST-ORDER LOGIC
    AJTAI, M
    GUREVICH, Y
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 49 (03) : 562 - 588
  • [24] First-order classical modal logic
    Arló-Costa H.
    Pacuit E.
    Studia Logica, 2006, 84 (2) : 171 - 210
  • [25] First-Order da Costa Logic
    Graham Priest
    Studia Logica, 2011, 97 : 183 - 198
  • [26] A denotational semantics for first-order logic
    Apt, KR
    COMPUTATIONAL LOGIC - CL 2000, 2000, 1861 : 53 - 69
  • [27] On First-Order Logic and CPDA Graphs
    Christopher H. Broadbent
    Theory of Computing Systems, 2014, 55 : 771 - 832
  • [28] Combining Probability and First-Order Logic
    Leiva, Mario A.
    Garcia, Alejandro J.
    Shakarian, Paulo
    Simari, Gerardo I.
    ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2021, (345): : 4 - 4
  • [29] Monitoring First-Order Interval Logic
    Havelund, Klaus
    Omer, Moran
    Peled, Doron
    SOFTWARE ENGINEERING AND FORMAL METHODS (SEFM 2021), 2021, 13085 : 66 - 83
  • [30] Relating Z and first-order logic
    Martin, A
    FM'99-FORMAL METHODS, VOL II, 1999, 1709 : 1266 - 1280