Elementary theories of generic multialgebras (Q1589022)

An \(n\)-ary multifunction \(f\) on a set \(A\) is a map \(f: A^n\to P(A)\), where \(P(A)\) is the power set of \(A\). Let \(A\) be the underlying set of a universal algebra \(\mathcal A\) and, for any \(X\subseteq A\), let \(\langle X\rangle\) denote the underlying set of the subalgebra generated by \(X\). Let \(p_0\) denote the multifunction defined by \(p_0(a)=a\) and, for \(n=1,2,\dots\), let \(p_n\) be the \(n\)-ary multifunction defined by \(p_n(a_1,\dots,a_n)=\langle\{a_1,\dots,a_n\}\rangle\). Then the generic multialgebra \(G({\mathcal A})\) is the algebra on \(A\) with set of multifunctions \(\{p_0,p_1,\dots\}\). If \(\mathcal A\) belongs to a class of algebras \(\mathcal K\), then \(G({\mathcal K})=\{G({\mathcal A})\mid {\mathcal A}\in {\mathcal K}\}\). This paper shows that the elementary theory of the class of all generic multialgebras is undecidable. The class \(G({\mathcal K})\) is not axiomatizable unless \(\mathcal K\) is a locally finite axiomatizable class of universal algebras with at most countable signature. If \(\mathcal K\) is a locally finite universal class of universal algebras of finite signature, then \(G({\mathcal K})\) is axiomatizable.