Is negation distributive

logicpredicate-logic

Take a proposition like $\neg(\forall x \in S, P(x))$. If negation is not distributive, how does one determine which connective to be negated? Here are the options I've seen:

$$\neg(\forall x \in S, P(x)) \iff \neg\forall x \in S, P(x) \iff \exists x \in S, \neg P(x)\tag1$$

$$\neg(\forall x \in S, P(x)) \iff \forall x \not \in S, P(x) \tag2 $$

$$\neg(\forall x \in S, P(x)) \iff \forall x \in S, \neg P(x) \tag3$$

$$\neg(\forall x \in S, P(x)) \iff \neg\forall x \not \in S, \neg P(x) \iff \exists x \in S^c, P(x) \tag4$$

Here, $(4)$ is the version in which negation is distributive. If $(4)$ is not correct, how does one determine what is to be negated in cases like the LHS above?

EDIT:

All even numbers are divisible by three: $\forall n \in \Bbb N, n | 3$

Obviously not true. What is true? Following the Law of Excluded Middle, $P \lor \neg P$. Since $P$ is false, its negation must be true. The following RHS expressions are true:

$\neg(\forall n \in \Bbb N, n | 3) \iff (\neg \forall n \in \Bbb N, n | 3 ) \iff (\exists n \in \Bbb N, \displaystyle \frac n3 \not \in \Bbb N)$

However, it is also true that there exists a number outside of the naturals that is divisible by three, tagged as $(4)$ here. So, if we assume LEM, my above list is shortened:

$$\neg(\forall x \in S, P(x)) \iff \neg\forall x \in S, P(x) \iff \exists x \in S, \neg P(x)\tag1$$

$$\neg(\forall x \in S, P(x)) \iff \neg\forall x \not \in S, \neg P(x) \iff \exists x \in S^c, P(x) \tag4$$

It is not the case that all naturals are disivisble by three. It is the case that there exists naturals that aren't divisble by three. It is also the case there exists non-natural numbers that are divisible by three. Both $(1)$ and $(4)$ satisfy LEM in the given example, and both of them seem like ways of negating the example proposition. Which one is correct? When not assuming LEM, which is correct then?

Best Answer

$$\neg(\forall x \in S, P(x)) \iff \neg\forall x \in S, P(x) \iff \exists x \in S, \neg P(x)\tag1$$

Only option $(1)$ is correct:

\begin{align}&\neg\,\forall x {\in}S \; P(x) \\\equiv{}&\neg\,\forall x\; \Big(x \in S \to P(x)\Big) \\\equiv{}&\exists x\; \neg\Big(x \in S \to P(x)\Big) \\\equiv{}&\exists x\; \neg\Big(x \notin S \:\lor\: P(x)\Big) \\\equiv{}&\exists x\; \Big(x \in S \:\land\: \neg P(x)\Big) \\\equiv{}&\exists x{\in}S\; \neg P(x). \end{align}

(Please refer to Quantifier notational shorthand.)

And so, $$\neg\,\exists x{\in}S\; Q(x)\equiv\ \forall x {\in}S \; \neg Q(x).$$

EDIT:

All even numbers are divisible by three: $$\forall n \in 2\Bbb N, n|3$$

Obviously not true. What is true?

Some even number is indivisible by three: $$\exists n {\in} 2\Bbb N\quad n\not|\,\:3.$$

This makes sense, since you would negate

  • Every person has a mother  (T)

not with (option 4)

  • Some non-person has a mother  (T)

but with (option 1)

  • Some person has no mother.  (F)

Is negation distributive?

No, negation is not straightforwardly "distributive", but it can be—using De Morgan's laws—if we first convert every conditional $\Big(A(x)\to B(x)\Big)$ to $\Big(\lnot A(x) \lor B(x)\Big).$

Related Question