A Blue-Eye Paradox: Solution Not Unique

  • A
  • Thread starter Thread starter Demystifier
  • Start date Start date
  • Tags Tags
    Paradox
  • #51
I think now you are nitpicking just for the sake of it. It is possible to phrase the problem clear enough to remove all those issues. Don't blame strawman problem statements if you don't understand the solution to the problem.

I don't see progress here, my last post in this thread.
 
Physics news on Phys.org
  • #52
Let's take the 3 monks example you mentioned in the P#22 and 30... Let's first of all define the state... I will call B the Blue eyes (RIPers) and R the Red eyes (survivors)...
The possible states are: 2^3/2 = 4
RRR, RRB, RBB, BBB

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

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

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

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

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

*More precisely, not important according to some interpretations of the problem. E.g. it is not important in the interpretation in which all the monks were informed about the law in the past, when another prophet told them the law when they were all together. This is certainly a logical possibility, and perfectly logical reasoning should not dismiss any logical possibility.
 
Last edited:
  • #54
mfb said:
I think now you are nitpicking just for the sake of it.
It's about logic. From the point of view of other mathematicians, most of the research in logic is nitpicking just for the sake of it. So yes, I am nitpicking, but that's what logic is about.

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

mfb said:
Don't blame strawman problem statements if you don't understand the solution to the problem.
I understand the standard solution, and I agree that the solution is valid. I just don't agree that the solution is unique. That's because the problem, as stated, can be interpreted in many inequivalent ways. Or to use the language of mathematical logic, the stated set of axioms has many inequivalent models.
 
Last edited:
  • #55
What is special about n=3?

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

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

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

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

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

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

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

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

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

...

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

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

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

Comment: In the standard solution, one uses induction starting with ##n=1##. That induction can be interpreted as a proof that all levels of knowledge are relevant. However, in the standard solution it is not obvious that such induction is legitimate. The principle of induction is an unproved axiom by itself. What I propose is to reject the axiom according to which the induction principle can be applied to all levels of knowledge, and replace it with my Axiom above.
 
Last edited:
  • #56
micromass said:
Demystifier, can you write out formal rules of the two logics that would have the opposite results?
One of the formal rules used in the standard solution is a certain version of the induction principle. (A version which refers to levels of knowledge.) In my last post above (the last paragraph of post #55), I have suggested that it seems reasonable to reject such a version of the induction principle. I would like to see what do you think of it.

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

EDIT: For a partial formalization, see also post #60 below.
 
Last edited:
  • #57
The induction starts from what you [who don't know your eye-color] see per round and how you interpret it...

Would you find a reason why, in day 2, the two Bs in the BBB case wouldn't have commited suicide if the 3rd one was not a B?
 
  • #58
ChrisVer said:
Would you find a reason why, in day 2, the two Bs in the BBB case wouldn't have commited suicide if the 3rd one was not a B?
This question does not make sense to me. In the BBB case it cannot be that the 3rd one is not a B.
 
  • #59
Demystifier said:
This question does not make sense to me. In the BBB case it cannot be that the 3rd one is not a B.

You know that it's BBB because you know the initial state...
Let me rephrase it then to be clearer... how would the XBB state evolve with time? X is unknown (B or R)... In particular now we look at the state as seen by the eyes of 1 of the Bs...
 
  • #60
Axiom for n=3, formalization, and self-reference

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

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

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

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

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

Now consider the case of ##n=3## blue-eyers, denoted by ##B_1##, ##B_2##, and ##B_3##. Consider the statement
"All blue-eyers know that (all blue-eyers know that (all blue-eyers know ##x##))"
This is really a list of ##3^3=27## statements. Some of them contain resolvable self-references such as
##B_1B_1B_1x=B_1B_1x=B_1x##
But others, such as
##B_1B_2B_1x##
contain self-references which cannot be resolved by the Reflexivity rule. So how to avoid such self-referencing statements? What do they really (if anything) mean? Since it is not clear how to resolve such self-reference, it seams reasonable to adopt my Axiom which states that statements of the form "All blue-eyers know that (all blue-eyers know that (all blue-eyers know ##x##))" are simply discarded (or treated as meaningless, irrelevant).
 
Last edited:
  • #61
ChrisVer said:
You know that it's BBB because you know the initial state...
Let me rephrase it then to be clearer... how would the XBB state evolve with time? X is unknown (B or R)...
What do you mean by "unknown"? Unknown by who? By external observer? By X himself? By one of the two known B's? Without that information, I cannot answer your question.

ChrisVer said:
In particular now we look at the state as seen by the eyes of 1 of the Bs...
That cannot be from the point of view of one of known B's, because they know what is X. So it can only be from the point of view of X himself. Now I, as external observer, know that X=B, so I know that the actual situation is BBB. But of course, X does not know it yet, so this is how his evolution looks like:
Day 0: XBB. X knows that the two B's will not kill themselves at Day 1.
Day 1: XBB. The two B's do not kill themselves, just as X predicted. X hopes that X=R, in which case the two B's will kill themselves at Day 2.
Day 2: The two B's do not kill themselves.
Day 3: X observes that B's did not kill themselves. Therefore BBB. Therefore X has to kill himself at Day 3. All 3 of them kill themselves at Day 3.
 
  • #62
you just wrote down what the solution actually looks like...
however you said in D3 that "Therefore BBB", how did you deduce that if you didn't had to run back to RBB example?
 
  • #63
ChrisVer said:
you just wrote down what the solution actually looks like...
however you said in D3 that "Therefore BBB", how did you deduce that if you didn't had to run back to RBB example?
I see what you mean. Yes, one needs to run back to RBB, but only for reductio ad absurdum. To prove that something cannot be, one considers the possibility that it can be and derives a contradiction.

But I don't think that there is any disagreement between you and me on that. The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.
 
  • #64
Demystifier said:
The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.
As I said in a previous post, no you don't need a prophet for that case, because it is an extreme... watch out; not needing him does not mean you get something wrong if you include him. We can just say that in that particular case his existence is unecessary...
But in all other cases his presence is needed to reach a reliable answer... (as I mentioned the RRB state, in which without the prophet everybody'd die)...I guess the prophet makes the problem solvable in all cases then, and so he's necessary for the solution, and for some special cases his information is just repeating.
 
  • #65
The puzzle mentioned in the first stackexhange link cannot be reduced to n=3 without changing the puzzle. The original states there are 100 blue eyed and 100 brown eyed. Thus each non-guru can see several blue eyed and several green eyed people.

That the guru stating she sees at least one blue eyed person changes anything for anyone I don't get, but hey I didn't even take logic at uni.
 
  • #66
Lord Crc said:
That the guru stating she sees at least one blue eyed person changes anything for anyone I don't get, but hey I didn't even take logic at uni.
try working with 5 blues and 5 reds...
Lord Crc said:
The original states there are 100 blue eyed and 100 brown eyed.
the numbers 100-100 are arbitrary and can be set to whichever value you want... you can also deduce that by the statement that the inhabitants don't know the absolute numbers of blue/brown eyes...
 
  • #67
ChrisVer said:
try working with 5 blues and 5 reds...

I'll use the more conventional blue and brown: If person X has blue eyes he will see 4 people with blue eyes and 5 with brown eyes.

On day zero the Oracle comes and says she sees someone with blue eyes. Person X says "duh".

The case is symmetrical if you swap blue and brown, so each person sees 4 with their own color and 5 with the other color. They all say "duh" when the oracle shares her insight.
 
  • #68
Lord Crc said:
I'll use the more conventional blue and brown: If person X has blue eyes he will see 4 people with blue eyes and 5 with brown eyes.
I went with reds because it allows better the single letter representation B and R ... (while both Blue and Brown start with B).

Lord Crc said:
On day zero the Oracle comes and says she sees someone with blue eyes. Person X says "duh".
what would a person X do for the next day then?

my point is that this:
Lord Crc said:
cannot be reduced to n=3 without changing the puzzle.
is wrong, since the number n can be anything (even 1000-1000 with n=2000) by keeping the puzzle the same... that's why I sent you into solving the n=10 one...you'd eventually start building the solution as was built for the n=3.
 
  • #69
ChrisVer said:
what would a person X do for the next day then?

Well what could X do? X knows each person sees at least two other persons with blue eyes, thus X know that a) the oracle did not give X any new information and crucially b) the oracle did not give anyone else any new information (every person already saw at least one blue eyed before the oracle spoke).

That's why n matters, with n=3 say X cannot make this conclusion.
 
  • #70
From X's prespective however, he (X) is either Blue or Brown eyed...
What would happen in the case that you had 1 Blue and 9 Brown eyed people [without the input of the prophet]. The answer is that the Browns are going to kill themselves.
 
  • #71
ChrisVer said:
From X's prespective however, he (X) is either Blue or Brown eyed...
What would happen in the case that you had 1 Blue and 9 Brown eyed people [without the input of the prophet].
That is an entirely different scenario from the one described in the stack exchange post and thus it's hardly surpring it has a different result, no?
 
  • #72
Demystifier said:
The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.
Why not? Please explain in detail what chain of inferences could allow any of the monks to discover his own eye color, without the prophet's input. If you like you can define day zero as when the suicide law was instituted.
 
  • #73
Demystifier said:
I agree that prophet's information is important in RRR, RRB, and RBB cases. However, I think that prophet's information is not important* in the BBB case.
The prophets is not important in the case RBB. Everybody sees a B so no information was imparted by the prophet. Now I know that you have some fancy pants logic that says otherwise, using ten dollar words like "inference", but my logic is a perfectly good solution. I see that you brought up B. Russel, well of course, he is depicted on your icon. Well I told my solution to my mom, and she's a wonderful person and pretty damn smart too, and she agrees with my solution. So in the RBB case after the prophet speaks nothing new happens. That's my solution and I'm sticking to it.

I hope the monitors allow sarcasm.
 
  • #74
Lord Crc said:
That is an entirely different scenario from the one described in the stack exchange post and thus it's hardly surpring it has a different result, no?
It is the same problem where the numbers are changed a little (ratios of Blue/Brown)... the concepts are still the same, since the inhabitants never knew those ratios to start with... For example for an inhabitant with blue eyes, the numbers could as well be 99 Blues and 101 Browns (considering himself a brown eye) or 100 Blues and 100 Browns... similiarily for a brown-eyed person (after replacing Blue<->Brown).

Someone has to give some numbers in the start, in order to get an answer to the logical question (because the total number of days depend on the total number of blue-eyed). Why would that affect the total logic that leads to the solution? This logic utilizes only what 1 observes and takes as information and the fact that they are robot-like taking decisions.
 
  • #75
maline said:
Why not? Please explain in detail what chain of inferences could allow any of the monks to discover his own eye color, without the prophet's input. If you like you can define day zero as when the suicide law was instituted.

I think I understood that objection.. let's call day 0 the day that the rule becomes known to the 3B inhabitants...
Day 0: each B sees BB... he can't say that he is a !B
Day 1: Noone dies. Each B sees BB again... he still can't say that he is a !B
Day 2: Noone dies. Each B sees BB again... however if that B was a !B, the other two Bs would have died by this day***. He becomes certain he is a B.
Day 3: B dies... all of B die...

The prophet's input here is unnecessary as I mentioned to 1 post, I suspect due to the complete symmetry of the setup... In fact, I agree with Demystifier here; that in this special case the outcome is determined just by the rule itself... However, I disagree that this is a complete answer since there are cases where it cannot be applied without inconsistency to the game rules (so it's preferable to add an extra unnecessary to some cases parameter which makes the solution always existent for all, even those that it is not supposed to affect)*** if the mentioned B was a !B, one of the other two Bs would have been seeing a B(!B) and would have died by Day2.
 
Last edited:
  • #76
ChrisVer said:
It is the same problem where the numbers are changed a little (ratios of Blue/Brown)... the concepts are still the same, since the inhabitants never knew those ratios to start with...

The initial conditions give are that there are 100 blue-eyed and 100 brown-eyed, so we know nobody on the island is thinking maybe he's the only blue-eyed and the other 199 are all brown-eyed. Everyone on the island knows the distribution is either 99 blue-eyed and 101 brown-eyed, or vice versa.

In either of these two cases (as with your 5/5 example), an arbitrary person X can see at least two blue-eyed people, regardless of their own color. This means that an arbitrary person X knows that any other person Y can see at least one blue-eyed person, regardless of Y's color.

This is why I don't see how the Oracle's fact changes anything.

That you can get other solutions by changing the initial conditions is irrelevant, just as the other solutions to \lim_{x \to \infty} a^x are irrelevant if you ask me to find the limit when a \in (0, 1).
 
Last edited:
  • #77
Lord Crc said:
The initial conditions give are that there are 100 blue-eyed and 100 brown-eyed, so we know nobody on the island is thinking maybe he's the only blue-eyed and the other 199 are all brown-eyed. Everyone on the island knows the distribution is either 99 blue-eyed and 101 brown-eyed, or vice versa.
I am sorry I don't understand your point here...
I believe you turn the "paradox" in something extremely specialized. Well you can find a solution to this, but it won't be the general solution.
In particular the solution: y(x)=5 e^{x} is a solution to the differential equation \frac{dy}{dx} = y but it's a special case of a complete family of solutions that are y(x) = a e^{x}.
Not only that (which has nothing wrong in it), but by just looking at the particular data will lead you to something worse/wrong. As I demonstrated with the alternative initial condition state, you will reach an unreasonable result which violates the game rules.
So the presence of the prophet is 100% necessary to make all the cases solvable and so he well exists in the initial setup. It changes nothing in some cases, but also makes others solvable as well...

In the diff eq example above, you can end up with 5e^x being the solution to \frac{dy}{dx} = y ~~,~~y(0)=5 (taking a particular initial condition), but it's not the solution to \frac{dy}{dx} = y ~~,~~y(0)=1 or \frac{dy}{dx} = y ~~,~~y(0)=9... The y=a e^x is by setting a appropriately.

Lord Crc said:
That you can get other solutions by changing the initial conditions is irrelevant, just as the other solutions to limx→∞axlim_{x \to \infty} a^x are irrelevant if you ask me to find the limit when a∈(0,1)a \in (0, 1).
Well that's like a flaw... I am not going to think a lot about it at the moment, to see whether you would have to approach the limit differently depending on whether a is in (0,1) or !(0,1)... but I could take your example one step further and ask you if you'd find the limit differently if a=0.0001 or a=0.98 (randomly taken numbers).
 
  • #78
ChrisVer said:
I am sorry I don't understand your point here...

My point is that initial conditions in the original problem means that every person can see at least two other persons with blue eyes, and from that it follows (or at least, my brain tells me so) that every person already knows at least one person has blue eyes. The logic used to deduce this cannot work for all initial conditions, but does (at least, my brain tells me so) for the initial conditions given in the original problem.

ChrisVer said:
Well that's like a flaw... I am not going to think a lot about it at the moment, to see whether you would have to approach the limit differently depending on whether a is in (0,1) or !(0,1)...

Well for non-negative a it has three solutions, 0 for a \in [0, 1), 1 for a = 1 and \infty for a \in (1, \infty). But my point was that if you tell me a \in [0, 1), then the two other cases are irrelevant.

edit: I meant a \in [0, 1), getting a bit tired here.
 
  • #79
Demystifier said:
That cannot be from the point of view of one of known B's, because they know what is X. So it can only be from the point of view of X himself. Now I, as external observer, know that X=B, so I know that the actual situation is BBB. But of course, X does not know it yet, so this is how his evolution looks like:
Day 0: XBB. X knows that the two B's will not kill themselves at Day 1.
Day 1: XBB. The two B's do not kill themselves, just as X predicted. X hopes that X=R, in which case the two B's will kill themselves at Day 2.
Day 2: The two B's do not kill themselves.
Day 3: X observes that B's did not kill themselves. Therefore BBB. Therefore X has to kill himself at Day 3. All 3 of them kill themselves at Day 3.

Could you proof that in the RBB case it follows that the two B's will kill themselves at Day 2? You seemed to agree that the prophet is needed for that case!
 
  • Like
Likes maline
  • #80
Demystifier said:
another solution (the standard one) is that they will all commit suicides after 100 days
How does suicide come into it? I read carefully over the first link in the OP and glanced over the other two and couldn't see any mention of suicide. The key action is leaving the island. Why the refs to suicide and how do they relate to the problem as stated?
 
  • #81
Apparently, in an alternative formulation the rule is that they have to kill themselves as soon as they are sure they have blue eyes. Of course for the logic problem it is not important what action it actually is as long as it is a unique action visible to the others.
 
  • #82
andrewkirk said:
How does suicide come into it? I read carefully over the first link in the OP and glanced over the other two and couldn't see any mention of suicide. The key action is leaving the island. Why the refs to suicide and how do they relate to the problem as stated?

The setup was somehow changed from the departing inhabitants of an island, to monks who listen to a prophet and commit suicide.
 
  • #83
Lord Crc said:
The initial conditions give are that there are 100 blue-eyed and 100 brown-eyed, so we know nobody on the island is thinking maybe he's the only blue-eyed and the other 199 are all brown-eyed. Everyone on the island knows the distribution is either 99 blue-eyed and 101 brown-eyed, or vice versa.

Let's say there are 3 blue-eyed monks on the island, A,B and C, and that the prophet has not spoken yet. Then everyone knows that there are either 3 or 2 blue-eyed monks. In the perspective of A, he must consider two cases. Either he has blue eyes, or he has brown eyes. If A has blue eyes, then B and C see two monks with blue eyes. If A has brown eyes, then B and C see one monk with blue eyes. Due to the latter possibility, A concludes that B and C individually can not exclude the possibility that they in fact too have brown eyes.

If we further investigate this last case, then the last monk can not exclude the possibility that he has brown eyes as well. In other words, A further concludes that B cannot conclude that C can exclude the possibility of having brown eyes. Similarly, A concludes that C cannot conclude that B can exclude the possibility of having brown eyes. And of course, B and C will mirror these conclusions.

So everyone does not know that everyone knows there are 3 or 2 blue-eyed monks. The correct statement is that everyone knows that everyone knows that there are 3,2 or 1 blue-eyed monks. And by the argument above, the only correct statement in a further nesting would be that everyone knows that everyone knows that everyone knows that there are 3,2,1 or 0 blue-eyed monks. But once the prophet claims there are at least one blue-eyed monk, everyone strengthens this last statement to everyone knows that everyone knows that everyone knows that there are 3,2,1 blue-eyed monks. This is because everyone knows that everyone heard the prophets claim. And everyone knows that everyone knows that everyone heard the prophets claim. And so on...

This is the explanation of precicely how the prophet is actually giving additional information to everyone. This may be extended to the cases where there are more monks on the island. It is similar, but of course much longer for 100 monks.
 
  • #84
I think that the problem is not well-specified, and hence has no solution. The reason is the vagueness of the term 'perfect logician'.

I take it that 'perfect logician' is intended to mean something like 'somebody that will deduce from a given set of axioms anything that can be deduced from them using first-order predicate logic (FOPL) in language L' . I choose FOPL because it is the most flexible and expressive logic one can use without having to make a whole bunch of other definitions and constraints in order to avoid paradoxes. We could consider it for other logics such as one of the many varieties of modal logic, but for the sake of concreteness and simplicity, let's stay with FOPL for now. The language L doesn't need to be specified for the purposes of this problem but I think we should assume it is countable, as I think there may be problems with uncountable languages.

The axioms are set out in the first paragraph of the problem statement, and include statements like 'the oracle speaks once a day ...' and 'those who have deduced that they have blue eyes leave on the day they make the deduction'. It also includes the 'perfect logician' statement. Let's denote all the other axioms collectively by B and the 'perfect logician' axiom by C. Then the set of axioms is B+C (where I use '+' here to indicate union). But 'perfect logician' is unclear so let us expand C. It says

'Each person will deduce whatever can be deduced from B+C in FOPL under L'

Oh dear. There's still a C in there, which we remember was unclear. Let's expand that. that gives us:

'Each person will deduce whatever can be deduced from B+(Each person will deduce whatever can be deduced from B+C in FOPL under L) in FOPL under L'

Bother! There's still a C in there. Let's get rid of it by expanding again:

'Each person will deduce whatever can be deduced from B+(Each person will deduce whatever can be deduced from B+
'Each person will deduce whatever can be deduced from B+(Each person will deduce whatever can be deduced from B+C in FOPL under L) in FOPL under L'
in FOPL under L)
in FOPL under L'


... and so on, ad infinitum

The consequence of this infinite regress is that there is no finite statement of the axiom C. Since an axiom must be a well-formed formula (wff) and one of the requirements of being a wff is that it be composed of a finite number of symbols, we find that there is no possible valid axiom C.

So the problem is not well-defined, and hence has no solution.

It's conceivable there may be some way around this using a higher-order logic. But my hunch is that, whatever logic we use, we are going to run into a Godelian problem that one cannot deduce, from inside any sufficiently rich logical theory, which wffs are theorems of the theory.
 
  • #85
I don't get it, what is wrong in your axiom "C"?
Also I don't see how this goes to infinity since there is a fixed and finite number of possible "each person".
 
  • #86
ChrisVer said:
I don't get it, what is wrong in your axiom "C"?
It's self-referential and generates an infinite regress in trying to understand what it is saying.

C says 'each person will deduce whatever can be deduced from this set of axioms'

But this set of axioms includes C. So to work out what a person can deduce, we first need to know what they can deduce.
 
  • #87
I see finiteness in the 3 people example, and I understand that in the BBB case, it's the perfect logician assuming that the others are perfect logicians that leads to the solution. Of course if you keep on trying to divide this up, you will end up interconnecting all people [since they all die on the same day] and start looping between their connections, "repeating the same axiom".
Is a circle something finite or infinite? Seeing it as a circle it's finite (parametrized in x<[0,2pi] )... seeing it as a closed curve it can be infinite (parametrized in x<[-infty, infty] ).
 
Last edited:
  • #88
Zafa Pi said:
The prophets is not important in the case RBB. Everybody sees a B so no information was imparted by the prophet. Now I know that you have some fancy pants logic that says otherwise, using ten dollar words like "inference", but my logic is a perfectly good solution. I see that you brought up B. Russel, well of course, he is depicted on your icon. Well I told my solution to my mom, and she's a wonderful person and pretty damn smart too, and she agrees with my solution. So in the RBB case after the prophet speaks nothing new happens. That's my solution and I'm sticking to it.

I hope the monitors allow sarcasm.
Demystifier said:
I see what you mean. Yes, one needs to run back to RBB, but only for reductio ad absurdum. To prove that something cannot be, one considers the possibility that it can be and derives a contradiction.

But I don't think that there is any disagreement between you and me on that. The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.
I apologize for being snarky in post #73, but in case RBB and BBB it can be claimed that the prophet creates no new info when she says there is at least one B. So in either case one could claim the solution is that nothing new will happen. But you see them as different. How so (in the fewest words you can)?
 
  • #89
Another way to see the difficulty is to note that a logical language cannot in general make statements about whether a statement in that language is provable. That's because we get an infinite regress when we try to refer to wffs in the language. To define a wff we need to give a recursive definition that starts with a fixed finite or infinite set of symbols for constants, variables, functions and predicates. But then how do we refer to a wff in the language? We run into the 'naming vs using' problem. A wff like '1+1=2' is not a reference to the wff '1+1=2', just as I am not my name. So we need to generate some new constant symbols to refer to wffs using the original set of language symbols. But that then means that our original assumption that we were starting with the full set of language symbols was incorrect.

Trying to define a formal language that can refer to itself ends up being like trying to define a set of all sets, and we know what sort of a muddle that leads to.

We can refer to our language in ordinary speech in our language, because ordinary speech is informal. But if we are to talk about 'perfect logicians' we can only use formal languages to specify what their perfection means, and then we get stuck in an infinite regress.
 
  • #90
Demystifier said:
The prophet said them something that they already knew, so there is no reason to change anything in their behavior.
Actually, this isn't correct. It is true that the prophet said something they all already knew, but this does not mean new information was not conveyed. The whole crux of the situation is that it is essential that everyone in the tribe witness the prophet speaking to everyone else, so the new information is that the people now know what the other people know. There is no reason to ever have any more than two blue-eyed people, that version of the puzzle makes all clear. If there are two blue-eyed people, the solution really is pretty much unique, but you do have to assume that people can tell when other people are listening, and that the other people will draw the correct conclusions. But that's not a stretch when there are two people with blue eyes.
 
  • #91
andrewkirk said:
Another way to see the difficulty is to note that a logical language cannot in general make statements about whether a statement in that language is provable. That's because we get an infinite regress when we try to refer to wffs in the language. To define a wff we need to give a recursive definition that starts with a fixed finite or infinite set of symbols for constants, variables, functions and predicates. But then how do we refer to a wff in the language? We run into the 'naming vs using' problem. A wff like '1+1=2' is not a reference to the wff '1+1=2', just as I am not my name. So we need to generate some new constant symbols to refer to wffs using the original set of language symbols. But that then means that our original assumption that we were starting with the full set of language symbols was incorrect.

Trying to define a formal language that can refer to itself ends up being like trying to define a set of all sets, and we know what sort of a muddle that leads to.

We can refer to our language in ordinary speech in our language, because ordinary speech is informal. But if we are to talk about 'perfect logicians' we can only use formal languages to specify what their perfection means, and then we get stuck in an infinite regress.
Perfect logicians is a red herring. Healthy young PhDs in math will do. You understand the spirit of the problem so do something constructive and give it your best formulation.
 
  • #92
I imagine Hilbert said something similar to Godel.
 
  • Like
Likes Nugatory and Zafa Pi
  • #93
andrewkirk said:
But 'perfect logician' is unclear so let us expand C. It says

'Each person will deduce whatever can be deduced from B+C in FOPL under L'
C does not refer to a particular set of axioms. It says that "each person, at each stage, has some set of axioms, and will make all possible deductions from those axioms".
For the riddle to work, we must additionally postulate C', namely : " C is in fact included in each person's axiom set". We must also add C'' and C''', defined recursively. But this recursion need not be infinite: it is sufficient that the number of such axioms (including C) be equal to the number of monks. If for instance there are two monks, it is okay if A does not know whether B knows that A is a perfect logician.
 
  • Like
Likes andrewkirk
  • #94
Now I've gone and confused myself! I'm still fairly sure that the problem cannot be properly stated in formal terms, and yet I think I've figured out a solution. One of those has to be wrong. I'll present my suggested solution, then I'll go back and try to work out if I can see a way to formally state the problem.

When I say a solution, I mean an explanation of why they all have to wait until the 100th day, and what new information is provided at each stage. It turns out that new information becomes available every night when the ferry departs empty, and also on the Oracle's pronouncement on the first day (but not on subsequent days).

I shall use unary predicate C(r) to indicate u\geq r, where u is the number of blue-eyed people, and unary predicate K to indicate 'everybody knows that'. I will use indices to signify repeated applications of K. Thus K^3C(7) means

'Everybody knows that (Everybody knows that (Everybody knows that (u\geq 7)))'

Say there are n blue-eyed people (I'll call each such person a 'blue' from now on). It is not hard to show that we people with eyes of other colours do not affect the calculations, so we will omit them from consideration.

Then each person can see n-1 blues. So we have
$$KC(n-1)$$
A given person P entertains two possibilities, that u=n or u=n-1. In the second case, P will be non-blue, and what do they know about what others know? Each other person P' will be able to see (n-2) blues. On the other hand if u=n each other person P' will be able to see n-1 blues. So P knows that regardless of their own eye colour, each other person P' can see at least n-2 blues. That is, P knows that KC(n-2). Hence we have, since P is arbitrary:
$$K^2C(n-2)$$
Now think about what P knows about what another person P' knows. P knows it might be the case that P is non-blue and if so, for each other person P' it appears possible that P' is also non-blue. For P' considering that case they realize that each person P'' in the group excluding P' and P can see n-3 blues, so they know that u\geq n-3. For P' considering the alternative, where P' is blue, P'' can see n-2 blues. So either way P'' knows u\geq n-2. So P knows that P' knows that P'' knows that n\geq n-3. Whence we have:
$$K^3C(n-3)$$
We can continue this process, noting that at each step the exponent of K and the argument of C add to n.

So the initial state of knowledge of all players can be written as a vector of statements:
$$KC(n-1),\ K^2C(n-2),\ K^3C(n-3),\ ...\ ,\ K^{n-2}(2),\ K^{n-1}(1),\ K^n(0)$$
The ends are the easiest to interpret. The left says that everybody knows u\geq n-1 and the right says that everybody knows - ad infinitum - that there are at least zero blues.

Then the oracle speaks. Everybody hears her, and everybody knows that everybody else has heard her, so it is now the case that, for any natural number r, we have K^rC(1). This enables us to strengthen the last component of the knowledge vector by increasing the argument to C, but does not affect any of the other components. The new knowledge vector is:
$$KC(n-1),\ K^2C(n-2),\ K^3C(n-3),\ ...\ ,\ K^{n-2}(2),\ K^{n-1}(1),\ K^n(1)$$
So the oracle has communicated new information, not about what people know directly but about what they know others know others know others know...

Next, the ferry leaves and, if n&gt;1 then nobody is on it. So now everybody knows that there are at least two blues, and they know that everybody else knows that, and they can prefix the K operator to that as many times as they like. The new knowledge vector is:
$$KC(n-1),\ K^2C(n-2),\ K^3C(n-3),\ ...\ ,\ K^{n-3}(3)\ ,\ K^{n-2}(2),\ K^{n-1}(2),\ K^n(2)$$
The next piece of new info is when the ferry leaves empty on day 2, provided n&gt;2. Then everybody knows (to the umpteenth power) that u\geq 3. So the new knowledge vector is:
$$KC(n-1),\ K^2C(n-2),\ K^3C(n-3),\ ...\ ,\ K^{n-4}(4)\ ,\ K^{n-3}(3)\ ,\ K^{n-2}(3),\ K^{n-1}(3),\ K^n(3)$$
This continues, and each day the knowledge vector changes, by the minimum argument to all C predicates being increased by 1.
The general form of the knowledge vector after an empty ferry departure on day r is a vector of n components, of which the jth is:
$$K^{j}C(\max(n-j,r+1))$$
Each day, the knowledge of what others know others know increases, even though the direct knowledge of each person about the number of blues does not change.

When the ferry departs empty on day n-2 the knowledge vector has arguments with a minimum of n-1. Now, for the first time, everybody knows that everybody knows (etc, etc) that u\geq n-1. But they still don't know if their own eyes are blue. They only discover that when the ferry departs empty on day n-1 and the knowledge vector arguments attain a minimum of n. So, for all r we now have K^rC(n).

So they all leave on the nth day's ferry.

Every day there was new info from the ferry departure. And the first oracle pronouncement was necessary, although the subsequent ones were not.
 
  • Like
Likes Nugatory, Dr.AbeNikIanEdL and maline
  • #95
andrewkirk said:
And the first oracle pronouncement was necessary, although the subsequent ones were not.

What subsequent pronouncements do you mean?
 
  • #96
Dr.AbeNikIanEdL said:
What subsequent pronouncements do you mean?
My mistake. I misremembered the problem statement. I thought it said the oracle made an announcement every day. But now that I check back, I see that she only makes the announcement on one day. So the days would have to be numbered starting with day 1 being the day she made her pronouncement.
 
  • #97
maline said:
But this recursion need not be infinite: it is sufficient that the number of such axioms (including C) be equal to the number of monks. If for instance there are two monks, it is okay if A does not know whether B knows that A is a perfect logician.
And indeed, it need not be the number of monks, only the number of blue-eyed monks!
 
  • #98
Ken G said:
And indeed, it need not be the number of monks, only the number of blue-eyed monks
Ah, in the version i heard they were all blue- eyed.
By the way, even if we did require an infinite recursive set of axioms- the union of all finite statements of the form "Each person has in his axiom sat the fact that each person has in his axiom set... that each person, at each stage, will make all possible FOPL deductions from whatever his axiom set is"- I think that would be a legitimate FOPL axiom schema, because each such axiom includes no self- reference.
 
  • #99
maline said:
Ah, in the version i heard they were all blue- eyed.
I see, a more general version has some N blue-eyed people, and then suicide is on day N, etc.
By the way, even if we did require an infinite recursive set of axioms- the union of all finite statements of the form "Each person has in his axiom sat the fact that each person has in his axiom set... that each person, at each stage, will make all possible FOPL deductions from whatever his axiom set is"- I think that would be a legitimate FOPL axiom schema, because each such axiom includes no self- reference.
Yes, I think the idea with axioms is you don't necessarily have to list them all, it is enough to provide an algorithm that churns them out, and then the algorithm can be used in proofs. A mathematician might be able to say this in a more formally correct way.
 
  • #100
To attack this, we need to know exactly what the monks know:
1) They know how many other monks have blues eyes.
2) They know that the monks will follow the rules.
3) Implicit from the way the problem is presented, the monks recognize the blue-eyed monks. In other words, they would know if a different set of blue-eyed monks were preset on one day from the previous day.

Also, as most on this thread have already noticed, we don't need to deal with brown-eyed monks. We just need to know that there may be some.

Demystifier suggested that history may be important, so I will present the logical reasoning so that there is a build up of history before the priest shows up and makes his declaration.

Day 1: 1 blue (named "A") is placed on the island. He has no way of determining his eye color. If the priest shows up and declares that he sees a blue, the blue will kill himslef at the next opportunity. Generally speaking, when there is 1 blue on the island, a declaration of blue will cause that blue to die at the next opportunity. All monks, being perfectly logical, and knowing that all other blues are perfectly logical, will rely on this rule.

Day 2: a second blue ("B") is placed on the island. This is where the logic becomes critical. Each monk knows that there are 1 or 2 blues. So they also know that if the priest showed up, he would say that there was a blue. What they don't know is how the blue (the other monk) will react. If A sees B kill himself, then A knows that he (A) is not blue. On the other hand, if B does not kill himself, then the number of blues cannot be 1. Both A and B would see this and kill themselves at the next opportunity.

But since they know what the priest would say, do they really need the priest? The answer is yes, because although each one knows that there are 1 or 2 blue, they don't know whether the other thinks there are (0 or 1) or (1 or 2). So what is important is not that priest said anything newsworthy, but that monks saw every blue monk be informed of this.

So this creates a second completely reliable rule: If a priest declares that there is a blue and there are two blue, both will kill themselves on the second opportunity.

Day 3: a third blue ("C") is placed onto the island. He immediately deduces that there are either 2 or 3 blues on the island and that the other blues know that there are either (1 or 2) or (2 or 3) blues on the island. At this point, he can deduce nothing else.

But if the priest makes a declaration, then he knows that on the second opportunity the "2" theory will be tested. And that if no one kills themselves, that the answer must be 3.

But I like the "history" idea, so I will make another post to this thread dealing with it more comprehensively - probably not today. But unless I run into a priest making eye declarations (or another monk beets me to it), it will be soon.
 
Back
Top