4
$\begingroup$

Let's play a game. You start with the ordinal $\alpha$ and I start with the empty sequence. Each turn, you decrease your ordinal, and I add a tree (where each node can have one of three labels), subject to the rule that no previous tree I choose can homeomorphically embed into the new one. Whoever moves last wins! What $\alpha$ should we choose to make the game fair, meaning whoever moves first will lose (so both players make the same number of moves)?

Note we can generalize this any number of labels $n$, or indeed, any well-quasi-ordered set instead of trees.


Well, note that the game can not go on forever, for two reasons. There is no infinite decreasing sequence of ordinals, so you must eventually hit $0$ and be out of moves. Likewise, due to Kruskal's tree theorem, I too can not go on forever. Indeed, we could have replaced trees with any other well-quasi-ordered set.

Now, what do we mean by fair? Well, since the tree picking game correspond to a game in the CGT sense, there is some ordinal $\alpha$ such that $T(3) - \alpha = 0$ (implying $T(3) = \alpha$, hence the title), where $T(3)$ is the tree picking game. $T(3)-\alpha$ is therefore the game described in the first paragraph. Since $T(3) - \alpha = 0$, whoever moves first in that game will lose (this is why we say whoever moves first will lose).

$\endgroup$
  • $\begingroup$ Presumably one can bound this by examining the proof of Kruskal's tree theorem? $\endgroup$ – Will Sawin Oct 27 '17 at 21:03
  • $\begingroup$ @WillSawin that would at least give an upper bound. $\endgroup$ – PyRulez Oct 27 '17 at 21:04
  • $\begingroup$ And get a lower bound by examining Friedman's proof of lower bounds for tree numbers? $\endgroup$ – Will Sawin Oct 27 '17 at 21:05
  • 1
    $\begingroup$ I think (and seem to remember that) the answer is in the paper "Well-partial-orderings and the big Veblen number" by van der Meeren, Rathjen and Weiermann (Arch. Math. Logic 54 (2014) 193–230), but I'm lost in a maze of twisty little papers all alike so I'm not sure this is really the right one. It's certainly relevant, though. $\endgroup$ – Gro-Tsen Oct 27 '17 at 22:27
  • $\begingroup$ @WillSawin Actually, it seems like the proofs are nonconstructive for the most part. $\endgroup$ – PyRulez Oct 28 '17 at 5:14
4
$\begingroup$

If Player 1 moves first, Player 2 wins the game if and only if $\alpha\leq o(T(3))$, where $o$ denotes the maximal order type of the well-quasi-order $T(3)$. This ordinal was studied by Diana Schmidt in her 1979 Habilitation thesis Well-partial orderings and their maximal order types, which might not be so easy to find online. The introduction of the 2015 Ph.D. thesis of Van der Meeren Connecting the two worlds: Well-partial-orders and ordinal notation systems does a nice quick survey of these questions in Section 1.2; the answer to the question is $\vartheta(\Omega^\omega\cdot 3)$, assuming you are talking about finite ordered unranked trees.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.