# Monthly Archives: August 2008

## Lots of Fun Math Papers

In the course of looking up a link for my last blog entry, I discovered the MAA Writing Awards site, which collects many pdfs of articles that have won MAA writing awards.  From browsing it a bit, it seems to be a goldmine of fun math articles.

Filed under Uncategorized

## Non-Rigorous Arguments 1: Two Formulas For e

I’m a big fan of non-rigorous arguments, especially in calculus and analysis. I think there should be a book cataloging all the beautiful, morally-true-but-not-actually-true proofs that mathematicians have advanced, but until that time I’ll try to at least catalog a few of them on my blog.

This first one is Euler’s original argument for the equality of two expressions (both of which happen to define $e$):

$\displaystyle{\sum_{n=0}^\infty \frac{1}{n!} = \lim_{n\to\infty}\left(1 + \frac{1}{n}\right)^n}$

I’ll also sketch how this can be made rigorous in non-standard analysis.

Filed under Uncategorized

## A Curious Application of Ambiguity with Respect to the Possessive Form

Why did the chicken cross the island on Lost?

Filed under Uncategorized

## Almost a Number-Theoretic Miracle

An arithmetic statement is one made up of quantifiers “$\forall n\in\mathbb{N}$,” “$\exists n\in \mathbb{N}$,” the logical connectives “and,” “or,” “not”, function symbols $\times$, $+$, constants ${0}$, $1$, and variables $n$ which are bound by the aforementioned quantifiers.

It is known that there is no algorithm which will decide whether or not an arithmetic statement is true or not. This shouldn’t be surprising, since if there were such an algorithm, it would be able to automatically prove Fermat’s Last Theorem, settle Goldbach’s Conjecture and the Twin Prime Conjecture, etc.

However, if we call a quasi-arithmetic statement one which uses the quantifiers “for all but finitely many $n \in\mathbb{N}$” (denoted “$\forall^\infty n\in\mathbb{N}$”) and “there exists infinitely many $n\in\mathbb{N}$” (denoted “$\exists^\infty n\in\mathbb{N}$”) instead of “$\forall n\in\mathbb{N}$” and “$\exists n\in\mathbb{N}$”, then we do have an algorithm for deciding whether a quasi-arithmetic statement is true or not!

Filed under Uncategorized

## Set Theory and Weather Prediction

Here’s a puzzle:

You and Bob are going to play a game which has the following steps.

1. Bob thinks of some function $f\colon \mathbb{R}\to\mathbb{R}$ (it’s arbitrary: it doesn’t have to be continuous or anything).
2. You pick an $x \in \mathbb{R}$.
3. Bob reveals to you the table of values $\{(x_0, f(x_0))\mid x_0\ne x\}$ of his function on every input except the one you specified
4. You guess the value $f(x)$ of Bob’s secret function on the number $x$ that you picked in step 2.

You win if you guess right, you lose if you guess wrong. What’s the best strategy you have?

This initially seems completely hopeless: the values of $f$ on inputs $x_0\ne x$ have nothing to do with the value of $f$ on input $x$, so how could you do any better then just making a wild guess?

In fact, it turns out that if you, say, choose $x$ in Step 2 with uniform probability from $\lbrack 0,1\rbrack$, the axiom of choice implies that you have a strategy such that, whatever $f$ Bob picked, you will win the game with probability 1!

Filed under Puzzles, Set Theory

## Making Money Disappear Through Infinite Iteration

In Joel David Hamkin’s paper Supertasks and Computation, he relates the following puzzle: Suppose that you have a countable infinity of dollar bills, and one day you meet the devil, who offers you the following bargain: In the first half minute from now, the devil will give you two dollar bills, and take one from you in return. In the quarter minute after that, the devil again gives you two dollar bills, and takes one from you in return. And so on, in the eighth of a minute after that, and the sixteenth of a minute after that, etc. After a minute, the whole transaction is complete. Should you take this bargain?

The answer is “no” and the reason is that the devil could do the following: Think of the bills you have at the start as being numbered 1, 3, 5, etc. and imagine that the devil has an initial pile of bills numbered 2, 4, 6, etc. Then on the nth transaction, the devil gives you the two lowest-numbered bills from his initial pile and takes bill n from you (one can easily show that you have bill n in your possession at this point). Since the devil takes bill n from you on the nth transaction, he gets all the bills in the end and you end up with nothing.

So, even though you start with infinitely many bills and each transaction produces a net gain of one bill for you, after all the transactions are done you have nothing.

In that puzzle, the devil was able to use a tricky strategy to give you more than he took at each stage and still end up with everything. In the following puzzle, which made the rounds when I was a graduate student, no matter what the devil does, he takes everything from you!

You and the devil are taking a train ride together. The train stops at each ordinal. At stop 0, you have countably infinitely many dollar bills. At each stop, the devil does the following two things (in order):

1. If you have nonzero number of dollar bills, the devil takes one and destroys it.
2. The devil gives you countably infinitely many dollar bills.

Prove that no matter what the devil does, when the train reaches stop $\omega_1$ (the first uncountable ordinal), you will have no money.

Solution below.

Filed under Ordinals, Puzzles, Set Theory

## What do We Have to Know About a Function in Order to Compute its Definite Integral?

Suppose that $f$ is a continuous function from $\lbrack 0,1\rbrack$ to $\lbrack 0,1\rbrack$ and that we have a program which computes it. (Ignore for now exactly what it means to “compute” a real-valued function of the reals. Suffice it to say that almost every natural continuous function you come across is computable). If we want to compute $\int_{0}^1 f(x)\,dx$, say to within an accuracy of $0.001$, how would we do it, and would we need any further information about $f$ in order to do it?

The obvious thing to do is to compute a Riemann sum $R(f,n)=\sum_{i=0}^{n-1} (1/n)\cdot f(i/n)$ for some large $n$. However, this could be arbitrarily far from the true value of $\int_0^1 f(x)\,dx$. For example, $f(i/n)$ might be 0 for all $0 \leq i \leq n-1$, but $f$ might curve sharply up in between each $i/n$ and $(i+1)/n$ so that its definite integral is arbitrarily close to 1.

However, since $f$ is continuous on $\lbrack 0,1\rbrack$, it is uniformly continuous. This means that for all $\epsilon > 0$ there is a $\delta > 0$ such that whenever $|x - y| < \delta$, $|f(x) - f(y)| < \epsilon$. If we could compute a function $\delta(\epsilon)$ such for all $\epsilon > 0$, whenever $|x - y| < \delta(\epsilon)$, $|f(x) - f(y)| < \epsilon$, then we could compute the definite integral of $f$ with arbitrary accuracy: If we want to know $\int_0^1 f(x)\, dx$ to within 0.001, then choose $n$ so that $1/n < \delta(0.001)$ and we can take $R(f,n)$, since $|R(f,n) - \int_0^1 f(x)\,dx| < 0.001$.

So, one answer to the question “What extra information do we need in order to compute $\int_0^1 f(x)\,dx$?” is: a function $\delta(\epsilon)$ witnessing $f$‘s uniform continuity.

In 1998, Alex Simpson showed, building on ideas of Ulrich Berger and others, that another answer is: Nothing!

Filed under Programming

## Rosser’s Clever Improvement to Gödel’s Original First Incompleteness Theorem

Sometimes it’s the case that in a first-order system T in which you can do number theory there is a property P(n) of natural numbers such that the following two seemingly contradictory statements hold:

For every n, T proves P(n)

and

T does not prove that for all n, P(n)

To see that these statements are not actually contradictory, replace T with a person Bob and observe that it’s certainly possible that

For every a, b, c > 1, and n > 2, Bob can verify that an + bncn.

is true but that

Bob can verify that for every a, b, c > 1, and n > 2, an + bncn.

is false, since for the first statement it suffices for Bob to be able to remember grade school arithmetic, whereas for the second statement to be true Bob must be able to prove Fermat’s Last Theorem.

If it’s the case that there is a property P(n) such that for all n, T proves P(n) but it is not the case that T proves for all n, P(n), then we could actually add “There exists an n such that ~P(n)” to T and still have a consistent theory. Thus, we might be in the even stranger situation where

For every n, T proves P(n).

but

T proves that there exists an n such that ~P(n)

even though T is consistent. Such a T is called ω-inconsistent. (T is called ω-consistent if it is not ω-inconsistent.)

On the other hand, note that it’s not really possible that

Bob cannot verify that there exists a, b, c > 1 such that a2 + b2 = c2.

given that there are such a, b, and c, since we could just tell Bob an example and have him use his knowledge of grade-school arithmetic to verify it.

Similarly, for all the theories T we will consider, if there exists an n such that T proves P(n), then T proves that there exists an n such that P(n).

Now consider the following argument, which is a rough version of Gödel’s original argument for the first incompleteness theorem:

Suppose that T is a complete theory (meaning that for every sentence S, either T proves S or T proves ~S.) Let G be the sentence “G is not provable in T” which it turns out we can interpret in the language of number theory. Suppose that G is provable in T. Then there exists a proof of G in T, so T can prove “There exists a proof of G in T.” But this is the same as ~G. So, since T can prove both G and ~G, it is inconsistent.

Now suppose that G is not provable in T. If T was ω-consistent, then since T is also complete, we would know that T proved “There is no proof of G in T.” But this is equivalent to G. So, since T can prove both G and ~G, it is inconsistent.

So, what we have proven is that if T is ω-consistent, then it is incomplete. But Gödel’s First Incompleteness Theorem is usually stated as: If T is consistent, then T is incomplete. This is a stronger and cleaner statement. (Note that in both statements we are assuming that number theory can be expressed in T.)

J. Barkley Rosser was able to prove this stronger statement with a very clever change in the self-referential statement G.

1 Comment

Filed under Provability Logic, Self-Reference

## Great Intro to Intuitionistic Logic

At Mathematics and Computation, there’s a really good accessible introduction to intuitionistic logic called Intuitionistic Logic for Physics. It also includes some nice accessible remarks on smooth infinitesimal analysis.

## Is the “Hardest Logic Puzzle Ever” too Easy?

In 1992, the philosopher George Boolos gave what he called the “Hardest Logic Puzzle Ever”, which he attributed to Raymond Smullyan. In 2008, a clever paper by two graduate students, Brian Rabern and Landon Rabern, appeared in the philosophical journal “Analysis” which gave a simpler solution to the puzzle than Boolos gave—and furthermore claimed that a solution to a stronger puzzle was possible!

As its name implies, the “Hardest Logic Puzzle Ever” has a number of complicating factors which will be irrelevant for this discussion. Instead, consider the following much simpler puzzle which will do just as well.

You are on an island populated by knights and knaves. Knights always tell the truth; knaves always lie. You meet a inhabitant of the island who you know is holding up either 1, 2, or 3 fingers behind his back. You don’t know if this inhabitant is a knight or a knave. By asking two yes-or-no questions, determine how many fingers the inhabitant has behind his back.

There are a number of ways to solve this. One solution follows from the observation that, for any question Q, if you ask a inhabitant of the island

If I asked you question Q, would you say “yes”?

then you will get a truthful response to question Q. A knight will tell the truth about his truthful response to Q, whereas a knave would lie about his false response to Q.

So one solution would be to ask

If I asked you if you were holding 1 finger up, would you say “yes”?

If the inhabitant says “yes”, then you know he is holding 1 finger up. On the other hand, if the inhabitant says “no”, then you ask “If I asked you if you were holding 2 fingers up, would you say `yes’?” If the inhabitant says “yes”, then he is holding 2 fingers up, otherwise he is holding 3 fingers up.

This works, and it seems like you can’t do any better: There are three possibilities for how many fingers the inhabitant could be holding up, and since you can only ask yes-or-no questions, you couldn’t determine which of the three possibilities holds with only one question. But this is exactly what Rabern and Rabern claim you can do.

Filed under Puzzles, Self-Reference

## One Puzzle with Two Totally Different Solutions

Peter Winkler‘s excellent book Mathematical Puzzles: A Connoisseur’s Collection has in it the problem of finding a partition of $\mathbb{R}^3$ into disjoint non-trivial circles. (Here “non-trivial” means “not a point.”) Winkler gives a very clever solution which is purely geometric.

Later, I read the same problem in Krzysztof Ciesielski‘s excellent book Set Theory for the Working Mathematician. In that book Ciesielski gives an almost purely set-theoretic solution.

I’ll discuss both solutions below. 　(Don’t read on yet if you want to think about the puzzle first.)

Filed under Ordinals, Puzzles, Set Theory

## Multivariable Calculus with Nilpotent Infinitesimals: More Smooth Infinitesimal Analysis

This is a continuation of my earlier post on smooth infinitesimal analysis. In this installment, I’ll show how the definition of a “stationary point” in Smooth Infinitesimal Analysis leads directly to a nice substitute for the Lagrange multipliers method. Then I’ll show how you can define differential forms as objects which assign a “signed volume” to genuinely infinitesimal objects, and how you can get Stokes’s Theorem (and the divergence theorem, etc.) in SIA.

## Ax’s Theorem: An Application of Logic to Ordinary Mathematics

There are a number of applications of logic to ordinary mathematics, with the most coming from (I believe) model theory. One of the easiest and most striking that I know is called Ax’s Theorem.

Ax’s Theorem: For all polynomial functions $f\colon \mathbb{C}^n\to \mathbb{C}^n$, if $f$ is injective, then $f$ is surjective.

Very rough proof sketch: The field $\mathbb{C}$ has characteristic 0, so each of the axioms $\psi_p \equiv \overbrace{1 + 1 + \cdots + 1}^{p\text{ 1's}} \ne 0$ (where $p$ is a prime) is true in $\mathbb{C}$. Suppose that some polynomial is injective but not surjective. Then there is a proof of that fact from the axioms of algebraically closed fields, together with the axioms $\psi_p$. But a proof can only use finitely many axioms. Therefore, there must be some $\psi_p$ that is not used in the proof. One can then show that there would be a polynomial function which is injective but not surjective from $F^n$ to $F^n$, where $F$ is a finite field of characteristic $p$. But this is impossible, because $F$ is a finite set.

More details below.

Filed under Model Theory

## Did we learn all there is to know about exponentiation in sixth grade?

By sixth grade (I think), you’ve learned some basic facts about addition, multiplication, and exponentiation over the natural numbers: you’ve learned that addition and multiplication are commutative and associative, that multiplication distributes over addition, that 0 is an identity for addition and 1 is an identity for multiplication, and the following simplification rules for exponents:

1x = 1

x1 = x

xy + z = xyxz

(xy)z = xzyz

(xy)z = xyz

Tarski called these the High School Identities (but I think we learn them before high school) and asked if every identity true in the natural numbers that just used addition, multiplication, and exponentiation followed from them.

The answer turned out to be “no.”

Filed under Universal Algebra

## Löb’s Theorem: Santa Claus and Provability

Consider the following argument for the existence of Santa Claus (which is called Curry’s paradox):

Let S be the sentence

If S is true, then Santa Claus exists.

Lemma: S is true.

Proof. S is of the form “If P, then Q.” so to show S we just have to assume P and show Q. So, assume that S is true (with the goal of showing that Santa Claus exists). Since we’ve assumed that S is true, it follows that if S is true, then Santa Claus exists (since that’s exactly what S says). Then, since S is true, Santa Claus exists. $\square$

Corollary: Santa Claus exists.

Proof. Since S is true, it is the case that if S is true, then Santa Claus exists (since that’s exactly what S says). Therefore, since S is true, Santa Claus exists. $\square$

Since Santa Claus doesn’t exist, this argument seems to just prove that informal reasoning combined with self-reference can often lead you astray. Can we extract any interesting theorems out of this argument? It turns out that we can.

1 Comment

Filed under Provability Logic

## Kreisel’s No-Counterexample Interpretation: How can we turn proofs in elementary number theory into programs?

For every true number-theoretic statement of the form “For all n there is an m such that P(n, m)” there is a witnessing function f such that for all n, P(n, f(n)) is true.

For example, a witnessing function for the statement “For all n there is an m such that m > n and m is prime” is any function which takes a number and returns a prime higher than that number, which certainly exists.

In general, if the statement “For all n0 there is an m0 such that for all n1 there is an m1 such that … for all nr there is an mr such that P(n0, m0, …, nr, mr)” is true then there are witnessing functions f0(n0), …, fr(n0, …, nr) such that for all n0, …, nr, P(n0, f0(n0), …, nr, fr(n0, …, nr)) is true.

Because it’s the case that if a number-theoretic statement is true, then its witnessing functions exist, we might hope that it woud be the case that if a number-theoretic statement is provable, then its witnessing functions are computable, that is, that we could extract a computer program for the witnessing functions from the proof.

For example, a computable witnessing function for the statement “For all n there is an m such that m > n and m is prime” can be easily extracted from Euclid’s proof that there are infinitely any primes.

Can this always be done? Unfortunately the answer is no, but Georg Kreisel’s No-Counterexample Interpretation gives an elegant piece of computational data that can be extracted from any provable number-theoretic statement.

Filed under Proof Theory

## How can one do calculus with (nilpotent) infinitesimals?: An Introduction to Smooth Infinitesimal Analysis

Many mathematicians, from Archimedes to Leibniz to Euler and beyond, made use of infinitesimals in their arguments. These were later replaced rigorously with limits, but many people still find it useful to think and derive with infinitesimals.

Unfortunately, in most informal setups the existence of infinitesimals is technically contradictory, so it can be difficult to grasp the means by which one fruitfully manipulates them. It would be useful to have an axiomatic framework with the following properties:

1. It is consistent.

2. The system acts as a good “intuition pump” for the real world. In particular, this entails that if you prove something in the system, then while it won’t necessarily be true in the real world, there should be a high probability that it’s morally true in the real world, i.e., with some extra assumptions it becomes true. It should also ideally entail that many of the proofs of Archimedes, et al., involving infinitesimals can be formulated as is (or close to “as is”).

“Smooth infinitesimal analysis” is one attempt to satisfy these conditions.