home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / logic / 2131 < prev    next >
Encoding:
Text File  |  1992-11-20  |  2.2 KB  |  55 lines
  1. Newsgroups: sci.logic
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!bcm!tamsun.tamu.edu!cmenzel
  3. From: cmenzel@tamsun.tamu.edu (Chris Menzel)
  4. Subject: Re: recursive definitions and paradoxes
  5. Message-ID: <1992Nov20.210803.5903@tamsun.tamu.edu>
  6. Organization: Texas A&M University, College Station
  7. References: <26788@optima.cs.arizona.edu>
  8. Date: Fri, 20 Nov 1992 21:08:03 GMT
  9. Lines: 44
  10.  
  11. In article <26788@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
  12. >A "recursive definition" of a name X is a sentence of the form
  13. >
  14. >  X := E
  15. >
  16. >where E is an expression that contains X as a free variable.  Naively we
  17. >might associate with such definitions the axiom
  18. >
  19. >  X := E => X = E
  20. >
  21. >To express what a definition means.  (We also need some syntactic rules
  22. >to allow the introduction of definitions so that the same name is not
  23. >used for different purposes.)
  24. >
  25. >Here are some examples of recursive definitions:
  26. >
  27. >(1) x := x + 1
  28. >(2) x := x * 2
  29. >(3) x := 1/x
  30. >(4) x := x * 1
  31.  
  32. It seems to me, David, that you cause unnecessary confusion by calling
  33. these and, as you do later in your post, the definition of the Russell
  34. set recursive definitions.  By my lights, the usual understanding is
  35. that a recursive definition is one in which a function f is defined on
  36. a well-founded relation R such that for each object b in the field of
  37. R, f(b) is defined in terms of f(x) for x such that xRb.  (The
  38. legitimacy of such definitions in set theory is of course a theorem to
  39. be proved; I believe von Neumann was both the first to see this and
  40. the first to provide the requisite proof.  Levy's Basic Set Theory
  41. has a nice, detailed proof in ZF.)  Unless I'm really missing
  42. something, the above are not recursive definitions in this sense, nor
  43. is the definition of the Russell set.
  44.  
  45. Since you say at the beginning of your note what *you* mean by a
  46. recursive definition, my comment here is essentially a quibble that
  47. doesn't address the substance of your remarks.  But if you are in fact
  48. using such a deeply entrenched term in a nonstandard fashion, you
  49. would seem to be a lot better off calling the notion you've defined
  50. something else.
  51.  
  52. --Chris Menzel
  53.   Philosophy Department
  54.   Texas A&M University
  55.