# Set Builder Notation for Prime Numbers

How can I express the set of primes using set builder notation. The less words, the better!

I was thinking something along the lines of: $P = \{x_i \mid x_j \equiv x_k \pmod\alpha \Rightarrow x_k = 1, \beta x_j; \; x_i > 1; \; i,j,k \in \mathbb{Z}^+; \; \alpha, \beta \in \mathbb{Z} \}$.

Is this correct?

• Translate your predicates into words and see if they make sense and capture primality,
– lhf
Sep 2 '15 at 19:53
• The set you have written above gives you $\{x|x>1\}$. Also, it isn't true that a prime mod a number always has to give 1 or the prime. For example, $5(\mod 3)\equiv 2$. Sep 2 '15 at 19:54
• How about: $$P=\{x\in\Bbb N:\forall a,b\in\Bbb N,ab\ne x\ne1\}$$ Sep 2 '15 at 20:03
• Less words might be better; but clear definitions are the best. Sep 2 '15 at 20:03
• @user251257 $$P=\{x\in\Bbb N:\forall a,b\in\Bbb N,a=1\lor b=1\lor ab\ne x\ne1\}$$Mehhh Sep 2 '15 at 20:30

Another option: $$\left\{n\in\mathbb{Z}_{\geq2}: m\in\mathbb{Z}\wedge1<m<n\implies m\not\mid n\right\}$$ (the set of integers $n$ that are at least 2, such that whenever $m$ is an integer and $m$ is between 1 and $n$, then $m$ won't divide $n$)

or $$\left\{n\in\mathbb{Z}_{\geq2}: m\mid n\implies |m|=1\vee|m|=n\right\}$$ (the set of integers $n$ that are at least 2, such that whenever $m$ divides $n$, it means that either $m$ is $1,-1,n$, or $-n$.)

• Can you please "spell" this out like @Paul did in the case of his answer? Sep 4 '15 at 1:15
• @JonathanPrescott OK Sep 4 '15 at 2:06
• Thanks @alex.jordan. This is what I was looking for. Something very simple and concise! Sep 4 '15 at 3:01

How about this? $$\{n\in\mathbf{Z} : \forall a,b \in \mathbf{Z},\, n\mid ab \Rightarrow n\mid a \vee n \mid b\}$$

• What do you mean by $ab \Rightarrow n$ ?
– Paul
Sep 2 '15 at 20:48
• @paul it reads $(n|ab) \implies (n|a \lor n|b)$! Sep 2 '15 at 21:24
• It's good, but technically, $1$, $0$, $-1$, or any negative of a prime meet this too. That's why I went with $\mathbb{Z}_{\geq2}$ in mine. Sep 4 '15 at 6:55

$$P = \{n \in \mathbb{N}_{\gt 1}\mid (n-1)! \equiv -1 \bmod{n}\}$$ Wilson's theorem

$$P = \{x \in \mathbb{Z} \;| \;\;\; [\;\neg\exists y\in\mathbb{Z} : {\;\;\;\;(x \mod y = 0)}; \;\; 1<|y|<|x|)\;] \;; \;|x| \neq1\;\}$$

{$x$ belonging to the Integers | No Integer (whose absolute value is between 1 and the absolute value of x) should leave a remainder when $x$ is divided by it; x is not 1 or -1}

• Shouldn't we have $x \in \mathbb{N}$ instead? Sep 2 '15 at 20:52
• There are negative primes as well that should be taken into account
– Paul
Sep 2 '15 at 20:54
• But if you want to account for only the positive primes, then yes, and then you could also leave out the absolute values
– Paul
Sep 2 '15 at 20:55