Hi John, hi Marty,
On 10 Oct 2009, at 21:47, John Mikes wrote:

> Bruno, we had similar puzzles in middle school in the 30s.
> The barber could not shave himself because he shaved only those who  
> did not shave themselves (and shaved all). So for  (Q #1) in the 1st  
> vriant
> she(?) was a female, unless he(?) was a beardless male

You are right. The barber gender is female. I don't see why you add  
that he could be a beardless male. It is part of the problem that we  
are in a tyrannic country where no man can have a beard.

> (and the 'all' refers to only the bearded males requiring a shave).
> *
> Q#2 is beyond me, I do not resort to a QM-pattern like Schrodinger's  
> cat.
> (Sh/H)e is either-or, not both.

I am not sure I understand, except that Q#2 remains unanswered, OK. I  
will first comment Marty's posts.

On 11 Oct 2009, at 01:30, m.a. wrote:

> Or the barber is a special exception to the group designated as  
> "men" and exists on a higher level of being. Therefore he can shave  
> himself without transgressing the rule as stated in the premise.  
> Isn't this one of Russell's paradoxes?       marty a.

Well, if the barber is not human, there is indeed no problem. But here  
the fact that it can be a woman, and that usually a barber is a human  
being, and that the question refer to a gender strongly suggest that  
the solution "the barber is a woman" is more reasonable that "the  
barber is an extraterrestrial". I think.

> And didn't Russell decide that this type of paradox should be  
> outlawed from allowable statements within the practice of  
> logic?      m.a.

Nice you see the relation with Russel's paradox. This is a very deep  
paradox which shows we have to handle the notion of sets with some  
care. Torgny Tholerus already mentionned this, and he defended the  
idea this is an argument for ultrafinitism, which in my opinion is  
like throwing the baby (the infinite sets) with the water of the bath.

If we dare to consider that the collection of *all* sets is itself a  
set, we have a nice example of a set which contains itself as an  
This is not problematical in itself, and in some axiomatic set  
theories, some sets can belong to themselves.

What becomes problematical is the idea of defining a set in intension  
by using *any* criteria.
Indeed, let us call *universe*, U,  the set of all sets. U belongs-to  
U. But {1, 2} does not belongs to {1, 2}, so some sets belong to  
themselves and some sets don't. So it looks like we could define a new  
set E of which contains all the sets which does not belongs to  
themselves. For example clearly the set {1, 2} is an element of E, and  
U is not an element of E.
But then we are in trouble. Does E belongs to E?
If E belongs to E, then he contradicts the definition of E, which  
contains only those set which does not belong to themselves. So E has  
to not belong to E. But then E does verify its own definition, so that  
he does belong to E. So E belongs to E and E does not belong to E.  

Well, this proves that the intuitive idea of set is inconsistent. We  
do have to make the notion more precise to avoid such kind of  
reasoning. All the many very different attempts to make the notion of  
set precise have lead toward interesting mathematics, philosophy and  
even religion (i think). But this would lead us far away of the topic.  
We will have opportunity to come back on this. With the most usual  
axiomatic set theories, the set of all sets is not a set, and the  
criteria to defined set in intension is usually weakened. So much that  
some axioms have to be added to get a reasonably rich theory.

Question 2.

> 2) What the hell has all this to do with diagonalization, ...  and
> universal machine?

Let us write (x y) to say that some relation between x and y exists.
In the problem, for example, (x y) means that x shaves y, and x and y  
are supposed to be humans.
In Russel's paradox (x y) means that x belongs to y, that is X  
contains y as an element, and x and y are supposed to be sets.

Argument by diagonalization always proceeds by using the diagonal  
twice. Which diagonal?

1) the first diagonal:

Well (x y) is a couple, and so belongs to the cartesian product of the  
set (of those x, y) with itself. Put in another way, if you look at  
all (x y) you get a matrix of pair of things (humans in the problem,  
sets in the paradox).


Well, the (x x) will constituted the diagonal of that matrix. x is  
supposed to vary in their respective domain (the humans in the  
village, the set, in the universe of all sets.

In the village, this gives something like (Sophie Sophie) (Claude  
Claude) (Arthur Arthur) etc. As long as there are inhabitants in the  
village. With the sets, the diagonal is any couple (x x) with x an  
arbitrary set.

The barber,  let us call it B, and the paradoxical set E from above  
are defined in a very similar way, said "by diagonalization", because  
it involves the diagonal (x, x).

The barber is defined by the condition that he shaves all and only the  
men who does not shave themselves.

B shaves x
if and only if
x is a man and NOT (x x).    "NOT (x,x)" means that x does not shave  
x. OK?

E is defined by the condition that it contains all and only the sets  
which does not contain themselves as element.

E contain x as element
if and only if
NOT(x x)

2) The second diagonal:

Consist in looking what happen to the barber B, or the set E, when  
applied to itself.

The second diagonalisation is the question (B B)?, or the question (E  

(B B)? = Does B shaves B?

And then, by definition of the barber B, if it is a man, we get a  
contradiction. Fortunately no contradiction occurs in case the barber  
is a woman. If he is a man, he has to shave himself if and only if he  
does not shave himself. If she is a woman, then she does not shave  
herself and has no obligation to do given that the barber shaves  
*only* men, by definition. So here, we have just proved that in that  
village the barber is a woman. Or, taking Marty's remark into account;  
we have proved that IF the barber is a human, THEN it is a woman. No  
contradiction occurs if the barber is a god, an extraterrestrial or a  
machine, with or without gender. It can be anything not shaving  
itself, and shaving by definition only the men of the village.

(E E)? = Does the set E contains itself as an element?

If yes: then it violates its own definition.
If no: well, it violates again its definition.

With (B B), we "prove a theorem", thanks to the saving condition  
excluding the possibility that (B B) is true in advance.
With (E E) we get a genuine difficulty showing that the naïve idea of  
sets is inconsistent.

And what if we delete the saving condition in the Barber problem,  
leading us to the "usual" Barber paradox. What if we say, with x  
varying on all humans (making barber shaving all womans, unless using  
John's proposal for the notion of "not shaving").

First diagonalisation:

B shaves x
if and only if
NOT (x x).

Well, second diagonalisation, we get:

(B B)
if and only if

A contradiction. Is it catastrophical? Not at all, it is a  
contradiction only assuming such a village exists. So it is only a  
proof that nowhere in any consistent reality or galaxies, multiverses,  
whatsoever you will ever find a barber, inhabiting a village and  
shaving all and only all the inhabitants who don't shave themselves.  
You will not find it for the same reason you will never find a square  
with only three sides, (unless dreaming or hallucinating or something?).

Do you see the two diagonalisations in Cantor theorem's proof? And in  
Kleene's proof?

We suppose there is a bijection between N and some set of functions.  
So we suppose there is an indexing of the functions, f_i available.  
The first diagonalisation is in the definition of g:

g(n) = f_n(n) + 1

Then, for "good" or "bad" reasons, according of the context, we  
suppose g belongs to the set of f_n, so that we can apply g on its own  
index, that is the second diagonalization, and get wonderful variate  
results according again the context.


1) when f_i are supposed to be a bijection between N and N^N, we get a  
contradiction. Showing that N^N are not enumerable.
2) when f_i are supposed to be a computable bijection between N and  
N^N-comp, we get a contradiction. Showing that, although enumerable,  
2^N-comp and N^N-comp are not computably enumerable.
3) when f_i are supposed to belong to an universal sequence of N^N- 
comp, we ... crash the universal machine, and find ourself unable to  
prevent by any means such crashing without destroying the machine  
universality. Showing that if we want *all*l total computable  
functions in the universal sequence N^N-partial-comp, they will be  
hidden in a non solvable ways (Pi-2 complete) among the partial  
functions. Partial function are like ignorance tunnels, or abysses, in  
the reality with which universal machines can be confronted.

I will come back on this, and develop, but this could make sense for  
those who have followed the last posts, in this thread.

Precisely N^N-comp is the set of functions from N to N which are  
N^N-partial-comp is the set of partial functions from N to N which are  
computable on their domains. Those partial functions are either  
defined on all N, and called total functions, or they are not defined  
for some number, and which, strictly speaking are functions from a  
subset of N to N.

Take it easy. I intend to summarize and come back on some crucial  
points, soon or a bit later.


> On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal <marc...@ulb.ac.be>  
> wrote:
> Hi,
> I am so buzy that I have not the time to give long explanations, so I
> give here a short exercise and a subject of reflexion instead.
> Exercise:
> There is Tyrannic country where by law it was forbidden for any man to
> have a beard.
> And there is village, in that country, and it is said that there is a
> barber in that village, who shaves all and only the men who don't
> shave themselves.
> Two questions:
> 1) What is the gender of the barber?
> 2) What the hell has all this to do with diagonalization, ...  and
> universal machine?
> Have a good day,
> Bruno
> http://iridia.ulb.ac.be/~marchal/
> >


You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to