Have I negated the statement "for every prime number $p$, $p+7$ is composite" correctly?

Question

This is the original statement:

For every prime number $p$, $p+7$ is composite.

This is my negation:

There exists a prime number $p$, where $p+7$ is prime.

Have I negated this correctly?

As a side note: Your first statement is true. ($p$ is either $2$ or odd. If it's $2$, then $p+7=9$ which is composite. If it's odd, then $p+7$ is even and hence composite.) — Akiva Weinberger, Sep 24 '14 at 14:55

score 7 · Answer 1 · answered Sep 24 '14 at 07:39

7

Yes it is. If you want to get this is an "automatic way", you can write the sentence logically:

$$\forall p \in Prime, p+7 \in Comp.$$

The negation is $$\exists p\in Prime, p+7\notin Comp.$$

To negate a sentence, switch the quantifiers (but not their domain), and negate all predicates.

answered Sep 24 '14 at 07:39

Denis

6,945
1
21
22

... and switch all connectives with their De Morgan duals, and if there's a $\to$ in there (which doesn't have a nice named De Morgan dual) you need to do something additional with that. – hmakholm left over Monica Sep 24 '14 at 10:44
yes, you can replace $a\to b$ by $\neg a\vee b$. – Denis Sep 24 '14 at 10:48
1

“…negate all predicates” could easily be misunderstood. The general point is: “to negate a quantified sentence, switch the quantifier, and then negate whatever’s on the inside of the quantifier”. What happens next depends on what’s on the inside: if it’s equality, set membership, or some other atomic predicate then all you can do is its atomic negation; if it’s a conjunction or disjunction you use de Morgan, as @HenningMakholm says; if it’s an implication then you treat it appropriately too; and so on. – Peter LeFanu Lumsdaine Sep 24 '14 at 11:43

score 5 · Answer 2 · answered Sep 24 '14 at 08:10

5

Strict negation: a prime number $p$ exists such that $p+7$ is not composite.

Note that $1$ is a number that is not prime and not composite. Of course (working in $\mathbb N$) from $p>1$ it follows that $p+7\neq 1$, but that is a side-issue.

answered Sep 24 '14 at 08:10

drhab

151,093

4

"that is a side-issue" -- specifically it's a side-issue because the equivalence relies on a theorem about numbers, as opposed to only relying on formal logic (or theorems about symbolic logic, if that's the way you write it). Once we're allowed to use theorems about numbers, then of course we could just come straight out and say that since the statement is true, the negation of the statement is false, so any contradiction will do :-) – Steve Jessop Sep 24 '14 at 10:35

score 2 · Answer 3 · answered Sep 24 '14 at 07:32

2

Yes you are right.

The negation would be: there exists a prime number $p$ such that $p+7$ is not composite, or equivalently, there exists a prime number $p$ such that $p+7$ is prime.

answered Sep 24 '14 at 07:32

Peter Huxford

2,561

score 0 · Answer 4 · answered Sep 24 '14 at 14:10

The negation of $\forall x \in Y: P(x)$ is $\exists x \in Y: \lnot P(x)$.

Specifically, the negation of: $$\forall p \in \text{prime numbers} : p+7\ \text{is composite}$$ is: $$\exists p \in \text{prime numbers} : \lnot( p+7\ \text{is composite}),$$ which is equivalent to: $$\exists p \in \text{prime numbers} : p+7\ \text{is not composite},$$ or, in English, "there is a prime number $p$ for which $p+7$ is not composite."

Further, noting that:

all prime numbers are integers greater than 1,
if $p$ is an integer greater than 1, then $p+7$ is an integer greater than 1, and
an integer greater than 1 is prime if and only if it is not composite,

we can rephrase the statement equivalently as "there is a prime number $p$ for which $p+7$ is also prime."

Have I negated the statement "for every prime number $p$, $p+7$ is composite" correctly?

4 Answers4