Every ordinal has only finitely many order-types for its final segments

droste_effect_clock_by_kiluncle-d4ya2gnI was recently asked an interesting elementary question about the number of possible order types of the final segments of an ordinal, and in particular, whether there could be an ordinal realizing infinitely many different such order types as final segments.  Since I found it interesting, let me write here how I replied.

The person asking me had noted that every nonempty final segment of the first infinite ordinal $\omega$ is isomorphic to $\omega$ again, since if you start counting from $5$ or from a million, you have just as far to go in the natural numbers. Thus, if one includes the empty final segment, there are precisely two order-types that arise as final segments of $\omega$, namely, $0$ and $\omega$ itself. A finite ordinal $n$, in contrast, has precisely $n+1$ many final segments, corresponding to each of the possible cuts between any of the elements or before all of them or after all of them, and these final segments, considered as orders themselves, all have different sizes and hence are not isomorphic.

He wanted to know whether an ordinal could have infinitely many different order-types for its tails.

Question. Is there an ordinal having infinitely many different isomorphism types for its final segments?

The answer is no, and I’d like to explain why. I’ll discuss two different arguments, the first being an easy direct argument aimed only at this answer, and the second being a more careful analysis aimed at understanding exactly how many and which order-types arise as the order type of a final segment of an ordinal $\alpha$.

Theorem. Every ordinal has only finitely many order types of its final segments.

Proof: Suppose that $\alpha$ is an ordinal, and consider the order types of the final segments $[\eta,\alpha)$, for $\eta\leq\alpha$. Note that as $\eta$ increases, the final segment $[\eta,\alpha)$ becomes smaller as a suborder, and so it’s order type does not go up. And since these are well-orders, it can go down only finitely many times. So only finitely many order types arise, and the theorem is proved. QED

But let’s figure out exactly how many and which order types arise.

Theorem. The number of order types of final segments of an ordinal $\alpha$ is precisely $n+1$, where $n$ is the number of terms in the Cantor normal form of $\alpha$, and one can describe those order types in terms of the normal form of $\alpha$.

Cantor proved that every ordinal $\alpha$ can be uniquely expressed as a finite sum $$\alpha=\omega^{\beta_n}+\cdots+\omega^{\beta_0},$$ where $\beta_n\geq\cdots\geq\beta_0$, and this is called the Cantor normal form of the ordinal. There are alternative forms, where one allows terms like $\omega^\beta\cdot n$ for finite $n$, but in my favored formulation, one simply expands this into $n$ terms with $\omega^\beta+\cdots+\omega^\beta$. In particular, the ordinal $\omega=\omega^1$ has exactly one term in its Cantor normal form, and a finite number $n=\omega^0+\cdots+\omega^0$ has exactly $n$ terms in its Cantor normal form. So the statement of the theorem agrees with the calculations that we had made at the very beginning.

Proof: First, let’s observe that every nonempty final segment of an ordinal of the form $\omega^\beta$ is isomorphic to $\omega^\beta$ again. This amounts to the fact that ordinals of the form $\omega^\beta$ are additively indecomposable, or in other words, closed under ordinal addition, since the final segments of an ordinal $\alpha$ are precisely the ordinals $\zeta$ such that $\alpha=\xi+\zeta$ for some $\xi$. If $\alpha$ is additively indecomposable, then it cannot be that $\zeta<\alpha$, and so all final segments would be isomorphic to $\alpha$. So let’s prove that $\omega^\beta$ is additively indecomposable. This is clear if $\beta=0$, since the only ordinal less than $\omega^0=1$ is $0$ and $0+0<1$. If $\beta$ is a limit ordinal, then the ordinals $\omega^\eta$ for $\eta<\beta$ are unbounded in $\omega^\beta$, and adding them stays below because $\omega^\eta+\omega^\eta=\omega^\eta\cdot 2\leq\omega^\eta\cdot\omega=\omega^{\eta+1}<\omega^\beta$. If $\beta=\delta+1$ is a successor ordinal, then $\omega^\beta=\omega^{\delta+1}=\omega^\delta\cdot\omega=\sup_{n<\omega}\omega^\delta\cdot n$, but again adding them stays below because $\omega^\delta\cdot n+\omega^\delta\cdot m=\omega^\delta\cdot(n+m) < \omega^\delta\cdot\omega=\omega^\beta$.

To prove the theorem, consider any ordinal $\alpha$ with Cantor normal form $\alpha=\omega^{\beta_n}+\cdots+\omega^{\beta_0}$, where $\beta_n\geq\cdots\geq\beta_0$. So as an order type, $\alpha$ consists of finitely many pieces, the first of type $\omega^{\beta_n}$, the next of type $\omega^{\beta_{n-1}}$ and so on up to $\omega^{\beta_0}$. Any final segment of $\alpha$ therefore consists of a final segment of one of these segments, together with all the segments after that segment (and omitting any segments prior to it, if any). But since these segments all have the form $\omega^{\beta_i}$, they are additively indecomposable and therefore are isomorphic to all their nonempty final segments. So any final segment of $\alpha$ is order-isomorphic to an ordinal whose Cantor normal form simply omits some (or none) of the terms from the front of the Cantor normal form of $\alpha$. Since we may start with any of the $n$ terms (or none), this gives precisely $n+1$ many order types of the final segments of $\alpha$, as claimed.

The argument shows, furthermore, that the possible order types of the final segments of $\alpha$, where $\alpha=\omega^{\beta_n}+\cdots+\omega^{\beta_0}$, are precisely the ordinals of the form $\omega^{\beta_k}+\cdots+\omega^{\beta_0}$, omitting terms only from the front, where $k\leq n$. QED

Transfinite Nim

Wooden blocksShall we have a game of transfinite Nim? One of us sets up finitely many piles of wooden blocks, each pile having some ordinal height, possibly transfinite, and the other of us decides who shall make the first move. Taking turns, we each successively remove a top part of any one pile of our choosing, making it strictly shorter. Whoever takes the very last block wins. (It is fine to remove an entire pile on a turn or to remove blocks from a different pile on a later turn.)

In my challenge problem last week, for example, I set up six piles with heights:
$$1\qquad \omega+3\qquad \omega^\omega+5 \qquad \omega^{\omega+3}+\omega^\omega\cdot3+\omega\cdot 5+7\qquad \epsilon_0\qquad \omega_1$$Would you want to go first or second? What is the best move? In general, we can start with any finite number of piles of arbitrary ordinal heights — what is the general winning strategy?

Before proceeding with the transfinite case, however, let’s review the winning strategy in ordinary finite Nim, which I explained in my post last week concerning my visit to the 7th/8th grade Math Team at my son’s school. To say it quickly again, a finite Nim position is balanced, if when you consider the binary representations of the pile heights, there are an even number of ones in each binary place position. Another way to say this, and this is how I explained it to the school kids, is that if you think of each pile height as a sum of distinct powers of two, then any power of two that arises in any pile does so an even number of times overall for all the piles. The mathematical facts to establish are that (1) any move on a balanced position will unbalance it; and (2) any unbalanced position admits a balancing move. Since the winning move of taking the very last block is a balancing move, it follows that the winning strategy is to balance whatever position with which you are faced. At the start, if the position is unbalanced, then you should go first and balance it; if it is already balanced, then you should go second and adopt the balancing strategy. It may be interesting to note that this winning strategy is unique in the sense that any move that does not balance the position is a losing move, since the opposing player can adopt the balancing strategy from that point on. But of course there is often a choice of balancing moves.

Does this balancing strategy idea continue to apply to transfinite Nim? Yes! All we need to do is to develop a little of the theory of transfinite binary representation. Let me assume that you are all familiar with the usual ordinal arithmetic, for which $\alpha+\beta$ is the ordinal whose order type is isomorphic to a copy of $\alpha$ followed by a copy of $\beta$, and $\alpha\cdot\beta$ is the ordinal whose order type is isomorphic to $\beta$ many copies of $\alpha$. Consider now ordinal exponentiation, which can be defined recursively as follows:
$$\alpha^0=1$$ $$\alpha^{\beta+1}=\alpha^\beta\cdot\alpha$$ $$\alpha^\lambda=\sup_{\beta<\lambda} \alpha^\beta\qquad\lambda\text{ limit}$$ It turns out that $\alpha^\beta$ is the order-type of the finite-support functions from $\beta$ to $\alpha$, under the suitable lexical order. Ordinal exponentiation should not be confused with cardinal exponentiation, since they are very different. For example, with ordinal exponentiation, one has $$2^\omega=\sup_{n<\omega}2^n=\omega,$$which of course is not the case with cardinal exponentiation. In this post, I use only ordinal exponentiation.

Theorem. Every ordinal $\beta$ has a unique representation as a decreasing finite sum of ordinal powers of two. $$\beta=2^{\beta_n}+\cdots+2^{\beta_0}, \qquad \beta_n>\cdots>\beta_0$$

The proof is easy! We simply prove it by transfinite induction on $\beta$. If the theorem holds below an ordinal $\beta$, first let $2^\alpha$ be the largest power of two that is at most $\beta$, so that $\beta=2^\alpha+\gamma$ for some ordinal $\gamma$. It follows that $\gamma<2^\alpha$, for otherwise we could have made $2^{\alpha+1}\leq\beta$. Thus, by induction, $\gamma$ has a representation with powers of two, and so we may simply add $2^\alpha$ at the front to represent $\beta$. To see that the representations are unique, first establish that any power of two is the supremum of the finite decreasing sums of any strictly smaller powers of two. From this, it follows that any representation of $\beta$ as above must have used $2^\alpha$ just as we did for the first term, because otherwise it couldn’t be large enough, and then the representation of the remaining part $\gamma$ is unique by induction, and so we get uniqueness for the representation of $\beta$. QED

Thus, the theorem shows that every ordinal has a unique binary representation in the ordinals, with finitely many nonzero bits. Suppose that we are given a position in transfinite Nim with piles of ordinal heights $\eta_0,\ldots,\eta_n$. We define that such a position is balanced, if every power of two appearing in the representation of any of the piles appears an even number of times overall for all the piles.

The mathematical facts to establish are (1) any move on a balanced position will unbalance it; and (2) every unbalanced position has a balancing move. These facts can be proved in the transfinite case in essentially the same manner as the finite case. Namely, if a position is balanced, then any move affects only one pile, changing the ordinal powers of two that appear in it, and thereby destroy the balanced parity of whichever powers of two are affected. And if a position is unbalanced, then look at the largest unbalanced ordinal power of two appearing, and make a move on any pile having such a power of two in its representation, reducing it so as exactly to balance all the smaller powers of two appearing in the position.

Finally, those two facts again imply that the balancing strategy is a winning strategy, since the winning move of taking the last block or blocks is a balancing move, down to the all-zero position, which is balanced.

In the case of my challenge problem above, we may represent the ordinals in binary. We know how to do that in the case of 1, 3, 5 and 7, and actually those numbers are balanced. Here are some other useful binary representations:

$\omega+3=2^\omega+2+1$

$\omega^\omega+5 = (2^\omega)^\omega+5=2^{\omega^2}+4+1$

$\omega^{\omega+3}=(2^\omega)^{\omega+3}=2^{\omega^2+\omega\cdot 3}$

$\omega^\omega\cdot3=(2^\omega)^\omega\cdot 3=2^{\omega^2}\cdot 2+2^{\omega^2}=2^{\omega^2+1}+2^{\omega^2}$

$\omega\cdot 5+7 =2^{\omega}\cdot 2^2+2^\omega+7=2^{\omega+2}+2^\omega+4+2+1$

$\epsilon_0 = 2^{\epsilon_0}$

$\omega_1=2^{\omega_1}$

I emphasize again that this is ordinal exponentiation. The Nim position of the challenge problem above is easily seen to be unbalanced in several ways. For example, the $\omega_1$ term among others appears only once. Thus, we definitely want to go first in this position. And since $\omega_1$ is the largest unbalanced power of two and it appears only once, we know that we must play on the $\omega_1$ pile. Once one represents all the ordinals in terms of their powers of two representation, one sees that the unique winning move is to reduce the $\omega_1$ pile to have ordinal height
$$\epsilon_0+\omega^{\omega+3}+\omega^\omega\cdot 2+\omega\cdot 4.$$This will exactly balance all the smaller powers of two in the other piles and therefore leaves a balanced position overall. In general, the winning strategy in transfinite Nim, just as for finite Nim, is always to leave a balanced position.

Special honors to Pedro Sánchez Terraf for being the only one to post the winning move in the comments on the other post!

Solution to my transfinite epistemic logic puzzle, Cheryl’s Rational Gifts

Thanks so much to everyone for trying out my transfinite epistemic logic puzzle, which I have given the name Cheryl’s Rational Gifts, on account of her gifts to Albert and Bernard. I hope that everyone enjoyed the puzzle.  See the list of solvers and honorable mentions at the bottom of this post. Congratulations!

As I determine it, the solution is that

Albert has the number $100\frac38$, and

Bernard has the number $100\frac7{16}$.

Let me explain my reasoning and address a few issues that came up in the comments.

First, let’s understand the nature of the space of possible numbers that Cheryl describes, those of the form the form $$n-\frac{1}{2^k}-\frac{1}{2^{k+r}},$$ where $n$ and $k$ are positive integers and $r$ is a non-negative integer. Although this may seem complicated at first, in fact this set consists simply of a large number of increasing convergent sequences, one after the other. Specifically, the smallest of the numbers is $0=1-\frac12-\frac12$, and then $\frac14$, $\frac38$, $\frac7{16}$, and so on, converging to $\frac12$, which itself arises as $\frac12=1-\frac14-\frac14$. So the numbers begin with the increasing convergent sequence $$0 \quad\frac14\quad \frac38\quad \frac7{16}\quad\cdots\quad\to\quad \frac12.$$Immediately after this comes another sequence of points of the form $1-\frac14-\frac1{2^{2+r}}$, which converge to $\frac34$, which itself arises as $1-\frac18-\frac18$. So we have $$\frac12\quad \frac58\quad \frac{11}{16}\quad\frac{23}{32}\quad\cdots\quad\to\quad \frac34.$$Following upon this, there is a sequence converging to $\frac78$, and then another converging to $\frac{15}{16}$, and so on. Between $0$ and $1$, therefore, what we have altogether is an increasing sequence of increasing sequences of rational numbers, where the start of the next sequence is precisely the limit of the previous sequence.

Cheryl's numbers

The same pattern recurs between $1$ and $2$, between $2$ and $3$, and indeed between any positive integer $n$ and its successor $n+1$, for the numbers the occur between $n$ and $n+1$ are simply a translation of the numbers between $0$ and $1$. Thus, for every positive integer $k$ we have $n-\frac1{2^k}$ as the limit of the numbers $n-\frac{1}{2^k}-\frac{1}{2^{k+r}}$, as $r$ increases. Between any two non-negative integers, therefore, we have an increasing sequence of converging increasing sequences. Altogether, we have infinitely many copies of the picture between $0$ and $1$, which was infinitely many increasing convergent sequences, one after the other.

For those readers who are familiar with the ordinals, what this means is that the set of numbers forms a closed set of order type exactly $\omega^3$. We may associate the number $n-\frac{1}{2^k}-\frac{1}{2^{k+r}}$ with the ordinal number $\omega^2\cdot (n-1)+\omega\cdot (k-1)+r$, and observe that this correspondence is a (continuous) order-isomorphism of our numbers with the ordinals below $\omega^3$. In this way, we could replace all talk of the specific rational numbers in this puzzle with their corresponding ordinals below $\omega^3$ and imagine that Cheryl has actually given her friends ordinals rather than rationals. But to explain the solution, allow me to stick with the rational numbers.

The fact that Albert initially does not know who has the larger number implies that Albert does not have $0$, the smallest number overall, since if he were to have had $0$, then he would have known that Bernard’s must have been larger. Since then Bernard does not know, it follows that his number is neither $0$ nor $\frac14$, which is the next number, since otherwise he would have known that Albert’s number must have been larger. Since Albert continues not to know, we rule out the numbers up to $\frac38$ for him. And then similarly ruling out the numbers up to $\frac7{16}$ for Bernard. In this way, each step of the back-and-forth continuing denials of knowing eliminates the lowest remaining numbers from possibility.

Consequently, when Cheryl interrupts the first time, we learn that Albert and Bernard cannot have numbers on the first increasing sequence (below $\frac12$), since otherwise they would at some point come to know in that back-and-forth procedure who has the larger number, and so it wouldn’t be true that they wouldn’t know no matter how long they continued the back-and-forth, as Cheryl stated. Thus, after her remark, both Albert and Bernard know that both numbers are at least $\frac12$, which is the first limit point of the set of possible numbers.

Since at this point Albert states that he still doesn’t know who has the larger number, it cannot be that he has $\frac12$ himself, since otherwise he would have known that he had the smaller number. And then next since Bernard still doesn’t know, it follows that Bernard cannot have either $\frac12$ or $\frac58$, the next number. Thus, if they were to continue the iterative not-knowing-yet pronouncements, they would systematically eliminate the numbers on the second increasing sequence, which converges to $\frac34$. Because of Cheryl’s second interruption remark, therefore, it follows that their numbers do not appear on that second sequence, for otherwise they would have known by continuing that pattern long enough. Thus, after her remark, they both know that both numbers are at least $\frac34$.

And since Albert and Bernard in succession state that they still do not know, they have begun to eliminate numbers from the third sequence.

Consider now Cheryl’s contentful exasperated remark. What she says in the first part is that no matter how many times the three of them repeat that pattern, they will still not know. The content of this remark is precisely that neither of the two numbers can be on next sequence (the third), nor the fourth, nor the fifth and so on; they cannot be on any of the first $\omega$ many sequences (that is, below $1$), because if one of the numbers occurred on the $k^{th}$ sequence below $1$, as $1-\frac1{2^k}-\frac1{2^{k+r}}$, for example, then after $k-1$ repetitions of the three-way-pattern, it would no longer be true for Cheryl to say that no matter how long Albert and Bernard continued their back-and-forth they wouldn’t know, since they would indeed know after $r$ steps of that at that point. Thus, the first part of Cheryl’s remark implies that the numbers must both be at least $1$.

But Cheryl also says that the same statement would be true if she said it again. Thus, the numbers must not lie on any of the first $\omega$ many sequences above $1$. Those sequences converge to the limit points $1\frac12$, $1\frac34$, $1\frac78$ and so on. Consequently, after that second statement, everyone would know that the numbers must both be at least $2$. Similarly, after making the statement a third time, everyone knows the numbers must be at least $3$, and after the fourth time, everyone knows the numbers must be at least $4$.

Cheryl says that she could make the statement a hundred times altogether in succession (counting the time she has already said it as amongst the one hundred), and it would be true every time. Since each time she makes the statement, it eliminates precisely the possibility that one of the numbers is on any of the next $\omega$ many sequences, what everyone would know after the one hundredth pronouncement is precisely that both numbers are at least $100$. Even though she didn’t actually make the statement one hundred times, Albert and Bernard are entitled to know exactly that information even so, because she had said that the statement would be true every time, if she were to have said it one hundred times.

Note that it would be perfectly compatible with Cheryl making that statement one hundred times, if one of the numbers had been $100$, since each additional assertion simply eliminates the possibility that one of the numbers occurs on the sequences strictly before the next integer limit point, without eliminating the integer limit point itself.

Next Cheryl makes an additional statement, which it seems to me that some of the commentators did not give sufficient attention. Namely, she says, “And furthermore, even after my having said it altogether one hundred times in succession, you would still not know who has the larger number!” This statement gives additional epistemic information beyond the content of saying that the $100^{th}$ statement would be true. After the $100^{th}$ statement, according to what we have said, both Albert and Bernard would know precisely that both numbers are at least $100$. But Cheryl is telling them that they still would not know, even after the $100^{th}$ statement. Thus, it must be that neither Albert nor Bernard has $100$, since having that number is the only way they could know at that point who has the larger number.  (Note also that Cheryl did not say that they would know that the other does not know, but only that they each would not know after the $100^{th}$ assertion, an issue that appeared to trip up some commentators. So she is making a common-knowledge assertion about what their individual epistemic states would be in that case.)  The first few numbers after $100$ are: $$100\qquad 100\frac14\qquad 100\frac38\qquad 100\frac7{16}\qquad 100\frac{15}{32}\qquad\cdots\to\quad
100\frac12$$ So putting everything together, what everyone knows after Cheryl’s exasperated remark is that both numbers are at least $100\frac14$.

Since Albert still doesn’t know, it means his number is at least $100\frac 38$. Since Bernard doesn’t know after this, it means that Bernard cannot have either $100\frac14$ or $100\frac38$, since otherwise he would know that Albert’s is larger. So Bernard has at least $100\frac7{16}$.

But now suddenly, finally, Albert knows who has the larger number! How can this be? So far, all we knew is that Albert’s number was at least $100\frac 38$ and Bernard’s is at least $100\frac7{16}$. If Albert had $100\frac 38$, then indeed he would know that Bernard’s number is larger; but note also that if Albert had $100\frac7{16}$, then he would also know that Bernard must have the larger number (since he knows the numbers are different). But if Albert’s number were larger than $100\frac7{16}$, then he couldn’t know whether Bernard’s number was larger or not. So after Albert’s assertion, what we all know is precisely that Albert has either $100\frac38$ or $100\frac7{16}$.

But now, Bernard claims to know both numbers! How could he know which number Albert has? The only way that he can distinguish those two possibilities that we mentioned is if Bernard himself has $100\frac7{16}$, since this is the smallest possibility remaining for Bernard and if Bernard’s number were larger than that then Albert could have consistently had either $100\frac38$ or $100\frac7{16}$. Thus, because Bernard knows the numbers, it must be that Bernard has $100\frac7{16}$, which would eliminate this possibility for Albert.

So Albert has $100\frac38$ and Bernard has $100\frac7{16}$, and that is the solution of the puzzle.

A number of commentators solved the puzzle, coming to the same conclusion that I did, and so let me give some recognition here. Congratulations!

Let me also give honorable mentions to the following people, who came very close.

 

Cheryl’s Rational Gifts: transfinite epistemic logic puzzle challenge!

 

Can you solve my challenge puzzle?

 

Cheryl's numbers

Cheryl   Welcome, Albert and Bernard, to my birthday party, and I thank you for your gifts. To return the favor, as you entered my party, I privately made known to each of you a rational number of the form $$n-\frac{1}{2^k}-\frac{1}{2^{k+r}},$$ where $n$ and $k$ are positive integers and $r$ is a non-negative integer; please consider it my gift to each of you. Your numbers are different from each other, and you have received no other information about these numbers or anyone’s knowledge about them beyond what I am now telling you. Let me ask, who of you has the larger number?

Albert    I don’t know.

Bernard    Neither do I.

Albert    Indeed, I still do not know.

Bernard    And still neither do I.

Cheryl    Well, it is no use to continue that way! I can tell you that no matter how long you continue that back-and-forth, you shall not come to know who has the larger number.

Albert    What interesting new information! But alas, I still do not know whose number is larger.

Bernard    And still also I do not know.

Albert    I continue not to know.

Bernard    I regret that I also do not know.

Cheryl    Let me say once again that no matter how long you continue truthfully to tell each other in succession that you do not yet know, you will not know who has the larger number.

Albert    Well, thank you very much for saving us from that tiresome trouble! But unfortunately, I still do not know who has the larger number.

Bernard    And also I remain in ignorance. However shall we come to know?

Cheryl    Well, in fact, no matter how long we three continue from now in the pattern we have followed so far—namely, the pattern in which you two state back-and-forth that still you do not yet know whose number is larger and then I tell you yet again that no further amount of that back-and-forth will enable you to know—then still after as much repetition of that pattern as we can stand, you will not know whose number is larger! Furthermore, I could make that same statement a second time, even after now that I have said it to you once, and it would still be true. And a third and fourth as well! Indeed, I could make that same pronouncement a hundred times altogether in succession (counting my first time as amongst the one hundred), and it would be true every time. And furthermore, even after my having said it altogether one hundred times in succession, you would still not know who has the larger number!

Albert    Such powerful new information! But I am very sorry to say that still I do not know whose number is larger.

Bernard    And also I do not know.

Albert    But wait! It suddenly comes upon me after Bernard’s last remark, that finally I know who has the larger number!

Bernard    Really? In that case, then I also know, and what is more, I know both of our numbers!

Albert    Well, now I also know them!

 


Question. What numbers did Cheryl give to Albert and Bernard?

If you can determine the answer, make comments below or post a link to your solution. I have posted my own solution on another post.

See my earlier transfinite epistemic logic puzzles, with solutions. These were inspired by Timothy Gowers’s example.

 

Now I know!

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.

infinity

 

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.

  1. 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$.
  2. 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.