Sat, 08 Dec 2012 22:48:03 GMT

Again, I gave a talk for the best mathematics-club in the multiverse. This time, it is for "older" people, that is, pupils in their last year and young students. So I will try to keep this text short, assuming that the reader is able to find out some details, mostly from usual mathematical practice I know, himself. Also keep in mind that **a large part of this text was created during hasty evenings when I had other things to do. If something is wrong or not clear, feel free to tell me.**

I will use some results from Transfinite Chomp by S. Huddleston and J. Shurman which I found on this excellent post from Xor's hammer.

Also keep in mind**this is not a scientific paper**, I will not always put footnotes everywhere I use information from the named paper. Especially, I change the notation so it will (hopefully) be compatible with ZFC (that is, there is no set of ordinal Numbers, etc.), as I think I have seen proofs in that paper that are not correct because of this (but I might be mistaken).

**1 Finite Chomp**

Before understanding ordinal chomp, it is useful to know finite chomp, and what makes it so interesting. We will try to give a definition that is less "economic" than the usual ones, but much more compatible with the intuition of a chocolate bar, which is the usual metaphor for explaining chomp.

Keep in mind that these definitions are preliminary and will later be generalized.

**Definition:** As a slight abuse of notation, we identify every integer with the set of its preceding numbers. So , , , etc. - this will later fit into our definition of ordinal numbers. It has nice properties like being equivalent to . For now, it just helps us to have a simpler notation of the functions involved.

**Definition:** A *chocolate bar* is a function . The function is the *initial chocolate bar*. The function is the *final chocolate bar*. We may leave out the indices if their value is clear from the context. A legal move on an chocolate bar is some . Its application defines a new chocolate bar with . A chocolate bar is called *legal*, if it is acquired by applying a sequence of legal moves to , that is, if there exist such that . It is a *player 1 chocolate* bar if , and a *player 2 chocolate* otherwise. A legal move is called *player move*, if it is applied to a *player chocolate*.

**Lemma:** Every sequence of legal moves is finite.

**Proof:** Trivially, the number of preimages of decreases with every application, and the chocolate bar is finite.

**Definition:** Let be the set of sequences of legal moves starting from . These sequences form a tree of legal chocolate bars, where every edge connects a player 1 chocolate bar and a player 2 chocolate bar. A *strategy for player n* is a subtree in which

**Lemma:** For every there (strongly) exists a strategy for player 1 from the quadratic board .

**Proof:** Player 1 has to use , and then answer every move of the other player by . By a simple parity argument, it is easy to see that this enforces winning.

**Lemma:** For every chocolate bar there either (weakly) exists a strategy for player 1, (weak-)or one for player 2.

**Proof:** Note first that the "or" is exclusive here: Assume both existed, then consider a strategy for player 1. It will have some edge from to some player 2 chocolate bar from which winning is not possible for player 2 anymore. This contradicts the existence of a player 2 startegy.

On the other hand, assume there is no strategy for player 1 or player 2. Then there must be some move player 1 can make, such that player 2 still has no winning strategy after this move. Player 2 can answer with a move after which player 1 again has no winning strategy, and so on. This is a contradiction, as every game has finite length.

**Theorem:** For every there (weakly) exists a strategy
that wins against every other strategy
from .

**Proof:** Assume player 2 had a strategy . Then, since player 1 can make the first move , this strategy yields a player 1 strategy from the chocolate bar . Let be the a first move of this strategy, especially, . This yields a player 2 strategy for . But player 1 could also have chosen from the beginning, and would thus have a winning strategy. Contradiction, by the above Lemma.

So we have an explicit winning strategy for finite quadratic chocolate bars. Unfortunately, even though we know we can always win, we have no winning strategy except bruteforcing for the rest of the cases (except for some additional special cases like our above Lemma).

**Short introduction to ordinal numbers**

**Definition:** A (strict) *well-ordering* is a (strict) total ordering in which every set has a minimum. A *transitive set* is a set of which every element is also a subset. An *ordinal (number*) is a transitive set which is strictly well-ordered by the -Relation.

Here are some facts about ordinals which I will not prove:

**Transfinite Chomp**

A transfinite chocolate bar is defined similarily to the finite ones: An -chocolate bar is a function , the initial chocolate bar is again , and the final chocolate bar is again . The definitions of legal moves and their applications are also similar: A legal move on a chocolate bar is a pair such that , and the application yields a chocolate bar . A chocolate bar is legal if it is the result of finitely many applications of legal moves from .

We first prove a few generalizations for properties of finite chomp.

**Lemma:** The sequence of moves is legal if and only if .

**Proof:** By definition of the application and , . Therefore, , from which the Lemma follows directly.

**Theorem:** Every sequence of legal moves is finite.

**Proof:** By the Lemma, we know that the sequences and are decreasing, with at least one of them strictly decreasing at every step. Therefore, the sequence strictly decreases and must hence be finite.

**Lemma:** For every chocolate bar there either (weakly) exists a strategy for player 1, (weak-)or one for player 2.

**Proof:** The above proof only requires every game to be of finite length, so it also applies here.

**Lemma:** Player 1 has a winning strategy for , .

**Proof:** The strategy is the same as for the finite case, but we have no parity here. However, it is easy to see that after every player 2 move, player 1 recovers a quadratic state, from which he has a winning move again.

**Theorem:** If and have predecessors, and not both are equal to , then player 1 has a winning strategy for .

**Proof:** The argument is exactly the same as for the finite case.

One interesting part about transfinite chomp is that in some cases it is possible that the second player has a winning strategy.

**Theorem:** Let , and a legal chocolate bar be given. Then there is a unique such that player 2 wins .

**Proof: **Firstly we show uniqueness. Assuming the existence of with the property, player 1 could use to win, contradiction. We show the existence by induction on . Parallely, we maintain an cardinal , such that all ordinals occuring are in (we have to do this to make sure everything we talk about is a set)

**Corollary 1:** The second player wins if and only if .

**Proof:** For this is trivial. For trivially player 1 loses after every move not being of the form , so assume he chose such a move. Assuming there was no winning strategy for player 2 from this point is equivalent to assuming that there is no finite , such that with can be won by player 1. But this contradicts the uniqueness of the previous theorem. For , player 1 may just choose as first move and wins.

I will use some results from Transfinite Chomp by S. Huddleston and J. Shurman which I found on this excellent post from Xor's hammer.

Also keep in mind

Before understanding ordinal chomp, it is useful to know finite chomp, and what makes it so interesting. We will try to give a definition that is less "economic" than the usual ones, but much more compatible with the intuition of a chocolate bar, which is the usual metaphor for explaining chomp.

Keep in mind that these definitions are preliminary and will later be generalized.

- every branch of the tree ends in the final chocolate bar (that is, every branch is a whole game)
- the final chocolate bar in every branch is a player chocolate bar (that is, player wins)
- every player node in the subtree is adjacent to all the player n chocolate bars that are adjacent in the original tree (that is, the winning of player n does not depend on the choices of player

We distinguish between weak and strong existence and disjunction. Usually, this is done to get a finer distinction between constructive and non-constructive propositions. However, we do not want to get too deep into that topic. So we give an informal definition.

**Informal Definition:** The weak disjunction between two propositions and is a disjunction which we proved without giving a possibility of deciding which one of these actually holds inside the proof. Strong disjunction always comes with a theoretical possibility of decision directly inside the proof. The weak existence holds if only the existence of an object is proved, but there is no way of calculating it giving imlicitly with the proof. With strong existence comes such a way.

The distinction between those two kinds of existence and disjunction can be seen as one main difference between constructive and classical mathematics. While in constructive theories, one can set , in non-constructive mathematics, this is equivalent to usual disjunction.

On the other hand, assume there is no strategy for player 1 or player 2. Then there must be some move player 1 can make, such that player 2 still has no winning strategy after this move. Player 2 can answer with a move after which player 1 again has no winning strategy, and so on. This is a contradiction, as every game has finite length.

So we have an explicit winning strategy for finite quadratic chocolate bars. Unfortunately, even though we know we can always win, we have no winning strategy except bruteforcing for the rest of the cases (except for some additional special cases like our above Lemma).

Here are some facts about ordinals which I will not prove:

- The above notation is consistent with them.
- Every well-ordering on a set is isomorphic to some unique ordinal.
- Every decreasing sequence of ordinals is finite.
- The collection of ordinals forms a proper class. It is
__not__a set. - Every ordinal has a successor .
- Some ordinals also have a predecessor. If has no predecessor, we say that is a limit ordinal, writing .
- The smallest limit ordinal is called , it is the set of finite (natural) numbers.

**Definition:** A *cardinal* is an ordinal which satisfies .

We will only need cardinals in one small argument, in which we just need some "upper bound" for stuff we want to do.

A transfinite chocolate bar is defined similarily to the finite ones: An -chocolate bar is a function , the initial chocolate bar is again , and the final chocolate bar is again . The definitions of legal moves and their applications are also similar: A legal move on a chocolate bar is a pair such that , and the application yields a chocolate bar . A chocolate bar is legal if it is the result of finitely many applications of legal moves from .

We first prove a few generalizations for properties of finite chomp.

One interesting part about transfinite chomp is that in some cases it is possible that the second player has a winning strategy.

- For , we use induction on . If , , . Otherwise, we assume that for all legal chocolate bars with , there already exists a with the property. Especially then, for all legal chocolate bars that can be reached from by one move, there exist . Then is the solution: Trivially, every move player 1 makes leads to a state which player 2 can now win. Notice that if was our previous cardinal, is sufficient for everything we do (I am too lazy now to reason why should be sufficient).
- For every other , we may assume that for every pair of and a legal chocolate bar some already exists. Let be the to the power of the supremum of all previous cardinals. Furthermore, for every legal chocolate bar which can be reached from for some by a move with , we also already have a . Then the of all these exists (since the cardinality is bounded), and its own cardinality is bounded, and it trivially satisfies what we want.

Show comments (Requires JavaScript, loads external content and cookies from Disqus.com)