The formula $\phi(x_1,\ldots,x_n)$ defines the $n$-ary relation $R$ if $(a_1,\ldots,a_n) \in R$ iff $\phi(a_1,\ldots,a_n)$ is true (under a particular interpretation).

I know how to define addition from the successor and zero functions using primitive recursion, but I can't seem to find the formula that defines its graph, i.e. formula $\phi(x,y,z)$ true (under the usual interpretation) iff $x+y=z$. Anyone care to show it to me?

Boolos' "Computability and logic" presents a general way of, given any recursive relation/function, finding a formula that defines it, but I can't for the life of me follow it.


Remember that in first-order $PA$, the symbols "$+$" and "$\times$" are part of the language. So "$x+y=z$" is a formula in the language of $PA$, and defines (indeed, represents) addition.

Although addition can be defined via primitive recursion using successor alone, successor is not enough to represent addition, or even define it in a first-order manner: there is no formula $\varphi(x, y, z)$ in the language of successor alone, whose graph (in the usual interpretation) is $\{(x, y, z): x+y=z\}$. This follows from a general analysis of the definable subsets of $(\mathbb{N}; 0, S)$; for example, the set of even numbers is not definable in this structure, but is definable relative to addition (if $\varphi$ defines addition, then $z$ is even iff $\exists x(\varphi(x, x, z))$). The proof that the even numbers aren't definable using successor alone is via quantifier elimination; see here, starting at slide 12.

If you don't like quantifier elmination, here's a proof that you can't define addition using only successor using Ehrenfeucht-Fraisse games. First, note that if you could, you could also define it using successor and the order relation $<$. So let's look at the structure $\mathcal{N}=(\mathbb{N}; 0, S, <)$. Now, there's another structure of interest, $\mathcal{M}$, which consists of $\mathcal{N}$ together with a "$\mathbb{Z}$-chain" of elements, each of which are $>$ every element of $\mathbb{N}$. Think of $\mathcal{M}$ as $$0<1<2<3<... \infty-3<\infty-2<\infty-1<\infty<\infty+1<\infty+2<\infty+3<...$$ (although of course there isn't a "special" infinite element $\infty$). Basically, $\mathcal{M}$ looks like an "$\mathbb{N}$-part" (the standard natural numbers) followed by a "$\mathbb{Z}$-part" (the bi-infinite sequence of infinite elements).

Now here's a neat fact: via Ehrenfeucht-Fraisse games, we can show that $\mathcal{N}\equiv\mathcal{M}$. (Strictly speaking this takes a bit of mucking around. EF-games only apply to relational structures, so we have to replace $\mathcal{N}$ and $\mathcal{M}$ with their "relationalizations": instead of a unary function $S$, they have a binary relation $R_S$ which "graphs" $S$. But this doesn't introduce any problems; note that $R_S$ and $S$ each define each other, so once you've proved that the relationalizations of $\mathcal{M}$ and $\mathcal{N}$ are elementarily equivalent, you've proved that $\mathcal{M}$ and $\mathcal{N}$ themselves are elementarily equivalent.)

So what? Well, suppose $\varphi$ is any formula in one variable in the language $\{0, S, <\}$. Then I claim that the set $\varphi$ defines in $\mathbb{N}$ is either finite or cofinite.

Suppose not; then $\mathcal{N}$ satisfies "$\forall x\exists y(y>x\wedge\varphi(y))$" and "$\forall x\exists y(y>x\wedge\neg\varphi(y))$." So - since $\mathcal{M}$ and $\mathcal{N}$ satisfy the same sentences - we can find in $\mathcal{M}$ two infinite elements $\infty_1, \infty_2$ such that $\mathcal{M}\models\varphi(\infty_1)\wedge\neg\varphi(\infty_2)$.

So what? Well, look at $\mathcal{M}$! Given any two infinite elements $a$ and $b$, there's an automorphism of $\mathcal{M}$ sending $a$ to $b$ (just "shift the $\mathbb{Z}$-part"). So there's an automorphism sending $\infty_1$ to $\infty_2$. But automorphisms preserve truth - that is, if there's an automorphism sending $a$ to $b$ and $a$ satisfies some formula $\psi$, then $b$ also satisfies $\psi$ (exercise - induction on the complexity of $\psi$). So we have a contradiction, since $\infty_1$ and $\infty_2$ satisfy different formulas.

Going further, it turns out that addition isn't enough to define multiplication: Presburger arithmetic is decidable! (As an odd side note, so is arithmetic with only multiplication.) But surprisingly, once we add multiplication, everything else falls into place - it turns out that addition and multiplication alone are enough to define every computable function. This should be very surprising! Intuitively, there's no reason at first to think that we'll ever be "done" - why shouldn't we have to keep adding more symbols to the language? In fact, if I recall correctly this was implicitly believed by a number of people pre-Turing, as part and parcel of a more general belief that there would never be a formal definition of "computable".

Note that for Goedel's theorem, we do not need that every computable function is representable, or even definable (even though that's usually how it's taught these days); Goedel's original proof only showed how to represent the functions that he specifically needed. And until Turing, Goedel was himself skeptical of attempts (e.g. by Church) to formalize the notion of "computable function."

  • 2
    $\begingroup$ Very informative answer. Thank you. $\endgroup$ – marty cohen Aug 29 '16 at 19:44

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.