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
element.
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.
Damned.
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).
OK?
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
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
NOT(B B)
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.
Actually
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
computable.
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.
Bruno
> On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal <[email protected]>
> 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/
>
>
>
>
>
> >
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 [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
