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.)
Is a set-theoretic approach the only way to reach arrive at the non-existence of the shaves relation? Any comments would be appreciated.