##
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.