×

What the finitization problem is not. (English) Zbl 0797.03063

Rauszer, Cecylia (ed.), Algebraic methods in logic and in computer science. Papers of the XXXVIII semester on algebraic methods in logic and their computer science applications held in Warsaw (Poland) between September 15 and December 15, 1991. Warsaw: Polish Academy of Sciences, Institute of Mathematics. Banach Cent. Publ. 28, 95-116 (1993).
The ‘finitization problem’ is one of the open problems posed by L. Henkin and J. D. Monk [Proc. Tarski Symp., Proc. Symp. Pure Math. 25, 105-121 (1974; Zbl 0307.02041)] that “are of a programmatic nature and are not precisely formulated”:
Problem 1. Devise an algebraic version of predicate logic in which the class of representable algebras forms a finitely based equational class.
This problem was motivated by the fact that many equational classes of algebras associated with first-order logic are not finitely axiomatizable. Such results, according to J. D. Monk [J. Symb. Log. 35, 19-28 (1970; Zbl 0196.010)]:
“contribute to the conjecture that no equational form of first-order logic is finitely axiomatizable – more precisely, with respect to any conception \(\mathcal S\) of a set algebra (corresponding to the notion of satisfaction), and any choice of basic operations, the corresponding class \({\mathcal S}'\) is not finitely axiomatizable. It appears difficult to give this conjecture a precise form, since there is a wide latitude of choice with regard to the fundamental operations as well as the kinds of sequences considered for the satisfaction relation.”
Using standard techniques and results from model theory and cylindric algebra theory, the author constructs a finitely based equational class SCA, a computable function \(F\) (mapping formulas \(\varphi\) in a first- order language \(L\) to SCA-equations), and a function Alg (mapping models \(\mathfrak M\) of \(L\) to algebras in SCA) such that \({\mathfrak M}\models \varphi\) iff \(\text{Alg}({\mathfrak M})\models F(\varphi)\), and more. While acknowledging that such results were already proved (for a different finitely based equational class) in Theorems 21-23 of the reviewer [Z. Math. Logik Grundlagen Math. 35, 321-332 (1989; Zbl 0661.03052), Math. Log. Quart. 39, 566-569 (1993)], the author uses the details of the construction of SCA, \(F\), and Alg to argue that such results should not be regarded as solutions of Problem 1. Two reasons are given: the construction is too easy, and there are subdirectly irreducible algebras in SCA that do not have the form \(\text{Alg}({\mathfrak M})\). Some more detailed versions and variations of Problem 1 are also formulated.
For the entire collection see [Zbl 0777.00048].
Reviewer: R.Maddux (Ames)

MSC:

03G15 Cylindric and polyadic algebras; relation algebras
03B99 General logic
03C99 Model theory
03C75 Other infinitary logic
PDFBibTeX XMLCite