0
$\begingroup$

The "Paradox"

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.

  • 0
    I hope the new headings help clarify just what the question is.2011-11-28

2 Answers 2

3

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.

  • 0
    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.2011-11-27
1

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)))$