home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17408 < prev    next >
Encoding:
Internet Message Format  |  1992-12-24  |  3.3 KB
  1. Xref: sparky sci.math:17408 sci.logic:2480
  2. Path: sparky!uunet!think.com!hsdndev!husc-news.harvard.edu!husc10.harvard.edu!zeleny
  3. From: zeleny@husc10.harvard.edu (Michael Zeleny)
  4. Newsgroups: sci.math,sci.logic
  5. Subject: Re: The Continuum Hypothesis:  Must it be {True or False}
  6. Message-ID: <1992Dec24.233312.18834@husc3.harvard.edu>
  7. Date: 25 Dec 92 04:33:11 GMT
  8. References: <1992Dec14.200024.6435@nas.nasa.gov> <1992Dec24.034938.11339@smsc.sony.com> <1992Dec24.161747.18827@husc3.harvard.edu>
  9. Organization: The Phallogocentric Cabal
  10. Lines: 48
  11. Nntp-Posting-Host: husc10.harvard.edu
  12.  
  13. In article <1992Dec24.161747.18827@husc3.harvard.edu> I wrote:
  14.  
  15. >FLT is a \Pi^0_1 sentence.  In any first-order, or otherwise complete
  16. >theory, undecidability of a \Pi^0_1 sentence requires that it be false
  17. >in some models of the theory, but true in others; for otherwise by
  18. >semantic completeness it would have been provable or refutable,
  19. >according as it were valid or contradictory.  The question of truth
  20. >reduces to whether the sentence can be false in a standard model, --
  21. >iff not, it is by definition true.  Now, by Tarski's definition of
  22. >satisfaction, falsehood in the models of the theory depends on the
  23. >existence therein of a witness set for the \Sigma^0_1 negation of the
  24. >original sentence; but in case of an arithmetical sentence, these
  25. >witnesses must be the integers.  If they are standard integers, then
  26. >they have names in the language of the theory, and therefore the
  27. >original sentence receives an explicit refutation in the latter, in
  28. >contradiction to the hypothesis of undecidability.  On the other hand,
  29. >if all the witnesses in all the relevant models are *non-standard*
  30. >integers, then _a fortiori_ the proposition in question is true in all
  31. >standard models, and so true _simpliciter_, albeit not valid. Hence,
  32. >if a \Pi^0_1 sentence is undecidable in a semantically complete theory
  33. >of Peano Arithmetic, wherein provability is coincident with validity,
  34. >then it is _ipso facto_ true.
  35. >
  36. >On the other hand, in second-order PA, all models are standard by
  37. >categoricity; in other words, the adoption of a full strength
  38. >induction axiom allows us to characterize the integers up to
  39. >isomorphism.  But then the completeness argument, as distinct from
  40. >soundness alone, is likewise inapplicable for standard second-order
  41. >semantics.  (All we can get is that undecidability in second-order PA
  42. >entails falsehood in a faithful (satisfying AC and every instance of
  43. >comprehension) Henkin model.  Henkin semantics is non-categorical, and
  44. >generally is equivalent to the case of many-sorted first-order logic,
  45. >so I think that the first-order situation is recapitulated in this
  46. >case.)  But the moral of this story is that there is a critical
  47. >difference between undecidability in a first-order theory, which by
  48. >L\"owenheim-Skolem theorems cannot characterize infinite structures up
  49. >to isomorphism, and a higher-order theory, which can do so.
  50.  
  51. To continue, suppose a \Pi^0_1 sentence is undecidable in second-order
  52. PA; suppose further that it is not valid, i.e. there is a model of
  53. second-order PA,in which it is false.  By categoricity, such a model
  54. would contain standard integer witnesses to its negation, which could
  55. be used in an explicit refutation of the sentence in question.
  56. Contradiction.
  57.  
  58. cordially,
  59. mikhail zeleny@husc.harvard.edu
  60. "Nothing can be said truly of what does not exist."
  61.