From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Fri Jan 25 08:40:16 2008 Date: Fri, 25 Jan 2008 08:35:59 -0500 From: "William J. Rapaport" Subject: The Barber Paradox (Rosen, 1.1, prob. 44) To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: The Barber Paradox (Rosen, 1.1, prob. 44) ------------------------------------------------------------------------ I understand that several of you had questions about HW #1, problem 44, about the barber who shaves all & only those who don't shave themselves. The problem as stated in the book is perhaps not as clear as it should be. Here's another version: Consider a barber, who lives in the village, shaves all those people who live in the village who don't shave themselves, and he shaves only those people who live in the village who don't shave themselves. Can such a barber exist? Suppose such a barber exists. Then (I) either he shaves himself or else ("+", i.e., XOR) (II) he does not shave himself. (This is an exclusive disjunction: He can't both shave himself and not shave himself.) Case I: Suppose the barber shaves himself. But he shaves only villagers who don't shave themselves. That's a contradiction. Therefore, our supposition is wrong. Therefore, he does not shave himself. Case II. We have just concluded that the barber does not shave himself. But he shaves all villagers who don't shave themselves! Another contradiction. Conclusion: Such a barber cannot exist. Another version of this considers a book that is a catalog of all book catalogs that do not list themselves. By similar reasoning, no such catalog can exist. By the way, there is, in SEL, a catalog of catalogs! It **does** list itself! The most important version of this is the set of all sets that do not contain themselves as members. No such set can exist. This is called "Russell's paradox", because it was discovered by Bertrand Russell. For more information, do a Google search on "barber paradox", or see: Wikipedia contributors, "Barber paradox," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Barber_paradox&oldid=186398870 (accessed January 25, 2008). http://mathworld.wolfram.com/BarberParadox.html