# Is my conversion of this statement into formal language and its negation correct?

Every natural number is a product of two natural numbers.

$N(x)$ for $x$ is a natural number and $a,b \in\mathbb{N}$

$$\forall x(N(x)\rightarrow \exists a\exists b(N(a)\wedge N(b)\wedge (x=a\cdot b)))$$

Negation:

$$\neg\forall x(N(x)\rightarrow \exists a\exists b(N(a)\wedge N(b)\wedge (x=a\cdot b)))$$

$$\Rightarrow \exists x \neg(N(x)\rightarrow \exists a\exists b(N(a)\wedge N(b)\wedge (x=a\cdot b)))$$

$$\Rightarrow \exists x (N(x)\wedge \neg\exists a\exists b(N(a)\wedge N(b)\wedge (x=a\cdot b)))$$

$$\Rightarrow \exists x (N(x)\wedge \forall a\forall b \neg(N(a)\wedge N(b)\wedge (x=a\cdot b)))$$

$$\Rightarrow \exists x (N(x)\wedge \forall a\forall b (N(a)\rightarrow N(b)\rightarrow (x \neq a\cdot b)))$$

All is good except for the last step, converting $\neg(N(a)\wedge N(b)\wedge (x=a\cdot b)))$. Consider these equivalences: \begin{align} \neg (p_1 \wedge p_2 \dots \wedge p_n \wedge q) &\iff \neg (p_1 \wedge p_2 \dots \wedge p_n) \vee \neg q \quad\text{(by De Morgan)} \\ &\iff (p_1 \wedge p_2 \dots \wedge p_n) \implies \neg q \end{align} So the matrix (inner, unquantified formula) of your result should be $$(N(a)\wedge N(b)\implies (x\neq a\cdot b)) \text{.}$$

Everything looks good except for changing it to $N(a) \implies N(b)$

• Why should it remain $neg(N(a)\wedge N(b)$ ? – nikolita Nov 1 '15 at 20:56