NON-COMPUTABILITY OF THE EQUATIONAL THEORY OF POLYADIC ALGEBRAS
Gábor Sági · 2001
In [3] Daigneault and Monk proved that the class of (! dimensional) representable polyadic algebras (RPA! for short) is axiomatizable by finitely many equationschemas. However, this result does not imply that the equational theory of RPA! would be recursively enumerable; one simple reason is that the language of RPA! contains a continuum of operation symbols. Here we prove the following. Roughly, for any reasonable generalization of computability to uncountable languages, the equational theory of RPA! remains non-recursively enumerable, or non-computable, in the generalized sense. This result has some implications on the non-computational character of Keisler’s completeness theorem for his “infinitary logic” in Keisler [6] as well.