A computational glimpse at the Leibniz and Frege hierarchies

2019/08/01 by Tommaso Moraschini, Moraschini, T.
Computer Science · #Advanced Algebra and Logic #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.1908.00922

openalex publication_date 2019/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we consider, from a computational point of view, the problem of classifying logics within the Leibniz and Frege hierarchies typical of abstract algebraic logic. The main result states that, for logics presented syntactically, this problem is in general undecidable. More precisely, we show that there is no algorithm that classifies the logic of a finite consistent Hilbert calculus in the Leibniz and in the Frege hierarchies.

Related

• On the complexity of the Leibniz hierarchy
• Finite axiomatizability of logics of distributive lattices with negation
• Algebraic logic for the negation fragment of classical logic
• Algebraic classifications for fragments of first-order logic and beyond
• Proofs of valid categorical syllogisms in one diagrammatic and two symbolic axiomatic systems