Journal of Logic and Computation · 2021 · 17 citations · 30 references
HumanitiesComputer ScienceMathematicsLogicSemanticsTheory Of ComputationDeductive ReasoningFirst-order LogicFormal SemanticsIntuitionistic LogicModel TheoryTheorem ProvingCompletenessCoqGame-theoretic SemanticsLogical CompletenessModel SemanticsModel-theoretic SemanticsNon-classical SemanticsType Theory
Abstract We study various formulations of the completeness of first-order logic phrased in constructive type theory and mechanised in the Coq proof assistant. Specifically, we examine the completeness of variants of classical and intuitionistic natural deduction and sequent calculi with respect to model-theoretic, algebraic, and game-theoretic semantics. As completeness with respect to the standard model-theoretic semantics à la Tarski and Kripke is not readily constructive, we analyse connections of completeness theorems to Markov’s Principle and Weak Kőnig’s Lemma and discuss non-standard semantics admitting assumption-free completeness. We contribute a reusable Coq library for first-order logic containing all results covered in this paper.
30
Foundations of Constructive Analysis.
Abraham Robinson, Errett Bishop · American Mathematical Monthly · 1968 · 1.3K citations
Call-by-name, call-by-value and the λ-calculus
Gordon Plotkin · Theoretical Computer Science · 1975 · 1.2K citations
The completeness of the first-order functional calculus
Leon Henkin · Journal of Symbolic Logic · 1949 · 537 citations
H. M. MacNeille · Transactions of the American Mathematical Society · 1937 · 335 citations