Negating a certain if-then statement in English involving a quantifier

Question

I want to negate the statement $S \equiv$ "If not all integers are composite, then there are integers that are prime".

The general rule that $\neg(Q \to P) \equiv Q \wedge \neg P$ may lead one to believe that $\neg S \equiv$ "Not all integers are composite, and no integer is prime".

However, I can rewrite $S$ as "If there are integers which are not composite, then there are integers that are prime".

Now using the rule that negating an $\exists$ is a $\forall$, coupled with the rule that negating an if-then with a quantifier on the outside changes the quantifier, may lead one to believe that $\neg S \equiv$ "All integers are composite, and there are no integers are prime".

So which is it?

Answer 1

The quantifiers are not on the "outside"; rather the conditional is the root connective.

Take $Q(n)$ to read "$n$ is composite" and $P(n)$ to read "$n$ is prime".

"If not all integers are composite, then there are integers that are prime" would thus be $\big(\lnot\forall n~Q(n)\big)\to\big(\exists m~P(m)\big)$

The negation would be $\big(\lnot\forall n~Q(n)\big)\land\big(\lnot\exists m~P(m)\big)$; that is "Not all integers are composite, and no integers are prime."

---

You can now use quantifier duality equivalences to substitute. The negative is then $\big(\exists n~\lnot Q(n)\big)\land\big(\forall m~\lnot P(m)\big)$; that is "Some integers are not composite, and all integers are not prime."

Answer 2

If not all integers are composite, then there are integers that are prime.

This can be paraphrased to the following.

If there is a non-composite integer, then there is a prime integer.

It can be paraphrased again, replacing if with disjunction.

$$ \text{Every integer is composite} \lor \text{There is a prime integer} $$

The negation of this statement is

$$ \text{There is a non-composite integer} \land \text{There are no prime integers} $$

Thus, the first one is correct.

Not all integers are composite and no integer is prime.