let's play a game: on each turn t, you'll draw a tree of at most t labeled nodes. you have 3 labels to choose from; let's denote them ▲, ■, and ⬟.

there's one additional rule, which is that each tree you draw must not contain any previous tree - not even by skipping intermediate nodes. the sequence below^† is invalid because the first tree can be found inside the second (skipping a ■ in the right branch):

(your trees don't have to be binary - they're just easier to CSS than any arbitrary tree)

here's the question: how many turns can this game go on for? can it be played forever, or is there an upper bound?

first, the bad news: you can't play this game forever. this was proven by Joseph Kruskal in 1960, and it applies to this game regardless of how many labels you can choose from: any infinite sequence of trees labeled in this fashion must contain a pair of trees where the earlier tree is contained in (homeomorphically embeddable, the cool kids say) the later tree.

now for the much worse news: the longest game you can play goes on for far, far longer than any mortal can possibly comprehend. power towers, the Ackermann function, even Graham's number are all nothing compared to this monumental number. it's hard to believe that something so far detached from the well-known "big numbers" can still be considered finite.

harder yet is understanding how such an enormous number can stem from such seemingly simple rules. it's absurd! trees aren't some arcane structure understood only by mathematicians, and 3 labels is the fewest you can play this game with that isn't completely trivial (one label leads to a game of length 1, and two labels produce a maximum of 3 turns).

proving this result is best done using second-order arithmetic, a system that can meaningfully represent infinity (by way of infinite sets)^††. this isn't strictly necessary — the finite world of Peano arithmetic can prove this result, too — but at a ridiculous cost: doing so requires around 2↑↑1000 symbols to be defined (that's a power tower of a thousand 2's).

I find this fact perversely hilarious. the infinities looked upon this number and said, “no, you are not one of us.” but nor did the finite numbers want this number, and so they constructed a number so remote, so inaccessible, that they themselves can never prove its finiteness within the bounds of our universe.

this number is called TREE(3), by the way. Numberphile has produced a video about it that does a good job of explaining the setup:

there is also an incredibly helpful answer on the Math StackExchange that builds up to the number in a way that's kind of comprehensible to non-mathematicians: