Dieses Rätsel ist unter dem Namen „Der Barbier“ (R. M. Sainsbury: Paradoxien. Erweiterte Ausgabe 2001, S. 12) oder „Der Barbier von Sevilla“ bekannt: Der Friseur rasiert alle Männer des Dorfes, die sich nicht selbst rasieren. Sainsbury lokalisiert das Geschehen in einem Dorf Siziliens und sagt schließlich: „Es kann keinen solchen Barbier oder ein solches Dorf geben. Dies ist keine sehr tiefe Paradoxie, denn die Unannehmbarkeit ist durch Berge und Ferne nur sehr wenig verschleiert.“ Das gilt noch mehr für Cohens Lokalisierung: im Hindukusch (plus Hände abhacken).
Wodurch kommt das Paradox zustande? Wieder durch eine idiotische Formulierung: „alle Männer rasieren, die sich nicht selbst rasieren“.
1. Was gilt, wenn jemand keine Lust hat, sich rasieren zu lassen, sondern lieber als echter Taliban einen Bart wachsen lässt?
2. Was geschieht, wenn ausnahmsweise eine Frau zum Rasieren kommt? Darf der Barbier sie dann rasieren, ohne dass er aufhörte, Barbier zu sein?
Das Problem entsteht durch überspitzte Formulierung eines trivialen Sachverhalts (bzw. durch die Verknüpfung der All-Aussage mit der Negation): Der Barbier ist ein Mann (kann es auch eine Frau sein?), der beruflich andere Menschen (in der Regel Männer) rasiert. Mit diesem Satz ist der Wirklichkeit Genüge getan. Manche Männer lassen sich auch von ihrer Frau rasieren – das wird bei Cohen verboten.
Nehmen wir also an, der Barbier rasierte alle Männer, die sich nicht selbst rasieren. Das kann man akkurat sagen: „Der Barbier rasiert von Beruf Männer, die sich nicht selbst rasieren.“ Das ist gemeint; und deshalb kann man sagen: „Er rasiert von Beruf alle Männer des Dorfes, die sich nicht selbst rasieren.“ [Man könnte auch sagen: „Er rasiert von Beruf andere Männer des Dorfes.“] Dann ist das Paradox verschwunden; denn der Barbier rasiert sich als Mann, braucht sich also nicht als Barbier zu rasieren, was anzunehmen ohnehin Unsinn wäre: Dann müsste er sich ja für seine eigene Rasur bezahlen (aber „von Beruf“ heißt eo ipso: andere gegen Bezahlung rasieren); dieser Unsinn wird bei Cohen per Dekret festgelegt und ist Kriterium des Paradoxen.
Ergebnis:
1. Mit der Unterscheidung „von Beruf“ – „privat (als Mann)“, die ohnehin dem gängigen Verständnis des Barbiers zugrunde liegt, vermeidet man die Paradoxie; in dieser Hinsicht entsteht das Paradox also aus einer ungenauen bzw. bewusst überspitzten Formulierung oder der Unterschlagung eines Unterschieds, den jeder Mensch kennt.
2. Das Verflixte der Paradoxie kommt aus der All-Aussage plus Negation: „alle Männer rasieren, die nicht…“; wenn man ein bisschen vorsichtiger formuliert und „alle“ weglässt, wie man es als gebildeter Mensch tun sollte, verschwindet das Paradox.
3. In der Erörterung identifiziert Cohen das Barbier-Problem als Russells Paradox; Sainsbury (Paradoxien, RUB 18135, 2. Aufl.) unterscheidet beide und widmet Russell eine gründliche Eröterung (S. 162 ff.; 190 ff.; in der 5. Auflage sind es S. 235 ff. und 269 ff.). Johann Berger: Paradoxien aus Naturwissenschaft, Geschichte und Philosophie, 2006, S. 150 ff., identifiziert das Problem mit Russells Paradox.
http://de.wikipedia.org/wiki/Barbier-Paradoxon
http://de.wikipedia.org/wiki/Russellsche_Antinomie
http://glossar.hs-augsburg.de/Russellsche_Antinomie
http://www.lrz.de/~ulrich_metschl/AnPhil6.pdf (elementar)
http://www.mathematik.de/ger/presse/pressestimmen/russellparadoxon.html (verständlich: das Paradox im Rahmen der Mathe-Geschichte und des Denkens Russells)
http://www.wissenschaft-online.de/artikel/790702 (verständlich: Mengenlehre und Mathematik)
http://mata.gia.rwth-aachen.de/Vortraege/Kathrin_Hoevelmanns/Paradoxa/Vortrag.pdf (Einordnung: Mathematikgeschichte)
http://www.stauff.de/methoden/dateien/psychologie_ii.htm (didaktischer Kommentar)
http://www.hyperkommunikation.ch/lexikon/paradoxie.htm
P.S. Ich weise ausdrücklich auf den Kommentar von Herrn Dr. Greiter hin!
also42 
Anerkanntes, über nunmehr schon mehr als 2000 Jahre bewährtes Prinzip der mathematischen Logik ist der indirekte Beweisweg (der sog. Widerspruchsbeweis). Er besagt:
Eine Ausage ist falsch oder eine Definition ist sinnlos, d.h. ohne Lösung, wenn sich aus der Annahme, sie sei richtig bzw. sinnvoll, ein Widerspruch ableiten lässt.
Dieses Prinzip sagt demnach insbesondere: Hat man eine Menge S von Aussagen und/oder Definitionen und eine Aussage A derart, dass sich aus
S AND ( A OR NOT A )
ein Widerspruch ableiten lässt, so beweist das, dass dieser Widerspruch schon aus S selbst ableitbar ist und somit wenigstens eine Aussage aus S falsch oder mindestens eine Definition aus S sinnlos sein muss (S als paradox einzustufen, zeugt dann lediglich davon, dass man gar nicht in Erwägung zieht, S könne falsch oder sinnlos sein).
An der oft als paradox eingestuften Aussage "Der Barbier von Korfu rasiert alle Männer aus Korfu, die sich nicht selbst rasieren" ist nichts Geheimnisvolles — sie hat einfach nur den Wahrheitswert FALSE. Leider scheint das selbst berühmten Professoren nicht immer klar zu sein: siehe etwa Godel and the End of Physics, worin auch Steven Hawking auf dieses Beispiel zu sprechen kommt.)
Mehr zum Wesen sog. paradoxer Aussagen findet sich hier: http://www.greiterweb.de/spw/Denkfehler.htm.