© 2000 by Oxford University Press
On the search for a finitizable algebraization of first order logic
Algréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, PF. 127, H-1364, Hungary E-mail: sain@renyi.hu
We give an algebraic version of first order logic without equality in which the class of representable algebras forms a finitely based equational class. Further, the representables are defined in terms of set algebras, and all operations of the latter are permutation invariant. The algebraic form of this result is Theorem 1.1 (a concrete version of which is given by Theorems 2.8 and 4.2), while its logical form is Corollary 5.2.
For first order logic with equality we give a result weaker than the one for first order logic without equality. Namely, in this case - instead of finitely axiomatizing the corresponding class of all representable algebras - we finitely axiomatize only the equational theory of that class. Subsection 6.1, especially Remark 6.6 there.
The proof of Theorem 1.1 is elaborated in Sections 3 and 4. These sections contain theorems which are interesting of their own rights, too, e.g. Theorem 4.2 is a purely semigroup theoretic result. Cf. also 'Further main results' in the Introduction.
Key Words: Algebraic logic, finitization problem, representation problem, finite axiomatization, completeness problem, ultraproducts, formula schemes, cylindric algebras, polyadic algebras, algebras of relations, finite presentation of semigroups of relations.