7
$\begingroup$

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.

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

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.