2.5: More About Quantification

When writing mathematical proofs, we do not explicitly use the symbolic representation of a given statement in terms of quantifiers and logical connectives. Nonetheless, having this notation at our disposal allows us to compartmentalize the abstract nature of mathematical propositions and provides us with a way to talk about the general structure involved in the construction of a proof.

Definition 2.74. Two quantified propositions are logically equivalent if they have the same truth value in every universe of discourse.

Problem 2.75. Consider the propositions (∃x ∈ U)(x² − 4 = 0) and (∃x ∈ U)(x² − 2 = 0), where U is some universe of discourse.

(a) Do these propositions have the same truth value if the universe of discourse is the set of real numbers?

(b) Provide an example of a universe of discourse such that the propositions yield different truth values.

(c) What can you conclude about the logical equivalence of these propositions?

It is worth pointing out an important distinction. Consider the propositions “All cars are red” and “All natural numbers are positive”. Both of these are instances of the logical form (∀x)P (x). It turns out that the first proposition is false and the second is true; however, it does not make sense to attach a truth value to the logical form. A logical form is a blueprint for particular propositions. If we are careful, it makes sense to talk about whether two logical forms are logically equivalent. For example, (∀x)(P (x) =⇒ Q(x)) is logically equivalent to (∀x)(¬Q(x) =⇒ ¬P (x)) since a conditional proposition is logically equivalent to its contrapositive (see Theorem 2.39). For fixed P (x) and Q(x), these two forms will always have the same truth value independent of the universe of discourse. If you change P (x) and Q(x), then the truth value may change, but the two forms will still agree.

The next theorem tells us how to negate logical forms involving quantifiers. Your proof should involve several mini arguments. For example, in Part (a), you will need to proof that if ¬(∀x)P (x) is true, then (∃x)(¬P (x)) is also true.

Theorem 2.76. Let P (x) be a predicate in some universe of discourse. Then

(a) ¬(∀x)P (x) is logically equivalent to (∃x)(¬P (x));

(b) ¬(∃x)P (x) is logically equivalent to (∀x)(¬P (x)).

Problem 2.77. Negate each of the following sentences. Disregard the truth value and the universe of discourse.

(a) (∀x)(x > 3)

(b) (∃x)(x is prime∧x is even)

(c) All cars are red.

(d) Every Wookiee is named Chewbacca.

(e) Some hippies are Republican.

(f) Some birds are not angry.

(g) Not every video game will rot your brain.

(h) For all x ∈ N, x² + x + 41 is prime.

(i) There exists x ∈ Z such that 1/x < Z.

(j) There is no function f such that if f is continuous, then f is not differentiable.

Using Theorem 2.76 and our previous results involving quantification, we can negate complex mathematical propositions by working from left to right. For example, if we negate the false proposition

(∃x ∈ R)(∀y ∈ R)(x + y = 0),

we obtain the proposition

¬(∃x ∈ R)(∀y ∈ R)(x + y = 0),

which is logically equivalent to

(∀x ∈ R)(∃y ∈ R)(x + y , 0)

and must be true. For a more complicated example, consider the (false) proposition

(∀x)[x > 0 =⇒ (∃y)(y < 0∧xy > 0)].

Then its negation

¬(∀x)[x > 0 =⇒ (∃y)(y < 0∧xy > 0)]

is logically equivalent to

(∃x)[x > 0∧ ¬(∃y)(y < 0∧xy > 0)],

which happens to be logically equivalent to

(∃x)[x > 0∧(∀y)(y ≥ 0∨xy ≤ 0)].

Can you identify the theorems that were used in the two examples above?

Problem 2.78. Negate each of the following propositions. Disregard the truth value and the universe of discourse.

(a) (∀n ∈ N)(∃m ∈ N)(m < n)

(b) For every y ∈ R, there exists x ∈ R such that y = x².

(c) For all y ∈ R, if y is not negative, then there exists x ∈ R such that y = x².

(d) For every x ∈ R, there exists y ∈ R such that y = x².

(e) There exists x ∈ R such that for all y ∈ R, y = x².

(f) There exists y ∈ R such that for all x ∈ R, y = x².

(g) (∀x,y, z ∈ Z)((xy is even∧yz is even) =⇒ xz is even)

(h) There exists a married person x such that for all married people y, x is married to y.

Problem 2.79. Consider the following proposition in some universe of discourse.

“For all goofy wobblers x, there exists a dinglehopper y such that if x is a not a nugget, then y is a doofus.”

Find the negation of this proposition so that it includes the phrase “is not a doofus.”

Problem 2.80. Consider the following proposition in some universe of discourse.

“If x and y are both snazzy, then xy is not nifty.”

Find the contrapositive of this proposition so that it includes the phrase “not snazzy”.

At this point, we should be able to use our understanding of quantification to construct counterexamples to complicated false propositions and proofs of complicated true propositions. Here are some general proof structures for various logical forms.

Skeleton Proof 2.81 (Direct Proof of (∀x)P (x)). Here is the general structure for a direct proof of the proposition (∀x)P (x). Assume U is the universe of discourse.

Proof. [State any upfront assumptions.] Let x ∈ U.

... [Use definitions and known results.] ...

Therefore, P (x) is true. Since x was arbitrary, for all x, P (x).

Combining Skeleton Proof 2.81 with Skeleton Proof 2.48, we obtain the following skeleton proof.

Skeleton Proof 2.82 (Proof of (∀x)(A(x) =⇒ B(x))). Below is the general structure for a direct proof of the proposition (∀x)(A(x) =⇒ B(x). Assume U is the universe of discourse.

Proof. [State any upfront assumptions.] Let x ∈ U. Assume A(x).

... [Use definitions and known results to derive B(x)] ...

Therefore, B(x).

Skeleton Proof 2.83 (Proof of (∀x)P (x) by Contradiction). Here is the general structure for a proof of the proposition (∀x)P (x) via contradiction. Assume U is the universe of discourse.

Proof. [State any upfront assumptions.] For sake of a contradiction, assume that there exists x ∈ U such that ¬P (x).

... [Do something to derive a contradiction.] ...

This is a contradiction. Therefore, for all x, P (x) is true.

Skeleton Proof 2.84 (Direct Proof of (∃x)P (x)). Here is the general structure for a direct proof of the proposition (∃x)P (x). Assume U is the universe of discourse.

Proof. [State any upfront assumptions.] ...

... [Use definitions, axioms, and previous results to deduce that an x exists for which P (x) is true; or if you have an x that works, just verify that it does.] ...

Therefore, there exists x ∈ U such that P (x).

Skeleton Proof 2.85 (Proof of (∃x)P (x) by Contradiction). Below is the general structure for a proof of the proposition (∃x)P (x) via contradiction. Assume U is the universe of discourse.

Proof. [State any upfront assumptions.] For sake of a contradiction, assume that for all x ∈ U, ¬P (x).

... [Do something to derive a contradiction.] ...

This is a contradiction. Therefore, there exists x ∈ U such that P (x).

Note that if Q(x) is a predicate for which (∀x)Q(x) is false, then a counterexample to this proposition amounts to showing (∃x)(¬Q(x)), which can be proved by following the structure of Skeleton Proof 2.84.

It is important to point out that sometimes we will have to combine various proof techniques in a single proof. For example, if you wanted to prove a proposition of the form (∀x)(P (x) =⇒ Q(x)) by contradiction, we would start by assuming that there exists x in the universe of discourse such that P (x) and ¬Q(x).

Problem 2.86. Determine whether each of the following statements is true or false. If the statement is true, prove it. If the statement is false, provide a counterexample.

(a) For all n ∈ N, n² ≥ 5.

(b) There exists n ∈ N such that n² − 1 = 0.

(c) There exists x ∈ N such that for all y ∈ N, y ≤ x.

(d) For all x ∈ Z, x³ ≥ x.

(e) For all n ∈ Z, there exists m ∈ Z such that n + m = 0.

(f) There exists integers a and b such that 2a + 7b = 1.

(g) There do not exist integers m and n such that 2m + 4n = 7.

(h) For all a,b, c ∈ Z, if a divides bc, then either a divides b or a divides c.

(i) For all a,b ∈ Z, if ab is even, then either a or b is even.

Problem 2.87. Explain why the following “proof” is not a valid argument.

Claim. For all x,y ∈ Z, if x and y are even, then x + y is even.

“Proof.” Suppose x,y ∈ Z such that x and y are even. For sake of a contradiction, assume that x+y is odd. Then there exists k ∈ Z such that x+y = 2k+1. This implies that (x +y)−2k = 1. We see that the left side of the equation is even because it is the difference of even numbers. However, the right side is odd. Since an even number cannot equal an odd number, we have a contradiction. Therefore, x + y is even.

Sometimes it is useful to split the universe of discourse into multiple collections to deal with separately. When doing this, it is important to make sure that your cases are exhaustive (i.e., every possible element of the universe of discourse has been accounted for). Ideally, your cases will also be disjoint (i.e., you have not considered the same element more than once). For example, if our universe of discourse is the set of integers, we can separately consider even versus odd integers. If our universe of discourse is the set of real numbers, we might want to consider rational versus irrational numbers, or possibly negative versus zero versus and positive. Attacking a proof in this way, is often referred to as a proof by cases (or proof by exhaustion). A proof by cases may also be useful when dealing with hypotheses involving “or”. Note that the use of a proof by cases is justified by Theorem 2.30.

If you decide to approach a proof using cases, be sure to inform the reader that you are doing so and organize your proof in a sensible way. Note that doing an analysis of cases should be avoided if possible. For example, while it is valid to separately consider the cases of whether a is an even integer versus odd integer in the proof of Theorem 2.11, it is completely unnecessary. To prove the next theorem, you might want to consider two cases.

Theorem 2.88. For all n ∈ Z, 3n² + n + 14 is even.

Prove the following theorem by proving the contrapositive using two cases.

Theorem 2.89. For all n,m ∈ Z, if nm is odd, then n is odd and m is odd.

When proving the previous theorem, you likely experienced some dejavu. You should have assumed “n is even or m is even” at some point in your proof. The first case is “n is even” while the second case is “m is even.” (Note that you do not need to handle the case when both n and m are even since the two individual cases already yield the desired result.) The proofs for both cases are identical except the roles of n and m are interchanged. In instances such as this, mathematicians have a shortcut. Instead of writing two essentially identical proofs for each case, you can simply handle one of the cases and indicate that the remaining case follows from a nearly identical proof. The quickest way to do this is to use the phrase, “Without loss of generality, assume. . . ”. For example, here is a proof of Theorem 2.89 that utilizes this approach.

Proof of Theorem 2.89. We will prove the contrapositive. Let n,m ∈ Z and assume n is even or m is even. Without loss of generality, assume n is even. Then there exists k ∈ Z such that n = 2k. We see that \[nm = (2k)m = 2(km)\].

Since both k and m are integers, km is an integer. This shows that nm is even. We have proved the contrapositive, and hence for all n,m ∈ Z, if nm is odd, then n is odd and m is odd.

Note that it would not be appropriate to utilize the “without loss of generality” approach to combine the two cases in the proof of Theorem 2.88 since the proof of the second case is not as simple as swapping the roles of symbols in the proof of the first case.

There are times when a theorem will make a claim about the uniqueness of a particular mathematical object. For example, in Section 5.1, you will be asked to prove that both the additive and multiplicative identities (i.e, 0 and 1) are unique (see Theorems 5.2 and 5.3). As another example, the Fundamental Theorem of Arithmetic (see Theorem 6.17) states that every natural number greater than 1 can be expressed uniquely (up to the order in which they appear) as the product of one or more primes. The typical approach to proving uniqueness is to suppose that there are potentially two objects with the desired property and then show that these objects are actually equal. Whether you approach this as a proof by contradiction is a matter of taste. It is common to use \(∃!\) as a symbolic abbreviation for “there exists a unique. . . such that”.

Skeleton Proof 2.90 (Direct Proof of (∃!x)P (x)). Here is the general structure for a direct proof of the proposition (∃!x)P (x). Assume U is the universe of discourse.

Proof. [State any upfront assumptions.] ...

... [Use definitions, axioms, and previous results to deduce that an x exists for which P (x) is true; or if you have an x that works, just verify that it does.] ...

Therefore, there exists x ∈ U such that P (x). Now, suppose x1 , x2 ∈ U such that P (x1) and P (x2 ).

... [Prove that x1 = x2 .] ...

This implies that there exists a unique x such that P (x).

The next theorem provides an opportunity to practice proving uniqueness.

Theorem 2.91. If c,a, r ∈ R such that c , 0 and r , a/c, then there exists a unique x ∈ R such that (ax + 1)/(cx) = r.