Blue-Eye Paradox: Solution Not Unique

[maline]

Can you outline how you think one might do the proof using a model-based approach?

If explicit definitions are given for all the undefined terms in all the languages- what axioms exactly each person has at each level, numerical values for how many blues she sees (on each day), etc. then as long as we are satisfied that all the terms are well-defined in ZF, and that our meta-axioms are in fact theorems of ZF under some such model, (because they are true given the situation described), then consistency of ZF implies consistency of these axioms- as axioms, no matter how they are modeled.
Since a wff can be defined as a ZF object, and the relation of "implication" can be definrd as well, it should be possible to model each nun's knowledge at each level as a ZF set (of whatever wff's are in the formalization).

 

[maline]

Each such set, at level k, will be interpreted to describe a set of possible states for each nun's knowledge at level k-1. Each such state can be thought of as a sub-model of its own.
Then what we need to do is show that for any possible setup of who is actually blue, for each nun m, at every level k, and on the first day considered, there is a sub-model corresponding to the assumption that m is blue, and another corresponding to the opposite. Both of these fulfill all m's level k axioms, so m's color is undecidable at level k. The axiom about all valid deductions being made at level k-1 can simply be stated (in ZF terms) without additional checking. It cannot lead to any inconsistency, because even if someone leaves, it will not be until later that day. So the undecidability on the first day is actually rather trivial. We can conclude that no one leaves on the first day. But since in every sub- model and sub-sub- model etc. the same applies, including of course the sub-sub-sub-model in which no one is blue at all, the new information that no one leaves on the first day will not affect the consistency of any of the sub-sub- models. Therefore in also will not affect the undecidabality for the second day, and by induction, no one ever leaves.

 

[maline]

As a matter of fact, it's probably not necessary to model the whole problem and translate the meta language. The important thing is to translate the languages corresponding to the nuns' knowledge at each level k-1, so that undecidability at level k can be proved.

 

[stevendaryl]

That works if the number is specified as a hard-coded number (constant), rather than a pronumeral (variable). If it is a pronumeral, induction is needed.

Right. In mathematical logic, there is a distinction between

• For all numerals $n$, the statement $\phi(n)$ is provable.
• The statement $\forall x \phi(x)$ is provable.

Without using induction, the first can be true, without the second being true. (Actually, even with induction, that can be the case; for example, a statement such as "Every integer greater than 2 can be written as the sum of two prime numbers" (Goldbach's conjecture) might be provable for each integer, even if the general statement is not provable.

 

[Buzz Bloom]

The axiom about all valid deductions being made at level k-1 can simply be stated (in ZF terms)

Hi maline:

I tried to locate a meaning for "ZF" but failed to do so. Would you please post a definition and a reference?

Regards,
Buzz

 

[stevendaryl]

I tried to locate a meaning for "ZF" but failed to do so. Would you please post a definition and a reference?

ZF is Zermelo-Frankel set theory, which is a framework for for formulating mathematics in terms of pure sets. It's not actually important for this discussion, other than being some kind of standard for rigorous mathematical proofs--in theory, just about anything proved about integers, reals, functions, etc., can be formalized as a formal proof in ZF (or ZFC or ZF + something or other).

 

[Buzz Bloom]

The principle of induction only needs to be used when we wish to state the theorem using a pronumeral rather than a hard-coded number.

Hi andrewkirk:

I think you are making the following point. The OP problem does not give a specific value for the number, say N, of blue-eyed people on the island. Therefore N is pronumeral, Therefore a induction proof is needed.

Is this correct?

Regards,
Buzz

 

[Buzz Bloom]

ZF is Zermelo-Frankel set theory

Hi Steven:

Thanks for your prompt post answering my question.

Regards,
Buzz

 

[stevendaryl]

Hi andrewkirk:

I think you are making the following point. The OP problem does not give a specific value for the number, say N, of blue-eyed people on the island. Therefore N is pronumeral, Therefore a induction proof is needed.

Is this correct?

Regards,
Buzz

There is an informal use of something equivalent to induction, which is to say: "Suppose there are 3 people on the island". Then you show how the proof goes in this case. Then you say "There was nothing special about the number 3, so it obviously works the same for any number of islanders". That last step can be error-prone, though. It's very easy to take advantage of some unique fact about whatever number you use as an example without realizing it.

 

[Buzz Bloom]

it is formally stated in axiom 1 of the theory T00T0_0 (on page 4)

Hi andrewkirk:

I was unable to find your post on page 4 with "axiom 1". Did you mean (1) your post #204 on page 11?

that axiom is then used to prove the base case of the induction proof in L‡L^\ddagger. See the statement on page 8 that 'the base case ψ(0)\psi(0) follows directtly from axiom 1 of T00T0_0...'. Without proving that base case, the induction cannot succeed.

What I am getting from your post #239 is that you are referring to some general formal logic principles for rigorously using an inductive proof. Is that correct? If so, then what I need to see, in order to understand what you are doing, is an English interpretation of ω(0).

Regards,
Buzz

 

[Ken G]

What I would like to point out is that we could have said there were 10 blue-eyed people, and 90 brown-eyed people, and everything that is interesting about that puzzle is still there. So let us not confuse what is interesting about this puzzle with what is interesting about inductive reasoning, because that latter issue can be in a thread on induction and need not be connected to this puzzle.

 

[stevendaryl]

What I would like to point out is that we could have said there were 10 blue-eyed people, and 90 brown-eyed people, and everything that is interesting about that puzzle is still there. So let us not confuse what is interesting about this puzzle with what is interesting about inductive reasoning, because that latter issue can be in a thread on induction and need not be connected to this puzzle.

As I pointed out in another post, there is a distinction between "inductive reasoning", which is a heuristic technique for coming up with general laws based on a small number of examples, and "mathematical induction", which is a mathematically rigorous way to prove a general statement about all nonnegative integers by showing that the case for $n$ logically reduces to the case for $n-1$. I would say that your case for 10 people does involve something like mathematical induction, because you use the result for 9 people to prove the case for 10 people.

 

[Ken G]

If there are 10 blue eyed people, there is never any using the case of 9 to prove anything. It's simply taking the two possible cases, 9 or 10, and eliminating 9 (for a blue-eyed logician). That's not induction, it's like proving that if a real number is not negative or zero then it is positive. The way to eliminate 9 can be enumerated explicitly (though it would of course be tedious), but this still means that nothing like induction would be necessary, so none of the problems with inductive logic need to appear in the solution of this puzzle. I'm only saying this to eliminate any objections that people have about induction, as if this puzzle somehow relies on induction.

The key point here is that the links from 10 to 9 to 8 and so on are not inductive links, they are links between what people know about what other people know. That's not induction, it's just a chain of knowledge that counts downward.

 

[stevendaryl]

If there are 10 blue eyed people, there is never any using the case of 9 to prove anything. It's simply taking the two possible cases, 9 or 10, and eliminating 9. That's not induction, it's like proving that if a real number is not negative or zero then it is positive.

But how do you eliminate the possibility that there are 9?

Suppose there are 10 blue-eyed people, and someone announces that there is at least 1 blue-eyed person. Each blue-eyed person knows already that there are at least 9 blue-eyed people, so there are two possibilities, as you say:

Either there are 9 blue-eyed people, or there are 10 blue-eyed people.

How do you eliminate the possibility that there are 9? The only way is to reason: "If there were only 9, then they would figure this out by day 9". But how do you prove that?

 

[Ken G]

It is true that the number 10 must count downward through 9, 8, etc., but this isn't induction, it's a chain of what people know about what other people know. Let's do it for 3 blue-eyed people in the tribe. We'll say person A has blue eyes, and sees that B and C also do. Before the visitor, A knows that B knows that there are blue- eyed people, but A does not know that B knows that C knows there are blue-eyed people. There is no induction here, that's just a true statement. When the visitor says there are blue-eyed people, then A knows that B knows that C knows there are blue-eyed people. But if A knows that B knows that C knows there are blue-eyed people, and A knows that B knows that C sees B's eyes, then if A is brown-eyed (that's the reasoning by case, not induction), then A knows that B knows that C will expect B to leave the island on day 1. When B does not, information is gained on day 1. More information is gained on day 2, etc. So there's just no induction there, it's simply knowledge about what other people know, coupled with the new information gained each day that those people don't leave the island. The entire reasoning can be explicitly enumerated if the number of blue-eyed people is known. Making that number a variable does not introduce induction when induction is not necessary for any given number.

Now, induction is an elegant method to prove the result here, but it is not required-- a more tedious option is available. Making the number a variable does not by itself introduce induction, induction is an optional choice to increase elegance and conciseness, but it is not really part of the puzzle. The puzzle is about how knowledge of what other people know interacts with knowledge gained from watching their behavior day after day.

 

[stevendaryl]

The key point here is that the links from 10 to 9 to 8 and so on are not inductive links, they are links between what people know about what other people know. That's not induction, it's just a chain of knowledge that counts downward.

That's what mathematical induction is. You're proving a statement about $n=10$ by using an analogous statement about $n=9$, which uses an analogous statement about $n=8$, etc.

 

[stevendaryl]

The entire reasoning can be explicitly enumerated if the number of blue-eyed people is known. Making that number a variable does not introduce induction when induction is not necessary for any given number.

I say that induction is the essential element here. You can't make a conclusion about the case $n=10$ without already knowing about the case $n=9$, which involves the case $n=8$, etc.

[edit]

Okay, I sort of see what you mean. If you have 10 people, Alice, Bob, Carol, Dan, ..., John, then you can arrange it so that Alice is worrying about what Bob knows, who is worrying about what Carol knows, etc. That is, you can ignore the symmetry between their situations. But to me, it seems like that would be going out of your way to avoid it being an induction.

Mathematical induction is a special case of a more general type of reasoning, which is reasoning on well-founded binary relations, which means ordering the statements in a way that makes the truth of one statement follow from the truth of lower-level statements. It seems to me that your non-inductive way of reasoning about it is just substituting a different well-founded relation.

 

[Ken G]

But there are not "analogous statements" being cited as such anywhere in the proof, there is simply A tracking the reasoning of B tracking the reasoning of C, etc. It's a simple chain of logic that can be explicitly enumerated. It only becomes induction if you want to prove something like "the blue eyes leave on day N for any N", because then you cannot explicitly enumerate it. If you can explicitly enumerate the solution for some N, there's no induction there, it's explicit.

I think what you are saying is there is some kind of self-similar spirit to the logic here, and that is certainly true. But that isn't induction, because the self-similarity is not a formal property, the proof never refers to any such self-similarity. It is merely something that we get a sense of, it's not part of the proof anywhere (unless induction is actually invoked to make the proof more elegant, but this is not necessary). So what I really mean is, one cannot dispute an explicit proof on the grounds that induction is being invoked and there is some problem with induction. It's for the people who think logic does not lead to the people leaving the island.

 

[stevendaryl]

But there are not "analogous statements" being cited as such anywhere in the proof, there is simply A tracking the reasoning of B tracking the reasoning of C, etc. It's a simple chain of logic that can be explicitly enumerated.

I really don't see the distinction that you are making.

 

[Ken G]

How do you formalize your claim that the statements are "analogous", in an explicitly enumerated proof that never uses that property?

The distinction I'm making is that between proofs that require induction, so require the formalization of some kind of internal symmetry property that is being iterated automatically, from proofs that are explicitly enumerated in ways that allow us, if we like, to observe self-similar looking embedded arguments. The latter cannot be objected to on the grounds that they require induction. In particular, it is not correct that this puzzle requires induction to give a solution when the number of blue eyes are explicit, it is only correct to say that the chain of logic will have informally evident self-similar elements that still work in a logical system that does not allow induction.

The issue relates to things like the prisoner who can only be executed on a day he does not know he will be executed, where a faulty application of induction into a logical system not built to support it leads to nonsensical conclusions.

 

[stevendaryl]

The distinction I'm making is that between proofs that require induction, so require the formalization of some kind of internal symmetry property that is being iterated automatically, from proofs that are explicitly enumerated in ways that allow us, if we like, to observe self-similar looking embedded arguments.

Well, the heart of a proof by induction is the proof that the case for $n$ reduces to the case for $n-1$. That core is present in this problem. You're right, that if the number of islanders is given explicitly as 10, then it is not necessary to establish that for all $n$, the case for $n$ reduces to the case for $n-1$, it's only necessary to establish it for $n=1, n=2, n=3, ... n=10$. But as far as the reasoning in this case, it's not any easier to establish it for the $10$ instances than it is to establish it for the general case.

 

[Buzz Bloom]

Hi @andrewkirk:

I agree with you that there are ambiguities in the Wikipedia statement of the problem, which I quote below for convenience.

On an island, there are k people who have blue eyes, and the rest of the people have green eyes. At the start of the puzzle, no one on the island ever knows their own eye color. By rule, if a person on the island ever discovers they have blue eyes, that person must leave the island at dawn; anyone not making such a discovery always sleeps until after dawn. On the island, each person knows every other person's eye color, there are no reflective surfaces, and there is no discussion of eye color.

At some point, an outsider comes to the island, calls together all the people on the island, and makes the following public announcement: "At least one of you has blue eyes". The outsider, furthermore, is known by all to be truthful, and all know that all know this, and so on: it is common knowledge that he is truthful, and thus it becomes common knowledge that there is at least one islander who has blue eyes. The problem: assuming all persons on the island are completely logical and that this too is common knowledge, what is the eventual outcome?​

In your post #84, you discuss the ambiguity in the text: "all persons on the island are completely logical". I want to discuss that ambiguity with you, but before I do that I thought it would be useful to mention another ambiguity:

By rule, if a person on the island ever discovers they have blue eyes, that person must leave the island at dawn​

The ambiguity is due to the two underlined elements. There are two possible interpretations.
1. The rule specifies that a person has an obligation to leave the island at dawn the day following their ascertaining that they have blue eyes. However, there is no specification that a person who has the obligation will actually leave.
2. The "rule" is not just a rule, but rather it is some "wired in the brain programming", and "must" means "has an uncontrollable compulsion to".

Using (1) would produce the conclusion that no one has the knowledge that if someone deduced that they had blue eyes that person would actually leave the island. That means the answer to the puzzle is: No one leaves he island. (2) is the more interesting case, so perhaps the puzzle text would be improved by using some appropriate text to express (2) to replace the "By rule ..." text.

In #84 you deal with the ambiguity by deciding the puzzle had no valid answer. There are ways to improve the text of the puzzle to produce what I think is the most likely (but not the only possible) intention of the originator of the puzzle.
I would appreciate your help in coming up with such improved text. I am not completely happy with my attempt at it below:

All persons on the island are experts in and completely adept at using first order two-valued predicate logic, and they all know that what they deduce using this logic is TRUE regarding both hypothetical worlds as well as the world in which they live, and that all of this is also common knowledge.​

With this change in the text the answer to the puzzle is the following:

Given that there are N blue eyed person on the island, All N of them will leave the island N days after the visitor makes his/her announcement.​

I have no doubt that there are many ways that this result can be "proved", possibly including the one I outline in my post #238.

I would much appreciate any comments.

I plan to post another resolution of this ambiguity in another post at a later time.

Regards,
Buzz

 

[stevendaryl]

I agree with you that there are ambiguities in the Wikipedia statement of the problem

In these sorts of puzzles, if there is an interpretation under which the problem has no interesting solutions, then that is obviously not the correct interpretation.

 

[Buzz Bloom]

In these sorts of puzzles, if there is an interpretation under which the problem has no interesting solutions, then that is obviously not the correct interpretation.

Hi Steven:

I agree completely. I also think that if there is an interpretation under which a puzzle has no interesting solutions, it would help readers if the text were changed to eliminate that interpretation.

I think the alternative interpretation I plan to explore later is interesting, but I recognize that others may disagree.

BTW: Do think a conclusion that a puzzle has no solution would be interesting or not?

Regards,
Buzz

 

[stevendaryl]

Hi Steven:

I agree completely. I also think that if there is an interpretation under which a puzzle has no interesting solutions, it would help readers if the text were changed to eliminate that interpretation.

Maybe, but that's a lot of extra trouble for nothing, in my opinion. If the ambiguity actually causes problems, in the sense that someone goes down a blind alley under a misinterpretation about what was actually meant, then there is a need to clarify it. But if it's just a case of someone being able to say: "Ha ha! I found a solution that the original author missed by interpreting his words in a different way!", I don't see that that's a problem. If someone gets pleasure out of finding loopholes, why deny them the opportunity?

BTW: Do think a conclusion that a puzzle has no solution would be interesting or not?

The fact that something has no solution might indeed be very interesting. It depends on the puzzle.

 

[Ken G]

Well, the heart of a proof by induction is the proof that the case for $n$ reduces to the case for $n-1$. That core is present in this problem. You're right, that if the number of islanders is given explicitly as 10, then it is not necessary to establish that for all $n$, the case for $n$ reduces to the case for $n-1$, it's only necessary to establish it for $n=1, n=2, n=3, ... n=10$. But as far as the reasoning in this case, it's not any easier to establish it for the $10$ instances than it is to establish it for the general case.

That's all true, all I'm saying is there is no need for any inductive axiom to solve a specific version of this puzzle. Yet the puzzle is still interesting. So the puzzle is not about the use of an inductive axiom, it's about the chain of logic you can produce by tracking what people know, and how they gain new information each day. So people who object to any proofs on the basis of how the induction is being done do not have a relevant objection to the puzzle solution. The discussion seemed in danger of getting off on a tangent about the use of inductive axioms, but what is interesting about the puzzle does not involve inductive axioms.

In other words, if you are using something that is true for N, and you are showing that if it is true for N, it is true for N+1, you are not invoking any additional information input to go from the N to the N+1 case. But in this puzzle, it is crucial that there is information input-- there is the new information that no one left on day N. That's what is crucial, and a proof for a given N can be supplied by explicitly enumerating all the possibilities, so induction is never necessary. Thus the puzzle isn't about induction, it is about how new information each day culls the possibilities when you think about what other people know. Induction is merely an elegant path to a solution, it's not a requirement so it cannot be the reason the puzzle works. If I generate the integers from 1 to 10 by adding 1 to each previous one, I may notice a certain self-similarity to what I am doing, but I am not doing induction because I have not invoked any inductive axioms.

An example would be, if I wanted to prove that all the integers from 1 to 10 are >0 and <11, I could simply enumerate the list, and the proof is done without induction. Or, I could say that if N>0, then N+1>0, and if N<11, then N-1<11, and prove it by noting that N=1 > 0 and N=10 < 11 and apply induction in both directions to show that all the numbers in the list are both > 0 and <11. The latter is shorter and more elegant, especially if the numbers get large, but the former proof is still a valid solution that is not inductive.

 

[andrewkirk]

Hi andrewkirk:

I think you are making the following point. The OP problem does not give a specific value for the number, say N, of blue-eyed people on the island. Therefore N is pronumeral, Therefore a induction proof is needed.

Is this correct?

Regards,
Buzz

Yes, that is correct.

I was unable to find your post on page 4 with "axiom 1". Did you mean (1) your post #204 on page 11?

The page reference is to page 4 of the linked proof, not page 4 of this thread.

 

[Buzz Bloom]

But there are not "analogous statements" being cited as such anywhere in the proof, there is simply A tracking the reasoning of B tracking the reasoning of C, etc. It's a simple chain of logic that can be explicitly enumerated.

Hi Ken:

I confess thinking about the complex chain of A knows that B knows, etc. gives me a headache.
@andrewkirk, in his post #271, agrees that an induction proof is needed to prove the result for the OP puzzle. From the above quote I get that you disagree with this for any specific case when N, the number of blue-eyed persons, is specified.

For the case when N=4, can you post just an informal outline of the steps in such a non-inductive proof? My intuition tells me that somewhere in the proof, even without induction, you will need to specifically prove something of the form:

IF N=1 THEN X.​

The alternative interpretation of "all persons on the island are completely logical" (which I mentioned in my post #266 that I would discuss in another post) will discuss the logical use of the above proposition in different plausible logic systems, leading to different results.

Regards,
Buzz

 

[Ken G]

For the case when N=4, can you post just an informal outline of the steps in such a non-inductive proof? My intuition tells me that somewhere in the proof, even without induction, you will need to specifically prove something of the form:

IF N=1 THEN X.​

If N=4, I will never need anything that says if N=1. Everyone in the tribe knows that N is either 3 or 4, so there is never an "if N=1", that would be an irrelevant hypothetical to all concerned. Here is an entirely non-inductive proof for N=4:

Let us say that the blue eyed people are named A, B, C, and D. Let us follow the logic of A. Prior to the visitor's statement, A knows that B knows that C knows there are blue-eyed people. However, A does not know that B knows that C knows that D knows there are blue-eyed people. After the visitor's statement, A does know that, and this is what makes all the difference. Since A now knows that B knows that C knows that D knows there are blue-eyed people, A will leave on day 4, and here is the proof of that.

It all starts with the key "IF":
IF A has brown eyes, then:
___B sees 2 blue eyed people, C and D. A knows that B will follow the following logic:
______B: IF I have brown eyes, then C only sees 1 person with blue eyes, and that is D. So B can conclude this will be C's logic:
___________C: IF I have brown eyes, then D will leave on day 1. But when day 1 comes and D does not leave, C concludes that he/she
___________has blue eyes also, which means that C and D will leave on day 2.
_______BUT that does not happen, so B knows that B has blue eyes also, and B, C, and D leave on day 3.
___BUT that does not happen, so the IF that started it all off must not be true.
THUS A has blue eyes.

Notice how the proof involves A thinking about what B is thinking about what C is thinking about what D is doing or not doing. We simply add the information that no one leaves on days 1, 2, or 3 wherever in that thinking that information is relevant, and we get the proof. There is no induction anywhere in this proof, there is only the nesting of one person thinking about another person thinking about another person.



​

 

[Buzz Bloom]

Hi Ken:

Thank you very much for your post. I now understand your logic, and I am impressed that the logic is completely clear without any need of inscrutable formal notation.

I think your demonstration is a clear example of what @stevendaryl said in his post #248.

I will need to take some time to think about the implications this has on my former thinking.

Regards,
Buzz

 

[maline]

and I am impressed that the logic is completely clear without any need of inscrutable formal notation.

The inscutable formal notation was introduced only to prove that the problem and its solution are in fact logically rigorous. It was never designed to be user friendly. There have been several fairly clear "natural language" presentations of the solution earlier in the thread.

 

[Buzz Bloom]

The inscutable formal notation was introduced only to prove that the problem and its solution are in fact logically rigorous.. . . . There have been several fairly clear "natural language" presentations of the solution earlier in the thread.

Hi maline:

My reference to the notation issue was to express my personal frustration regarding my own inadequacies.

I apologize for not noticing the other clear "natural language" proofs among the 275 posts of this thread. If you would post the post numbers for some of these, I would much appreciate it.

Regards,
Buzz