Cheq logic cannot be captured finitely and is undecidable
Non-finite Axiomatizability and Undecidability of $\mathsf{Cheq}$
Logic in Computer Science
Summary
Some parts of logic are tricky to fully describe with a small set of rules. The authors showed that the system called Cheq cannot be captured with a finite list of axioms, which solves a question that has been open for a long time. They also found that if a related logic called Medvedev logic is impossible to decide automatically, then Cheq is also undecidable. This means certain logical problems in Cheq have no algorithm that always gives an answer.
What this means in practice
- •For logic system designers: Avoid attempts to finitely axiomatize Cheq when designing logical frameworks since it provably cannot have a finite axiom set.
- •For automated reasoning engineers: Recognize that automated decision procedures for Cheq logic are impossible due to its undecidability inherited from Medvedev logic.
A theory result. No direct application yet.
Authors
Han Xiao
Abstract
We prove that $\mathsf{Cheq}$ is not finitely axiomatizable, resolving a longstanding open problem in intermediate and modal logics. We further prove that the undecidability of Medvedev logic implies the undecidability of $\mathsf{Cheq}$.