Write using logical symbols: “Every even number greater than two is the sum of two prime numbers”

Write using logical symbols: "Every even number greater than two is the sum of two prime numbers"
This is how I attempted to write this: $$((n=2m \land n > 2) \Rightarrow n=p_1+p_2)\land(x|p_1 \Rightarrow x=1 \lor x=p_1) \land (y|p_2 \Rightarrow y=1 \lor y=p_2) \land (p_1 >1 \land p_2 >1)$$ I am not sure if I haven't confused logical operations. I also think whether I should have used "iff" in the first parentheses instead. What should I change in my solution?

• Where are the quantifiers? (i.e., $\forall$ and $\exists$) – quasi Oct 30 '17 at 19:26
• @quasi They are not allowed, only logical operations. It is, however, known that we are working with natural numbers. – Aemilius Oct 30 '17 at 19:27
• What about the requirement $n > 2$? – quasi Oct 30 '17 at 19:29
• Also, since you are using the divisibility symbol anyway, why not dispense with the variable $m$, and instead write $2|n$? – quasi Oct 30 '17 at 19:32
• Do you think that $\forall$ and $\exists$ are not "logical operations"? What makes you think so? Unless you have something like set builders (which are quite arguably less of a "logical operations" than quantification), I don't think the meaning you want to be express can be expressed without quantifiers. – hmakholm left over Monica Oct 30 '17 at 19:59

(I'm assuming this is homework; by the way, you should provide more context in your question, like where the question came from, and any restrictions like "quantifiers are not allowed".)

Anyway, I don't know what your teacher wants you to do, but I think you should be aware that you can't write "Every even number etcetc" without quantifiers. Look at the statement $$\left(2\mid n\right)\implies\left(\mbox{n is the sum of two primes}\right)$$ for example. It does not mean that "every even $n$ is the sum of two primes". It means, by definition, the same as: $$\left(2\nmid n\right)\lor\left(\mbox{n is the sum of two primes}\right).$$ What this means is: for some given $n$ (I didn't say what's the value of $n$, but it's some fixed value), either this $n$ is not even, or it is the sum of two primes. Now, what we want to do is state this for all $n$. Is is commonly assumed, when there are just a few variables (like in my example), that all variables that were not declared have an universal quantifier attached to it. That is, it is commmonly assumed that this: $$\left(2\mid n\right)\implies\left(\mbox{n is the sum of two primes}\right)$$ is just a shorthand for this: $$\forall n, \left(2\mid n\right)\implies\left(\mbox{n is the sum of two primes}\right).$$

Ok, now on to your question. The statement I wrote above is, as you know, wrong, since $2$ is not a sum of two primes. The statement should read: $$\forall n, \left(2\mid n\land n>2\right)\implies\left(\mbox{n is the sum of two primes}\right).$$ Now that it's not obviously wrong anymore, we must write "$n$ is the sum of two primes" using logic symbols. This is done like "There exist two primes such that $n$ is their sum". Again, I don't believe you could do it without quantifiers. Anyway, you would write it like: $$\exists p_1,\exists p_2, \mbox{p_1 is prime} \land \mbox{p_2 is prime} \land n=p_1+p_2.$$

You could use the fact that $\forall x$ is the same as $\neg\exists x\neg$ to rewrite it as $$\neg\forall p_1,\forall p_2, \left( \mbox{p_1 is prime} \land \mbox{p_2 is prime}\right) \implies n\neq p_1+p_2$$ And then you could drop the quantifiers, since they could be regarded as implicit: $$\neg\left[ \left( \mbox{p_1 is prime} \land \mbox{p_2 is prime}\right) \implies n\neq p_1+p_2\right]$$ but I hope you agree that this is quite unreadable.

Getting back to our problem, our statement is: $$\forall n, \left(2\mid n\right)\implies\left(\mbox{n is the sum of two primes}\right)$$ and we have already rewritten it as: $$\forall n, \left(2\mid n\right)\implies \exists p_1,\exists p_2, \mbox{p_1 is prime} \land \mbox{p_2 is prime} \land n=p_1+p_2$$ Now, we just have to write "$p$ is prime" using logic. Writing it as "if $n$ is a positive divisor of $p$, then $n$ is either $1$ or $p$", I hope you can do it by yourself, after all of this (as you have already done in your question).

As for the way you have written it, I can see where you want to get, but I wouldn't consider it "correct". The way it's written, it means "$p_1$ and $p_2$ are prime, and $n$ is a natural number such that either it isn't an even greater than $2$, or else it equals $p_1+p_2$". You still haven't said in your logic statement that $p_1$ and $p_2$ depend on the value of $n$, and that this happens for any value of $n$ we come up with.

Finally, you asked whether you should have used $\iff$ instead of $\implies$ in $\left(2\mid n\right)\implies\left(\mbox{$n$is the sum of two primes}\right)$. No, you shouldn't. The point is to write that "every even greater than two is a sum of two primes", not that "$n$ is an even greater than $2$ iff it is a sum of two primes". Actually, the converse is just wrong. If a number is a sum of two primes, it doesn't mean that it is "even and greater than two". Even if the converse were right, you could still write just the forward implication, and it would be correct.

Slightly different view : $$P := \{ p \: \mid p \in \mathbb{N} \rightarrow \ \forall q \in \mathbb {N } : \: 1<q<p , \: mod(p,q) \ne 0 \: \}$$

$$n = 2(m+1), \: m \in \mathbb{N} \implies \exists p_{1}, p_{2} \in P \rightarrow n =p_{1}+p_{2}$$

• It is my personal opinion that p\bmod q\neq0 $p\bmod q\neq0$ looks better. Either way, precede mod with a backslash. – gen-ℤ ready to perish Oct 30 '17 at 20:48