Constructing logical sentences that involve negative integers over the nonnegative integers

Question

Consider the following statement:

If $x$ and $y$ are integers and $x^5 = y^7$, then $y$ is at most $x$.

I'd like to build a sentence for this statement in the model of $(\mathbb{N}, +, \times)$, where $\mathbb{N}$ is the set of nonnegative integers and $+$ is just the relation (where here I define a relation as a mapping from tuples of nonnegative integers to a boolean value): $\{(a,b,c): a + b = c\}$ and $\times$ is the relation $\{(a,b,c): a \times b = c\}$. By "sentence", I mean a logical formula with no free variables.

How can I write the above highlighted statement in terms of the given model if variables in this model can only take only take on nonnegative integers? It seems to me that since any relation I can derive from the '$+$' can only involve tuples of nonnegative integers, it is impossible to define negative integers in terms of the model. I'm wondering if instead I should construct a sentence for the following statement

If $x$ and $y$ are nonnegative integers and $x^5 = y^7$, then $y$ is at most $x$.

But I'm not sure if these two highlighted statements are logically equivalent.

As an example, suppose I want to construct a sentence for the following statement in the model $(\mathbb{N}, +, \times)$:

Infinitely many prime numbers exist

The corresponding sentence would be

$\forall q \exists p \forall x \forall y[p > q \land ((x > 1 \land y > 1) \implies xy \neq p)]$

We can easily define the relations $<$ and $\neq$ in terms of the $+$ and $\times$ relations.

Answer 1

Basically, you have to formally define arbitrary integers in terms of nonnegative integers. For instance, you could choose to represent an integer by an equivalence class of pairs $(a,b)$ (which you think of as representing $a-b$) under the equivalence relation $(a,b)\sim (c,d)$ if $a+d=b+c$. So every time you want to talk about an integer, you can talk about two natural numbers, and every time you want to say two integers are equal you should instead refer to this relation $\sim$. You can define addition and multiplication of integers as well: $(a,b)+(c,d)$ can be represented as $(a+c,b+d)$ (since $(a-b)+(c-d)=(a+c)-(b+d)$) and $(a,b)\cdot(c,d)$ can be represented as $(ac+bd,ad+bc)$ (since $(a-b)(c-d)=(ac+bd)-(ad+bc)$). You can also define the ordering of the integers by $(a,b)<(c,d)$ iff $a+d<b+c$ (since $a-b<c-d$ iff $a+d<b+c$).

So as a simple example, if you wanted to express the statement $$\text{For every integer $n$ there exist integers $k$ and $\ell$ such that $k\ell=n$}$$ in the structure $(\mathbb{N},+,\times)$ you could do so as follows: $$\forall a\forall b\exists c\exists d\exists e\exists f[cf+de+b=a+ce+df]$$ Here $(a,b)$ represents $n$, $(c,d)$ represents $k$, and $(e,f)$ represents $\ell$, so $(cf+de,ce+df)$ represents $k\ell$. You can use the same idea to express your statement involving $x^5$ and $y^7$ (but it will be pretty complicated since in representing $x^5$ and $y^7$ you will essentially be expanding out $(a-b)^5$ and $(c-d)^7$ completely).

In the language of model theory, we say that we can interpret the structure $(\mathbb{Z},+,\times,<)$ in the structure $(\mathbb{N},+,\times)$.

Answer 2

EDIT: the edited OP makes this answer obsolete; Eric's is the correct one. However, I'm going to leave this up since I think it helps illustrate some of the subtleties around questions like this one.

What do you mean by "construct a sentence for the statement ..."?

The simplest interpretation is that - given a statement $\sigma$ in English - you want a sentence (=wff with no free variables) $p$ such that $p$ is true in $(\mathbb{N}, +)$ iff $\sigma$ is true. Well, then this is easy: just determine whether $\sigma$ is true, and then if $\sigma$ is true, let $p$ be "$\forall x(x=x)$," and if $\sigma$ is false, let $p$ be "$\exists x(x\not=x)$". Then $p$ is true in $(\mathbb{N}, +)$ iff $\sigma$ is true!

Presumably you find that unsatisfying. Well, then you need to clarify what exactly you mean by "construct a sentence for the statement . . .". I'm not just nitpicking - this ambiguity gets in the way of giving your question a meaningful answer.

Incidentally, it's worth noting that exponentiation isn't even definable using addition alone, so in a precise sense there can't be a non-"cheating" answer.