Natural factors of the Medvedev lattice capturing IPC

DOI10.1007/S00153-014-0393-8MaRDI QIDQ481874zbMATH OpenOpenAlexFDO

Authors Rutger Kuyper

Publication date 15 December 2014

Published in Archive for Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

intuitionistic logicMedvedev degreesJankov's logic

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: Skvortsova showed that there is a factor of the Medvedev lattice which captures intuitionistic propositional logic (IPC). However, her factor is unnatural in the sense that it is constructed in an ad hoc manner. We present a more natural example of such a factor. We also show that for every non-trivial factor of the Medvedev lattice its theory is contained in Jankov's logic, the deductive closure of IPC plus the weak law of the excluded middle. This answers a question by Sorbi and Terwijn.

Recommendations

• Natural factors of the Muchnik lattice capturing IPC
• On the structure of the Medvedev lattice
• Factorization properties of lattices over the integers
• Factorization by lattice homomorphisms
• Factoring the characteristic polynomial of a lattice
• Factorizing lattices by interval relations
• Some Quotient Lattices of the Medvedev Lattice
• scientific article; zbMATH DE number 3093093
• A natural lattice basis problem with applications

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 841094 (Why is no real title available?)
• scientific article; zbMATH DE number 3250567 (Why is no real title available?)
• scientific article; zbMATH DE number 3264054 (Why is no real title available?)
• scientific article; zbMATH DE number 3110190 (Why is no real title available?)
• A faithful interpretation of the intuitionistic propositional calculus by means of an initial segment of the Medvedev lattice
• A survey of Mučnik and Medvedev degrees
• Algorithmic randomness and complexity.
• Characterizing the join-irreducible Medvedev degrees
• Classical recursion theory. The theory of functions and sets of natural numbers
• Degrees joining to 0′
• Distributive Initial Segments of the Degrees of Unsolvability
• Finite groups whose maximal subgroups of Sylow \(p\)-subgroups admit a \(p\)-solvable supplement.
• Intermediate logics and factors of the Medvedev lattice
• Intuitionistic logic and Muchnik degrees
• Natural factors of the Muchnik lattice capturing IPC
• On closed elements in closure algebras
• On the interpretation of intuitionistic number theory
• Realizability. An introduction to its categorical side
• Some theorems about the sentential calculi of Lewis and Heyting
• The Medvedev lattice of computably closed sets
• The upper semi-lattice of degrees of recursive unsolvability

Cited in

(5)

• Constructive logic and the Medvedev lattice
• First-order logic in the Medvedev lattice
• Comparing the degrees of enumerability and the closed Medvedev degrees
• scientific article; zbMATH DE number 4059356 (Why is no real title available?)
• Natural factors of the Muchnik lattice capturing IPC

This page was built for publication: Natural factors of the Medvedev lattice capturing IPC

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