Divisibility is not definable over $\mathbb{N}$ with coprimality relation

Asked Jun 29 '14 at 22:23

Active Jun 29 '14 at 22:41

Viewed 80 times

I am asked to show that the divisibility relation "|" is not definable over $(\mathbb{N},\perp)$, where "$\perp$" is the coprimality relation.

I am pretty sure that I should use the following:

Let $M$ be a structure, $F$ an automorphism of $M$ and $A \subseteq M^n$ for some $n$. If $A$ is definable over $M$ then $(a_1,...,a_n) \in A \Rightarrow (F(a_1),...,F(a_n)) \in A$.

Therefore, I should find a bijection $F: \mathbb{N} \rightarrow \mathbb{N}$ such that $\forall x,y (x \perp y \Leftrightarrow F(x) \perp F(y))$ and $\exists a,b (a \mid b \wedge F(a) \not\mid F(b))$

Any help? Thanks.

edited Jun 29 '14 at 22:41

asked Jun 29 '14 at 22:23

aerdna91

1,144
6
19

1

For $F$ to be an automorphism, you need it to be $\iff$ and not just $\implies$. – Asaf Karagila Jun 29 '14 at 22:27
7

Simply swap $4$ and $8$. – Hagen von Eitzen Jun 29 '14 at 22:28
Ok, that was really easy...thanks – aerdna91 Jun 29 '14 at 22:48

Divisibility is not definable over $\mathbb{N}$ with coprimality relation

0 Answers0