Monthly Archives: September 2008

Playing Games in the Transfinite: An Introduction to “Ordinal Chomp”

Chomp is a two-player game which is played as follows: The two players, A and B, start with a “board” which is a chocolate bar divided into $n \times m$ small squares. With Player A starting, they take turns choosing a square and eating it together with all squares above and to the right. The catch is that the square at the lower left-hand corner is poisonous, and the player who is forced to eat it loses.

This image from the Wikipedia article shows a typical sequence of moves for a $5\times 3$ chocolate bar:

At this point, Player A is forced to eat the poisoned square and hence loses the game.

Although the question of what the winning strategies are for this game is very much an open problem, the question of who has a winning strategy is not: On the $1\times 1$ board, Player B wins (since Player A must eat the poison piece on his first move). But for any other board, Player A has a winning strategy.

To see why, suppose not. Then if Player A’s first move is to eat just the one square in the top right-hand corner, Player B must have a winning response (since we are supposing that Player B has a winning response to any move that Player A makes). But if Player B’s response is winning, then Player A could have simply made that move to start with.

However, suppose we play Chomp not just on $n\times m$ boards, but on $\alpha\times\beta$ boards, where $\alpha$ and $\beta$ are arbitrary ordinals. The game still makes sense just as before, and will always end in finite time, but Player A no longer wins all of the time (there will no longer be a top right-hand corner square if either $\alpha$ or $\beta$ is a limit ordinal).

Scott Huddleston and Jerry Shurman investigated Ordinal Chomp in this paper, and showed that it has a number of interesting properties. I’ll describe a few of them below.

Filed under Uncategorized

Intuitively, for any property $P(x)$ of sets, there should be a set $\{x \mid P(x)\}$ which has as its members all and only those sets $x$ such that $P(x)$ holds. But this can’t actually work, due to Russell’s Paradox: Let $b = \{x\mid x\notin x\}$, and then you can derive a contradiction from both $b\in b$ and $b\notin b$.

The standard solution to this is essentially to forbid the construction of any set which is too big. This solves the problem since you can prove that there are many sets which are not members of themselves, making $b$ too big to be a set. But you also end up throwing out many sets which you might want to have: for example, the set of all sets, the set of all groups, etc.

Randall Holmes recently published a paper espousing another solution: instead of forbidding the construction of sets which are too big, forbid the construction of sets which are too asymmetric. Details below.

1 Comment

Filed under Uncategorized

The Undecidability of Identities Involving Sine, Exponentiation, and Absolute Value

In the book A=B, the authors point out that while the identity

$\displaystyle{\sin^2(|10 + \pi x|) + \cos^2(|10 + \pi x|) = 1}$

is provable (by a very simple proof!), it’s not possible to prove the truth or falsity of all such identities. This is because Daniel Richardson proved the following:

Let $\mathcal{R}$ denote the class of expressions generated by

1. The rational numbers, and $\pi$.
2. The variable $x$
3. The operations of addition, multiplication, and composition.
4. The sine, exponential, and absolute value functions.

Then the problem of deciding whether or not an expression $E$ in $\mathcal{R}$ is identically zero is undecidable. This means as well that the problem of deciding whether or not two expressions $E_1, E_2\in \mathcal{R}$ are always equal is also undecidable, since this is equivalent to deciding if $E_1 - E_2 = E_1 + (-1)\cdot E_2$ is identically zero.

A summary of Richardson’s proof (mostly from Richardson’s paper itself) is below.

Filed under Uncategorized

A Geometrically Natural Uncomputable Function

There are many functions from $\mathbb{N}$ to $\mathbb{N}$ that cannot be computed by any algorithm or computer program. For example, a famous one is the halting problem, defined by $f(n) = 0$ if the $n$th Turing machine halts and $f(n) = 1$ if the $n$th Turing machine does not halt. Another one in the same spirit is the busy beaver function.

We also know a priori that there must be uncomputable functions, since there are $2^{\aleph_0}$ functions from $\mathbb{N}$ to $\mathbb{N}$ but only $\aleph_0$ computer programs. But that is nonconstructive, and the two examples I gave above seem a bit like they’re cheating since their definitions refer to the concept of computability. Is there a natural example of an uncomputable function that does not refer to computability?

In this paper, Alex Nabutovsky found what I think is a great example of such a function from geometry. Details below.

Filed under Uncategorized

Integrability Conditions (Guest Post!)

Please enjoy the following guest post on differential geometry by Tim Goldberg.

A symplectic structure on a manifold $M$ is a differential $2$-form $\omega$ satisfying two conditions:

1. $\omega$ is non-degenerate, i.e. for each $p \in M$ and tangent vector $\vec{u}$ based at $p$, if $\omega_p(\vec{u},\vec{v}) = 0$ for all tangent vectors $\vec{v}$ based at $p$, then $\vec{u}$ is the zero vector;
2. $\omega$ is closed, i.e. the exterior derivative of $\omega$ is zero, i.e. $\mathrm{d} \omega = 0$.

In trying to come up with answers to questions like “what do you do?” and “what is symplectic geometry?” that would be accessible to an advanced undergraduate or beginning graduate student, I’ve tried to come up with fairly intuitive descriptions of what the two symplectic structure conditions really mean.

Non-degeneracy is pretty easy, because my intended audience is certainly familiar with the dot product in Euclidean space, and probably familiar with more general machinery like inner products and bilinear forms. A bilinear form on a vector space over a field $\mathbb{F}$ is just an assignment of a number in $\mathbb{F}$ to each pair of vectors, in such a way that the assignment is linear in each vector in the pair. A bilinear form is called non-degenerate if the only thing that pairs to zero with every single vector is the zero vector. A $2$-form on $M$ is a collection $\omega = \{ \omega_p \mid p \in M \}$ of skew-symmetric bilinear forms, one for each tangent space of $M$. Saying that $\omega$ is non-degenerate is saying that each of these bilinear forms is non-degenerate.

It’s much less clear how to describe to the uninitiated what the closed condition means. It’s even a bit unclear why this condition is required in the first place. A pretty nice answer came up yesterday, in a reading group I attend that is trying to learn about generalized complex structure. We are going through the PhD thesis of Marco Gualtieri, titled “Generalized Complex Geometry”. It is available at the following websites:

http://front.math.ucdavis.edu/0401.5221

This was the first meeting, and Tomoo Matsumura was the speaker. He suggested that the requirement that $\mathrm{d} \omega = 0$ is an integrability condition. I had never thought of it this way, but I probably will from now on.