home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / logic / 1905 < prev    next >
Encoding:
Text File  |  1992-11-04  |  3.2 KB  |  63 lines
  1. Newsgroups: sci.logic
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!sun-barr!cs.utexas.edu!usc!rpi!uwm.edu!linac!unixhub!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: Impredicativity - was: Russell's Paradox
  5. Message-ID: <1992Nov5.044052.12870@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department,  Stanford University.
  8. References: <Bx81Ho.9HL@cantua.canterbury.ac.nz>
  9. Date: Thu, 5 Nov 1992 04:40:52 GMT
  10. Lines: 51
  11.  
  12. In article <Bx81Ho.9HL@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
  13. >Randall Holmes - a question.  You say that it is a *theorem* of ZF that
  14. >
  15. >   "for any set x, for some ordinal a, x E V(a)" .
  16. >
  17. >[where V(a) is defined by  V(0) = {}
  18. >                           V(a+1) = P{V{a}}
  19. >                           V(L) = U{a < L}[V(a)] (L a limit ordinal). ]
  20. >
  21. >Is this really true ? Surely not. The collection of V's is a model for ZF, yes.
  22. >But the above isn't a theorem, is it? 
  23. >I expect it *is* a theorem of ZF+AxFndtn.
  24.  
  25. I'm sure that's what Randall meant.  You can't rank sets without FA.
  26. If you weaken FA to AFA you have counterexamples to the above like
  27. Omega = {Omega}, to which the above definition cannot assign any
  28. ordinal in a way that satisfies these equations.  (Consider the least
  29. ordinal a for which Omega E V{a}.  Clearly a is not 0.  Since Omega has
  30. only one element a cannot be a limit ordinal.  So a is a successor
  31. ordinal, call it b+1.  But then Omega is a subset of V{b}, whence
  32. Omega's only element, Omega, is an element of V{b} and hence of rank
  33. less than a, contradiction.)
  34.  
  35. Conversely, once you have FA you can prove the above theorem by
  36. assigning a rank to each set by the following informally described
  37. procedure.  To rank set x, assign ranks to its elements.  This
  38. recursive procedure is well-defined because there are no infinite
  39. descending membership chains.  Now take the rank of x to be the least
  40. ordinal strictly greater than the rank of any element of x.  This rank
  41. will be 0 when x is empty, a successor ordinal when x contains an
  42. element of rank maximal among its siblings, and otherwise a limit
  43. ordinal.
  44.  
  45. This informal procedure can be made rigorous as follows.  The form of
  46. FA that I find most useful for these purposes is the Axiom Schema of
  47. Restriction, namely one axiom for every ZF formula phi(x) with one free
  48. variable x.  The axiom says that either phi holds of no set, or there
  49. exists a set y for which phi holds of y but of none of its members.
  50.  
  51. So now take phi(x) to be "for every ordinal a, x is not in V(a)".  If
  52. phi holds of no set we are done.  Otherwise by restriction there is a
  53. set y for which phi(y) holds but for all members z of y, phi(z) is
  54. false.  If y is empty this contradicts the first equation defining V.
  55. If y is nonempty then all its members have ranks.  If there is a
  56. maximum rank b of those members then y is a subset of V(b), hence an
  57. element of V(b+1) by the second equation.  If there is no maximum rank
  58. then let b be the union of these ranks, necessarily a limit ordinal.
  59. Then y is an element of V(b) by the third equation, and we are done.
  60. (And hence of course phi holds of no sets.)
  61. -- 
  62. Vaughan Pratt                There's no truth in logic, son.
  63.