# Propositional logic implication confusion

The problem asks to convert the following statements into propositional logic

1. The square of a nonzero integer is positive

$\forall n \in \mathbb{Z}, (n \neq 0) \implies (n^2 > 0)$

The book adds these parenthesis for some reason.

Now since we can rewrite $P \implies Q$ as $\neg P \vee Q$, I thought this can be converted to

$\neg (\forall n \in \mathbb{Z}, n \neq 0) \implies (n^2 > 0)$

And then using DeMorgan's laws, we can do

$\exists n \not\in \mathbb{Z}, n = 0 \vee(n^2 > 0)$

but this turned out to be wrong, the book's answer is

$\forall n \in \mathbb{Z}, (n = 0) \vee (n^2 > 0)$

So a few questions, why did they choose to only negate $(n \neq 0)$ and leave the rest of the $\forall n \in \mathbb{Z}$ alone? Is it that they only do operations on propositions and that quantifiers are not propositions? Do negations apply to the $\in$ in $a \in A$?

## 2 Answers

When the book says $\forall n \in \mathbb{Z}, (n \neq 0) \implies (n^2 > 0)$, it means for this to be parenthesized as $$\forall n \in \mathbb{Z},[(n \neq 0) \implies (n^2 > 0)].$$ So you don't negate the quantifier or anything because the implication statement is entirely inside the quantifier.

Note that the interpretation $$[\forall n \in \mathbb{Z}, (n \neq 0)] \implies (n^2 > 0)$$ doesn't make any sense. If the quantifier only applies to $n\neq 0$, then the variable $n^2>0$ is not bound by the quantifier and is just a free variable whose meaning is unknown (and in particular, it is not the same $n$ as in $n\neq 0$, since that $n$ only has meaning when bound by the quantifier). That is, the statement above would mean "if it's true that every integer is nonzero, then $n^2$ is positive". This is a (rather silly) statement about an unspecified number $n$, rather than a general statement about all integers.

First, the fact that the book uses a $\forall$ means that they go beyond propositional logic, so I think the question was ill-posed.

Second, what you really have is:

$$\forall n \in \mathbb{Z} (n \not = 0 \Rightarrow n^2 >0)$$

The book should have put those parentheses! Without them, the $n$ in the $n^2$ term would be a free variable, not quantified by the quantifier.

So applying Implication on the conditional gives you:

$$\forall n \in \mathbb{Z}(n =0 \lor n^2>0)$$

But because the book failed to put parentheses around the conditional, it looked like all of $\forall n \in \mathbb{Z} \ n =0$ was the antecedent. No wonder you got confused!

What's the title of this book? I'll make a note never to use it ...

• :) they are notes published by our professor, not from a real textbook Jun 13, 2017 at 2:43
• @Carpetfizz OK, well, at least it didn't make it into print :) Jun 13, 2017 at 2:51