Blue-Eye Paradox: Solution Not Unique

[Demystifier]

The blue-eye puzzle (or paradox, or riddle) is a well known logical puzzle, explained and discussed in many places, including
http://puzzling.stackexchange.com/q...blue-eyes-problem-why-is-the-oracle-necessary
https://en.wikipedia.org/wiki/Common_knowledge_(logic)
http://math.stackexchange.com/questions/489308/blue-eyes-a-logic-puzzle

Since the puzzle is explained in those and many other places, I will assume that readers are familiar with the problem, so I will not explain what the problem is. I want to discuss the solution(s).

I have my own solution of the problem. (Perhaps someone already proposed that solution, but I am not aware of that.) In short, my solution is that the solution of the problem is not unique. There are (at least) two solutions, and from the formulation of the problem it is impossible to eliminate one of them. One solution (the obvious one) is that nobody will do anything, and another solution (the standard one) is that they will all commit suicides after 100 days. In a sense, both solutions are "correct".

Let me explain. At the beginning of the puzzle it is said that all people are "perfect logicians". But that means absolutely nothing. There is no such thing as "perfect logic". If you open a logic textbook, you will find chapters such as Propositional logic, Predicate logic, Second order logic, Modal logic, etc. But you will not find chapter entitled "Perfect logic", simply because neither of those types of logic is "perfect". Each kind of logic has its own principles of inference, and in general there is no purely logical way to determine when to apply which kind of logic. The principles of inference for each kind of logic are defined by humans, not given by God. It is left to the human intuition (not to the human logic) to decide when to use which kind of logic.

So, to get to the point, the two different solutions of the blue-eye problem correspond to an application of two different types of logic. It is not predefined which type of logic should be used (it is only said that "perfect logic" should be used, but that means nothing), so it is impossible to give a unique answer. In this sense, the problem is not well posed.

To conclude, the paradox stems from the false belief that there is such thing as "perfect logic", seducively suggesting that the solution should be unique. But there isn't. You must use one type of reasoning or the other, and neither of them is perfect or necessarily better than the other.

 

[mfb]

Is the whole thread about the word "perfect"? It just means they don't make mistakes, and know all the mathematics. They are not performing "perfect logic", they are performing logic flawlessly.

One solution (the obvious one) is that nobody will do anything

Where does that come from, and why is it "obvious"?

 

[Demystifier]

Is the whole thread about the word "perfect"? It just means they don't make mistakes, and know all the mathematics. They are not performing "perfect logic", they are performing logic flawlessly.

Suppose that I ask you if parallel lines ever intersect, if you knew all the mathematics and don't make mistakes what would you answer? You would answer that it depends on the kind of geometry one uses (Euclidean vs Non-Euclidean), so the answer is not unique.

Where does that come from, and why is it "obvious"?

The prophet said them something that they already knew, so there is no reason to change anything in their behavior.

 

[micromass]

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

 

[Demystifier]

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

That's the right question! Unfortunately, I am not so skilled in formal logic. Perhaps you could do that? But let me explain my intuitive idea.

In the standard solution of the problem, what new information is provided by the prophet? Let n be the number of people with blue eyes.
- In the case n=1, the new information for the blue-eyer is that somebody has blue eyes.
- In the case n=2, the new information for the blue-eyers is that all blue-eyers know that somebody has blue eyes.
- In the case n=3, the new information for the blue-eyers is that all blue-eyers know that all blue-eyers know that somebody has blue eyes.
...
So the standard solution of the problem requires a logic in which finite sentences of the form "I know that you know that I know that you know that I know ..." are legitimate sentences with well defined meaning. I am not sure about that, but it seems to me that sentences of that form are not legitimate and well defined in all kinds of formal logic. According to the wikipedia link I gave in the first post, it seems that such reasoning requires modal logic, but I am certainly not an expert in formal modal logic so I cannot tell much more about that.

 

[mfb]

Suppose that I ask you if parallel lines ever intersect, if you knew all the mathematics and don't make mistakes what would you answer? You would answer that it depends on the kind of geometry one uses (Euclidean vs Non-Euclidean), so the answer is not unique.

Okay, but how does that apply to our situation? Where do you see the "alternative logic" that would be relevant?
"it seems to me that sentences of that form are not legitimate and well defined in all kinds of formal logic" is not really an argument. Be specific.

The prophet said them something that they already knew, so there is no reason to change anything in their behavior.

That is not true, and it is the typical logical fallacy that leads to the wrong answer - they are flawless mathematicians, they would not fall for that fallacy. They gained common knowledge that did not exist before.

 

[micromass]

The point is that "flawless mathematician" is an empty phrase. It needs to be defined accurately in order for this puzzle to have a resolution. I agree with demystifier on this.

 

[micromass]

That's the right question! Unfortunately, I am not so skilled in formal logic. Perhaps you could do that? But let me explain my intuitive idea.

You could try constructivist logic. In constructivist logic, we use the same language, but the truth values have a different interpretation. Saying "there exists something with that property" is only true if you give a complete construction of this object. So the prophet saying "there is somebody with blue eyes" might be true for the prophet who can construct this, but not necessarily for somebody else since the phrase is meaningless without giving a specific construction of who has blue eyes.

 

[fresh_42]

This paradox reminded me on a riddle from Martin Gardner and somehow seems to be a long version of it:
http://puzzling.stackexchange.com/questions/2323/unexpected-hanging-paradox

 

[Stephen Tashi]

So the standard solution of the problem requires a logic in which finite sentences of the form "I know that you know that I know that you know that I know ..." are legitimate sentences with well defined meaning. I am not sure about that, but it seems to me that sentences of that form are not legitimate and well defined in all kinds of formal logic.

That reminds me of the curious and cryptic book "Laws Of Form" by G. Spencer Brown https://en.wikipedia.org/wiki/Laws_of_Form.

The book (as I interpreted it) proposed a logic which applied to sentences that could be assigned infinite sequences of truth values. The sequence associated with a proposition $P$ would be {T, T, T, T,...} if it was true and a non-recursive sentence. The sequence associated with a recursive sentence like $P \equiv ( P \implies \lnot P)$ would be {T, F, T, F, T,...} if it was "initially" true.

The Wikipedia article has a more sophisticated sounding interpretation of "Laws of Form" than mine. Perhaps some of the the more traditional topics in logic it mentions are relevant to recursive sentences.

 

[Demystifier]

I have found a new solution to the problem, perhaps more natural then the two solutions (do nothing or commit suicide after exactly 100 days) that we already know.

Here is the logic (in informal form). Before prophet said that there is somebody with blue eyes, the citizens already knew the law that they have to commit suicide at the day they find out that they have blue eyes. So at some point in the past they had to acquire that knowledge. That could happen in many different ways. One possibility is that somebody told them when they were all together. In this case it was logical to start from that day with applying the logic which will eventually result in massive suicide after 100 days. So when prophet said that somebody has blue eyes, it made no change; the 100 day clock was already ticking. Since they were still alive when the prophet said what he said, it follows that they acquired the knowledge of the law before no more than 100 days. So the final solution is that, when the prophet says what he does, they will commit massive suicide after 100 days or less.

More generally, from this solution we see that it may be very important to know how the citizens acquired the knowlesdge of the law. Since it is not specified in the formulation of the problem, the solution of the problem is far from being unique.

 

[mfb]

One possibility is that somebody told them when they were all together. In this case it was logical to start from that day with applying the logic which will eventually result in massive suicide after 100 days.

There is nothing that would start if you just tell them about the suicide rule.

Consider the same puzzle with just two monks, then it is easier to follow the logic.

 

[Demystifier]

There is nothing that would start if you just tell them about the suicide rule.

Consider the same puzzle with just two monks, then it is easier to follow the logic.

Ok, there are two monks, monk1 and monk 2. They both have blue eyes. One day someone tells them about the new suicide rule. The logic is this:
Day 1:
- monk 1: I hope my eyes are not blue. In this case monk 2 will see that, so he will commit suicide today.
Day 2:
- monk 1: Sh*t, monk 2 did not yet commit suicide. That means my hope was wrong. I have blue eyes too. I have to commit suicide today.

As you see, there is something that would start their action in the case of two blue-eyers. The similar would be the case with more than two blue-eyers. Only in the case of only one blue-eyer there would be nothing to start the action.

 

[mfb]

Day 1:
- monk 1: I hope my eyes are not blue. In this case monk 2 will see that, so he will commit suicide today.

Why should monk 2 commit suicide? No matter which eye color monk 1 has, he cannot know his own eye color. "Both have brown eyes" is a possible scenario for monk 2 if monk 1 has brown eyes.

"At least one of you has blue eyes" is exactly the information that starts the process: every monk then knows "okay, if I have brown eyes, then the other monk gains information, and will commit suicide". "Crap, he didn't commit suicide, which means I have blue eyes as well".Edit: Improved phrasing.

 

[Stephen Tashi]

Here is the logic (in informal form).

We can encounter paradoxes and ambiguity when we make an application of mathematics (including an application of logic). Such rough spots aren't really problems of "logic". They are problems involving the inadequacy or ambiguity of our models.

In your solutions, you introduce the model of "time". The model of the problem also contains a model of how individual persons perceive certain information and make deductions from it. So you are dealing with more than pure "logic".

An objection to your solution of the form: "Your model isn't the only possible interpretation of the problem" doesn't bear on the matter of a "logical" paradox. It only points out an ambiguity in the statement of the problem.

micromass questions:

Why should monk 2 commit suicide? No matter which eye color monk 1 has, he cannot know his own eye color. They could both have brown eyes.

This asserts you have incorporated information in your solution that is not in the original problem. However, if the original problem has enough ambiguity in it to preclude unique solutions then any model of it which has a unique solution would have to add information.

 

[Demystifier]

"At least one of you has blue eyes" is exactly the information that starts the process

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.

 

[Demystifier]

We can encounter paradoxes and ambiguity when we make an application of mathematics (including an application of logic). Such rough spots aren't really problems of "logic". They are problems involving the inadequacy or ambiguity of our models.

In your solutions, you introduce the model of "time". The model of the problem also contains a model of how individual persons perceive certain information and make deductions from it. So you are dealing with more than pure "logic".

An objection to your solution of the form: "Your model isn't the only possible interpretation of the problem" doesn't bear on the matter of a "logical" paradox. It only points out an ambiguity in the statement of the problem.

micromass questions:

This asserts you have incorporated information in your solution that is not in the original problem. However, if the original problem has enough ambiguity in it to preclude unique solutions then any model of it which has a unique solution would have to add information.

In other words, would you agree that the initial problem, as formulated, can be thought of as a non-categorical set of axioms?

 

[Stephen Tashi]

In other words, would you agree that the initial problem, as formulated, can be thought of as a non-categorical set of axioms?

I don't understand the terminology "non-categorical".

The initial problem (in any of its variations) has implicit content that is not expressible in terms of straightforward mathematical structures (e.g. sets of numbers, statements about lattices etc.). For example, formulating the problem in terms of "monks" involves creating a model of something that can perceive and reason (in an idealized and deterministic fashion). Whether a monk knows that at least one monk has blue eyes It is not a question of pure "logic" or pure mathematics. It involves having a mental model of the capabilities and behaviors of a "monk".

I suppose one could rigorously describe such a model of a "monk" by stating a computer algorithm that models how monks perceive and reason. Intuitivey, I think that if one were to describe the problem precisely enough to formulate a computer simulation of it then the simulation would provide "the" answer.

One possibility is that the "paradox" involved in the problem is that the given information in the problem an be modeled in different ways and that different ways give different answers. In that case the "paradox" is due to the problem being ill-posed.

Another possiblity, is that no model can be found that is consistent with the given information in the problem. Does this make the "paradoxical" nature of the problem interesting? Is that situation more interesting that being given a problem that contains an outright contradiction - such as "Given x = 5 and x = 6, find..." ?

 

[Demystifier]

I don't understand the terminology "non-categorical".

http://modeltheory.wikia.com/wiki/Categoricity

 

[Stephen Tashi]

http://modeltheory.wikia.com/wiki/Categoricity

That would explain things, once I have an explanation of "model theory" and what kind of isomorphism is being used in that article.

Formal languages are an abstract topic. On the one hand, a computer language is probably a formal language. But I don't know whether the sequence of execution implied by a computer language can be expressed in the definition of a formal language. If we must simulate what monks do day-by-day then we need a program to do something, not merely to be "well formed".

 

[mfb]

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.

They know that, but they don't know the other monk knows that. Without the stranger, monk 1 does not know if monk 2 knows that at least one monk has blue eyes. With the stranger, monk 1 can be sure monk 2 knows about the existence of at least one monk with blue eyes. And vice versa of course.

 

[Demystifier]

Without the stranger, monk 1 does not know if monk 2 knows that at least one monk has blue eyes.

Suppose that there are 3 blue-eyes monks. Then monk1 knows that (monk2 knows that (monk3 has blue eyes)). Therefore monk1 knows that (monk2 knows that (at least one monk has blue eyes)).

 

[Demystifier]

Self-reference?

Many logical paradoxes involve self-reference. Is it possible that the blue-eyes paradox also involves a hidden self-reference? Certainly there is no self-reference in the formulation of the problem. But I suspect that the standard solution (massive suicide after 100 days) of the problem contains some sort of self-reference, which might be the reason why this solution looks weird. Indeed, the solution contains reasoning of the form "Monk1 knows that monk2 knows that monk1 knows", which looks like self-reference.

 

[fresh_42]

Are there restrictions on the numbers of eye colors? Because if there were only one brown-eyed monk, what prevents him from committing suicide?

 

[mfb]

Suppose that there are 3 blue-eyes monks. Then monk1 knows that (monk2 knows that (monk3 has blue eyes)). Therefore monk1 knows that (monk2 knows that (at least one monk has blue eyes)).

But monk 1 does not know that (monk 2 knows that monk 3 knows that someone has blue eyes): If monk 1 has brown eyes, then monk 2 has to consider "monk 3 is the only one with blue eyes" as valid option, in that case monk 3 would not know that someone has blue eyes.

The 2-monk problem already contains the full complexity of the 100-monk problem. Understand it with 2 monks (and given that you escape to 3, I guess you did), and you can generalize to 100.

Are there restrictions on the numbers of eye colors? Because if there were only one brown-eyed monk, what prevents him from committing suicide?

They should commit suicide (or leave the island, or whatever) if and only if they are sure they have blue eyes, or if they are sure about their eye color (depends on the problem statement). The monk with brown eyes does not know he has brown eyes.

 

[Demystifier]

If monk 1 has brown eyes

But it is not a valid possibility, given that I stipulated that all 3 monks have blue eyes.

Understand it with 2 monks (and given that you escape to 3, I guess you did)

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.

 

[Demystifier]

Are there restrictions on the numbers of eye colors? Because if there were only one brown-eyed monk, what prevents him from committing suicide?

Obviously, if he is a brown-eyer, no reasonable kind of logic should make him conclude that he is a blue-eyer. That would be a false conclusion, and false conclusions cannot result from reasonable logic.

 

[mfb]

But it is not a valid possibility, given that I stipulated that all 3 monks have blue eyes.

Monk 1 does not know that. He has to take "I have brown eyes" into account as possible situation.

 

[fresh_42]

Obviously, if he is a brown-eyer, no reasonable kind of logic should not make him conclude that he is a blue-eyer. That would be a false conclusion, and false conclusions cannot result from reasonable logic.

But isn't that true for the last blue-eyer as well? I'm not sure, but I try to apply the same deduction rules to the opposite point of view which might result in "there is no leave at all".

 

[Demystifier]

Monk 1 does not know that. He has to take "I have brown eyes" into account as possible situation.

OK, let us take it into account. In fact, let us write down explicitly all the possibilities.

From the point of view monk1, there are two basic possibilities:
1. blue blue blue
2. brown blue blue
Here "brown blue blue" means monk1 has brown eyes, monk2 has blue eyes, etc. and bolding shows whose perspective is this.

In the first case we can consider two subcases
1.1 blue blue blue
1.2 blue brown blue
while in the second case we can consider another two subcases
2.1 brown blue blue
2.2 brown brown blue
You can see that in all subcases 1.1, 1.2, 1.3 and 1.4, monk2 (the bolded one) can see at least one (non-bolded) blue.

Hence, 1 and 2 show that monk1 knows that there is at least one blue, while 1.1, 1.2, 1.3 and 1.4 show that monk1 knows that monk2 knows that there is at least one blue.

Similarly, instead of subcases 1.1, 1.2, 1.3 and 1.4 one can consider subcases
1.1' blue blue blue
1.2' blue blue brown
2.1' brown blue blue
2.2' brown blue brown
This shows that monk1 knows that monk3 knows that there is at least one blue.

I hope you can follow my bookkeeping conventions, because if you can the rest should be easy.

 

[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.