home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14938 < prev    next >
Encoding:
Text File  |  1992-11-14  |  1.6 KB  |  36 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!agate!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: Boolean Algebras
  5. Message-ID: <1992Nov14.025504.16516@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department,  Stanford University.
  8. References: <42536@gremlin.nrtc.northrop.com> <Bxo1Hw.6qA@dcs.ed.ac.uk>
  9. Date: Sat, 14 Nov 1992 02:55:04 GMT
  10. Lines: 24
  11.  
  12. In article <Bxo1Hw.6qA@dcs.ed.ac.uk> mxh@dcs.ed.ac.uk (Martin Hofmann) writes:
  13. >In article <42536@gremlin.nrtc.northrop.com>, jbarnett@nrtc.northrop.com (Jeff Barnett) writes:
  14. >> 
  15. >> Is there a free boolean algebra such that the cardinality of
  16. >> the algebra (not the cardinality of its generators) is that
  17. >> of the continuum?
  18. >> 
  19. >> Jeff Barnett
  20. >
  21. >I guess the powerset of the natural numbers ordered by inclusion provides an example.
  22.  
  23. For any infinite X, the power set of X, and for that matter the set of
  24. all finite and cofinite subsets of X, are Boolean algebras with atoms.
  25. Hence they cannot be free Boolean algebras.
  26.  
  27. (In any equationally defined class, the free algebra F(X) on a set X
  28. consists of the equivalence classes of those formulas whose variables
  29. are drawn from X.  Claim: for Boolean algebras, if X is infinite F(X)
  30. has no atoms.  Proof: Let the equivalence class [p] be an atom where p
  31. is some (necessarily finite) Boolean formula, and let Q be a Boolean
  32. variable not appearing in p.  Then 0 < p&Q < p, contradicting [p]'s
  33. atomicity.)
  34. -- 
  35. Vaughan Pratt              A fallacy is worth a thousand steps.
  36.