home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17577 < prev    next >
Encoding:
Internet Message Format  |  1993-01-01  |  3.8 KB
  1. Xref: sparky sci.math:17577 comp.theory:2778 sci.logic:2526
  2. Path: sparky!uunet!think.com!hsdndev!husc-news.harvard.edu!scws7.harvard.edu!zeleny
  3. From: zeleny@scws7.harvard.edu (Michael Zeleny)
  4. Newsgroups: sci.math,comp.theory,sci.logic
  5. Subject: Self-Reference and Coding
  6. Message-ID: <1993Jan1.122745.18924@husc3.harvard.edu>
  7. Date: 1 Jan 93 17:27:44 GMT
  8. Organization: The Phallogocentric Cabal
  9. Lines: 60
  10. Nntp-Posting-Host: scws7.harvard.edu
  11.  
  12. Consider a formula in the language of Robinson Arithmetic.  Ask the
  13. question whether it is self-referential, in the sense of containing a
  14. term which encodes it via some scheme of G\"odel numbering.  To what
  15. extent can this question be answered, effectively or otherwise?
  16.  
  17. Motivation: assume a compositional intensional semantics, i.e. an
  18. ontology of concepts for all constants and formulae.  The fundamental
  19. rule is that the concept of a formula is an appropriate function on
  20. the concepts of its terms.  Example: for $1+1=2$ (pardon my TeX, --
  21. the dollar sign is a math delimiter), have the concept $1_1 +_1 1_1
  22. =_1 2_1$, where the subscript 1 indicates the first concept of each
  23. thing, whether individual, function, or relation.  Agree to omit
  24. subscripts from function and relation constants, -- they can be
  25. restored from the context.  We say that terms and formulae express
  26. their concepts; the concept of a formula is also called a proposition.
  27.  
  28. Define a relation of synonymy, which partitions the concepts into
  29. equivalence classes, and induces a Lindenbaum algebra of the
  30. corresponding sentences, to be that of logical equivalence.  (This is
  31. Church's Alternative (2); another notion of synonymy is given by the
  32. Alternative (1), which takes \lambda-convertibility as its definition.
  33. Since the language is typed, the latter relation is decidable.)  So,
  34. for instance, $1_1+1_1$ is synonymous with $2_1$ as concepts of the
  35. integer 2.  Unfortunately, this means that the synonymy relation is
  36. undecidable, inasmuch as our language may allow us to express the same
  37. concept via such rocky roads as the Goldbach conjecture or Fermat's
  38. last theorem.
  39.  
  40. Now, to exclude G\"odel-type sentences, I stipulate that a necessary
  41. condition for a concept to be meaningful, is that it not contain any
  42. well-formed constituents synonymous with itself.  Note that this is
  43. precisely the intensional analogue of the set-theoretic Axiom of
  44. Foundation, which ensures that all meaningful concepts may be assigned
  45. a rank in the cumulative hierarchy of concepts. Thus, in particular,
  46. the sentences $\psi$, for which $$\psi \equiv \neg \mbox{Pr}_{\cal
  47. Q}(\lceil \psi \rceil),$$ (incidentally, what is the proper AMS LaTeX
  48. symbol for corner quotes?) that is, such that they are materially
  49. equivalent to the sentence denying the provability in Robinson
  50. arithmetic of the sentence with their G\"odel number, are deemed
  51. meaningless.  Since nothing depends on the negation, the L\"ob
  52. sentences, which assert their own provability, are likewise excluded.
  53. All meaningless sentences (i.e. ones not expressing a meaningful
  54. concept) are regarded as bereft of truth-values.  All formal proofs
  55. are required to be valid, i.e to contain only meaningful formulae.
  56. Now say that synonymy is *provable* logical equivalence, and
  57. reconstrue the above accordingly.
  58.  
  59. In accordance with the above considerations, this means that
  60. meaningfulness is not an effectively decidable notion.  (Gerald Sacks
  61. says that Church tried what sounds like a similar approach towards
  62. analyzing G\"odel's results.  I am unaware of any published work, so
  63. references would be greatly appreciated.)  However, it appears to be
  64. semi-decidable.  What else can be said about this notion?
  65.  
  66. Happy New Year to all.
  67.  
  68. cordially,
  69. mikhail zeleny@husc.harvard.edu
  70. "Les beaulx bastisseurs nouveaulx de pierres mortes ne sont escriptz
  71. en mon livre de vie.  Je ne bastis que pierres vives: ce sont hommes."
  72.