Predicate Logic: Distinguishing structures in the first-order language having only multiplication

56 Views Asked by At

I am attempting to distinguish the below structures under the multiplication function. As of right now I have determined the following:

<N, ⋅>|= ∃z∀x∀y ((x-x=z)∩(y-y=z)) (xy ≥ z)

  • "There exists a z that equals the difference of all x and y with themselves. For all x and y the product is always at least zero"

<Q, ⋅>|= ∀z (z=(z1/z2)) ∀x∀y(xy=z) ∀x∃y (z1∤z2)∪(z2∤z1)

  • "Every z consists of a numerator and denominator. For all x and y, the product is z. For all x there exists a number where the product consists of a numerator and denominator that do not divide each other without remainder"

<Z, ⋅>|= ~(∃z∀x∀y ((x-x=z)∩(y-y=z)) (xy ≥ z)) ∩ ~(∀z (z=(z1/z2)) ∀x∀y(xy=z) ∀x∃y (z1∤z2)v(z2∤z1))

  • "Not <N, ⋅> and not <Q, ⋅>"

However, I have come to realize that I am not allowed to use other relations, such as less than or equal to, and other functions, such as subtraction.

I understand the concept of the structure statements but lack the imagination to properly distinguish them.

I appreciate any help.

2

There are 2 best solutions below

6
On BEST ANSWER

Call an element $z$ "unreachable" if the only way to produce $z$ as a product of two elements is for one of the factors to be $z$ itself.

$\mathbb Q$ has exactly one unreachable element, namely $0$.

$\mathbb Z$ has exactly two unreachable elements, namely $0$ and $-1$.

$\mathbb N$ has more than two unreachable elements, namely every prime number, as well as $1$ (and $0$ if $0$ is in your $\mathbb N$).

3
On

First, you can define $1$ by saying $ \varphi(x) \equiv \forall y (x \cdot y = y)$.

Now you know that $\mathbb{Q} \models \forall x \exists y (x \cdot y =1)$ and $\mathbb{N} \models \neg \forall x \exists y (x \cdot y =1)$. So putting the two above together, we note that

$$\mathbb{Q} \models \forall x \exists y (x \cdot y =1) \equiv (\exists z)[\varphi(z) \wedge \forall x \exists y (x \cdot y = z )] $$

$$\mathbb{N} \models \neg \forall x \exists y (x \cdot y =1) \equiv \neg (\exists z)[\varphi(z) \wedge \forall x \exists y (x \cdot y = z )] $$