# 1.12 Negation

This section is about some examples of producing useful logical equivalents for negations of quantified formulas. We’re going to use real-life examples from bits of mathematics you may not have met yet, but this won’t be a problem as our negation procedure doesn’t require understanding anything about the meaning of the formulas!

###### Example 1.12.1.

$\mathbb{R}$ means the set of all real numbers. The statement “every value the function $f:\mathbb{R}\to\mathbb{R}$ takes is less than 10.” can be written

 $\forall x\;f(x)<10.$

This is an interpretation of a formula

 $\forall x\;P(x).$

Let’s negate it, using the negation of quantifiers lemma, Lemma 1.11.2:

 $\neg\forall x\;P(x)\equiv\exists x\neg P(x)$

Passing back to our interpretation, this says $\exists x\;\neg(f(x)<10)$ which is the same as $\exists x\;f(x)\geqslant 10$.

###### Example 1.12.2.

Consider the statement “the function $f:\mathbb{R}\to\mathbb{R}$ is bounded”, which we could write as

 $\exists M\forall x\;|f(x)|\leqslant M.$

This is an interpretation of a formula

 $\exists M\forall x\;P(x,M).$

Let’s negate it.

 $\displaystyle\neg\exists M\forall x\;P(x,M)$ $\displaystyle\equiv\forall M\neg\forall x\;P(x,M)$ $\displaystyle\equiv\forall M\exists x\;\neg P(x,M)$

so “the function $f$ is not bounded” is $\forall M\exists x\;\neg(|f(x)|\leqslant M)$, or equivalently, $\forall M\exists x\;|f(x)|>M$.

###### Example 1.12.3.

Goldbach’s conjecture is that every integer larger than 2 is either odd or is a sum of two prime numbers. We could write this as

 $\forall n\;\operatorname{Odd}(n)\vee\exists p\exists q\;\operatorname{Prime}(p% )\wedge\operatorname{Prime}(q)\wedge(p+q=n)$

This is an interpretation of a formula

 $\forall n\;O(n)\vee\exists p\exists q\;P(p)\wedge P(q)\wedge R(p,q,n).$

Let’s negate it.

 $\displaystyle\neg(\forall n\;O(n)\vee\exists p\exists q\;P(p)\wedge P(q)\wedge R% (p,q,n))$ $\displaystyle\equiv\exists n\neg(O(n)\vee\exists p\exists q\;P(p)\wedge P(q)% \wedge R(p,q,n))$ $\displaystyle\equiv\exists n\;\neg O(n)\wedge(\neg\exists p\exists q\;P(p)% \wedge P(q)\wedge R(p,q,n))$ $\displaystyle\equiv\exists n\;\neg O(n)\wedge(\forall p\neg\exists q\;P(p)% \wedge P(q)\wedge R(p,q,n))$ $\displaystyle\equiv\exists n\;\neg O(n)\wedge(\forall p\forall q\;\neg(P(p)% \wedge P(q)\wedge R(p,q,n)))$ $\displaystyle\equiv\exists n\;(\neg O(n))\wedge(\forall p\forall q\;\neg P(p)% \vee\neg P(q)\vee\neg R(p,q,n))$