Quantifiers, Part 2

Return to Course Outline

Previous Lecture

Misc

First hour exam is next Friday, February 16.

Covers material from the beginning of the semester through sets, e.g., statements, proof writing, logic, sets. Also see problem sets 1 through 3, and lecture notes from Jan. 17 through Feb. 5.

You’ll have the full class period.

Expect 3 to 5 short-answer questions, similar (at least in my mind) to those on problem sets. But any questions that ask for formal proofs will not require them to be typeset.

Open book, open notes, open computer for reference, but closed person.

Questions?

Quantifiers

Negated Quantifiers

Recall the students and ID numbers from last time:

• S is a set of students.
• D is a set of ID numbers.
• Predicate n(s,d) means that student s has ID number d.

Write negations of the following, both in English and symbolically:

• Every ID number is an integer, i.e., (∀ d ∈ D)(d ∈ ℤ). Negation is some ID is not an integer, i.e., (∃ d ∈ D)(d ∉ ℤ)
• Some ID number is less than 0, i.e., (∃ d ∈ D)(d < 0). Negation is (∀ d ∈ D)(d ≥ 0), i.e., every ID is greater than or equal to 0 (note that “not less than” is “greater than or equal”).
• Every student has an ID number, i.e.,(∀ s ∈ S)(∃ d ∈ D)(n(s,d)). The negation is some student has no ID number, i.e., (∃ s ∈ S)(∀ d ∈ D)(¬n(s,d)).

Proofs about Quantified Statements

Universal Quantifiers

Prove that for every even integer, n, n/2 is an integer.

Proof: If n is an even integer, then there must be an integer x such that n=2x . Now n/2 = 2x/2 = x which is an integer. We have thus proven that for every even integer n, n/2 is an integer. QED.

Notice how the universal quantifier is approached as a conditional statement in this proof. This is a very common way of proving universal statements.

Existential Quantifiers

Prove that there is some real number x such that cos x = 0.

Proof: π/2 is real and cos π/2 = 0. QED.

Notice that all this proof had to do is show one example. This is the shortest and simplest way to prove an existential statement.

But you can’t always find such an example. For instance, prove that there is some real number x such that cos x = x.

Intuitively, the graphs of x and cos x must cross, and they can’t “jump over” or “slip through” each other because both are continuous:

The Intermediate Value Theorem (if f(x) is continuous over [a,b] and f(a) < c < f(b) then there is a d in (a,b) such that f(d) = c) makes this more precise.

Proof: Let f(x) = cos x - x. Then f(0) = 1 and f(π/2) = -π/2, so by the IVT, somewhere between 0 and π/2 f(x) = 0, i.e., cos x = x. We have thus proven that there exists some real number x such that cos x = x. QED.

This is an example of a “non-constructive proof,” i.e., a proof that shows something exists without actually finding it.

Vacuous Truth

Is it true or false that every positive integer less than 0 is prime? It’s true. Intuitively, you can think of this following from the fact that its negation must be false (the negation is “there is some positive integer less than 0 that is non-prime,” but there cannot be because there are no positive integers of any kind less than 0), or from the view of universal statements as conditionals (if you set out to prove “if n is a positive integer less than 0, then n is prime” you’ll immediate conclude that the statement is true because its hypothesis, “n is a positive integer less than 0,” has to be false).

So every statement about all members of the empty set is true. This is “vacuous truth.”

On the other hand, every existential statement about members of empty set is false.

Key Points

The rules for negating quantified statements (which boil down to “replace the quantifier with the other one and negate the inner statement”).

Prove universals as conditionals.

Prove existentials by example or non-constructively.

Vacuous truth.

Next

Review of direct proofs via divisibility.

Read section 3.1.

Next Lecture