Construct a predicate for $x \leqslant y$ given the set of $\mathbb{R}$ or $\mathbb{Z}$ and the symbols $0, 1, +, \cdot, =$

73 Views Asked by At

1) Given is the signature $σ=⟨0,1;+,⋅;=⟩$ and the standard interpretation on the set of all real numbers $\mathbb{R}$. Construct the predicate P(x, y) = $x⩽y$.

2) Given is the signature $σ=⟨0,1;+,⋅;=⟩$ and the standard interpretation on the set of all integers $\mathbb{Z}$. Construct the predicate P(x, y) = $x⩽y$.

At first this seemed like a trivial exercise, since I thought you could just write $P(x, y) = \exists z(x + z = y)$, but I quickly realised this only works with non-negative numbers. If I could somehow form a predicate $A(x)$ that is true if x is positive, then I would be golden, but that is a very similar task to the one I was trying to solve in the first place ($x > y$). So I am stuck in this loop. In order to write out that $x < y$, I need to write out that $x < y$. Therefore, help would be appreciated.

1

There are 1 best solutions below

8
On BEST ANSWER

For the reals is rather simple

$$P(x, y) = \exists z(x + z^2 = y)$$

For the integers, it's more subtle and uses a Theorem of Lagrange that every natural number is a sum of $4$ squares of integers. Therefore

$$P(x, y) = \exists (z_1, z_2, z_3, z_4) (x + z_1^2 + z_2^2 + z_3^2 + z_4^2 = y)$$