home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / research / 563 < prev    next >
Encoding:
Text File  |  1992-11-20  |  1.4 KB  |  34 lines
  1. Newsgroups: sci.math.research
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
  3. From: aaronm@cybernet.cse.fau.edu (aaron meyerowitz)
  4. Subject: Finite axioms of choice
  5. Message-ID: <sPiguB1w165w@cybernet.cse.fau.edu>
  6. Originator: dan@symcom.math.uiuc.edu
  7. Sender: Daniel Grayson <dan@math.uiuc.edu>
  8. X-Submissions-To: sci-math-research@uiuc.edu
  9. Organization: Cybernet BBS, Boca Raton, Florida
  10. X-Administrivia-To: sci-math-research-request@uiuc.edu
  11. Approved: Daniel Grayson <dan@math.uiuc.edu>
  12. Date: Wed, 18 Nov 1992 22:52:15 GMT
  13. Lines: 19
  14.  
  15. I've heard this result but can't recall where. Can anyone provide a
  16. reference or related results for other number pairs?
  17.  
  18. Theorem: Suppose that there is a choice function for 2 element sets
  19. , then there is a choice function for 4 element sets.
  20.  
  21. Proof: Given a set {a,b,c,d} form each of the 6 2-element subsets
  22. and apply the choice function to it. Each of the four elements is
  23. chosen 0,1,2 or 3 times. If any is chosen 3 times, choose it (it must
  24. be unique). If none is chosen 3 times and one is never chosen, choose
  25. it (IT must be unique. The remaining possibility is that two are chosen 
  26. twice and 2 chosen once. Take the two chosen once (or twice, just decide 
  27. which) and let the chosen element be that chosen by the function for 
  28. that pair/////
  29.  
  30. So this result might be termed AC2 implies AC4. 
  31. Thanks,
  32. Aaron Meyerowitz
  33.  
  34.