A Blue-Eye Paradox: Solution Not Unique

[maline]

Proving that no proof can be constructed without using it would be much more difficult, as proving a negative nearly always is

Oh, I had thought you agreed to what I wrote that showing two situations conforming to the axioms, with differing colors for a particular nun, is sufficient because we can use the desired situations as models to translate wff's in our languages to wff's of ZF, or whatever underlying system we are using.

 

[Ken G]

No induction is necessary, the puzzle can simply specify the number of people with blue eyes, and the logic follows based on people knowing what other people know, enumerated out to whatever degree is necessary. Hence, no induction.

 

[andrewkirk]

No induction is necessary, the puzzle can simply specify the number of people with blue eyes, and the logic follows based on people knowing what other people know, enumerated out to whatever degree is necessary. Hence, no induction.

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.

That is generally the case for non-transfinite induction. Given a hard-coded number, a proof can be created simply by writing out the induction step that number of times, changing the numbers at each iteration. 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.

Of course, if the hard-coded number is large, such as 100, it is much quicker to write the proof using induction than to write out the induction step 100 times.

 

[andrewkirk]

@maline I haven't yet been able to convince myself of that. I put it on the backburner while I worked on constructing the rigorous proof that, given n blues, they will all leave no later than the nth day.
Since that's all finished, it's now opportune to re-engage with that issue. Can you outline how you think one might do the proof using a model-based approach? I thought I got the gist of it earlier, but now I'm not so sure.

thanks

Andrew

 

[Ken G]

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.

My point was that the puzzle can be stated in a way that is still the same puzzle, with all the same interesting elements, yet not require induction. So induction is a bit of a red herring to worry about.

Of course, if the hard-coded number is large, such as 100, it is much quicker to write the proof using induction than to write out the induction step 100 times.

Yes, one would use induction if the number was large, but if someone thinks there is some kind of problem with the induction, the problem can be sidestepped by avoiding it. Some people seem generally suspicious of induction.

Those types of suspicions, by the way, relate to the problems mentioned above in a concept of a "perfect logician." Which logic is being applied perfectly? So the puzzle always has flaws surrounding what can be known and what is perfect logic, but I still find it a very cute puzzle despite those limitations.

 

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