home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11019 < prev    next >
Encoding:
Internet Message Format  |  1992-09-07  |  2.5 KB
  1. Path: sparky!uunet!pipex!unipalm!uknet!pavo.csi.cam.ac.uk!camcus!gjm11
  2. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  3. Newsgroups: sci.math
  4. Subject: Re: A set-theoretic proof:need help
  5. Message-ID: <1992Sep4.213120.22824@infodev.cam.ac.uk>
  6. Date: 4 Sep 92 21:31:20 GMT
  7. References: <181cvgINNptm@matt.ksu.ksu.edu>
  8. Sender: news@infodev.cam.ac.uk (USENET news)
  9. Organization: U of Cambridge, England
  10. Lines: 82
  11. Nntp-Posting-Host: bootes.cus.cam.ac.uk
  12.  
  13. In article <181cvgINNptm@matt.ksu.ksu.edu>, bubai@matt.ksu.ksu.edu (P.Chatterjee)
  14. writes:
  15. > Hi,
  16. > 
  17. > I have a 'homework' problem which I'd like some help on. It's a proof. It's 
  18. > awfully simple but the only problem is that I'm not sure how exactly one 
  19. > should approach it especially if one is looking to give a 'slick' proof.
  20. > 
  21. > It goes like this:
  22. > 
  23. > Prove that for subsets A, B c X:
  24. > 
  25. > A c B <=> A U B = B <=> A ^ B = A <=> B' c A'
  26. > 
  27. > where: c:= subset
  28. >        U:= union
  29. >        ^:= intersection
  30. > 
  31. > My request is for some help on how to go about using the logical equivalence 
  32. > symbol in proving the above equivalences. I have constructed a 'scrappy' and 
  33. > lengthy proof but would like to achieve brevity in expression.
  34. > 
  35. > Would really appreciate if somebody, without giving the actual proof, helped me
  36. > with how to proceed.
  37. > 
  38. > Thanks for all the help.
  39.  
  40. I'm not sure I can give much useful advice for this case without basically
  41. giving you a complete proof. The trouble is that the most natural "proof" is
  42. just to say "Well, it's obvious, isn't it?"...
  43.  
  44. One observation that is sometimes helpful (not sure whether it is in this case):
  45. If you have to prove A<=>B<=>C...<=>Z, see if you can do it by proving something
  46. like A=>B=>C=>...=>Z -- this can substantially decrease the number of separate
  47. results you have to prove.
  48.  
  49. One other thing, specifically about this problem... (This will be really obvious
  50. to some, but you mightn't have thought of things this way.) I'll put lots of
  51. newlines in, in case it counts as telling you how to proceed.
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86. Things like union and intersection of sets are really sort of abstractions of
  87. logical operations like "or" and "and". In other words, if A is the set of all
  88. things such that P, and B is the set of all things such that Q, then AnB is
  89. the set of all things such that (P and Q), and AuB is the set of all things 
  90. such that (P or Q), and A c B if and only if P=>Q, and so on. Oh, and A=B
  91. if and only if P<=>Q.
  92.  
  93. So the present problem is reduced to asking questions about one object at a
  94. time: we have to prove P=>Q iff PvQ<=>Q iff etc.
  95.