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!
means the set of all real numbers. The statement “every value the function takes is less than 10.” can be written
This is an interpretation of a formula
Let’s negate it, using the negation of quantifiers lemma, Lemma 1.11.2:
Passing back to our interpretation, this says which is the same as .
Consider the statement “the function is bounded”, which we could write as
This is an interpretation of a formula
Let’s negate it.
so “the function is not bounded” is , or equivalently, .
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
This is an interpretation of a formula
Let’s negate it.