Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-18T17:53:14.250Z Has data issue: false hasContentIssue false

A HENKIN-STYLE PROOF OF COMPLETENESS FOR FIRST-ORDER ALGEBRAIZABLE LOGICS

Published online by Cambridge University Press:  13 March 2015

PETR CINTULA
Affiliation:
INSTITUTE OF COMPUTER SCIENCE, ACADEMY OF SCIENCES OF THE CZECH REPUBLIC, POD VODÁRENSKOU VĚŽÍ 2, 182 07 PRAGUE, CZECH REPUBLICE-mail:cintula@cs.cas.czURL:http://www.cs.cas.cz/cintula
CARLES NOGUERA
Affiliation:
INSTITUTE OF INFORMATION THEORY AND AUTOMATION, ACADEMY OF SCIENCES OF THE CZECH REPUBLIC, POD VODÁRENSKOU VĚŽÍ 4, 182 08 PRAGUE, CZECH REPUBLICE-mail:noguera@utia.cas.czURL:http://www.carlesnoguera.cat
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

This paper considers Henkin’s proof of completeness of classical first-order logic and extends its scope to the realm of algebraizable logics in the sense of Blok and Pigozzi. Given a propositional logic L (for which we only need to assume that it has an algebraic semantics and a suitable disjunction) we axiomatize two natural first-order extensions L∀m and L∀ and prove that the former is complete with respect to all models over algebras from , while the latter is complete with respect to all models over relatively finitely subdirectly irreducible algebras. While the first completeness result is relatively straightforward, the second requires non-trivial modifications of Henkin’s proof by making use of the disjunction connective. As a byproduct, we also obtain a form of Skolemization provided that the algebraic semantics admits regular completions. The relatively modest assumptions on the propositional side allow for a wide generalization of previous approaches by Rasiowa, Sikorski, Hájek, Horn, and others and help to illuminate the “essentially first-order” steps in the classical Henkin’s proof.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2015