The "Paradox"
Suppose there exists a man in a village (the barber) who must shave those and only those men in that village who do not shave themselves. (No, the barber can't be a woman or from out of town OR a robot!) Does the barber shave himself? Applying the definition of the barber to the barber himself, we obtain a contradiction: If he shaves himself, then he must not shave himself. And if he does not shave himself, then he must shave himself.
The Usual First-Order Resolution
Since postulating the existence of such a man in the village to leads a logical contradiction, no such barber can exist. Or, in first order predicate language (FOPL):
$$\neg \exists b(Mb \wedge \forall x(Mx \rightarrow (bSx \leftrightarrow \neg xSx)))$$
where $M$ is the "is a man in the village" predicate, and $S$ is the "shaves" predicate
A Set-Theoretic Resolution
If, however, we replace the predicates M and S by sets, m and s respectively, where s is a set of ordered pairs, we can obtain other more "natural" resolutions including the following:
$$\forall m \forall b(b \in m \rightarrow \neg \exists s \forall x(x \in m \rightarrow ((b,x) \in s \leftrightarrow \neg (x,x) \in s)))$$
Why "more natural?" In trying to devise a popular version of BP (at my website, bottom of my homepage), I found it easier to explain it by first supposing that the barber actually is man in the village and then showing that no combination of shavers and shaved could possibly meet the requirement that the barber shave those and only men in the village who do not shave themselves. (To say the barber simply didn't exist would have been a bit of an anti-climax as I told the story.)
My Question
Is a set-theoretic approach the only way to reach arrive at the non-existence of the shaves relation? Any comments would be appreciated.
Best Answer
You don't need full notion of set, only second-order logic, i.e. logic which allows to quantify over predicates, as opposed to first-order logic, where you can quantify only over elements of universe. The equivalent formula is:
$\forall m \forall b(b(m) \rightarrow \neg \exists s \forall x( x(m) \rightarrow (s(b,x) \leftrightarrow \neg s(x,x))))$
Personally I prefer first version, first we select some men and the shaving relation, and then we show that existence of a barber leads to contradiction. In the second version, we select first some men, then a barber, then we select shaving relation, then we get contradiction. The resolution "there is no such barber, assumptions are wrong" might be disappointing, but it's the simplest possible. Perhaps you can write it like this:
$\forall m \forall b \forall s(b(m) \rightarrow \neg \forall x( x(m) \rightarrow (s(b,x) \leftrightarrow \neg s(x,x))))$
For any $m$, $b$ and $s$ it is impossible to fulfill the condition imposed on the barber.