home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / logic / 1678 < prev    next >
Encoding:
Text File  |  1992-10-07  |  1.8 KB  |  38 lines
  1. Newsgroups: sci.logic
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: A set cannot contain itself as a member
  5. Message-ID: <1992Oct8.033542.20684@CSD-NewsHost.Stanford.EDU>
  6. Keywords: recursion
  7. Sender: news@CSD-NewsHost.Stanford.EDU
  8. Organization: Computer Science Department,  Stanford University.
  9. References: <1992Sep29.161016.19533@ghost.dsi.unimi.it> <1992Sep29.175554.12758@cs.rochester.edu> <Oct05.201328.96457@yuma.ACNS.ColoState.EDU>
  10. Date: Thu, 8 Oct 1992 03:35:42 GMT
  11. Lines: 25
  12.  
  13. In article <Oct05.201328.96457@yuma.ACNS.ColoState.EDU> sa114984@longs.lance.colostate.edu (Steven Arnold) writes:
  14. >
  15. >    I am not an expert in set theory or the predicate
  16. >calculus, but I was leafing through a book on the subject and the
  17. >following informal "proof" occured to me.  Could any of you experts out
  18. >there tell me if this contains a major flaw -- and if so, what it
  19. >is?  Thanks.
  20. >
  21. >    The proposition to be proven is: A set can never contain
  22. >itself as a member.
  23.  
  24. One more point about this "proof":
  25.  
  26. If in your proof you replace "set" by "list", and write X = [g,X] in
  27. place of X = {g,X} to denote a list instead of a set, then you will
  28. have proved that such lists cannot exist.  This contradicts what
  29. happens in Lisp.  Lisp lists are necessarily finite, but may contain
  30. cycles.  Peter Aczel's treatment of AFA does in careful detail for sets
  31. what Lisp long ago did for lists, albeit without the mandatory
  32. agonizing over whether this would blow the universe's fuse.
  33.  
  34. -- 
  35. =================================================== In short, I am floundering
  36. Vaughan Pratt   pratt@cs.Stanford.EDU  415-494-2545 around and don't take what
  37. =================================================== I say seriously.
  38.