Multiple barber paradox

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.