# Multiple barber paradox

I'm having a little trouble formalizing the proof for this statement

Suppose B is the set of barbers in a town who shave ALL those and ONLY those who DO NOT shave themselves

I have to prove that the set B is either the empty set , or the barbers do not shave.

This result is intuitive given this particular formulation of the paradox, however I haven't been able to formally prove this result

I've tried to write down my process using latex but I end up with unformatted code \forall \exists \land

• It seems to me that barbers who do not shave surely do not shave themselves. So I'm having trouble understanding how it could be that $B$ is not the empty set. (I mean that even if "the barbers do not shave" is true, the set $B$ should still be empty.) Aug 25 '14 at 13:35
• This question was taken from an Italian maths textbook, I understood it to mean that any given Barber cannot have his beard shaved under any circumstances. If a barber shaves another barber, then the barber being shaved would be compelled to shave himself , because he did not shave himself. If the barber shaves himself, he is compelled not to shave himself. The only solution is not to shave at all, which I understood to be different from not shaving oneself I'm trying to formalize the above with set notation, or even propositional logic Aug 25 '14 at 13:40
• Perhaps it is a case of original meaning lost in translation? In English, I would regard "he does not shave" to imply "he does not shave himself and does not have anyone else shave him," which in turn implies "he does not shave himself." On the other hand, "he is shaved by someone else" would imply "he does not shave himself," but is a stronger statement (because it also implies "he shaves"). Aug 25 '14 at 13:49
• I think this explains it quite well. Aug 25 '14 at 13:52
• I had already read the section on multiple barbers on Wikipedia, and I agree with their conclusion, I'm just running into problems when trying to formalize it using set notation or predicate logic Aug 25 '14 at 14:03

You might try the following formalization:

$\forall a\in M :[[\exists b\in B: bSa] \iff \neg aSa]$

where

$M$ is the set of men in town

$B$ is the set of barbers, $B\subset M$

$bSa$ mean b shaves a

In words: Together, the barbers shave those and only those men in the village who do not shave themselves.

I have to prove that the set B is either the empty set , or the barbers do not shave.

It is not possible that there is only one barber.

It is possible that there are exactly two barbers x and y such that x shaves every man in town but himself, and y shaves x.

EDIT $1$

In addition, you can construct the shaves relation as a subset $S$ of $M\times M$ as follows:

$\forall a,b :[(a,b)\in S \iff (a,b)\in M\times M \land [[a=x \land b\ne x]\lor[a=y \land b=x]]]$

Then you can prove:

$\forall a\in M:[a\ne x \implies (x,a)\in S]$

$(x,x)\notin S$

$(y,x)\in S$

$\forall a\in M:[[ \exists b\in B:(b,a)\in S] \iff (a,a)\notin S]$

Other possibilities exist for $S$ including no barbers ($B=\emptyset$) and every man shaving himself (thanks WmE).

EDIT $2$

We make the following assumptions about the sets M, S and B:

1) All barbers are men who live in town

$B\subset M$

2) Shavers are unique.

$(a,b)\in S \land (c,b)\in S\implies a=c$

3) If a man doesn't shave himself, then a barber must shave him.

$(a,a)\notin S\implies \exists b\in B: (b,a)\in S$

Then it can be shown that

$\forall a\in M:[[ \exists b\in B:(b,a)\in S] \iff (a,a)\notin S]$

$\iff \forall a\in B: (a,a)\notin S$

i.e. the barbers cannot shave themselves.

See my formal proof (in DC Proof format) at Multiple Barber Paradox.

• Thanks for your reply ! Yes I have already written a similar formalization, however it is not complete. Consider two of the barbers (elements of B) call them b1 and b2. If B1 shaves B2, then B2 is one of those who don't shave themselves, thus B2 must then shave himself. Contradiction If B2 shaves himself, he breaks the rules once again. That is the condition I can't formalize. I even tried considering the cartesian product subset of M^2 . Note: why does latex not work with me ? i followed the syntax ! \land Aug 26 '14 at 15:46
• In the scenario of two barbers x and y, I think you will find that no such contradictions can be obtained since no man in town, including the two barbers shave themselves. If, on the other hand, you have only one barber, you can always obtain a contradiction. BTW, to use Latex here, you have to enclose your string in \$-signs. Aug 27 '14 at 14:19
• Very nice--well done Aug 27 '14 at 16:11

You can say that with two or more barbers it is not a problem. For example with two barbers a and b, they together shave everyone who doesn't shave themselves and a shaves b and b shaves a, with three barbers, a b and c, a shaves b, b shaves c, and c shaves a. This thing keeps going further for four five or even 100 barbers.

With zero barbers it is also not a problem, as everyone has to shave themselves. With one barber only there is a problem. There can never be a negative number of barbers.