[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