Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Excuse me for the awkward wording. I'm new to logic. What I really mean is this:

Consider the number theory that spawns from the structure $N=\{\mathbb{N},+,\cdot\}$ (equipped with the usual interpretation) using first order logic. I understand that the formal sentences generated this way are capable of expressing all elementary number theory statements in the sense that the statement "$x$ divides $y$" can be expressed as $\exists z(x\cdot z=y)$, so that $N\models \exists z(x\cdot z=y)$ iff $x$ divides $y$.

But there's a kind of statement that I don't know how to express in the system, like "$x$ can be written as the sum of cubes". It is easy to write "$x$ can be written as the sum of $n$ cubes" given specific $n$ into something like $\exists z_1z_2...z_n(x=z_1\cdot z_1\cdot z_1+z_2\cdot z_2\cdot z_2+...+z_n\cdot z_n\cdot z_n=x)$. But in the first statement it seems one can't follow suit because the "$n$" there is not specific. How can we quantify the unspecific parameter? What are tricks for expressing it?

Edit: By the way, "...that the formal sentences generated this way are capable of expressing all elementary number theory statements..." Is this true?

share|cite|improve this question
yes you are right. thank you for pointing that out – Eric Mar 21 '12 at 3:15
up vote 2 down vote accepted

The trick is to encode the sequences of natural numbers by a natural number. For example the sequence $x_1, ..., x_n$ can be encoded by the number $p_1^{x_1 + 1} \cdot ... \cdot p_n^{x_n + 1}$, where $p_i$ is the $i$-th prime number. Then you express properties of such an encoding. That is you construct formulas to express some of the following relations and functions

  • $seq(x)$ - $x$ encodes a sequence
  • $lh(x)$ - the length of the sequence encoded by $x$
  • $(x)_i$ - $i$-th element of the sequence encoded by $x$.

Then the statement ''$x$ can be written as the sum of cubes'' can be expressed by something like this $$\exists y (seq(y) \land x = sum(y) \land \forall (i < lh(y)) cube((y)_i))$$ where x = sum(y) is the following formula $$\exists z (seq(z) \land lh(z) = lh(y) \land (z)_0 = (y)_0 \land x = (z)_{lh(z) -1} \land \forall (0 < i < lh(z)) (z)_i = (z)_{i-1} + (y)_i)$$ which expresses the relation $x$ is the sum of elements of the sequence encoded by $y$.

share|cite|improve this answer
But what is $x=sum(y)$? – Eric Mar 20 '12 at 1:17
Edited the answer to explain that. – Levon Haykazyan Mar 20 '12 at 20:54
$cube((x)_i)$ should be $cube((y)_i)$, right? – Eric Mar 21 '12 at 1:25
yes, that's right, thanks. Edited to fix that. – Levon Haykazyan Mar 21 '12 at 14:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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