7

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.

Community
  • 1
barak manos
  • 43,109
  • 3
    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
  • 6
    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
  • Related: http://math.stackexchange.com/q/1081845 – Jonas Meyer Dec 27 '14 at 09:16
  • @JonasMeyer: Thanks. This (rather simple) question is in fact the motivation behind my own question. I tried to answer it with a logical proof as formal as possible, but ran into the problem described in this post. From the comments above, I sort of realized my mistake (I think), of not using $\forall{x\in\mathbb{N}}$, which would later "turn" into $\exists{x\in\mathbb{N}}$. – barak manos Dec 27 '14 at 09:36
  • @barakmanos Now that you know how to answer your own question, perhaps you can answer it yourself so this question has an answer? Edit: Also, don't mind the down votes too much. You were a victim of serial down voting (though it might not have been the case here), see this. – Git Gud Dec 27 '14 at 11:38
  • @GitGud: OK, thanks for the advice. I thought about adding an answer so that other users can make benefit of it in the future, but I figured it would just get a couple more down-votes. I will add it though, as you suggest. BTW, how did you become aware of the serial down voting??? – barak manos Dec 27 '14 at 12:05

1 Answers1

3

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

barak manos
  • 43,109