home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9501 < prev    next >
Encoding:
Internet Message Format  |  1992-07-24  |  1.3 KB
  1. Path: sparky!uunet!mcsun!uknet!warwick!mrccrc!icdoc!pt
  2. From: pt@doc.ic.ac.uk (Paul Taylor)
  3. Newsgroups: sci.math
  4. Subject: Re: The Schroder-Bernstein Theorem.
  5. Keywords: fixpoint, adjunction
  6. Message-ID: <1992Jul24.152649.13746@doc.ic.ac.uk>
  7. Date: 24 Jul 92 15:26:49 GMT
  8. References: <1992Mar20.141024.252962@cs.cmu.edu> <15994@ncar.ucar.edu>
  9. Sender: Paul Taylor <pt@doc.ic.ac.uk>
  10. Organization: Department of Computing, Imperial College, London.
  11. Lines: 18
  12. Nntp-Posting-Host: swan.doc.ic.ac.uk
  13.  
  14. The following proof of the Schroder-Bernstein Theorem is my own,
  15. but was inspired by that in Peter Johnstone's book "Set Theory and Logic"
  16. (Cambridge University Press).
  17.  
  18. Y denotes the "least fixed point" of a monotone endofunction of a poset.
  19. f^*(V) is the inverse image of a subset under a function.
  20. f_! and f_* denote the left and right adjoints of f^* considered as a monotone
  21. function between powersets.
  22. In fact f_!(U)={y:some x in U.fx=y} and f_*(U)={y:all y.fx=y => x in U}.
  23.  
  24. Let f:A->B and g:B->A be injective functions.
  25. Consider the subsets U=Y(g_!f_*) of A and V=Y(f_!g_*) of B.
  26. (Right-to-left composition; when I say "consider", I mean you have to think
  27. about it for a few minutes.).
  28. The given functions f and g restrict to bijections between U and B-V
  29. and between V and A-U.
  30.  
  31. The result depends on (and is probably equivalent to) Excluded Middle.
  32.