On varieties of cylindric algebras with applications to logic
type: Item
instance of: scholarly article
title: On varieties of cylindric algebras with applications to logic
zbMATH Open document ID: 0637.03062
DOI: 10.1016/0168-0072(87)90019-4
published in: Annals of Pure and Applied Logic
publication date: 1987-01-01T00:00:00Z
review text: Some interesting decidability and undecidability results are proved. They have to do with cylindric versions of logic with equality only, or with only monadic predicates. In ordinary first order logic the theories in question are among the simplest decidable theories known. Their cylindric versions turn out to be mostly undecidable; this is the main import of this interesting article. The exact logical counterparts of the cylindric apparatus is carefully formualated in this article, so that the reason behind this paradoxical sounding situation becomes clear. The main results are: (1) The equational theory of minimal \(CA_{\alpha}s\) is r.e. iff \(\alpha\geq \omega\). (2) The equational theory of monadic- generated \(CA_{\alpha}s\) is r.e. iff \(\alpha >2\). For the rest, let \(\alpha >2\) and let K be a class of monadic-generated \(CA_{\alpha}s\). (3) The equational theory of K is either decidable or not r.e. (4) For \(\alpha\) infinite, the equational theory of K is decidable iff there is an \(n\in \omega\) such that all set algebras in K have base of size at most n. (5) For \(\alpha <\omega\), the equational theory of K is decidable iff there is an \(n\in \omega\) such that \(K\subseteq SPL\), where L is the class of all monadic-generated \(CA_{\alpha}s\) generated by at most n 1- dimensional elements. Several other interesting results are proved, too. It is interesting that the unsolvability of diophantine equations plays a role in the proofs.
reviewed by: J. Donald Monk
Mathematics Subject Classification ID: 03G15
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D35
zbMATH DE Number: 4037864
zbMATH Keywords: cylindric algebra
zbMATH Keywords: minimal algebra
zbMATH Keywords: monadic-generated algebra
zbMATH Keywords: decidability
zbMATH Keywords: undecidability
zbMATH Keywords: cylindric versions of logic with equality
zbMATH Keywords: monadic predicates
author: István Németi
MaRDI profile type: Publication
full work available at URL: 0168-0072(87)90019-4
OpenAlex ID: W2054137194
cites work: Q3340129
cites work: The lattice of varieties of modal algebras is not strongly atomic
cites work: The lattice of modal logics: an algebraic investigation
cites work: Q4029628
cites work: Finite inseparability of some theories of cylindrification algebras
cites work: The Gödel class with identity is unsolvable
cites work: Q5549024
cites work: Q5681997
cites work: Q5616133
cites work: Cylindric set algebras. Cylindric set algebras and related structures. By L. Henkin, J. D. Monk, and A. Tarski. On cylindric-relativized set algebras. By H. Andreka and I. Nemeti
cites work: Axiom systems for first order logic with finitely many variables
cites work: Varieties of relation algebras
cites work: The equational theory of CA3 is undecidable
cites work: Some sufficient conditions for the representability of relation algebras
cites work: A sequent calculus for relation algebras
cites work: Nonfinite axiomatizability results for cylindric and relation algebras
cites work: Q5682023
cites work: Singularly Cylindric and Polyadic Equality Algebras
cites work: Nonfinitizability of classes of representable cylindric algebras
cites work: Completions of B<scp>OOLEAN</scp> Algebras with operators
cites work: Provability with Finitely Many Variables
cites work: Q4124795
cites work: Cylindric-relativised set algebras have strong amalgamation
cites work: Deux ou trois choses que je sais de Ln
cites work: Q4124831
cites work: An undecidability result for relation algebras
cites work: Q4040000
description: scientific article; zbMATH DE number 4037864