Logical representation of a prime number

Is it correct to represent a prime number like this?

$$\exists k \in \mathbb N,\, \exists n\in \mathbb N\, \Big((n\mid k) \land (n=k \lor n=1)\Big)$$

-
Are you going to accept the other answers? –  Euler Nov 5 '13 at 0:56
@DonAnselmo, I definitely didn't know I had to do that... I kept clicking an arrow whenever I got an answer. –  Daniel Ortiz Costa Nov 5 '13 at 0:59
You seem to want a formula $\varphi(n)$ if and only if $n$ is prime. Your formula does not work. Depending on details of language, and what the variables range over, something like $\forall x\forall y((xy=n)\implies ((x=1)\lor (y=1)))$ will work. –  André Nicolas Nov 5 '13 at 2:16
You are looking for a predicate $\phi(n)$, a formula that is true when $k$ is prime and false when $k$ is not prime. You can think of it as a function from $\Bbb N$ to $\{$True, False $\}$. You don't want to quantify over $k$, because the value depends on $n$. Joe Johnson 126 has given a good answer to that, but I wanted to show this part of the thought. –  Ross Millikan Nov 5 '13 at 17:38
add comment

1 Answer

What you have claimed is that there are two natural numbers, $n$ and $k$, such that $n$ divides $k$ and $n=k$ or $n=1$. This is true. For instance, let $k=5$ and $n=1$. What you want is that $k$ is prime if whenever $n$ divides $k$, $n$ must be $1$ or $k$. That is, if $k$ is prime then $$\forall n\in \mathbb{N}, \left((n\mid k)\Rightarrow (n=1)\vee (n=k)\right).$$

-
But in a more general way that would be false... If k were 6 and n = 3, then if 3|6 => n=1 or n=6 would be false! I am looking for an expression that helps me determine if a number is a prime... –  Daniel Ortiz Costa Nov 5 '13 at 1:22
@Daniel If you let n=3 and k=6, then the statement would be false and thus 6 is not prime. –  GAM Nov 5 '13 at 1:25
A nit: this returns true for $k=1$, so you need to exclude that. –  Ross Millikan Nov 5 '13 at 17:38
add comment