2
$\begingroup$

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?

  • 0
    yes you are right. thank you for pointing that out2012-03-21

1 Answers 1

2

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$.

  • 0
    yes, that's right, thanks. Edited to fi$x$ that.2012-03-21