Inspired by Timothy Gowers’s example, here is my transfinite epistemic logic problem.
First, let’s begin with a simple finite example.
Cheryl Hello Albert and Bernard! I have given you each a different natural number ($0, 1, 2, \ldots$). Who of you has the larger number?
Albert I don’t know.
Bernard I don’t know either.
Albert Even though you say that, I still don’t know.
Bernard And still neither do I.
Albert Alas, I continue not to know.
Bernard And also I do not know.
Albert Yet, I still do not know.
Bernard Aha! Now I know which of us has the larger number.
Albert In that case, I know both our numbers.
Bernard. And now I also know both numbers.
Question: What numbers do Albert and Bernard have?
Click for the solution.
Now, let us consider a transfinite instance. Consider the following conversation.
Cheryl I have given you each a different ordinal number, possibly transfinite, but possibly finite. Who of you has the larger ordinal?
Albert I don’t know.
Bernard I don’t know, either.
Albert Even though you say that, I still don’t know.
Bernard And still neither do I.
Albert Alas, I still don’t know.
Bernard And yet, neither do I.
Cheryl Well, this is becoming boring. Let me tell you that no matter how much longer you continue that back-and-forth, you still will not know the answer.
Albert Well, thank you, Cheryl, for that new information. However, I still do not know who has the larger ordinal.
Bernard And yet still neither do I.
Albert Alas, even now I do not know!
Bernard And neither do I!
Cheryl Excuse me; you two can go back and forth like this again, but let me tell you that no matter how much longer you continue in that pattern, you will not know.
Albert Well, ’tis a pity, since even with this further information, I still do not know.
Bernard Aha! Now at last I know who of us has the larger ordinal.
Albert In that case, I know both our ordinals.
Bernard. And now I also know both ordinals.
Question: What ordinals do they have?
Click for a solution.
See my next transfinite epistemic logic puzzle challenge!
Solutions.
- For the first problem, with natural numbers, let us call the numbers $a$ and $b$, respectively, for Albert and Bernard. Since Albert doesn’t know at the first step, it means that $a\neq 0$, and so $a$ is at least $1$. And since Bernard can make this conclusion, when he announces that he doesn’t know, it must mean that $b$ is not $0$ or $1$, for otherwise he would know, and so $b\geq 2$. On the next round, since Albert still doesn’t know, it follows that $a$ must be at least $3$, for otherwise he would know; and then, because Bernard still doesn’t know, it follows that $b$ is at least $4$. The next round similarly yields that $a$ is at least $5$ and then that $b$ is at least $6$. Because Albert can undertake all this reasoning, it follows that $a$ is at least $7$ on account of Albert’s penultimate remark. Since Bernard announces at this point that he knows who has the larger number, it must be that Bernard has $6$ or $7$ and that Albert has the larger number. And since Albert now announces that he knows the numbers, it must be because Albert has $7$ and Bernard has $6$.
- For the transfinite problem, let us call the ordinal numbers $\alpha$ and $\beta$, respectively, for Albert and Bernard. Since Albert doesn’t know at the first step, it means that $\alpha\neq 0$ and so $\alpha\geq 1$. Similarly, $\beta\geq 2$ after Bernard’s remark, and then $\alpha\geq 3$ and $\beta\geq 4$ and this would continue for some time. Because Cheryl says that no matter how long they continue, they will not know, it follows that both $\alpha$ and $\beta$ are infinite ordinals, at least $\omega$. But since Albert does not know at this stage, it means $\alpha\geq\omega+1$, and then $\beta\geq \omega+2$. Since Cheryl says again that no matter how long they continue that, they will not know, it means that $\alpha$ and $\beta$ must both exceed $\omega+k$ for every finite $k$, and so $\alpha$ and $\beta$ are both at least $\omega\cdot 2$. Since Albert still doesn’t know after that remark, it means $\alpha\geq\omega\cdot 2+1$. But now, since Bernard knows at this point, it must be that $\beta=\omega\cdot 2$ or $\omega\cdot 2+1$, since otherwise he couldn’t know. So Albert’s ordinal is larger. Since at this point Albert knows both the ordinals, it must be because Albert has $\omega\cdot 2+1$ and Bernard has $\omega\cdot 2$.
It is clear that one may continue in this way through larger transfinite ordinals. When the ordinals become appreciable in size, then it will get harder to turn it into a totally finite conversation, by means of Cheryl’s remarks, but one may succeed at this for quite some way with suitably obscure pronouncements by Cheryl describing various limiting processes of the ordinals. To handle any given (possibly uncountable) ordinal, it seems best that we should consider conversations of transfinite length.
I changed the discussion slightly from the first posting, so that in each case both numbers are determined.
Nice puzzle!
I have a (maybe silly) question. Why is Albert’s number – or ordinal, for the transfinite case – determined? For instance, consider the finite case: wouldn’t be the dialogue just the same also if b=6 and a>7? In particular, suppose b=6 and a=100. In this case, Bernard can still announce that he knows who has the larger number (knowing that 6, at that point, is necessarily the minimum), and then Albert can still says that he knows both the numbers, for he deduced Bernard’s one and he clearly knows his own number.
— and similarly for the transfinite version.
What am i missing here?
Since Bernard’s number could be either 6 or 7 until the final remark, the only way that Albert can know both numbers is if he can rule one of these out, and the only that way that that can happen is if Albert himself has 7, so that he knows Bernard has 6. If Albert had 100, he wouldn’t know both numbers, since he wouldn’t know whether Bernard had 6 or 7.
I can imagine how this would work for ordinals up to, say, omega^omega or even epsilon_0, by Cherly short-circuiting conversations including not only Albert and Bernard but herself as well (by admitting that she will interrupt their exchange infinitely often). But I do not see a way of getting past even omega_1^CK which does not amount to Cheryl starting the conversation by saying how many times she will interrupt the exchange and reducing the game to the finite case.
Miha, I agree that for larger ordinals, it becomes increasingly difficult for Cheryl to carry them through the limit stages in that fashion. I can imagine her pointing to an oracle for some large ordinal saying that, “even if you go *that* far, you will not know.” For this reason, I find it more natural to consider an actually infinite transfinite conversation purely between Albert and Bernard, as I mention at the end.
I have no idea what you are talking about, but this quote from a Jane Austen novel comes to mind.
Elizabeth: There is, I believe, in every disposition a tendency to some particular evil, a natural defect, which not even the best education can overcome. And Your defect is a propensity to hate every body.
Mr. Darcy: And yours (he replied with a smile) is to willfully misunderstand them.
Pingback: Transfinite epistemic logic puzzle challenge! | Joel David Hamkins
Pingback: #thatlogicproblem round-up | The Aperiodical
I like to give a n interesting related puzzle.
Give two successive natural numbers greater than 10 to A and B, each one only knows his/her number and both of them know that the numbers are successive.
The puzzle rules:
1) Both players are honest!
2) Both are intelligent.
3) In each step, they can only say one of two following sentence:
I don’t know what your number is.
&
Now I can say what your number is and your number is…. .(Then conversation ends)
…………………….
Now puzzle starts.It’s beginning a conversation between A and B.
A: I don’t know what your number is.
B: I don’t know what your number is.
A: I don’t know what your number is.
B: I don’t know what your number is.
A: I don’t know what your number is.
B: I don’t know what your number is.
.
.
.
.
The game continues, but suddenly one of the says Now I can say what your number is and your number is….. and then game ends.
Question: How is it possible?
This problem show that you can get many information from nothing(they only say I don’t know)!!!!!!
Note that I didn’t think about transfinite situation.
I like your puzzle, and actually I had considered exactly that version before deciding to present the current one, where Albert and Bernard do not know that the numbers are necessarily successive, but the pattern of reasoning still works. It is indeed amazing to me!
So if it’s convenient, delete my post, I have another one, If you know it I don’t leave a comment otherwise it’s more interesting.
Summery of Puzzle: The situation is more complicated one of them has a number that is multiplication of a and b (a.b) and another one the summation of a and b (a+b).
but the numbers are less that 100. it’s important who starts first and in 4 steps second one says the answer.
Can this be generalized to transfinite case?
a(or b)=1?
b(or 1)=3?
whosoever has which # is well beyond my comprehension…
Also the relation ship between the least given number and the steps to reach the answer is also interesting.
“Since Albert doesn’t know at the first step, it means that a≠0”
HOW!?
Why does it have to start at 0?
Why does the conversation have to go sequentially?
I understand which exit to take; I just don’t know how to get to the highway or which direction to go once there…
Another interesting puzzle:
Using Joel’s characters!
Cheryl: Hello Albert and Bernard! I give you each a different natural number with following property:
“There exist two natural number 1<x<y<100 such that Albert's number is x.y and Bernard's number is x+y."(each one knows only his number)
Now start a conversation to determine x and y.
Albert: I cannot determine x and y from the given number.
Bernard: Yes I knew that.
Albert: Now I can determine x and y.
Bernard: Now I also can determine x and y.
Question: What are x and y?
I left a comment and explained full story.
Pingback: Post-Cherylmania wrap-up | Matt Baker's Math Blog
Pingback: Un puzzle transfinito « Mathing