# How to formally prove the negation of a statement “A if and only if B”?

Motivated by this question, I'm trying to establish a logical proof to the fact that the following statement is false:

$2x+1$ is prime if and only if $x$ is prime.

There are several ways to prove it of course, but I'm trying to understand where have I gone wrong with the following logical proof, so any help pointing out the error would be highly appreciated.

Let $\mathbb{P}$ denote the set of prime numbers.

We need to prove the logical statement:

$\neg({2x+1}\in\mathbb{P}\iff{x}\in\mathbb{P})$

Or the equivalent logical statement:

$\neg[({2x+1}\in\mathbb{P}\implies{x}\in\mathbb{P})\wedge({x}\in\mathbb{P}\implies{2x+1}\in\mathbb{P})]$

Or the equivalent logical statement:

$\neg({2x+1}\in\mathbb{P}\implies{x}\in\mathbb{P})\vee\neg({x}\in\mathbb{P}\implies{2x+1}\in\mathbb{P})$

Or the equivalent logical statement:

$\neg[({2x+1}\not\in\mathbb{P})\vee({x}\in\mathbb{P})]\vee\neg[({x}\not\in\mathbb{P})\vee({2x+1}\in\mathbb{P})]$

Or the equivalent logical statement:

$[({2x+1}\in\mathbb{P})\wedge({x}\not\in\mathbb{P})]\vee[({x}\in\mathbb{P})\wedge({2x+1}\not\in\mathbb{P})]$

That last statement is obviously false, for example, with $x=2$.

But this very example yields false statements "all the way up that proof".

So I'm thinking that my initial interpretation of $\neg({A}\iff{B})$ is incorrect somehow.

• Given the nature of the question, it's very, very weird that there's no quantification over $x$. – Git Gud Dec 26 '14 at 23:30
• @GitGud: quantification over $x$??? – barak manos Dec 26 '14 at 23:30
• There should be a healthy handful of "for all"s in there, at the very least. – Nick Dec 26 '14 at 23:31
• The statement "$2x+1$ is prime if and only if $x$ is prime" is false. Consider $x = 7$ or $x = 9$. – JimmyK4542 Dec 26 '14 at 23:31
• @JimmyK4542: Do you mean, the original "textual" statement? That's what I'm trying to prove. – barak manos Dec 26 '14 at 23:33

OK, so after reading the comments made by @GitGud and @JimmyK4542, I have realized my mistake of not using quantification over $x$ (i.e., use $\forall{x\in\mathbb{N}}$, which would later "turn" into $\exists{x\in\mathbb{N}}$).

Here is the correct way to establish a logical proof (for the benefit of the community):

We need to prove logical statement $A$:

$\neg\forall{x\in\mathbb{N}}:{2x+1}\in\mathbb{P}\iff{x}\in\mathbb{P}$

Or the equivalent logical statement $B$:

$\neg\forall{x\in\mathbb{N}}:({2x+1}\in\mathbb{P}\implies{x}\in\mathbb{P})\wedge({x}\in\mathbb{P}\implies{2x+1}\in\mathbb{P})$

Or the equivalent logical statement $C$:

$\exists{x\in\mathbb{N}}:\neg({2x+1}\in\mathbb{P}\implies{x}\in\mathbb{P})\vee\neg({x}\in\mathbb{P}\implies{2x+1}\in\mathbb{P})$

Or the equivalent logical statement $D$:

$\exists{x\in\mathbb{N}}:\neg[({2x+1}\not\in\mathbb{P})\vee({x}\in\mathbb{P})]\vee\neg[({x}\not\in\mathbb{P})\vee({2x+1}\in\mathbb{P})]$

Or the equivalent logical statement $E$:

$\exists{x\in\mathbb{N}}:[({2x+1}\in\mathbb{P})\wedge({x}\not\in\mathbb{P})]\vee[({x}\in\mathbb{P})\wedge({2x+1}\not\in\mathbb{P})]$

Finally, in order to prove $\exists{x}$, we only need to find such value of $x$:

$x=6\implies(2x+1\in\mathbb{P})\wedge(x\not\in\mathbb{P})\implies{E}\iff{D}\iff{C}\iff{B}\iff{A}$