1 Logic 1.11 First order equivalences Further reading

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