Protoalgebraic logics

There exist important deductive systems, such as the non-normal modal logics, that are not proper subjects of classical algebraic logic in the sense that their metatheory cannot be reduced to the equational metatheory of any particular class of algebras. Nevertheless, most of these systems are amenable to the methods of universal algebra when applied to the matrix models of the system. In the present paper we consider a wide class of deductive systems of this kind called protoalgebraic logics. These include almost all (non-pathological) systems of prepositional logic that have occurred in the literature. The relationship between the metatheory of a protoalgebraic logic and its matrix models is studied. The following results are obtained for any finite matrix model U of a filter-distributive protoalgebraic logic : (I) The extension _U of is finitely axiomatized (provided has only finitely many inference rules); (II) _U has only finitely many extensions.     

Relation Formulas for Protoalgebraic Equality Free Quasivarieties; Pałasińska’s Theorem Revisited

We provide a new proof of the following Pa?asińska's theorem: Every finitely generated protoalgebraic relation distributive equality free quasivariety is finitely axiomatizable. The main tool we use are ${\mathcal{Q}}$ Q -relation formulas for a protoalgebraic equality free quasivariety ${\mathcal{Q}}$ Q . They are the counterparts of the congruence formulas used for describing the generation of congruences in algebras. Having this tool in hand, we prove a finite axiomatization theorem for ${\mathcal{Q}}$ Q when it has definable principal ${\mathcal{Q}}$ Q -subrelations. This is a property obtained by carrying over the definability of principal subcongruences, invented by Baker and Wang for varieties, and which holds for finitely generated protoalgebraic relation distributive equality free quasivarieties.     

Characterizing Equivalential and Algebraizable Logics by the Leibniz Operator

In [14] we used the term finitely algebraizable for algebraizable logics in the sense of Blok and Pigozzi [2] and we introduced possibly infinitely algebraizable, for short, p.i.-algebraizable logics. In the present paper, we characterize the hierarchy of protoalgebraic, equivalential, finitely equivalential, p.i.-algebraizable, and finitely algebraizable logics by properties of the Leibniz operator. A Beth-style definability result yields that finitely equivalential and finitely algebraizable as well as equivalential and p.i.-algebraizable logics can be distinguished by injectivity of the Leibniz operator. Thus, from a characterization of equivalential logics we obtain a new short proof of the main result of [2] that a finitary logic is finitely algebraizable iff the Leibniz operator is injective and preserves unions of directed systems. It is generalized to nonfinitary logics. We characterize equivalential and, by adding injectivity, p.i.-algebraizable logics.     

Contextual Deduction Theorems

Logics that do not have a deduction-detachment theorem (briefly, a DDT) may still possess a contextual DDT??a syntactic notion introduced here for arbitrary deductive systems, along with a local variant. Substructural logics without sentential constants are natural witnesses to these phenomena. In the presence of a contextual DDT, we can still upgrade many weak completeness results to strong ones, e.g., the finite model property implies the strong finite model property. It turns out that a finitary system has a contextual DDT iff it is protoalgebraic and gives rise to a dually Brouwerian semilattice of compact deductive filters in every finitely generated algebra of the corresponding type. Any such system is filter distributive, although it may lack the filter extension property. More generally, filter distributivity and modularity are characterized for all finitary systems with a local contextual DDT, and several examples are discussed. For algebraizable logics, the well-known correspondence between the DDT and the equational definability of principal congruences is adapted to the contextual case.     

The Poset of All Logics III: Finitely Presentable Logics

Studia Logica - A logic in a finite language is said to be finitely presentable if it is axiomatized by finitely many finite rules. It is proved that binary non-indexed products of logics that are...     

Leibniz Filters Revisited

Leibniz filters play a prominent role in the theory of protoalgebraic logics. In [3] the problem of the definability of Leibniz filters is considered. Here we study the definability of Leibniz filters with parameters. The main result of the paper says that a protoalgebraic logic S has its strong version weakly algebraizable iff it has its Leibniz filters explicitly definable with parameters.     

Quasivarieties with Definable Relative Principal Subcongruences

For quasivarieties of algebras, we consider the property of having definable relative principal subcongruences, a generalization of the concepts of definable relative principal congruences and definable principal subcongruences. We prove that a quasivariety of algebras with definable relative principal subcongruences has a finite quasiequational basis if and only if the class of its relative (finitely) subdirectly irreducible algebras is strictly elementary. Since a finitely generated relatively congruence-distributive quasivariety has definable relative principal subcongruences, we get a new proof of the result due to D. Pigozzi: a finitely generated relatively congruence-distributive quasivariety has a finite quasi-equational basis. Presented by W. Dziobiak     

Concerning axiomatizability of the quasivariety generated by a finite Heyting or topological Boolean algebra

In classes of algebras such as lattices, groups, and rings, there are finite algebras which individually generate quasivarieties which are not finitely axiomatizable (see [2], [3], [8]). We show here that this kind of algebras also exist in Heyting algebras as well as in topological Boolean algebras. Moreover, we show that the lattice join of two finitely axiomatizable quasivarieties, each generated by a finite Heyting or topological Boolean algebra, respectively, need not be finitely axiomatizable. Finally, we solve problem 4 asked in Rautenberg [10].     

Not Every "Tabular" Predicate Logic is Finitely Axiomatizable

An example of finite tree Mo is presented such that its predicate logic (i.e. the intermediate predicate logic characterized by the class of all predicate Kripke frames based on Mo) is not finitely axiomatizable. Hence it is shown that the predicate analogue of de Jongh - McKay - Hosoi's theorem on the finite axiomatizability of every finite intermediate propositional logic is not true.     

Representations of monadic <Emphasis Type="Italic">MV</Emphasis> -algebras

Representations of monadic MV -algebra, the characterization of locally finite monadic MV -algebras, with axiomatization of them, definability of non-trivial monadic operators on finitely generated free MV -algebras are given. Moreover, it is shown that finitely generated m-relatively complete subalgebra of finitely generated free MV -algebra is projective.     

Finite Basis Problem for Semigroups of Order Five or Less: Generalization and Revisitation

A system of semigroup identities is hereditarily finitely based if it defines a variety all semigroups of which are finitely based. Two new types of hereditarily finitely based identity systems are presented. Two of these systems, together with eight existing systems, establish the hereditary finite basis property of every semigroup of order five or less with one possible exception.     

Linear Measurement Models-Axiomatizations and Axiomatizability

This paper examines, in the scope of representational measurement theory, different axiomatizations and axiomatizability of linear and bilinear representations of ordinal data contexts in real vector spaces. The representation theorems proved in this paper are modifications and generalizations of Scott's characterization of finite linear measurement models. The advantage of these representation theorems is that they use only finitely many axioms, the number of which depends on the size of the given ordinal data context. Concerning the axiomatizability, it is proved by model-theoretic methods that finite linear measurement models cannot be axiomatized by a finite set of first order axioms. Copyright 2000 Academic Press.     

The lattice of strengthenings of a strongly finite consequence operation

First, we prove that the lattice of all structural strengthenings of a given strongly finite consequence operation is both atomic and coatomic, it has finitely many atoms and coatoms, each coatom is strongly finite but atoms are not of this kind — we settle this by constructing a suitable counterexample. Second, we deal with the notions of hereditary: algebraicness, strong finitisticity and finite approximability of a strongly finite consequence operation. Third, we formulate some conditions which tell us when the lattice of all structural strengthenings of a given strongly finite consequence operation is finite, and subsequently we give some applications of them.This paper was read at the Third Autumn School on Strongly Finite Sentential Calculi organized by the Section of Logic, Polish Academy of Sciences, Institute of Philosophy and Sociology, in Ustronie (Poland), November 1979.     

Convergence to the Truth Without Countable Additivity

Must probabilities be countably additive? On the one hand, arguably, requiring countable additivity is too restrictive. As de Finetti pointed out, there are situations in which it is reasonable to use merely finitely additive probabilities. On the other hand, countable additivity is fruitful. It can be used to prove deep mathematical theorems that do not follow from finite additivity alone. One of the most philosophically important examples of such a result is the Bayesian convergence to the truth theorem, which says that conditional probabilities converge to 1 for true hypotheses and to 0 for false hypotheses. In view of the long-standing debate about countable additivity, it is natural to ask in what circumstances finitely additive theories deliver the same results as the countably additive theory. This paper addresses that question and initiates a systematic study of convergence to the truth in a finitely additive setting. There is also some discussion of how the formal results can be applied to ongoing debates in epistemology and the philosophy of science.

     

Multiple and iterated contraction reduced to single-step single-sentence contraction

Multiple contraction (simultaneous contraction by several sentences) and iterated contraction are investigated in the framework of specified meet contraction (s.m.c.) that is extended for this purpose. Multiple contraction is axiomatized, and so is finitely multiple contraction (contraction by a finite set of sentences). Two ways to reduce finitely multiple contraction to contraction by single sentences are introduced. The reduced operations are axiomatically characterized and their properties are investigated. Furthermore, it is shown how iterated contraction can be reduced to single-step, single-sentence contraction. However, in this framework the outcome of iterated contraction depends unavoidably on the order in which the inputs are received. This order-dependence makes it impossible to treat two inputs on an equal footing. Therefore it is often preferable to perform changes involving several pieces of information as multiple rather than iterated change.     

The Modal Logic of Bayesian Belief Revision

In Bayesian belief revision a Bayesian agent revises his prior belief by conditionalizing the prior on some evidence using Bayes’ rule. We define a hierarchy of modal logics that capture the logical features of Bayesian belief revision. Elements in the hierarchy are distinguished by the cardinality of the set of elementary propositions on which the agent’s prior is defined. Inclusions among the modal logics in the hierarchy are determined. By linking the modal logics in the hierarchy to the strongest modal companion of Medvedev’s logic of finite problems it is shown that the modal logic of belief revision determined by probabilities on a finite set of elementary propositions is not finitely axiomatizable.

     

Hobson’s Conception of Definable Numbers

In this paper, I explore an intriguing view of definable numbers proposed by a Cambridge mathematician Ernest Hobson, and his solution to the paradoxes of definability. Reflecting on König’s paradox and Richard’s paradox, Hobson argues that an unacceptable consequence of the paradoxes of definability is that there are numbers that are inherently incapable of finite definition. Contrast to other interpreters, Hobson analyses the problem of the paradoxes of definability lies in a dichotomy between finitely definable numbers and not finitely definable numbers. To bypass this predicament, Hobson proposes a language dependent analysis of definable numbers, where the diagonal argument is employed as a means to generate more and more definable numbers. This paper examines Hobson’s work in its historical context, and articulates his argument in detail. It concludes with a remark on Hobson’s analysis of definability and Alan Turing’s analysis of computability.     

Projective Beth Property in Extensions of Grzegorczyk Logic

All extensions of the modal Grzegorczyk logic Grz possessing projective Beth's property PB2 are described. It is proved that there are exactly 13 logics over Grz with PB2. All of them are finitely axiomatizable and have the finite model property. It is shown that PB2 is strongly decidable over Grz, i.e. there is an algorithm which, for any finite system Rul of additional axiom schemes and rules of inference, decides if the calculus Grz+Rul has the projective Beth property. Dedicated to the memory of Willem Johannes Blok     

On detachment-substitutional formalization in normal modal logics

The aim of this paper is to propose a criterion of finite detachment-substitutional formalization for normal modal systems. The criterion will comprise only those normal modal systems which are finitely axiomatizable by means of the substitution, detachment for material implication and Gödel rules.Some results of this paper were announced in the abstract [2].Allatum est die 10 Junii 1976     

Finite condensations of recursive linear orders

The complexity of aII ₄ set of natural numbers is encoded into a linear order to show that the finite condensation of a recursive linear order can beII ₂–II ₁. A priority argument establishes the same result, and is extended to a complete classification of finite condensations iterated finitely many times.