**The Barber Paradox
Revisited**

**Why We Need Set Theory**

ŠAnna Vasilkova

Here, we will consider simple variations of the famous Barber Paradox (3 versions) and demonstrate the need for set theory in a very simple and direct way.

**Version 1**

The
original Barber Paradox stated that the fabled *barber* is a man in a
village who is required to shave those and only those men living there who do
not shave themselves. It asks, does the barber shave himself or not? Either
way, we arrive at a contradiction, so we can only conclude that no such barber
can exist. Here is the original formalization of this scenario:

Suppose we define the *Shave*s relation
as follows where *Shaves(barber,a)
*means the *barber* shaves *a*.

**1** ALL(a):[Shaves(barber,a) <=> ~Shaves(a,a)]

Premise

Apply Universal Specifcation
setting *a=barber* to obtain the contradiction...

2 Shaves(barber,barber) <=> ~Shaves(barber,barber)

U Spec, 1

We conclude that no such barber can exist.

3
~EXIST(barber):ALL(a):[Shaves(barber,a)
<=> ~Shaves(a,a)]

4
Conclusion, 1

In this rather cartoonish formalization, we are quantifying over all objects in the universe. We are potentially shaving everything from black holes in space to the number 5.

**Version 2**

To make it just a bit more realistic, we might consider restricting our attention somewhat to the men living in the village. This will lead to an important insight that is not apparent in the original formalization.

Suppose the barber is a man in the village.

**1** Man(barber)

Premise

Define the shaving relation as follows...

**2** ALL(a):[Man(a)
=> [Shaves(barber,a) <=> ~Shaves(a,a)]]

Premise

Apply Universal Specification setting a=barber in the previous line.

3 Man(barber) => [Shaves(barber,barber) <=> ~Shaves(barber,barber)]

U Spec, 2

Since the barber is a man in the village, we obtain the following contradiction...

4 Shaves(barber,barber) <=> ~Shaves(barber,barber)

Detach, 3, 1

The "definition" on line 2 results on a contradiction, so it must be false.

5 ~ALL(a):[Man(a)
=> [Shaves(barber,a) <=> ~Shaves(a,a)]]

4 Conclusion,
2

Generalizing...

6
ALL(barber):[Man(barber)

=> ~ALL(a):[Man(a) => [Shaves(barber,a) <=> ~Shaves(a,a)]]]

4
Conclusion, 1

Or equivalently...

ALL(barber):[ALL(a):[Man(a) => [Shaves(barber,a) <=> ~Shaves(a,a)]] => ~Man(barber)]

Thus, if this shaving relation holds for all the men in the village, then the barber cannot be a man in the village (perhaps a women).

We can now ask, is the converse true, i.e. if the barber is not a man in the village, can this shaving relation still hold? By pure logic alone, we cannot prove the converse:

ALL(barber):[~Man(barber) => ALL(a):[Man(a) => [Shaves(barber,a) <=> ~Shaves(a,a)]]]

It is not even true in general, e.g. this statement would be false if the barber is not a man in the village and does not shave someone who does not shave himself.

**Version 3**

Using set theory, however, we can, formally prove:

ALL(v):ALL(barber):ALL(m):[Set(v)

& barber e v

& Set(m)

& ALL(a):[a e m
=> a e v]

=> [EXIST(s):ALL(a):[a e m => [(barber,a) e s <=> ~(a,a) e s]]

<=> ~barber e m]]

where

ˇ
*v* = the set of villagers (including men, women and children)

ˇ
*m* = the set men in the village

ˇ
*s* =
the shaving relation on *v *such that (barber,a) e s means the *barber* shaves *s*

See formal proof with commentary (81 lines)