Introduction to Quantifiers

Return to List of Lectures

Previous Lecture

Misc

Exam 1

Monday (Feb. 13)

Covers material from the start of the semester through problem set 4 (set basics).

Note that problem set 4 will be completed before the exam, but grading can be after — it’s up to you whether you want to schedule your grading appointment before or after the exam.

Expect 3 to 5 short-answer (e.g., around a paragraph of prose, 4 to 5 lines of derivation, etc.) questions. Some may be formal proofs. I think the questions will be comparable in difficulty to problem set questions, but your sense of “difficulty” may be different from mine.

I give partial credit, so showing scratch work can be good for you.

You’ll have the whole class period.

The test will be open book, open notes, open computer in so far as the computer is used as a reference. But you can’t communicate with other people during the test.

Questions?

Quantifiers

Section 2.4

Universal quantifier ∀ means “for every”

Existential quantifier ∃ means “there exists”

Theorem 2.16

• To negate a quantified statement, switch the quantifiers and negate the predicate
  • Note that “not greater than” is “less than or equal”
• Negating multiple quantifiers uses the rules for negating one over and over

Use counterexamples to disprove claims

Reading Statements with Quantifiers

Give English sentences that mean the same thing as (∀ x ∈ ℕ)(x > 0)

• “For every natural number x, x > 0“
• “All natural numbers are bigger than 0” (this is a less literal translation than the first, but better conveys the intuitive message of the quantified statement. Try to capture such intuition in your own translations when reading quantified statements.)

Give English sentences that mean the same thing as (∃ x ∈ ℕ)(x = 1/2)

• “1/2 is a natural number” (which is an example of a false quantified statement)

Give English sentences that mean the same thing as (∀ x ∈ ℝ)(∃ y ∈ ℤ)(y > x)

• “for every real number, there exists an integer greater than it”
• “Some integer is greater than all real numbers” (this is easily read as meaning that there is an integer that is bigger than every real number, which is not what the quantified statement says. Read quantifiers left to right, i.e., the quantified statement says that every real number has its own integer that is bigger than that particular real.)

Formulating Quantified Statements

Use quantifier symbols to say “every integer is either less than π or greater than π”

• (∀ x ∈ ℤ)( x<π or x>π )

Use quantifier symbols to say “π² is a natural number“

• (∃ x ∈ N )( x = π² )

Use quantifier symbols to say “some element of the set {2,3,5,7} is odd,” using the formal definition of “odd” rather than the word or its synonyms

• (∃ x ∈ {2,3,5,7}) ( (∃ m ∈ ℤ) (x = 2m+1) )

Negating Quantified Statements

Give (in English) the negation of “every dog has fleas.”

• “Some dog does not have fleas”
• Or “there exists a dog without fleas”

Give (in English) the negation of “some flea has littler fleas”

• All fleas do not have littler fleas

(Inspired by

Great fleas have little fleas upon their backs to bite ’em
and little fleas have lesser fleas, and so ad infinitum

variously attributed, with slight variations, to Jonathan Swift, Augustus de Morgan, and no doubt others)

Quantifiers over the Empty Set

For next class, consider the following two questions:

Is it true that every pink dragon in this room is dancing on the tables?

Is it true that some pink dragon in this room is writing down everything we say?

Problem Set

See handout for details

Next

Quantification over the empty set

Proofs about quantifiers

(No new reading)

Next Lecture