A Blue-Eye Paradox: Solution Not Unique

[Demystifier]

But isn't that true for the last blue-eyer as well?

Isn't what true?

 

[fresh_42]

Isn't what true?

Sorry, mistaken. I thought they leave on a daily basis and forgot that they are forced to leave all at once.

 

[mfb]

This shows that monk1 knows that monk3 knows that there is at least one blue.

Yes, but monk 1 does not know that monk 2 has the same knowledge about what monk 3 knows.

1.1 blue blue blue -> here 3 knows there is at least one monk with blue eyes
1.2 blue brown blue -> here 3 knows there is at least one monk with blue eyes
2.1 brown blue blue -> here 3 knows there is at least one monk with blue eyes
2.2 brown brown blue -> here 3 does not know there is at least one monk with blue eyes
Monk 2 cannot distinguish between 2.1 and 2.2, so if monk 1 has brown eyes, monk 2 does not know if monk 3 knows about the existence of at least one monk with blue eyes.

The common knowledge "at least someone has blue eyes" removes the previous uncertainty: If we would be in case 2.2, monk 3 would know he has blue eyes and kill himself. He does not, so in the next step monk 1 knows: if he has brown eyes, then monk 2 knows we are not in case 2.2, and kills himself (also 3 kills himself). They don't do that, therefore monk 1 knows he has blue eyes in the next step.

There is an easier way to see that nothing happens without the hint: consider any case. The monks have absolutely no information about their eye color, and no way to gain any information because they know the others have no information about their eye color either so nothing happens.

 

[Demystifier]

We disagree, but I don't know how to explain my argument without repeating myself. At least one of us is not a perfect logician.

 

[Zafa Pi]

But it is not a valid possibility, given that I stipulated that all 3 monks have blue eyes.Yes, we agree on the case of 2 blue-eyes monks. But we still disagree on the case of 3 blue-eyes monks. I think that the key number is 3. If we make an agreement on 3, we shall also agree on 100.

I must admit I am surprised (mystified?) by your reply.
You, Alice, and Bob are on the island and each of you have respect for the others as clever mathematicians. (no perfect logic stuff)
Scenario 1. Alice has blue eyes, you and Bob have non-blue eyes. Guru speaks on day 0, then Alice leaves on day 1. You and Bob must conclude to have non-blue eyes.
Scenario 2. Alice and Bob have blue eyes and you don't. Now Alice can't leave on day 1. But Bob sees the same thing he saw in scenario 1 and thus infers he has blue eyes and leaves on day 2. Alice is in the exact same boat as Bob so she also leaves on day 2. You conclude you have non-blue eyes.
Scenario 3. All of you have blue eyes. Now Bob sees both you and Alice have blue eyes as opposed to Scenario 1 & 2, so he can't leave on day 2, nor can Alice. Once they don't leave on day 2 you know it is not true that you have non-blue eyes, i.e. you have the blues, so you leave on day 3. Alice and Bob are in the same boat as you so they also leave on day 3.

 

[ChrisVer]

I believe that you are trying to approach the paradox from a "word" point of view rather than its logic itself...
Each appearence, adds a new "information" to the game... so things like:

So at some point in the past they had to acquire that knowledge. That could happen in many different ways.

are trying to approach the problem from a wording prespective...
The point is that without the prophet's appearence, nobody could deduce that they are the blue-eyed...
this can be seen for the case where you have 1 man alone; if the prophet does not tell him that he sees 1 person with blue eyes, no matter if he knew the rule of commiting suicide, he would never commit it.

 

[ChrisVer]

Yes, but if two monks have blue eyes, then each of them already knows that one of them has blue eyes, simply by watching the other monk. If I see that you have blue eyes, then I know that at least one person has blue eyes. Nobody has to tell me that.

However you have to understand that the two persons will act independently in the end of the game...
So in the 2 people case, let's take the world as seen from the eyes of agent 1 who happens to have blue eyes:
Prophet appears: says that he sees 1 person with blue eyes.
case 1: one has blue eyes, the other has brown eyes... the blue-eyed person kills himself because he knows that the other has brown eyes and he is the only one left to have blue eyes.
case 2: both have blue eyes:
Then the agent looks around and sees 1-blue eyed person, so he makes an assumption: if I have brown eyes, that person should be able to see that I do have brown eyes, and since the prophet said that there is 1 person with blue eyes, he should commit suicide by tomorrow [see case 1]... if he sees that the other person does not commit suicide tomorrow, he will deduce that it's himself who has blue eyes too... and commit suicide the day after.
Of course how we chose the agent is arbitrary... the other agent [since they cannot communicate and stuff] will reach the same deduction as well on the same day.

 

[Zafa Pi]

I believe that you are trying to approach the paradox from a "word" point of view rather than its logic itself...
First of all, the prophet could come out and talk to the crowd whenever he wants (one day he comes out on Monday, the other on Tuesday and the next on Friday)... the answer has to be given in terms of the prophet's appearence... because in each appearence, a new "information" is added to the game... so things like:
are trying to approach the problem from a wording prespective...
The point is that without the prophet's appearence, nobody could deduce that they are the blue-eyed...
this can be seen for the case where you have 1 man alone; if the prophet does not tell him that he sees 1 person with blue eyes, no matter if he knew the rule of commiting suicide, he would never commit it.

I am using the same logic I use in doing math, playing bridge, and in arguing with my dog. A lot of math problems have words, what do you mean word vs logic?
In scenario 1 I said the guru speaks on day 0, and of course what she says "at least one of you has blue eyes".
What is the 1st sentence I wrote in post #35 that you don't find valid?

 

[ChrisVer]

What is the 1st sentence I wrote in post #35 that you don't find valid?

simply put: I wasn't answering to your post.

word vs logic?

I said that demystifier was doing that...like adding new parameters in the problem out of nowhere (like the monks' common knowledge coming from somewhere)

 

[Zafa Pi]

simply put: I wasn't answering to your post.I said that demystifier was doing that...like adding new parameters in the problem out of nowhere (like the monks' common knowledge coming from somewhere)

Since your post #36 came right after mine and didn't start with "Demystifier said" I thought you were addressing me. Sorry, my bad.

 

[Demystifier]

The point is that without the prophet's appearence, nobody could deduce that they are the blue-eyed...
this can be seen for the case where you have 1 man alone; if the prophet does not tell him that he sees 1 person with blue eyes, no matter if he knew the rule of commiting suicide, he would never commit it.

You are right about one man alone. But my point was that with 3 (or more) men with blue eyes, they could deduce that even without the prophet.

 

[ChrisVer]

The thing is that the 3-blue eyed problem breaks down into 2-blue eyed persons problem.

If you had 3 brown eyes, how would you solve the problem? Nobody would ever leave.
If you had 2 brown eyes and 1 blue eyed, how would you solve the problem? without the input to everyone that there is 1 blue eye?
Each of the monks reaches the result on himself.

 

[Demystifier]

I said that demystifier was doing that...like adding new parameters in the problem out of nowhere (like the monks' common knowledge coming from somewhere)

All the monks know the law that they should kill themselves as soon as they became aware of their blue eyes. So this law is common knowledge. How can this common knowledge exist without coming from somewhere?

 

[Demystifier]

The thing is that the 3-blue eyed problem breaks down into 2-blue eyed persons problem.

I disagree, as I explained in posts #22 and #30.

 

[mfb]

All the monks know the law they they should kill themselves as soon as they became aware of their blue eyes. So this law is common knowledge. How can this common knowledge exist without coming from somewhere?

Someone told them about this law. Or they have a big stone where that law is engraved. It doesn't really matter, it is given as common knowledge.

Did you see post #35 by Zafa Pi? I think it is a good summary.

 

[Demystifier]

Did you see post #35 by Zafa Pi? I think it is a good summary.

Yes, this is the standard solution, and it is also a valid solution. But my point is that there are also other valid solutions.

 

[Demystifier]

Someone told them about this law. Or they have a big stone where that law is engraved. It doesn't really matter, it is given as common knowledge.

But in post #11 I have explained that it does matter.

 

[mfb]

The "counter" starts as soon as both "at least one person has blue eyes" and the suicide law become common knowledge. The usual problem statement tells us that the law is common knowledge but the monks lived on the island for a while before the stranger made the blue eye common knowledge, which implies "at least one person has blue eyes" never became common knowledge before.

You could also go the opposite way, let them start with the common knowledge of at least one monk having blue eyes, and then introducing the suicide law at a given day. That leads to the same conclusions with a different problem statement, but that is not the problem discussed here.

 

[Demystifier]

but the monks lived on the island for a while before the stranger made the blue eye common knowledge, which implies "at least one person has blue eyes" never became common knowledge before.

Yes, they lived for a while, but it is not specified how much was that. Since it is not specified, one cannot exclude the possibility that it was less then 100 days.

Or let us reformulate the problem. Suppose that the monks are not pure logicians, but brilliant detective-type thinkers, like Sherlock Holmes or Hercule Poirot. What one would expect to happen in that case?

 

[Demystifier]

More solutions

The story tells that one day, which I call day-zero, the prophet said what he said, but the story does not tell what other events were happening before that. For instance, the story does not exclude the possibility that prophet said the same thing already 3 days before the day-zero. In that case, by using the logic of the standard solution, the massive suicide should happen in 97 days (counting from the day-zero). This is another demonstration that the problem is not well posed, i.e. that the solution is not unique.

In an attempt to make the problem well posed, one might add that nothing remarkable or relevant happened before the day-zero. But that would be simply impossible. At some day in the past they had to be informed about the law, and that event, as I have shown, might have been very relevant.

 

[mfb]

I think now you are nitpicking just for the sake of it. It is possible to phrase the problem clear enough to remove all those issues. Don't blame strawman problem statements if you don't understand the solution to the problem.

I don't see progress here, my last post in this thread.

 

[ChrisVer]

Let's take the 3 monks example you mentioned in the P#22 and 30... Let's first of all define the state... I will call B the Blue eyes (RIPers) and R the Red eyes (survivors)...
The possible states are: 2^3/2 = 4
RRR, RRB, RBB, BBB

This is how the game of the 3 monks will start... [I haven't taken a particular monk so far]...

1. Let's say that the game starts in the state RRR... then in round 0 everybody will be informed by the prophet that there is no blue eyed beast among the red-eyers... And the game is over with nobody dying.

2. Let's take the case of the RRB... and let's take the Blue-eyed person: on day 0 he is informed that there is at least 1 blue eyed-beast between them, and he knows by seeing the other two with red eyes that he has to kill himself... on day 1 he dies and the rest are informed that the blue-eyed disease has been taken care of... day 1 is the game over.
From the prespective of a R's player, he sees a blue eyed person so he cannot rule out his "hypothesis" that he is not the "blue eyed person" the prophet spoke of... Then on day 1 he sees the blue guy died and he deduces that since the blue eyed died he was certain that he had the blue eyes and R determines he is a R.

3. Taking the RBB state...
day 0: prophet tells there is at least 1 blue eyed beast. B sees a B and a R... R sees two Bs... the R cannot say whether he was the one the prophet reffered to or not...
day 1: nobody dies so far... prophet resays there is 1 blue eyed beast... R is still uncertain of his eye colors... but now the Bs are certain of their eye colors: because the B1 says that if the other B2 was the only one blue eyed, then by day 1 he would have died... "so B2 is not the only blue eyed person between us - and the other is obviously an R... so I have to be a B" is what he says... getting certain of his eye color.
day 2: B1 commits suicide... B2 commits suicide... because both B1 and B2 independently worked and reached the same result... R survives after being informed that the blue disease is over.

4. Taking the BBB state...
day 0 : the same... B sees 2 Bs...
day 1 : the same... B sees 2 Bs surviving... (so far each B is really seeing the world as R did in the RBB state)
day 2: the same... B sees 2 Bs surviving ... he is certain that he is a B... if he was a R, by this day (see RBB case) his fellow men would have commited suicide...
day 3: B commits suicide... independently the other 2 Bs reach the same result (symmetry)... and also left this world...Where is your "objection" to the above points?
I think your point is that the prophet's information is useless? however it is pretty important in the RRR case... and RRB case... in the RRB state for example, if the prophet never spoke of a B's existense, then the Reds would also end up dead... because a R would see a B never dying [B was seeing RR but he would have no way to exclude that he is not an R as well], so they would assume they lived in an RBB world [one B corresponding to themselves]... at least in that case the 1 R would kill himself the day right after... who that R is is ambiguous; both Rs will kill themselves since they see the same things... the B will see 2 Rs dying and kill himself as well the day after... the fact that Rs die however is against the game rules.

 

[Demystifier]

Where is your "objection" to the above points?
I think your point is that the prophet's information is useless? however it is pretty important in the RRR case... and RRB case... in the RRB state for example, if the prophet never spoke of a B's existense, then the Reds would also end up dead... because a R would see a B never dying [B was seeing RR but he would have no way to exclude that he is not an R as well], so they would assume they lived in an RBB world [one B corresponding to themselves]... at least in that case the 1 R would kill himself the day right after... who that R is is ambiguous; both Rs will kill themselves since they see the same things... the B will see 2 Rs dying and kill himself as well the day after... the fact that Rs die however is against the game rules.

I agree that prophet's information is important in RRR, RRB, and RBB cases. However, I think that prophet's information is not important* in the BBB case. Therefore, it is incorrect to use induction to reduce BBB to RBB. In 4. it is incorrect to start with "day 0 : the same... B sees 2 Bs...".

*More precisely, not important according to some interpretations of the problem. E.g. it is not important in the interpretation in which all the monks were informed about the law in the past, when another prophet told them the law when they were all together. This is certainly a logical possibility, and perfectly logical reasoning should not dismiss any logical possibility.

 

[Demystifier]

I think now you are nitpicking just for the sake of it.

It's about logic. From the point of view of other mathematicians, most of the research in logic is nitpicking just for the sake of it. So yes, I am nitpicking, but that's what logic is about.

It is possible to phrase the problem clear enough to remove all those issues.

I would like to see such a phrasing. (Frege thought that he made phrasing of whole mathematics clear enough to remove all the problematic issues, until Russel showed him that he didn't. Most other mathematicians of that time didn't care, because it was just nitpicking.)

Don't blame strawman problem statements if you don't understand the solution to the problem.

I understand the standard solution, and I agree that the solution is valid. I just don't agree that the solution is unique. That's because the problem, as stated, can be interpreted in many inequivalent ways. Or to use the language of mathematical logic, the stated set of axioms has many inequivalent models.

 

[Demystifier]

What is special about n=3?

As I emphasized several times, the standard solution is not necessarily right when the number of blue-eyes monks is $n\geq 3$. So what is special about $n=3$? Let me try to explain it once again.

In general, there are many levels of knowledge that all blue-eyers may or may not have.
Level 1: All blue-eyers know that (someone has blue eyes).
Level 2: All blue-eyers know that (all blue-eyers know that (someone has blue eyes)).
Level 3: All blue-eyers know that (all blue-eyers know that (all blue-eyers know that (someone has blue eyes))).
...

We all agree that both Level 1 and Level 2 knowledge is relevant. But is Level 3 knowledge relevant? I cannot prove it, so I use my intuition to postulate the following axiom:
Axiom: Level 3 knowledge is not relevant.

As a reader may guess, it is this axiom which eventually will lead to the result that $n=3$ is special.

First, from the axiom it is not difficult to show that levels of knowledge higher than 3 are also not relevant.

Now let us study what is the lowest level of new information that is brought by the prophet.

Case n=1: In this case, the prophet brings new information at Level 1.

Case n=2: In this case, Level 1 knowledge is already present before the prophet. The lowest level of new information is at Level 2.

Case n=3: In this case, both Level 1 and Level 2 knowledge are already present before the prophet. The lowest level of new information is at Level 3.

...

But from the Axiom it follows that new information in the case n=3 is not relevant. Therefore, for $n\geq 3$ the prophet does not bring any new relevant information. Therefore the standard solution is not necessarily right for $n\geq 3$. Q.E.D.

Of course, a critique has right to question my Axiom. After all, that Axiom may look somewhat ad hoc. But I have a right to add any axiom I wish, provided that no inconsistency is brought by that axiom. And I don't see any such inconsistency. (In addition, the Axiom looks intuitively appealing to me.) If I am right that this new Axiom does not bring any new inconsistency, then I am right that my solution of the blue-eyes puzzle is also one of valid solutions.

So if one wants to prove that my solution is wrong, one has to prove that my Axiom brings some inconsistency. (Inconsistency with what? With other axioms which we can all accept as "perfectly reasonable".)

Comment: In the standard solution, one uses induction starting with $n=1$. That induction can be interpreted as a proof that all levels of knowledge are relevant. However, in the standard solution it is not obvious that such induction is legitimate. The principle of induction is an unproved axiom by itself. What I propose is to reject the axiom according to which the induction principle can be applied to all levels of knowledge, and replace it with my Axiom above.

 

[Demystifier]

Demystifier, can you write out formal rules of the two logics that would have the opposite results?

One of the formal rules used in the standard solution is a certain version of the induction principle. (A version which refers to levels of knowledge.) In my last post above (the last paragraph of post #55), I have suggested that it seems reasonable to reject such a version of the induction principle. I would like to see what do you think of it.

I am aware that it still far from being formal, but it at least indicates what exactly should be carefully formalized.

EDIT: For a partial formalization, see also post #60 below.

 

[ChrisVer]

The induction starts from what you [who don't know your eye-color] see per round and how you interpret it...

Would you find a reason why, in day 2, the two Bs in the BBB case wouldn't have commited suicide if the 3rd one was not a B?

 

[Demystifier]

Would you find a reason why, in day 2, the two Bs in the BBB case wouldn't have commited suicide if the 3rd one was not a B?

This question does not make sense to me. In the BBB case it cannot be that the 3rd one is not a B.

 

[ChrisVer]

This question does not make sense to me. In the BBB case it cannot be that the 3rd one is not a B.

You know that it's BBB because you know the initial state...
Let me rephrase it then to be clearer... how would the XBB state evolve with time? X is unknown (B or R)... In particular now we look at the state as seen by the eyes of 1 of the Bs...

 

[Demystifier]

Axiom for n=3, formalization, and self-reference

It is well known that self-reference often leads to logical paradoxes. I have found a way to formalize some of my statements and to show that my Axiom 3 is needed in order to avoid self-reference.

Let $L$ be some lower order language, that is a language that does not contain the notion of "knowledge". Let $x$ be some statement in $L$, e.g. $x=$"someone has blue eyes".

Next let us use a higher-order language which does contain a notion of "knowledge". In this higher order language, the capital letters denote object which can posses knowledge. For instance, if $B_1,B_2,B_3,\ldots$ are different blue-eyers, then
$B_1x$ means "$B_1$ knows $x$"
$B_1B_2x$ means "$B_1$ knows that ($B_2$ knows $x$)"
$B_1B_2B_3x$ means "$B_1$ knows that ($B_2$ knows that ($B_3$ knows $x$))"
etc...

Now consider a statement $BBx$. This means "$B$ knows that ($B$ knows $x$)". Clearly, this introduces a self-reference, which is potentially problematic. But this can easily be avoided by introducing the Reflexivity rule
$$BBx=Bx$$
This means that "$B$ knows that ($B$ knows $x$)" is the same as "$B$ knows $x$". By reflexivity, such self-reference is resolved in a simple way.

Now consider the case of $n=2$ blue-eyers, denoted by $B_1$ and $B_2$. Consider the statement
"All blue-eyers know that (all blue-eyers know $x$)"
This is really a list of $2^2=4$ statements
$B_1B_1x=B_1x$
$B_1B_2x$
$B_2B_1x$
$B_2B_2x=B_2x$
We see that for $n=2$ all self-reference is avoided by the the Reflexivity rule.

Now consider the case of $n=3$ blue-eyers, denoted by $B_1$, $B_2$, and $B_3$. Consider the statement
"All blue-eyers know that (all blue-eyers know that (all blue-eyers know $x$))"
This is really a list of $3^3=27$ statements. Some of them contain resolvable self-references such as
$B_1B_1B_1x=B_1B_1x=B_1x$
But others, such as
$B_1B_2B_1x$
contain self-references which cannot be resolved by the Reflexivity rule. So how to avoid such self-referencing statements? What do they really (if anything) mean? Since it is not clear how to resolve such self-reference, it seams reasonable to adopt my Axiom which states that statements of the form "All blue-eyers know that (all blue-eyers know that (all blue-eyers know $x$))" are simply discarded (or treated as meaningless, irrelevant).