home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / logic / 2079 < prev    next >
Encoding:
Text File  |  1992-11-17  |  1.9 KB  |  62 lines
  1. Newsgroups: sci.logic
  2. Path: sparky!uunet!destroyer!sol.ctr.columbia.edu!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!wjcastre
  3. From: wjcastre@magnus.acs.ohio-state.edu (W.Jose Castrellon G.)
  4. Subject: Re: Why invalid?
  5. Message-ID: <1992Nov18.002216.15277@magnus.acs.ohio-state.edu>
  6. Summary: Solution 
  7. Sender: news@magnus.acs.ohio-state.edu
  8. Nntp-Posting-Host: bottom.magnus.acs.ohio-state.edu
  9. Organization: The Ohio State University,Math.Dept.(studnt)
  10. References: <1992Nov16.091653.1@woods.ulowell.edu> <lgfubaINN7v@peaches.cs.utexas.edu> <1992Nov17.164246.18220@uklirb.informatik.uni-kl.de>
  11. Date: Wed, 18 Nov 1992 00:22:16 GMT
  12. Lines: 48
  13.  
  14. In article <1992Nov17.164246.18220@uklirb.informatik.uni-kl.de> ayala@uklirb.informatik.uni-kl.de (Mauricio Ayala R.) writes:
  15.  
  16. >Can anyone give me a counterexample of the following:
  17. >
  18. >Let T a consistent first order theory with equality which
  19. >decidable set of quatifier-free logical consequences:
  20. >
  21. >  QF(T) = { B  |   t |= B, B quantifier-free }
  22. >
  23. >Let A be a T-consistent quantifier-free formula.
  24. >Then (T,A) is also a consistent first order logic with
  25. >equality and QF(T,A) is ALSO DECIDABLE.
  26. >
  27. >M. Ayala
  28. >Universitaet Kaiserslautern
  29. >FRG
  30. >ayala@informatik.uni-kl.de
  31. >
  32.  
  33. Solution follows.
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44. Take the theory over the language with one constant  0 , one function  f(x) ,
  45. one unary predicate  P(x), and a binary relation  R(x,y), as follows:
  46.  
  47. For all  x  R(0,f(x))
  48. R(0,0)
  49. and for each  n  in a non-recursive r.e. set, the axioms:
  50.  
  51. [ There exists an  x  such that  not R(0,x) ]  -->  [ P(n) ]
  52.  
  53. (where  n  is the abbreviation of  f(x)  applied  n  times to  0 )
  54.  
  55. Then one can check that the set of quantifier free sentences that are logical
  56. consequences of this axioms is recursive.
  57.  
  58. However if one expands the language with one more constant  c , and add the
  59. sentence   not R(0,c), then that set becomes non-recursive.  [if you dont allow
  60. an expansion of the language, then it can be shown that there is no counter-
  61. example].
  62.