Blue-Eye Paradox: Solution Not Unique

[bahamagreen]

There are 2 possible reasons why people on that island don't discuss eye color:
1. They see others with blue eyes, but they don't want to provoke mass suicides, so they don't discuss eye color.
2. There were similar events (mass suicides) in the history of the island, and assuming that blue eyes could be a recessive gene and new babies could be born with blue eyes people don't discuss eye color to prevent suicides in the future, even they don't see any people with blue eyes NOW in the current population.
3 both

So from "people avoid discussions about eye color" you can't deduce "there are some people with blue eyes".

So the following quote is not true:
Each person's individual knowledge of other's eye color is based on never having been allowed to discuss eye color, so all they know is that they have observed two eye colors and any individual they observe may be classed as one or the other

- "there is no discussion of eye color" is a given without explanation, nor needing one

- I did not deduce nor claim anyone deduced "there are some people with blue eyes"

- nothing you wrote disputes the truth of my quoted statement, or is even
relevant

I don't think you understand the puzzle

 

[Buzz Bloom]

Since no one has responded to the question I asked in my post #201,

A. IF exactly one person on the island has blue eyes, THEN that person will know the s/he has blue eyes.

A has the form: IF X THEN Y. X and Y are the underlined statements. If it is assumed (everyone knows that) k>1, then X is FALSE. Therefore, (everyone knows that) A is TRUE before the visitor makes his announcement!

Can anyone spot the logical flaw here?
​

I offer my own answer.

X is not a statement about a possible, but unknown, true or false state of the island which happens to be false. It is instead a hypothetical statement about a possible different island (or different false state of the same island). As I understand the "paradox", the required logic regarding A is not 2-valued, that is each of X, Y, and A each are either TRUE or FALSE. Rather, the 3 possible truth values should be TRUE, FALSE, HYPOTHETICAL.

If X and Y can have the only the values TRUE and FALSE, then A will also be limited to these two values.
If the value of X is HYPOTHETICAL, then A also has the value HYPOTHETICAL. For this case, there are two possible rules for the value of Y, and the choice of the Y value determines the system of logic being used.

Y can be chosen as TRUE or HYPOTHETICAL.​

In the context of the paradox, the choice is TRUE. Thus A is not known to be TRUE (since it HYPOTHETICAL). When the guru makes the announcement, the TRUE value of Y permits the induction to be made that produces

C. IF there are exactly k persons on the island with blue eyes, THEN on k-1 days after A becomes known, all k of these persons will come to know that they have blue eyes.​

If the nuns are instead using the logic system in which Y has the value HYPOTHETICAL, then with k>1 the blue eyed nuns will not deduce that they have blue eyes.
In writing the above, I have become aware that my previous presentation of the induction is flawed. It should have been described in term of the following:

If any nun, say N, sees k other nuns with blue eyes, then if after k days all of these nuns demonstrate they know they have blue eyes then N knows she has green eyes, else N knows she has blue eyes.​

 

[bahamagreen]

Can anyone spot the logical flaw here?

Regards,
Buzz

I think I see a flaw in the form of the puzzle itself - see post #205

 

[Buzz Bloom]

I think I see a flaw in the form of the puzzle itself - see post #205

Hi bahamagreen:

Thank you for your post.

The (possible) flaw you mention is not related to logical construct I was asking about in my post #201.

I think it is reasonable in verbalizing a puzzle to skip mentioning every conceivable relevant element of everyone's knowledge that is common to almost all humans. In the is case, your "flaw" is remedied by mentioning that everyone knows the names of the common colors like blue and green and what these colors look like to them each person individually. Of course, different people see colors differently, and for those colors that are between two named colors, different people will define the boundary differently.

Regards,
Buzz

 

[bahamagreen]

Hi bahamagreen:

Thank you for your post.

The (possible) flaw you mention is not related to logical construct I was asking about in my post #201.

I think it is reasonable in verbalizing a puzzle to skip mentioning every conceivable relevant element of everyone's knowledge that is common to almost all humans. In the is case, your "flaw" is remedied by mentioning that everyone knows the names of the common colors like blue and green and what these colors look like to them each person individually. Of course, different people see colors differently, and for those colors that are between two named colors, different people will define the boundary differently.

Regards,
Buzz

How does knowing names of the colors remedy the flaw that no islander can know which of the colors is subject to the rule if prohibited from discussing eye color?
What form of representation of the rule does not contravene the discussion prohibition?
The most critical implication of the careful language of the puzzle is that the islanders do not know which eye color is subject to the rule.

 

[Buzz Bloom]

How does knowing names of the colors remedy the flaw that no islander can know which of the colors is subject to the rule if prohibited from discussing eye color?

Hi bahamagreen:

I apologize for misunderstanding the point you were making in your earlier post #205.

The Wikipedia version of the "paradox" does say:

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

This could possibly be interpreted as: "No one, including the visiting outsider, is allowed to discuss eye color." However, the text also says,

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".​

I would interpret this as meaning that the rule does not apply to the visitor. I suppose it would not hurt the problem description if this were said explicitly.

Regards,
Buzz

 

[andrewkirk]

numBlue(0) ≥ 1
What does the "0" represent?
Does the notation mean that
(a) there are more than one blue eyed person on the island, OR
(b) the guru sees that there are more than one blue eyed person on the island, OR
(c) everyone knows that at there are more than one blue eyed person on the island?

The statement is (1) a wff in the language ##L0_d## and (2) is an axiom of ##T0_d##. The statement, considered purely from within ##L0_d##, and hence ignoring (2) (because (2) cannot be expressed in ##L0_d##), says (a). However, reasoning from within a higher level language, ##L0_{d+1}## or above, the fact of (2) can also be taken into account, which enables the statement to be interpreted to mean (c), because ##T0_d## is the set of propositions known by everybody on day ##d##.

Formally, the statement ##numBlue(0)\geq 1##, interpreted from within ##L0_d##, means (a), whereas the following statement in ##L_{d+1}## or higher:
$$'T0_d'\vdash_{L_d}{}'numBlue(0)\geq 1'$$
means (c). The quotes are put around the two sides of the statement to show that they are terms that refer to formulas or collections of formulas in a lower level language, rather than formulas in the higher level language.

Also, I am pretty sure it is sufficient to consider only what the (members of the class of) blue eyed "nuns" see and know.

I'm pretty sure you are correct about that. I decided not to include a proof of that because the whole proof works easily enough, and I think is slightly shorter than it would otherwise be, without it.

 

[Ken G]

Incidentally, one can ask what would actually happen in this situation. If we are using the version where suicide of the tribe occurs (first all the blue-eyed people, and then the next day, all the brown-eyed people, assuming there are fewer blue-eyed people), that would be regarded as an unacceptable solution for the tribe. But they can avoid it, all they have to do is have people voluntarily leave the tribe, perhaps by random lottery. The lottery need only continue until a blue-eyed person leaves, and all the rest are then saved. I offer that this is what a tribe of logicians would actually do in that situation.

 

[Buzz Bloom]

BTW: I am working on the text for a new puzzle related to the discussion of this thread. I hope to post the puzzle in a new thread in a day or so.

I have posted the new puzzle as

https://www.physicsforums.com/threa...-on-the-blue-eye-paradox.882191/#post-5544579​

 

[bahamagreen]

Hi bahamagreen:

I apologize for misunderstanding the point you were making in your earlier post #205.

The Wikipedia version of the "paradox" does say:

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

This could possibly be interpreted as: "No one, including the visiting outsider, is allowed to discuss eye color." However, the text also says,

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".​

I would interpret this as meaning that the rule does not apply to the visitor. I suppose it would not hurt the problem description if this were said explicitly.

Regards,
Buzz

That's not it... the rule (that blue eyed that know it leave) and prohibition (no discussion) clearly don't apply to the oracle/visitor.
The problem is that when the islanders hear, "At least one of you has blue eyes", that means nothing to them because none of the islanders has ever known, nor knows after the public announcement, whether it is the blue or brown eye color that is subject to the rule.
And that is assuming they even know of some rule.
Prior to the announcement, how would any islander ever know of the rule that some must leave and the eye color subject to it?
How does the announcement address either of those lacks of information?

 

[Buzz Bloom]

whether it is the blue or brown eye color that is subject to the rule.

Hi bahamagreen:

I apologize again for misunderstanding your point.

The Wikipedia statement of the paradox includes the following:

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​

I think this text is reasonably clear that all the people living on the island know this rule, although the text does not explain how they came to know the rule. Do you think that the text needs to also include this explanation?

Regards,
Buzz

 

[bahamagreen]

Hi bahamagreen:

I apologize again for misunderstanding your point.

The Wikipedia statement of the paradox includes the following:

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​

I think this text is reasonably clear that all the people living on the island know this rule, although the text does not explain how they came to know the rule. Do you think that the text needs to also include this explanation?

Regards,
Buzz

Somehow the islanders need to know the rule; it is at the heart of the puzzle.
But, in order to not break the prohibition on discussing eye color, this rule can't be learned from one's family, nor in school, nor from the clergy, etc.
For the sake of the puzzle, perhaps one could imagine that the rule appears inscribed on some central structure on the island, its origin a mystery going back to their prehistory... so no body needs to "discuss" it in order to know it... kind of a loophole, but the puzzle needs that the rule to be universally known.

 

[Buzz Bloom]

For the sake of the puzzle, perhaps one could imagine that the rule appears inscribed on some central structure on the island

Hi bahamagreen:

If you look at the various ways this paradox has been presented, it is clear that different presenters have different ideas about how to present it. If sometime you feel like introducing the paradox to some people who have not seen it before, I for one see no harm in including your explanation of how the rule became known to the islanders.

Regards,
Buzz

 

[Buzz Bloom]

I have been thinking some more about the point @bahamagreen made in post #221, and I have decided that my suggestions and conclusions in my previous posts are wrong.

One of the lessons I have learned during my life is that it is difficult to avoid confusing oneself regarding a problem in which the givens are inconsistent with the known properties of reality. One's natural inclination is to think about a problem using what one knows is true in the real world, but that leads to errors in working on a problem with known false assumptions. One kind of such error is succumbing to the temptation to add more assumptions.

The Wikipedia form of the "paradox" includes (1):

The problem: assuming all persons on the island are completely logical and that this too is common knowledge, what is the eventual outcome?​

The counter-reality assumption given in this problem is underlined. It certainly in reality is false for a newborn.

The following is another quote the Wikipedia presentation (2):

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

The presentation does not say a person who discovers that they have blue eyes will leave the island. Certainly a newborn who learns they have blue eyes will not be able to leave the island without assistance, and if no one else knows that the newborn has made this discovery, no one will provide this assistance. Also, there is no stated obligation regarding someone, say A, who knows that someone else, say B, has discovered that they have blue eyes, that A must do something about making sure that B does what B must do according to the rule. Thus, there are no consequences if some blue-eyed person knowingly breaks the rule. Thus there is no way that a blue-eyed person's failure to leave the island, when it is deduced that that have an obligation to do so, can logically allow someone to know their own eye color.

Thus the answer to (1)'s question is: the ultimate outcome is that the visitor's announcement has no effect, and no one leave the island.

 

[Ken G]

To me, the problem is in giving an operational meaning to the term "knowing." Can a "perfect logician" really "know" anything? Certainly a perfect logician would be able to use logic to conclude that they might be wrong in any theorem they believe they have proven. This is kind of a dirty little secret of mathematics, which is that what is regarded as a proven theorem is anything that has been sufficiently vetted by an appropriate set of professional mathematicians, that is actually the only operational definition for a proof in mathematics. So should we regard "perfect logic" as a form of mathematics that we never do and have never seen? It would certainly introduce problems in bringing this puzzle into contact with the real world. Since the whole crux of the puzzle is the concept of what you can know about what someone else knows, it all has to begin with a careful operational definition of knowing, something that philosophers have struggled to produce for thousands of years, without a whole lot of success. Ironically, knowledge about what other people know is a concept we use all the time in real life-- without having a formal operational meaning for it.

 

[.Scott]

To me, the problem is in giving an operational meaning to the term "knowing." Can a "perfect logician" really "know" anything?

Perhaps you have heard the story about the Physicist, the Mathematician, and the Logician traveling by train through Scotland. After passing many white sheep, the Physicist spots a black sheep and announces "Look, there are black sheep in Scotland". The Mathematician corrects him saying "We only know that there is one black sheep in Scotland". Then the Logician advises "We know that one side of one sheep in Scotland is black".

 

[Buzz Bloom]

To me, the problem is in giving an operational meaning to the term "knowing." Can a "perfect logician" really "know" anything?

Hi Ken:

I may be mistaken, but I don't see this as an impediment to "solving" the stated problem. If it is reasonable to doubt the reality of an island person using "perfect logician" skills to logically deduce, and thereby come to know one's own eye color, then this would be an example of the need to assume for the purpose of a problem that a statement given as "true" which is not true in the real world, must be accepted as truth anyway for the purpose solving the problem.

I would expect that the originator of this "paradox" would expect anyone, say S, who is capable of solving the puzzle: (1) has the necessary logical skills to do this, and (2) expect that S is to assume the "perfect logician" islanders have logical skills comparable to S. I agree that there exists logical "proofs" that are so difficult that the protocol I quote below is necessary to for anyone to have "knowledge" that the conclusion is correct. However, I find that the "proofs" needed by some S, and also by the islanders, are not that difficult.

what is regarded as a proven theorem is anything that has been sufficiently vetted by an appropriate set of professional mathematicians

Regards,
Buzz

 

[Ken G]

Perhaps you have heard the story about the Physicist, the Mathematician, and the Logician traveling by train through Scotland. After passing many white sheep, the Physicist spots a black sheep and announces "Look, there are black sheep in Scotland". The Mathematician corrects him saying "We only know that there is one black sheep in Scotland". Then the Logician advises "We know that one side of one sheep in Scotland is black".

Exactly, it is always hard to export mathematical logic into the real world.

 

[Ken G]

If it is reasonable to doubt the reality of an island person using "perfect logician" skills to logically deduce, and thereby come to know one's own eye color, then this would be an example of the need to assume for the purpose of a problem that a statement given as "true" which is not true in the real world, must be accepted as truth anyway for the purpose solving the problem.

But the problem is, this puzzle is expressed in terms that involve people on an island, in other words, a real world situation. That is certainly a stretch, but the puzzle would be so much less interesting if it was framed in more formal logical terms. The puzzle involves what people can know about what other people know, which is what is so interesting about the puzzle-- we usually only concern ourselves with what we ourselves know, or maybe even what we know about what someone else knows, but how often do we worry about what person A knows about what person B knows about what person C knows about what person D knows? This puzzle is probably the first time any of us have even encountered a "chain of knowing" that is that long. But the whole idea of a chain of knowing like that is about what people know, not about formal logical connections that could be replaced by a relationship between a series of numbers or something like that. If the puzzle is arithemetic, it's not interesting, but if it is about what people on an island can conclude with their brains, it is interesting-- but that's also the flaw in it, because it forces us to have an understanding of what knowing is that we don't actually have.

I would expect that the originator of this "paradox" would expect anyone, say S, who is capable of solving the puzzle: (1) has the necessary logical skills to do this, and (2) expect that S is to assume the "perfect logician" islanders have logical skills comparable to S. I agree that there exists logical "proofs" that are so difficult that the protocol I quote below is necessary to for anyone to have "knowledge" that the conclusion is correct. However, I find that the "proofs" needed by some S, and also by the islanders, are not that difficult.

Yet look at the comments of posters on this thread. Some have concluded that the islanders would not need to leave! Shall we say those posters are not as good of logicians as those who are convinced that a proof exists that the islanders will leave? But then who is to say which are the "perfect logicians," might not a perfect logician understand the pitfalls in the concept of a perfect logician? So how can we know that none of the "perfect logicians" on the island will think like the posters who reject the proofs that they do indeed know their eye color? The problem I see is that even when a mathematician regards a proof as correct, he/she doesn't know it's correct, because they are aware that they could always be mistaken. So if that's the only kind of logic we've ever encountered, what other type can we be talking about? But still, I agree with you that objections like this, albeit important for the concept of what knowing is and what logic is, are not what is interesting about the puzzle, and it's probably better to simply take the puzzle at face value and not worry about our lack of an operational definition of what it means to know something!

 

[Buzz Bloom]

But the problem is, this puzzle is expressed in terms that involve people on an island, in other words, a real world situation.

Hi Ken:

Thanks for your post.

I have the impression that you are disagreeing with me about what I said in the first quote of your previous post. However, I am not sure I get what the disagreement is. Perhaps it is a disagreement about Ken's point I quoted in my post #226. I agree with Ken there there are some issues with the statement of the problem, but I don't see that the issues require a resolution by a body of mathematical logic authorities.

I see that some posts have pursued an analysis of a long series of "What A knows that B knows that C knows ..." I don't see any need for this complex approach. The logical issues I see with the problem statement are not that complex. For example, you might look at my posts #201 and #223.

Regards,
Buzz

 

[Buzz Bloom]

I have posted my solution to the puzzle I posted in
https://www.physicsforums.com/threads/a-new-puzzle-based-on-the-blue-eye-paradox.882191/ .

 

[Ken G]

I see that some posts have pursued an analysis of a long series of "What A knows that B knows that C knows ..." I don't see any need for this complex approach.

Then you do not understand the puzzle. Tracking what people know about what other people know about what other people know is the central issue.

For example, you might look at my posts #201 and #223.

Those objections are not significant, we can simply assert that the tribe does not include newborns, as that would violate the terms that they are all perfect logicians, and we don't care how they all know the rules of the game (and know that all others know the rules, etc.), we simply assert that they do, and go from there. None of that seems plausible grounds for claiming they cannot know their eye color, except insofar as we have difficulty establishing what it means to know something. I agree it is an extreme philosophical difficulty to establish an operational definition of knowing that dovetails with the concept of perfect logic, so that is a fundamental flaw in this puzzle, but we can simply decide to either make that flaw be what the puzzle is about, or we can set aside that flaw and follow more formal logic that is unconcerned with problems surrounding knowing things. Thus I agree that your effort to reframe the puzzle as a kind of team competition, involving strategy rather than formal "knowing", is a good way to avoid that problem, but winning strategy in a game like that still involves tracking what other people know about what other people know. (And the problem is that with multiple teams, there is at some point a good reason to guess without knowing, so that problem would need to be fixed up. )

For example, one might try an operational definition of "knowing" that goes something like "I will say I know something if I would bet $1000 against $1 that it is true", but this is not going to be a definition that has no problems of its own. Knowing is a difficult concept to put into a puzzle.

 

[Buzz Bloom]

Then you do not understand the puzzle. Tracking what people know about what other people know about what other people know is the central issue.

Hi Ken:

Thank you for your post. It is now clearer to me what our disagreement is about.

In my posts #201 and #211 I explain my reasoning for the conclusion that one can "prove" the required proposition WITHOUT any necessity to consider a chain knowledge for a series of individuals. It is sufficient to consider (given a hypothetical assumption that there are N blue-eyed persons) only what all members of two collections know. The two collections are:

(1) all the blue-eyed persons,
(2) all the blue-eyed persons which one arbitrarily chosen blue-eyed person sees.​

I would much appreciate you looking at and commenting on my posts #201 and #211.

At the end of #211 I also explain what I see as a logical flaw in my analysis. This flaw has nothing to do with issues about chains of knowledge of individuals. I see it as the heart of the "paradox" issue.

The following is a quote about the definitions of "paradox".

From http://www.merriam-webster.com/dictionary/paradox
a : a statement that is seemingly https://www.physicsforums.com/javascript:void(0) or opposed to common sense and yet is perhaps true
b : a self-contradictory statement that at first seems true
c : an argument that apparently derives self-contradictory conclusions by valid deduction from acceptable premises​

I find the Blue-eyed Paradox to be of type c. It seem possible to logically "prove" (without the logic not getting too complex) both of the following propositions:
1. The entire collection of N blue-eyed persons will leave the island exactly N days after the visitor makes his announcement.
2. Nothing will happen as a result of the visitor's announcement.

In my posts I first present a "proof" by induction of proposition (1). Then the demonstration of the flaw "proves" proposition (2).

Regards,
Buzz

 

[andrewkirk]

I see that some posts have pursued an analysis of a long series of "What A knows that B knows that C knows ..." I don't see any need for this complex approach.

The question is whether you are able to present a rigorous proof that does not use the logical equivalent of that 'chain of knowing'. I believe it is impossible. If you think it is, I encourage you to try.

In my posts #201 and #211 I explain my reasoning for the conclusion that one can "prove" the required proposition WITHOUT any necessity to consider a chain knowledge for a series of individuals

Those two posts do not contain proofs. At most they contain an outline of the direction in which one might start searching for a proof.

Discussion of whether your feeling that the problem can be solved without a chain of knowing can be validated with a proof, is pure speculation, until an attempt at constructing such a proof has been made and presented for critique. I have offered up for critique my attempt at a rigorous proof that does use a chain of knowing and, given that so far nobody has identified any errors in it, I am pretty confident that it is valid.

 

[Buzz Bloom]

Hi andrewkirk:

I have offered up for critique my attempt at a rigorous proof that does use a chain of knowing and, given that so far nobody has identified any errors in it, I am pretty confident that it is valid.

I would very much like to be able to analyze your proposed proof to see if I could find errors, but I confess I don't have the skills to do that.

I am very interested in seeing a proof using notation I can understand which will make clear why the visitor's announcement is necessary. Does your proof make this clear? If so, what specific part of the proof does that? I tend to doubt that can be done rigorously, so I wonder if you could explain in English explicitly what the visitor's announcement changed.

The question is whether you are able to present a rigorous proof that does not use the logical equivalent of that 'chain of knowing'. I believe it is impossible. If you think it is, I encourage you to try.

I also confess I may not have the skills to develop a rigorous formal proof, but I will make a try at it. Whatever I might produce will certainly not contain the current "standard" notations that you used in your proof since I am unfamiliar with those notations, and I believe I am unlikely to be able to become sufficiently familiar with these notations to use them without making errors.

Regards,
Buzz

 

[Ken G]

In my posts #201 and #211 I explain my reasoning for the conclusion that one can "prove" the required proposition WITHOUT any necessity to consider a chain knowledge for a series of individuals.

The problems with your reasoning is that your post #201 contains two incorrect claims. The first is this:
"What the stranger changed is that the following which was not previously known has also become known by everyone from the stranger's statement.
A. IF exactly one person on the island has blue eyes, THEN that person will know the s/he has blue eyes."

Your IF/THEN is only of significance in the case that there is either one or two blue-eyed persons. But those are both rather trivial cases for the puzzle, the interesting case is when there are at least three, so everyone can see at least two. If everyone sees at least two, then your conditional is of no importance-- no one cares about the hypothetical of there being only one blue-eyed people if everyone already knows that conditional is false. The reasoning only becomes important when people start thinking about what other people know about what other people know, that's where the puzzle appears.

The second flaw is this claim:
"The following conditional everyone already also previously knew.
B. IF there were exactly k persons on the island with blue eyes, AND on day, say D, they all came to know that they had blue eyes, THEN
IF there were exactly k+1 persons on the island with blue eyes, THEN on day D+1 they will all come to know that they had blue eyes."

That IF/THEN statement doesn't make any sense, because you have two contradicting conditionals in the IF parts that are linked by a THEN. It is like saying IF x>0 AND y<0 THEN IF x<0 THEN something else. That cannot be a useful statement, just by its structure.

The following is a quote about the definitions of "paradox".

The puzzle is not a paradox. In effect, the puzzle is to figure out why it's not a paradox. The seeming paradox is that the visitor is telling them all something they already know, and indeed he is. But that's not what causes the problem, what causes the problem is that he is telling them things about what other people know. To see that this is true, simply change the situation so that the visitor talks to each person privately, says what he says, but does not tell anyone what he says to anyone else. You will see there is no problem there. This proves why the puzzle is about knowledge about what others know about what others know about what others know, etc.

 

[Buzz Bloom]

Hi Ken:

Thank you for your comments.

I think that my lack of logical formality caused some confusion. I was attempting to show informally the two propositions

P(1) and
P(k) ⇒ P(k+1),​

from which inductive reasoning proves a general statement, P(N), (which all the blue-eyed people know) and which says that all of the blue eyed people will be required to leave the island at a specified time depending on their number. (In order to make this "proof" valid, it is necessary to assume (something like): "Everyone who a rule requires to do something will actually do it."

I will attempt to prepare a formal proof to show this, but it will take me a while.

The puzzle is not a paradox. In effect, the puzzle is to figure out why it's not a paradox. The seeming paradox is that the visitor is telling them all something they already know, and indeed he is. But that's not what causes the problem, what causes the problem is that he is telling them things about what other people know.

I am OK with this viewpoint. That is why I hope you will respond to the following.

Does your proof make this clear? If so, what specific part of the proof does that? I tend to doubt that can be done rigorously, so I wonder if you could explain in English explicitly what the visitor's announcement changed.

Regards,
Buzz

 

[Ken G]

Let us take the simplest case of 2 blue eyed people, as that's when the puzzle starts to get interesting. In that case, everyone already knows there are blue-eyed people in the tribe, so the visitor's statement is already known. That's why if the visitor says it in private to every tribe member, they just say "yes, I know", and that's the end of it. But if the visitor says it to all of them at once, and they all see that it was said to all of them, then they learn something they did not know before-- they know that the others know there are blue-eyed people in the tribe.

Now take the case of 3 blue eyed people. They all know there are blue eyed people, and they all know they all know there are blue eyed people. But they do not all know that they all know that they all know that there are blue-eyed people. So that is the new information if there are 3 blue eyed people.

And so on.

 

[Buzz Bloom]

Hi Ken:

I get what you are saying for N= 1, N= 2, and N=3. I am guessing you intend to extend this concept for all value of N, presumably by induction. If I am correct, this is similar to what I said in my Post #175. I am suggesting that the inductive process involves only two kinds of propositions, P_n and PP (see below), and all the others can be deduced from those. P_n and PP are both defined in terms of another series of propositions K_n.

N is the count of the actual number of blue-eyed people on the island.
n is the assumed count of the hypothetical number of blue-eyed people on the island.​

K_n states what everyone knows related to the existence on the island of at least one blue-eyed person, including a conjunction of all necessary nesting: "Everyone knows that everyone knows that ...", including a limit of the nesting and the number of terms in the conjunction equal to n.

P₁: IF X₁ THEN K₁​

What is required is to prove

P*: P_n is TRUE for n=1 to N.​

To do this by induction, two propositions need to be proved:

P₁ and
PP: IF P_n THEN P_n+1​

After proving P*, the next task is to prove R*. This task has a similar structure to proving P*. R* involves proving a series R_n.

R*: R_n is TRUE for n=1 to N.​

R_n states that if there are n blue-eyed people on the island, then all will leave the island n days after the visitors announcement. This is also proved by induction, based on proving two propositions.

R₁ and
RR: IF R_n THEN R_n+1​

I haven't thought much about proving PP, but RR seems rather simple to prove. However, I am running out of time to continue this now. Intuitively, I don't think proving RR requires proving PP.

If my guess is correct about your inductive proof of PP, then I would much appreciate seeing an explanation of how you would prove PP.Buzz

 

[andrewkirk]

I am very interested in seeing a proof using notation I can understand which will make clear why the visitor's announcement is necessary. Does your proof make this clear? If so, what specific part of the proof does that?

The visitor's announcement is necessary to my proof. Proving that no proof can be constructed without using it would be much more difficult, as proving a negative nearly always is. For instance, we cannot be certain that the yeti does not exist, just because there are no reliable reports of somebody having seen one. I am confident that no proof can be constructed without the oracle's announcement, but I have not proven that.

The announcement is necessary to my proof via the following mechanism:
- it is formally stated in axiom 1 of the theory ##T0_0## (on page 4), which is the set of things that all nuns know at 1pm on day 0. The statement is that the number of blues is at least 1, ie what the oracle said.
- that axiom is then used to prove the base case of the induction proof in ##L^\ddagger##. See the statement on page 8 that 'the base case ##\psi(0)## follows directtly from axiom 1 of ##T0_0##...'. Without proving that base case, the induction cannot succeed.

 

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