First-order logic in the Medvedev lattice

DOI10.1007/S11225-015-9615-2MaRDI QIDQ897478zbMATHOpenAlexDBLPWikidataFDO

Authors Rutger Kuyper

Publication date 7 December 2015

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.5311

zbMATH Keywords

first-order logicintuitionistic logicMedvedev degrees

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Logical aspects of lattices and related structures (03G10) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: Kolmogorov introduced an informal calculus of problems in an attempt to provide a classical semantics for intuitionistic logic. This was later formalised by Medvedev and Muchnik as what has come to be called the Medvedev and Muchnik lattices. However, they only formalised this for propositional logic, while Kolmogorov also discussed the universal quantifier. We extend the work of Medvedev to first-order logic using the notion of a first-order hyperdoctrine from categorical logic to a structure which we will call the Medvedev hyperdoctrine. We also study the intermediate logic that the Medvedev hyperdoctrine gives us, where we focus in particular on subintervals of the Medvedev hyperdoctrine in an attempt to obtain an analogue of Skvortsova's result that there is a factor of the Medvedev lattice characterising intuitionistic propositional logic. Finally, we consider Heyting arithmetic in the Medvedev hyperdoctrine and prove an analogue of Tennenbaum's theorem on computable models of arithmetic.

Recommendations

• Intermediate logics and factors of the Medvedev lattice
• scientific article; zbMATH DE number 4059356
• Mass problems and intuitionistic higher-order logic
• Kripke models, distributive lattices, and Medvedev degrees
• Constructive logic and the Medvedev lattice

Cites work

• scientific article; zbMATH DE number 1003731 (Why is no real title available?)
• scientific article; zbMATH DE number 4059356 (Why is no real title available?)
• scientific article; zbMATH DE number 50290 (Why is no real title available?)
• scientific article; zbMATH DE number 841094 (Why is no real title available?)
• scientific article; zbMATH DE number 3216177 (Why is no real title available?)
• scientific article; zbMATH DE number 3110190 (Why is no real title available?)
• A survey of Mučnik and Medvedev degrees
• Adjointness in Foundations
• Classical recursion theory. The theory of functions and sets of natural numbers
• Completeness properties of heyting's predicate calculus with respect to re models
• Computable Kripke models and intermediate logics
• Constructivism in mathematics. An introduction. Volume I
• Decidable Kripke models of intuitionistic theories
• Handbook of logic in computer science. Vol. 5: Logical and algebraic methods
• Mass problems and intuitionistic higher-order logic
• Natural factors of the Medvedev lattice capturing IPC
• Realizability. An introduction to its categorical side
• Semantical investigations in Heyting's intuitionistic logic
• Tripos theory in retrospect
• Zur Deutung der intuitionistischen Logik

Cited in

(5)

• Mass problems and intuitionistic higher-order logic
• scientific article; zbMATH DE number 4059356 (Why is no real title available?)
• Intermediate logics and factors of the Medvedev lattice
• scientific article; zbMATH DE number 7668110 (Why is no real title available?)
• scientific article; zbMATH DE number 6290323 (Why is no real title available?)

This page was built for publication: First-order logic in the Medvedev lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897478)