Last Update: 20 September 2010
Note: or material is highlighted
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 not as clear as it could be. Here's another version:
Consider a (male) barber, who:
Who shaves the barber? (Or: Can such a barber exist?)
Suppose such a barber exists. Then:
or else ("⊕", i.e., XOR)
(This is an exclusive disjunction: He can't both shave himself and not shave himself.)
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 used to be, in SEL, a catalog of catalogs! It did 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: