# Monthly Archives: November 2008

## Doing Calculus on the Rationals (with the help of Nonstandard Analysis)

Nonstandard Analysis is usually used to introduce infinitesimals into the real numbers in an attempt to make arguments in analysis more intuitive.

The idea is that you construct a superset $\mathbb{R}^*$ which contains the reals and also some infinitesimals, prove that some statement holds of $\mathbb{R}^*$, and then use a general “transfer principle” to conclude that the same statement holds of $\mathbb{R}$.

Implicit in this procedure is the idea that $\mathbb{R}$ is the real world, and therefore the goal is to prove things about it. We construct a field $\mathbb{R}^*$ with infinitesimals, but only as a method for eventually proving something about $\mathbb{R}$.

We can do precisely the same thing with $\mathbb{Q}$ instead of with $\mathbb{R}$. But, in Weak Theories of Nonstandard Arithmetic and Analysis, Jeremy Avigad observed that if we don’t care about transferring the results back down to $\mathbb{Q}$, then we can get all the basic results of calculus and elementary real analysis just by working with $\mathbb{Q}^*$, and without ever having to construct the reals.

Filed under Uncategorized

## Games Which are Impossible to Analyze

In the last post, I mentioned the computational complexity of various games. To be explicit, we consider each “game” $G$ to actually be a sequence of games $\{G_n\}$ for $n\in \mathbb{N}$. For example, $\text{checkers}_n$ would be checkers played on an $n\times n$ board. The problem was then to analyze the computational complexity of the function which takes $n$ and tells you which player has a winning strategy and what the winning strategy is. I’ll call that function the analysis function of $G$.

Are there any games which can actually be played in the real world with an undecidable analysis function? Robern Hearn, in the same thesis that I linked to last time, showed that the answer is yes.