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 <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/ > > > > > > > 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 everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---