Парадокс берберина

Парадокс берберина је парадокс који се односи на математичку логику и теорију скупова. Изведен је из Раселовог парадокса, и често се погрешно приписује Бертрану Раселу. Овај парадокс показује како наизглед изводљив сценарио може да буде немогућ.

Парадокс може да се формулише на следећи начин. Претпоставимо да постоји село са само једним берберином. Такође, претпоставимо да су сви мушкарци у селу обријани: неки се брију сами, а неке брије берберин. Звучи разумно да се берберин понаша на следећи начин: он брије све оне, и само оне људе који се не брију сами.

По овом сценарију, поставља се следеће питање: Да ли берберин брије самог себе?

Када се постави ово питање, уочава се да је ситуација представљена овим условима у ствари немогућа:

• Ако берберин не брије себе, мора да поштује своје правило, и да брије себе.
• Ако берберин брије себе, по свом правилу неће бријати себе.

Пролог

У Прологу, један аспекат парадокса берберина се може изразити самореферишућом клаузом:

brije(berberin, X) :- musko(X), not(brije(X,X)).
musko(berberin).

где not представља негацију као неуспех.

Логика првог реда

$(\exists x)(berberin(x)\wedge (\forall y)(\neg brije(y,y)\Leftrightarrow brije(x,y)))$

Ова реченица је незадовољива (представља контрадикцију), због универзалног квантификатора, $\forall$. Универзални квантификатор y ће укључити све елементе из домена, укључујући и берберина, x. Па када се вредност x додели променљивој y, реченица добија следећи облик

$\neg brije(x,x)\Leftrightarrow brije(x,x)$,

што се може поједноставити као

$brije(x,x)\wedge \neg brije(x,x)$,

што је контрадикција.