Paradoks berberina

Paradoks berberina je paradoks koji se odnosi na matematičku logiku i teoriju skupova. Izveden je iz Raselovog paradoksa, i često se pogrešno pripisuje Bertranu Raselu. Ovaj paradoks pokazuje kako naizgled izvodljiv scenario može da bude nemoguć.

Paradoks može da se formuliše na sledeći način. Pretpostavimo da postoji selo sa samo jednim berberinom. Takođe, pretpostavimo da su svi muškarci u selu obrijani: neki se briju sami, a neke brije berberin. Zvuči razumno da se berberin ponaša na sledeći način: on brije sve one, i samo one ljude koji se ne briju sami.

Po ovom scenariju, postavlja se sledeće pitanje: Da li berberin brije samog sebe?

Kada se postavi ovo pitanje, uočava se da je situacija predstavljena ovim uslovima u stvari nemoguća:

• Ako berberin ne brije sebe, mora da poštuje svoje pravilo, i da brije sebe.
• Ako berberin brije sebe, po svom pravilu neće brijati sebe.

Prolog

U Prologu, jedan aspekat paradoksa berberina se može izraziti samoreferišućom klauzom:

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

gde not predstavlja negaciju kao neuspeh.

Logika prvog reda

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

Ova rečenica je nezadovoljiva (predstavlja kontradikciju), zbog univerzalnog kvantifikatora, $\forall$. Univerzalni kvantifikator y će uključiti sve elemente iz domena, uključujući i berberina, x. Pa kada se vrednost x dodeli promenljivoj y, rečenica dobija sledeći oblik

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

što se može pojednostaviti kao

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

što je kontradikcija.