A computational glimpse at the Leibniz and Frege hierarchies

DOI10.1016/J.APAL.2017.07.003MaRDI QIDQ1676326zbMATH OpenOpenAlexWikidataFDO

Authors Tommaso Moraschini

Publication date 6 November 2017

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

abstract algebraic logicdecidabilityDiophantine equationFrege hierarchyLeibniz congruenceLeibniz hierarchyrelation algebra

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Other nonclassical logic (03B60) Cylindric and polyadic algebras; relation algebras (03G15) Abstract algebraic logic (03G27) Diophantine equations (11D99)

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.

Review text

The author deals with the following problem: is it possible to decide whether the logic of a given finite consistent Hilbert calculus in a finite language belongs to a given level of the Leibniz or Frege hierarchy? In the first case, the Hilbert's tenth problem (on Diophantine equations) is reduced to the problem of classifying such a logic in the Leibniz hierarchy. In the second case, the author relies on the undecidability of the equational theory of relation algebras in a single variable. Thus, for both hierarchies the problem is generally undecidable. Moreover, the problem is shown to remain undecidable when restricted to the classification, within the Frege hierarchy, of finite consistent Hilbert calculi that determine a finitely algebraizable logic.

Recommendations

• On the complexity of the Leibniz hierarchy
• Computable structures and the hyperarithmetical hierarchy
• Grzegorczyk's hierarchy of computable analysis
• Three roots for Leibniz's contribution to the computational conception of reason
• The predicative Frege hierarchy
• scientific article; zbMATH DE number 1337625
• Logic, computation, hierarchies. Dedicated to Victor L. Selivanov on the occasion of his 60th birthday
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• scientific article; zbMATH DE number 4118351
• Exploring Computational Contents of Intuitionist Proofs

Cites work

• A note on congruences of semilattices with sectionally finite height.
• A survey of abstract algebraic logic
• Abstract algebraic logic. An introductory textbook
• Algebraic characterizations of various Beth definability properties
• Algebraizable logics
• Epimorphisms in varieties of residuated structures
• Fregean logics with the multiterm deduction theorem and their algebraization
• scientific article; zbMATH DE number 2184446 (Why is no real title available?)
• scientific article; zbMATH DE number 1003731 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 193143 (Why is no real title available?)
• scientific article; zbMATH DE number 3559512 (Why is no real title available?)
• scientific article; zbMATH DE number 3625380 (Why is no real title available?)
• scientific article; zbMATH DE number 1302498 (Why is no real title available?)
• scientific article; zbMATH DE number 545277 (Why is no real title available?)
• scientific article; zbMATH DE number 2068678 (Why is no real title available?)
• scientific article; zbMATH DE number 945663 (Why is no real title available?)
• scientific article; zbMATH DE number 2196609 (Why is no real title available?)
• scientific article; zbMATH DE number 3321276 (Why is no real title available?)
• Logics of varieties, logics of semilattices and conjunction
• Protoalgebraic logics
• The Beth property in algebraic logic
• Theory of logical calculi. Basic theory of consequence operations

Cited in

(6)

• On the complexity of the Leibniz hierarchy
• A study of truth predicates in matrix semantics
• Assertional logics, truth-equational logics, and the hierarchies of abstract algebraic logic
• ON EQUATIONAL COMPLETENESS THEOREMS
• THE POSET OF ALL LOGICS II: LEIBNIZ CLASSES AND HIERARCHY
• Abstract algebraic logic. An introductory chapter

This page was built for publication: A computational glimpse at the Leibniz and Frege hierarchies

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