17
$\begingroup$

Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication" mentions:

... It turns out that you can "index" the supernaturals in a simple and natural way by assocating with each supernatural number a trio of ordinary integers... [e.g. (9,-8,3)] ... Under some indexing schemes, it is very easy to calculate the index triplet for the sum of two supernaturals, given the indices of the two numbers to be added. Under other indexing schemes, it is very easy to calculate the index triplet for the product of two supernaturals, given the indices of the two numbers to be multiplied. But under no indexing scheme is it possible to calculate both.

-- Douglas Hofstadter; Gödel, Escher, Bach; Chapter XIV

The description is mystifying me and also seems to have mystified at least one Wikipedia talk page, where you can also find a fuller quote.

Having done some basic digging on this, I'm confused.

  • It looks like what's being discussed is a countable non-standard model of arithmetic. However, the "index triplet" isn't something I can find reference to anywhere. Is there a plausible candidate for such a "simple and natural" indexing?
  • The theorem referenced sounds a lot like Tennenbaum's theorem, but that theorem says more strongly that neither addition nor multiplication is computable (cf discussion here). Is there some other candidate for what theorem is being referred to here?

An old Math Forum post has some hints, but I don't have access to the linked articles at the moment.

$\endgroup$
  • 2
    $\begingroup$ This is totally bizarre. $\endgroup$ – Emil Jeřábek Sep 18 '18 at 8:00
  • 3
    $\begingroup$ I would guess that Hofstadter just got the statement of Tennenbaum's theorem wrong. You could try writing to him. I have corresponded with Hofstadter a couple of times in the past, and found him to be surprisingly responsive for someone who is a minor celebrity. $\endgroup$ – Timothy Chow Sep 18 '18 at 15:06
10
$\begingroup$

My first guess is that the triples come from the fact that nonstandard countable models of PA look like $$\mathbb N + \mathbb Z\times\mathbb Q$$ and elements of $\mathbb Q$ can be represented by pairs.

As for the separate computability of $+$ (addition) and $\cdot$ (multiplication), I am speculating but perhaps the idea is something like this:

Let the theories $T_1$ and $T_2$ be obtained from $\mathrm{Th}(\mathbb N,+)$ and $\mathrm{Th}(\mathbb N,\cdot)$, respectively, by adding axioms saying that a new constant symbol $c$ is "infinite". Then $T_1$ and $T_2$ each have computable models. [Computable model just means that the operations $+$ and $\cdot$ are computable functions.]

For $T_1$ you could add axioms $\varphi_n$ expressing $c\ge n$ as $$\exists x(\underbrace{1+\dots+1}_{n}+x=c)$$

For $T_2$, you could say that there are at least $n$ primes that divide $x$. But in $T_2$ you do not get a linear ordering, so I don't know whether using triples is sensible for models of $T_2$.

$\endgroup$
  • 7
    $\begingroup$ I guess you may well be right, but then the quote does not make sense. (The additive reduct of a nonstandard model of arithmetic cannot be isomorphic to a recursive nonstandard model of $\mathrm{Th}(\mathbb N,+)$, and likewise for multiplication. This is true not just for PA, but also for very weak subtheories of arithmetic–essentially for all that are known not to have nonstandard recursive models in the first place.) Perhaps Hofstadter is just confused. $\endgroup$ – Emil Jeřábek Sep 18 '18 at 8:09
  • 1
    $\begingroup$ @ EmilJeřábek maybe he figured it was close enough to true $\endgroup$ – Bjørn Kjos-Hanssen Sep 18 '18 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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