Writing Fermat's last theorem in arithmetic hierarchy

Question

Somehow connected with How natural numbers can be defined using primitive recursive $\Sigma_0^0$:

OK, so here's how Fermat's last theorem is formulated:

$$\forall x,y,z,n>2 \quad (x^n+y^n + z^n \rightarrow xyz = 0)$$

I get how this formula is $\Pi_1$, as we see $\forall$ sign. (For checks: $\forall x,y,z,n>2$ means that for any x,y,z (no limitation of "greater than 2") and any n greater than 2, right?)

So, what would be $\Pi_0$ part? It seems that $x^n+ y^n + z^n \rightarrow xyz=0$ would be that part, but two seemingly contradictory definitions confuse me - one is that $\Pi_0$ is quantifier-fre formula - and in this case, I get it, but in somehow different definition, such as Wikipedia, it says that $\Pi_0$ only uses bounded quantifier. But then, it seems to say a different thing... (in this case, $\forall n > 2 \quad x^n+ y^n + z^n \rightarrow xyz=0$ seems to be $\Pi_0$ formula..)

Also, usually when we talk of Fermat's last theorem we says that $x,y,z$ are integers. But the above formula lacks any designation that these variables are integers. So we can neglect this designation because we assumed that we are under (Peano.. probably) arithmetic?

(The linked post can be closed if that post seems to be a duplicate post of this one.)

Answer 1

When talking about the arithmetic hierarchy, we are dealing with the language of Peano arithmetic, so every variable is of type natural number anyway. Then a bounded quantifier is one of the form $\forall a<b\colon \phi$ or $\exists a<b\colon \phi$ (i.e. more explicitly $\forall a\colon (a<b\to \phi)$ or $\exists a\colon (a<b\land\phi)$). These play a special role as the validity of such statements can be checked systematically in finite time (if $\phi$ can be checked in finite time) by simply testing $a=0, 1, \ldots, b-1$ in sequence. Your innermost statement, which should by the way rather read $$x^n+y^n=z^n\to xyz=0$$ has no quantifiers at all (if we have exponentiation as a primitive). Hence it is vacuously true that all the quantifiers it has are bounded. Note however that the quantifier in $\forall n>2\colon\phi$ (i.e. $\forall n\colon (n>2\to\phi)$) is not bounded in the sense of arithmetic hierarchy because it uses $>$, not $<$.

In real analysis we are used to bounded quatifiers such as $\forall \epsilon>0$ or $\forall h\in[0,1]\setminus\mathbb Q$, i.e. in a much broader sense, but for building up a hierarchy these do not qualify as making their statements simpler than others. For example, in the theory of real numbers, the unbounded $\forall x\colon\phi(x)$ is equivalent to the bounded $\forall x>0\colon(\phi(x)\land\phi(1-x))$. It is the "finite FOR loop testing" associated with bounded quantifiers as mentioned above that makes statements involving them simpler than others, and this is a specialty of the theory of natural numbers.

Answer 2

The expression $x^n + y^n = z^n$ is not expressible in Peano arithmetic as a quantifier-free formula, because exponentiation is not part of the language of Peano arithmetic. However, it is expressible as a $\Pi^0_1$ formula and, separately, as a $\Sigma^0_1$ formula. This is because exponentiation is primitive recursive, and there is a standard way of handling primitive recursive functions via Gödel's β function.

Because the ultimate the goal is to write $$ (\forall x,y,z,n) [ (n > 2 \land x^n + y^n = z^n) \to xyz = 0] $$ to be $\Pi^0_1$, you want to replace $x^n + y^n = z^n$ with a $\Sigma^0_1$ formula; then the long formula can be put into prenex form, and the resulting formula will have only universal quantifiers.

---

Separately, some books use $\Sigma^0_0$, $\Pi^0_0$, and $\Delta^0_0$ for quantifier-free formulas, and other use the same notation for formulas with only bounded quantifiers. I believe the former is more common. Some care is needed to establish the conventions in each text your read.