home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / logic / 1232 < prev    next >
Encoding:
Internet Message Format  |  1992-07-22  |  1.4 KB
  1. Path: sparky!uunet!mcsun!corton!cenaath.cena.dgac.fr!geant!alliot
  2. From: alliot@cenatls.cena.dgac.fr (Jean-Marc Alliot)
  3. Newsgroups: sci.logic
  4. Subject: Equivalence of Strong completeness and categoricity
  5. Message-ID: <1992Jul22.205827.16651@cenatls.cena.dgac.fr>
  6. Date: 22 Jul 92 20:58:27 GMT
  7. Sender: news@cenatls.cena.dgac.fr
  8. Organization: Centre d'Etudes de la Navigation Aerienne, Toulouse, France
  9. Lines: 30
  10.  
  11.  
  12. This question is perhaps trivial but...
  13.  
  14. I am first going to give the definition I am using, since many people
  15. use the same words for different things: 
  16.  
  17. Consistency: A system is consistent if, for any wff F, we
  18. can not have at the same time (F is a theorem) and (not F is a
  19. theorem). 
  20.  
  21. Categoricity: a system is categoric if, for any wff F, we have either
  22. (F is theorem) or (not F is a theorem).
  23.  
  24. Strong completeness: a system based on a set S of axioms is strongly
  25. complete if for any wff F, we have either (F is a theorem) or (F added
  26. to S is an inconsistent system).
  27.  
  28.  
  29. Now the questions:
  30.  
  31. 1) It seems quite clear that in any system which is a superset of
  32. propositional calculus Categoricity and Strong completeness are
  33. equivalent. However a short and clear demonstration would be very much
  34. welcome.
  35.  
  36. 2) Does the property hold in the general case (I especially think of
  37. intuitionist logic) ?
  38.  
  39. If the question is too trivial, a reference to a book giving the
  40. answers would be also welcome.
  41.