[FOM] Identities

Dana Scott dana.scott at cs.cmu.edu
Sun Jan 21 13:03:28 EST 2007


Take any equational theory with an unsolvable word
problem (e.g., monoids, groups, rings, lattices).

Then take as identities the axioms of the theory plus
a number of equations between constants (i.e., thinking
of generators and relations).

Hence, the problem of deducing another equation (without
variables, a special kind of identity) is exactly the
original word problem for the theory.



More information about the FOM mailing list