20
$\begingroup$

Tennenbaum's Theorem theory says that in a countable non-standard model of arithmetic with an underlying set consisting of standard numbers, neither the polynomial $A(x,y):=x+y$ nor the polynomial $M(x,y):=x\cdot y$ can be recursive functions.

Question: What integer polynomials in one or more variables can be recursive functions in some non-standard model of arithmetic?

$\endgroup$
4
  • 3
    $\begingroup$ Nice question ! $\endgroup$ Mar 4 at 1:35
  • $\begingroup$ I would object a little to the way that you have phrased things. The functions $x+y$ and $x\cdot y$ are indeed computable in the model, since PA proves that addition and multiplication are computable functions. What Tennenbaum's theorem says instead is that the model has no presentation (on domain $\mathbb{N}$) for which either of these functions is computable outside the model. $\endgroup$ Mar 4 at 3:12
  • 1
    $\begingroup$ I hope my edit satisfies your objection. $\endgroup$ Mar 4 at 4:33
  • $\begingroup$ David, I sent you an email (at the unh address I found), but if you didn't receive it, can you kindly send me an email at [email protected]? $\endgroup$ Mar 7 at 16:51

2 Answers 2

20
$\begingroup$

This is a great question!

Successor. Let me get things started by pointing out that the successor function $s(x)=x+1$ of a nonstandard model of PA can be computable. If $M$ is any countable nonstandard model of PA, then the order type of $M$ is $\mathbb{N}+\mathbb{Z}\cdot\mathbb{Q}$. This order type has a computable presentation, one on which the successor function is computable, and so $M$ has an isomorphic copy $M'$ on which the successor function is computable.

It follows that $x\mapsto x+k$ for any standard $k$ is also computable in this presentation. This model also shows that the order $x<y$ can be computable, and therefore also $\max(x,y)$ and $\min(x,y)$ and so forth.

Squaring. Next, let me show that the squaring function $f(x)=x^2$ also can be computable. What is the nature of the squaring function in a nonstandard model of PA? Well, the graph consists of infinitely many $\mathbb{N}$-chains proceeding upward from the numbers that are not perfect squares, plus infinitely many $\mathbb{Z}$-chains, proceeding upwards and downwards from the numbers that have infinitely many iterated square roots in the model, that is, for numbers that are perfect $2^k$ powers for all standard $k$. These various $\mathbb{N}$ and $\mathbb{Z}$-chains are totally separated from one another and have no common points or interference with one another. I can make a computable model with a unary function that has infinitely many $\mathbb{N}$-chains and infinitely many $\mathbb{Z}$-chains, and this will be the squaring function of any desired countable nonstandard model $M\models\text{PA}$.

Cubing, higher powers. The same idea works with any unary power $x^n$ for standard $n$. The graph of this function in a model of PA consists of infinitely many $\mathbb{N}$-chains starting from the numbers that are not perfect $n$th powers, and in a nonstandard model, we will also have infinitely many $\mathbb{Z}$-chains proceeding from the numbers that have iterated $n$th roots to any standard number of iterations.

Generalization to injective unary functions. A similar idea works with many injective unary functions. If $f:M\to M$ is an injective unary function in a nonstandard model of PA, then consider the graph of $f$ on $M$ as a directed graph pointing $x\to f(x)$. This graph will consist of some $\mathbb{N}$-chains, starting at points not in the range of $f$; it may have some $\mathbb{Z}$-chains that proceed in both directions infinitely; and it may have some finite cycles. Since the function is injective, these different chains and cycles have no interference with each other, and so the isomorphism type of $f$ is determined by the number of each type of chain/cycle. If this specification is computable, then $M$ will have a presentation on which $f$ is computable.

All polynomials in one variable. In the case of a polynomial function $p(x)$ in one variable (with standard coefficients), it will be injective for all large enough input (above some standard bound), once the leading term become sufficiently dominant, and that is good enough. There will be only finitely many finite cycles, and infinitely many $\mathbb{N}$-chains and $\mathbb{Z}$-chains (in the nonstandard part), which are disjoint except for finitely many exceptional merges. We can find a computable presentation of this digraph. And so every nonstandard model will have a presentation on which the given polynomial is computable.

Meanwhile, an impossibility. One of the usual proofs of Tennenbaum's theorem shows a stronger result, not just that $x+y$ is not computable, but that $x\mapsto px$ cannot be uniformly computable for standard $p$. To see this, we consider any noncomputable set $A\subseteq\mathbb{N}$ in the standard system of the model. Let $a$ be a nonstandard number that is a multiple of primes $p_i$ for $i\in A$, and let $b$ be a multiple of the other standard primes. If the functions $p_ix$ were uniformly computable, we could on input $i$ search for $y$ such that $p_i y=a$ or $p_i y=b$. We will find one or the other, and thereby know whether $i\in A$ or not. So those functions cannot be uniformly computable.

$\endgroup$
5
  • 2
    $\begingroup$ I tried to ask the simplest question that stumped me, but your impossibility resonates with my self-censoring! It's indeed immediately natural to ask about sets uniformly computable sets of polynomials. $\endgroup$ Mar 4 at 6:35
  • $\begingroup$ I think the question might be: is there any nontrivial polynomial at all in two variables that can be computable for a presentation of a nonstandard model of PA? I suspect not. $\endgroup$ Mar 4 at 17:06
  • 1
    $\begingroup$ An interesting case, Fermat-inspired, might be polynomials of the form x^n+y^n, or a little more generally, a x^n + b y^m. With n and m large, values of such polynomials probably determine x and y. So one can build a directed graph where x and y point to x^n + b y^m - and all nodes will have in-degree 0 or 2, but infinite out-degree. Maybe such a digraph has a recursive structure??? $\endgroup$ Mar 5 at 5:40
  • 2
    $\begingroup$ It is widely believed, but not proved, that $x^5+y^5=z^5+w^5$ has no solution in positive integers with $\{x,y\}\ne\{z,w\}$. $\endgroup$ Mar 5 at 10:40
  • $\begingroup$ I am expecting the impossibility result for polynomials of the form $x^ny^m$, but so far, I need also the successor function to computable, or at least the function $i\mapsto p_i^M$ pointing at the $i$th standard prime. $\endgroup$ Mar 5 at 14:35
6
$\begingroup$

$f(x,y) = P(x) + Q(y)$, for non-constant polynomials $P$ and $Q$, is not computable.

If $P$ and $Q$ both have degree 1, then $f(x,y) = ax + by + c$, so $f(f(0,x),f(y,0)) = a(bx+c) + b(ay+c) + c = a(bx + by + c) + bc + c$, so we can compute $bx + by + c = a0 + b(x+y) + c$, so we can compute $x + y$. So we can assume $Q$ has degree $> 1$.

The basic idea is that we want to use repeated applications of $f$ to encode a list of numbers: $f(i_1, f(i_2, f(i_3, ...)))$.

The first problem with this is that we can't compute what the standard natural numbers are. But we can compute a copy of $\mathbb{N}$ that is also definable. $Q$ is eventually larger than all of its values (because it has degree > 1), so pick some $k$ after this happens (and also after $P$ becomes injective, because that will be important later), and define $g(0) = k$, $g(n+1) = f(0,g(n))$. Now $g$ is increasing, and computable, and also exists in the model.

The second problem is that $f$ might not be injective. But because $P$ and $Q$ are eventually increasing, and $Q$ has degree > 1, it is eventually kind of injective: for any upper bound $K$ on the values of $x$, there is some $N$ such that, if $f(x,y) = f(z,w)$, and $y,w > N$ and $x,z < K$, and $x$ and $z$ are both after the point when $P$ becomes injective, then $x = z$ and $y = w$. We just choose $N$ large enough that the difference between two adjacent values of $Q$ is larger than any possible difference of two values of $P$ below $K$; then we get $y = w$, so $P(x) = P(z)$, and the condition that they're both after $P$ becomes injective means $x = z$.

When I first wrote out this answer, I thought that property was enough. Just put $N+1$ at the end of the list, everything is injective, and it all works, right?

The third problem is that we can't check if a number is $> N$ or not. Fortunately this isn't actually that hard to solve: we can just pick $N$ to also be bigger than any value of $Q$ before it becomes increasing. Now if we find a pair of values that produces the right output, as long as $x < K$, we know we found it; $y < N$ just wouldn't be big enough.

Pick $K$ to be larger than $g(n)$ for all standard $n$, and encode a set $A$ as the number $f(g(i_1), f(g(i_2), f(g(i_3), ...)))$, with $N+1$ at the end to make sure all of it is $> N$. Now given an input $i$, we can just search the list of elements of $A$, and the list of non-elements of $A$, to determine if $i \in A$.


$f(x,y) = x^ny^m$ is not computable, because $f(f(1,x),f(y,1)) = (xy)^{nm}$, and then we can compute $xy$. $f(x,y) = xy^n + c$ is also not computable, because $f(x,y) = (xy^n)1^n + c$ so we can compute $xy^n$. $f(x,y) = x^ny^n + c$ is also not computable, because $f(x,y) = (xy)^n1^n + c$ so we can compute $xy$. So I guess the next question in this family is whether $x^2y^3 + c$ can be computable.


$kx^2y^3 + c$ is not computable. Suppose we know what $n^2$ is, then we can compute $kn^6 + c$, then $n^3$, then $kn^{12} + c$, then $n^4$, then $kn^{14} + c$, then $n$. So for numbers $x$ and $y$, we can compute $y^2$, and then $kx^2(y^2)^3 + c$, and then $xy^3$. I suspect this argument generalises somehow, but I don't know how.

$\endgroup$
8
  • 1
    $\begingroup$ Fantastic! Great progress. $\endgroup$ Mar 5 at 14:58
  • 2
    $\begingroup$ Also $kxy^n+c$ isn't computable, because setting $y = 1$ we can compute $kx+c$, so we can compute $xy^n$. Similarly $kx^ny^n+c$ can compute $xy$. But $kx^ny^m$ is easier: $k(kx^m)^n(ky^n)^m = k(k(xy)^m)^nk^m$, so we can compute $k(xy)^m$ and then $xy$. $\endgroup$
    – paste bee
    Mar 5 at 15:05
  • $\begingroup$ I must be missing something. Joel established that all one-variable polynomials are computable. So if you can compute $kx^2y^3+c$, then immediately you can compute $k(x^3)^2(y^2)^3 + c = kx^6y^6+c$ and so $xy$. Isn't that easier? $\endgroup$ Mar 13 at 5:52
  • $\begingroup$ @DavidFeldman Joel established that they can be computable, more precisely that for any model there is some presentation in which they are computable. So that argument would only prove that in some presentation of a nonstandard model of PA, $kx^2y^3 + c$ is not computable. I proved the stronger result that in every presentation of a nonstandard model of PA, $kx^2y^3 + c$ is not computable. $\endgroup$
    – paste bee
    Mar 13 at 12:33
  • $\begingroup$ Also, Joel's result only works on one polynomial at a time: for instance $2x$ and $2x+1$ cannot both be computable in any nonstandard model of PA. (You can find two isomorphic models such that $2x$ is computable in one and $2x+1$ is computable in the other, but the isomorphism between them won't be computable.) $\endgroup$
    – paste bee
    Mar 13 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.