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 条
  • [31] Abductive equivalence in first-order logic
    Inoue, Katsumi
    Sakama, Chiaki
    LOGIC JOURNAL OF THE IGPL, 2006, 14 (02) : 333 - 346
  • [32] Rigid First-Order Hybrid Logic
    Blackburn, Patrick
    Martins, Manuel
    Manzano, Maria
    Huertas, Antonia
    LOGIC, LANGUAGE, INFORMATION, AND COMPUTATION (WOLLIC 2019), 2019, 11541 : 53 - 69
  • [33] GAME SEMANTICS FOR FIRST-ORDER LOGIC
    Laurent, Olivier
    LOGICAL METHODS IN COMPUTER SCIENCE, 2010, 6 (04) : 1 - 50
  • [34] Keynote: The First-Order Logic of Signals
    Bakhirkin, Alexey
    Ferrere, Thomas
    Henzinger, Thomas A.
    Nickovic, Dejan
    2018 PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON EMBEDDED SOFTWARE (EMSOFT), 2018,
  • [35] Literal Projection for First-Order Logic
    Wernhard, Christoph
    LOGICS IN ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2008, 5293 : 389 - 402
  • [36] A first-order conditional probability logic
    Milosevic, Milos
    Ognjanovic, Zoran
    LOGIC JOURNAL OF THE IGPL, 2012, 20 (01) : 235 - 253
  • [37] Positive First-order Logic on Words
    Kuperberg, Denis
    2021 36TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2021,
  • [38] Compositional Diagrammatic First-Order Logic
    Haydon, Nathan
    Sobocinski, Pawel
    DIAGRAMMATIC REPRESENTATION AND INFERENCE, DIAGRAMS 2020, 2020, 12169 : 402 - 418
  • [39] Coherence in inquisitive first-order logic
    Ciardelli, Ivano
    Grilletti, Gianluca
    ANNALS OF PURE AND APPLIED LOGIC, 2022, 173 (09)
  • [40] First-order Logic with Connectivity Operators
    Schirrmacher, Nicole
    Siebertz, Sebastian
    Vigny, Alexandre
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2023, 24 (04)