# The Barber Paradox — A proposed set-theoretic approach

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.

-
Your question will be easier to understand if you explain the notation in your equations. – Austin Mohr Nov 27 '11 at 7:11
To display tex, surround the formula within dollars. – sdcvvc Nov 27 '11 at 14:50
I attempted to fix latex code, please check if it was what you intended. – sdcvvc Nov 27 '11 at 14:57
Thanks. This was my first attempt as using Latex. – Dan Christensen Nov 27 '11 at 22:39
Doesn't look like a question to me. – Grigory M Nov 28 '11 at 8:54

Correct me if I am wrong, but I think this conclusion would only be possible with a set-theoretic approach

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.

-
Was it Quine who said 2nd order logic was just "set theory in disguise?" – Dan Christensen Nov 27 '11 at 16:25
Yes, but that's controversial statement. Google for quine second order set theory disguise, to see replies to this. Anyway remember that the embedding is not direct, since in 2nd order you can quantify only on predicates defined on elements, not on predicates defined on predicates. – sdcvvc Nov 27 '11 at 16:44
Still, compared to set theory, 2OL is relatively obscure -- something only for specialists in the field, isn't it? And I don't know if 2OL allows you to construct the equivalent of Cartesian products and subsets, but I am planning a follow-up where I tweak the requirements a bit and construct a set of ordered pairs s that meets these modified requirements, thus eliminating self-reference as the culprit. I would do this starting only from the fact that that b is an element of the set m. – Dan Christensen Nov 27 '11 at 19:23
It's not obscure at all, it's mentioned in most textbooks on math. logic. I don't know what your requirements are, but I wouldn't exclude possibility of writing them in second-order logic. – sdcvvc Nov 27 '11 at 19:48
Thank you for your thoughtful responses, sdcvvc. I accept your answer and comments. You have more than adequately answered my question, but I think I will stick to a set-theoretic approach as my intended audience is the typical 2nd year math undergrad transitioning to proof-based mathematics. (Yes, I should have said so. Sorry.) I don't think they will see anything resembling 2OL in any of their math textbooks. – Dan Christensen Nov 27 '11 at 22:36

This is a follow up to my 2nd comment above. It explains in part why I used a set-theoretic approach to BP. Does it make sense? Please critique. Any comments would be appreciated. (I am told that I shouldn't have made this a separate question. Too vague, not a real question or something like that. So it was closed, thus cutting off the possibilities of any feedback. Yikes!)

In many places on the web, the Barber Paradox is called a paradox of "self-reference." Here, I will try to eliminate self-reference as the culprit in this case. I will construct a scheme for shaving the men in the village (a set s of ordered pairs of men in the village) and show that it satisfies the requirement that the barber shaves himself, and that for every man in the village, if that man is not the barber, then the barber shaves him if and only if he does not shave himself. In set-theoretic notation:

$(b,b)\in s \wedge \forall x(x\in m \rightarrow (x\neq barber \rightarrow ((b,x)\in s \leftrightarrow \neg (x,x)\in s)))$

where b = the barber, m = set of men in the village, and s = a set of order pairs of men in the village. $(x,y)\in s$ means x shaves y. As I understand the term, there are two instances of "self-reference" here: $(b,b)\in s$ (the barber shaves himself) and $(x,x)\in s$ (man x shaves himself).

We start by assuming that the barber is a man in village: $b\in m$

Since m is a set, from the axioms of set theory, there exists the set m2 of all ordered pairs of m.

We can then select a subset s of m2 such that:

$\forall x \forall y ((x,y)\in s \leftrightarrow ((x,y)\in m^{2} \wedge x=b)))$

In other words, the barber shaves every man in the village. It is then easy to show that

$(b,b)\in s \wedge \forall x(x\in m \rightarrow (x\neq barber \rightarrow ((b,x)\in s \leftrightarrow \neg (x,x)\in s)))$

(See my proof using my DC Proof notation.) Thus we have:

$\forall b \forall m (b \in m \rightarrow \exists s ((b,b)\in s \wedge \forall x(x\in m \rightarrow (x\neq barber \rightarrow ((b,x)\in s \leftrightarrow \neg (x,x)\in s))))))$

Compare this to my resolution of the original Barber Paradox:

$\forall b \forall m (b\in m \rightarrow \neg \exists s \forall x(x\in m \rightarrow ((b,x)\in s \leftrightarrow \neg (x,x)\in s)))$

-