[FOM] identities
Insall, Matt
insall at umr.edu
Mon Jan 22 14:36:25 EST 2007
George McNulty read my earlier post to fom, and set me straight. :-}
With his permission, I am passing on his comments:
>
> I just read your message to fom in response to the question of
> Martin Davis. Here is my understanding of the situation.
>
> 0. It is a consequence of the 1948 construction
> of Post and Markov of a finitely presented
> semigroup with an unsolvable word problem
> that there is a finite set of identities
> using finitely many (actually 2 will serve)
> one-palce operation symbols and only one
> variable such that the one-varialbe identities
> which are logical consequence of the finite
> set comprise a nonrecursive set of identities.
>
> 1. Subsequently many undecidable equational theories
> (i.e. sets of identities closed under logical
> consequence) have been discovered. For example,
> Ralph Freese showed that the equational theory of
> modular lattices is undecidable.
>
> 2. In the McKenzie-Valierote monograph the subject
> is the full first-order theory, not the equational
> theory. Of course, if the first-order theory of
> the variety is decidable then so is the equational
> theory. But the equational theory of the variety
> may be decidable even when the first-order theory
> is undecidable. An example is the variety of all
> groups. Tarski, I think, showed this theory undecidable,
> but later, as a consequence of the work of Boone and
> Novikov, we even know that the universal Horn theory
> of the variety of groups is undecidable. Nevertheless,
> Max Dehn showed around 1910 that the equational
> theory of groups is decidable.
>
> Best Regards,
>
> George McNulty
>
>
Dr. Matt Insall
Associate Professor of Mathematics
Department of Mathematics and Statistics
University of Missouri - Rolla
Rolla MO 65409-0020
(573)341-4901
insall at umr.edu
More information about the FOM
mailing list