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!

This was shown by David Marker and Ted Slaman in this note. The proof goes as follows.

First, observe that “(\exists^\infty n\in\mathbb{N})\, \phi(n)” is equivalent to “\neg (\forall^\infty n\in\mathbb{N})\, \neg \phi(n)”, so that we can eliminate all occurrences of \exists^\infty.

Next, note that “(\forall^\infty n\in \mathbb{N})\, \phi(n)” is equivalent to “(\exists m\in\mathbb{N})\,(\forall n > m)\, \phi(n).” Thus, we can replace \forall^\infty n with Qn, where Qn is defined to be the quantifier (\exists m)\, (\forall n > m).

Now, prove that all statements involving only the quantifier Q are true in \mathbb{N} iff they are true in \mathbb{R}. This is proved by induction on the structure of the formulas. The crucial step is the following: If (Qn)\,\phi(n) holds in \mathbb{N}, then \phi(n) is true for all sufficiently large natural numbers. However, a subset of \mathbb{R}^n defined only by quantifiers over \mathbb{R} is a semialgebraic set, and it is known that all semialgebraic subsets of \mathbb{R} are finite unions of points and intervals. Therefore, if all sufficiently large natural numbers are in some semialgebraic set, then all sufficiently large real numbers must also be in that set.

So, we have reduced the problem to that of deciding whether or not sentences involving the quantifier Q are true over \mathbb{R}. But, by a result of Tarski’s, there is an algorithm which will decide whether or not statements using the quantifiers \forall and \exists is true over \mathbb{R} and Q can be defined in terms of \forall and \exists.

How does Tarski’s proof work? The first step is to observe that deciding quantifier-free statements is easy, since it’s just a computation. So, the second step is to systematically eliminate quantifiers from statements. One instance of quantifier elimination is familiar to everyone is: \exists x\, ax^2 + bx + c = 0 is equivalent to b^2 - 4ac \geq 0. This follows from the quadratic formula. Sturm’s theorem is a generalization of this test which will tell you how many distinct real roots any polynomial has, and Tarski’s theorem is a generalization of Sturm’s theorem.

For information on practical algorithms for quantifier elimination over the reals see Algorithms in Real Algebraic Geometry.

About these ads

2 Comments

Filed under Uncategorized

2 responses to “Almost a Number-Theoretic Miracle

  1. Wow! Which things are decidable and which things are undecidable keeps on surprising me.

  2. none

    Wait, does that say that the twin prime conjecture is decidable? For all but finitely many n, at least one of {n,n+2} is composite.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s