TITLE: Infinite Chomp is a finite game?
QUESTION [6 upvotes]: Regard the $(\omega \times \omega)$ version of Chomp. It is stated here that the version of chomp on an infinite chocolate bar is in fact a finite game. I am confused by this statement. Isn't it possible that the two player in turn take a $(1 \times 1)$ bite out of the chocolate for example only in the top row? Therefor playing an infinite game? Or is a bite $(n \times m) \in \mathbb{N}^2$, resulting in a finite chocolate bar after the first move. I only have this informal definition of the problem which is confusing to me.

REPLY [3 votes]: I think the distinction you may be missing here is the difference between $\omega$ as a set — that is, the set of all natural numbers $\{0,1,2,\ldots\}$— and $\omega$ as an ordinal, the entity which corresponds to the ordering $0\lt1\lt2\lt3\lt\ldots$ of the naturals.  The two concepts are obviously closely related, but they're not quite identical; for instance, consider $\omega+\omega$, defined as the set $\{0,1,\ldots,\omega, \omega+1, \ldots\}$ and similarly as the ordering $0\lt1\lt\ldots\lt\omega\lt\omega+1\lt\ldots$ on those entities.  Then there's a simple isomorphism from the set $\omega+\omega$ to the set $\omega$: for all integers $i$, map $i$ to $2i$ and map $\omega+i$ to $2i+1$. But the two aren't isomorphic as ordered sets; every element in $\omega$ has an immediate predecessor, but the element $\omega$ in the order $\omega+\omega$ doesn't have one.  To see why ordinals are the right concept, consider the nearly-trivial $1\times\omega$ version of Chomp; then the positions of this game correspond precisely to the ordinals $0, 1, \ldots, \omega$, and we can move from a position $P$ to a position $Q$ precisely if $Q\lt P$; we have a natural order on positions.
Now, let's take a look at the $2\times\omega$ case: positions of $2\times\omega$ Chomp aren't ordinals themselves (they're pairs $(m,n)$ with $0\leq m\leq n\leq\omega$), but the key point is that we can put them into one-to-one correspondence with ordinals, in such a way that every legal chomp move takes us to a lower ordinal; that is, there's an order-preserving isomormphism between the two.  To see this, we can break things into two cases: $n$ finite and $n=\omega$.  For $n$ finite, there are obviously $n+1$ different values $(0,1,\ldots,n)$ for $m$; each of these is reachable from the positions with the same $n$ and higher $m$, but none is reachable from any position with lower $n$, so we can order them $(0,0)\lt(0,1)\lt(1,1)\lt(0,2)\lt(1,2)\lt\ldots$ — that is, by increasing $n$, with $m$ increasing within each value of $n$; you should be able to construct an order isomorphism that maps this portion of the overall order of positions into the order $\omega$.  Now, 'after' these we can put all the positions with $n=\omega$ and $m$ finite, ordered by $m$: $(0,\omega)\lt(1,\omega)\lt(2,\omega)\ldots$; this is trivially order-isomorphic to $\omega$.  And finally, after all these comes the initial position $(\omega,\omega)$.  This gives us an overall order of order-type $\omega+\omega+1$ on the set of all $2\times\omega$ Chomp positions; we know that from any given position $P$, any legal move to a position $Q_i$ will have $Q_i\lt P$ under this ordering.
So how does this help?  Well, it helps because the ordinals are (essentially by definition) well-ordered — any set of ordinals has a least element, and so in particular there can be no infinite descending chain $O_0\gt O_1\gt O_2\gt\ldots$ (this is closely related to the Axiom of Foundation/Axiom of Regularity in set theory).  As others have said, this is what's meant by the game being finite; there's no specific bound on how long the game could take, but there's no infinite sequence of plays available from the starting position.
The $\omega\times\omega$ case is substantially more complicated, but it still falls to a similar analysis; the key is that each position can be mapped to some ordinal in order-preserving fashion.  One way of doing this: suppose the initial bite is at $(m,n)$ with $n\gt m$ (an obvious symmetry applies).  Then we can think of the bite as splitting the bar up into two $n\times\omega$ Chomp bars, the 'horizontal' and 'vertical' leftovers $B_h$ and $B_v$ (with one of these sub-bars already having been chomped down to an $m\times\omega$ piece).  But since each of $B_h$ and $B_v$ is a subposition of a $n\times\omega$ position, there are individual horizontal and vertical well-orderings $H = (H_0\lt H_1\lt\ldots)$ and $V = (V_0\lt V_1\lt\ldots)$ on them (you can see how to order the $n\times\omega$ positions for any $n$ in a fashion analagous to the $2\times\omega$ positions); and we can combine the horizontal and vertical orderings to form the product order, $H\cdot V = ((H_0, V_0)\lt (H_1,V_0)\lt\ldots\lt(H_0,V_1)\lt(H_1,V_1)\lt\ldots)$ (see http://en.wikipedia.org/wiki/Ordinal_arithmetic for more details on this process).  Finally, we can stack all of these positions up by increasing $n$ (the 'size' of the original bite - or more abstractly, the smallest value of $n$ such that there are no uneaten points northeast of $(n,n)$).  It's hard to piece all of these together, but hopefully you can get some sense of how this offers an overall well-ordering on the set of possible $\omega\times\omega$ Chomp positions.  Once we have that well-ordering, what its specific type is isn't relevant - merely the fact that it is a well-ordering is enough for the well-foundedness principle to apply and for us to conclude that the game is finite.