G. Sági

NON-COMPUTABILITY OF THE CONSEQUENCES OF THE AXIOMS OF THE OMEGA DIMENSIONAL POLYADIC ALGEBRAS

Abstract: Daigneault and Monk proved that the class of (omega dimensional) representable polyadic algebras (RPA_{\omega} for short) is axiomatizable by finitely many equation-schemas. However, this result does not imply that the equational theory of RPA_{\omega} would be recursively enumerable; one simple reason is that the language of RPA_{\omega} consists of continuum many operation symbols. Here we prove the following. Roughtly, for any reasonable generalization of computability to continuum large languages, the equational theory of RPA_{\omega} remains non-recursively enumerable, or non-enumerable in the generalized sense too. This will be seen to be an "intuitive" consequence of the following more formal statement. There is a strictly finite reduct L of the language of RPA_{\omega}, such that the following set of equations is not recursively enumerable:

{e: e is an equation written in the language L and derivable from the (PA_{\omega} axioms.}

Moreover, the indices of the substitutions and cylindrifications occouring in L are recursive functions and sets, respectively.


Retrieve dvi or PostScript version.