Intuitionistic Logic and Muchnik Degrees

2010/03/23 by Andrea Sorbi, Sorbi, Andrea, Sebastiaan A. Terwijn +1
Computer Science · #03D30 #03G10 #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.1003.4489

openalex publication_date 2010/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that there is a factor of the Muchnik lattice that captures intuitionistic propositional logic. This complements a now classic result of Skvortsova for the Medvedev lattice.

Related

• First-order logic in the Medvedev lattice
• Mass problems and intuitionistic higher-order logic
• Intermediate logics and factors of the Medvedev lattice
• Maximality of bi-intuitionistic propositional logic
• On the Equipollence of the Calculi Int and KM