home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / logic / 2454 < prev    next >
Encoding:
Internet Message Format  |  1992-12-14  |  1.7 KB
  1. Path: sparky!uunet!pipex!warwick!uknet!edcastle!dcs.ed.ac.uk!alti
  2. From: alti@dcs.ed.ac.uk (Thorsten Altenkirch)
  3. Newsgroups: sci.logic
  4. Subject: Re: decidable group theory
  5. Message-ID: <ALTI.92Dec14145206@campay.dcs.ed.ac.uk>
  6. Date: 14 Dec 92 14:52:06 GMT
  7. References: <19921208.075322039663.NETNEWS@ALIJKU11> <1g282rINN5ja@eagle.dfki.uni-sb.de>
  8. Sender: cnews@dcs.ed.ac.uk (UseNet News Admin)
  9. Organization: LFCS, Edinburgh
  10. Lines: 38
  11. In-Reply-To: treinen@dfki.uni-sb.de's message of 8 Dec 92 13:31:07 GMT
  12.  
  13. In article <1g282rINN5ja@eagle.dfki.uni-sb.de> treinen@dfki.uni-sb.de (Ralf Treinen) writes:
  14.  
  15.    In article <19921208.075322039663.NETNEWS@ALIJKU11>, groda@risc.uni-linz.ac.at (Giovanna Roda) writes:
  16.    |> Suppose we are given an axiomatization for the theory of groups consisting
  17.    |> of the following three axioms:
  18.    |> (x*y)*z=x*(y*z)
  19.    |> Vy x=y*z
  20.    |> Vz x=y*z
  21.    |> (where V is the existential quantifier).
  22.    |> Is this theory decidable?
  23.  
  24.    No. This has been proven in
  25.  
  26.    @InCollection{Tar:groups53,
  27.    author    = "Alfred Tarski",
  28.    title    = "Undecidability in the Elementary Theory of Groups",
  29.    pages    = "75--87",
  30.    crossref= "TMR:Undecidable53"
  31.    }
  32.  
  33. No I am slightly confused. Am I wrong remembering that the followoing
  34. presentation of groups
  35.  
  36.     (x*y)*z=x*(y*z)
  37.     x*e = x
  38.     e*x = x
  39.     i(x)*x = e
  40.     x*i(x) = e
  41.  
  42. could be completed using the Knuth-Bendix algorithm & therefore is
  43. decidable. How does this relate to the above mentioned result?
  44.  
  45. --
  46.  
  47.  Thorsten Altenkirch             And there's a hand, my trusty fiere,
  48.  Laboratory for Foundations         And gie's a hand o' thine,
  49.  of Computer Science               And we'll tak a right guid-willie waught
  50.  University of Edinburgh            For auld lang syne!
  51.