Set Builder Notation

Return to Course Outline

Previous Lecture

Misc

Grad School Talk

Geneseo alumnus Robert Tumasian talking about his experiences with post-baccalaureate research and education programs as preparation for biostatistics graduate school.

Friday, Feb. 15, 2:30 PM.

South 336.

Problem Set

Problem set on propositional logic and related proofs (and a little bit more) — see handout for details.

Exam 1

The first hour exam is scheduled for next Friday, Feb. 22.

It will cover material from the beginning of the semester through problem set 3 (e.g., mathematical statements, direct proofs, propositional logic, sets, predicates).

Expect 3 to 5 short-answer questions, similar (in my mind at least) to problem set questions.

You’ll have the whole class period to do the test.

Open references (book, notes, online references), but closed person.

Questions?

Set Builder Notation

Examples

From last time: The interval [0,1) on the real number line could be described as { x ∈ ℝ | 0 ≤ x < 1 } or { x ∈ ℝ | x ∈ [0,1) }.

More examples: use set builder notation to define the following:

• The set of natural numbers that can be written as a sum of 2 not-necessarily-distinct integer powers of 2. Note that to get natural numbers, the exponents in the powers of 2 actually have to be non-negative integers. The simplest set builder form gives an expression that calculates the members of the set, followed by a definition of the universal set(s) the variable(s) come from: { 2^x + 2^y | x, y ∈ ℕ ∪ {0} }. Alternatively, you can define the universal set and then “disguise” the calculation of set elements as a predicate: { z ∈ ℕ | z = 2^x + 2^y, where x, y ∈ ℕ ∪ {0} } .
• The set of real numbers that are solutions to x = cos x. There’s no good way to describe this other than with the predicate form of set builder notation: { x ∈ ℝ | x = cos x }
• The set of odd integers (ℤ). This could use either the calculation or predicate forms: { 2x + 1 | x ∈ ℤ } or { n ∈ ℤ | n = 2z + 1 where z ∈ ℤ }

Key Points re Set Builder Notation

There are two forms, but both specify a universal set from which some variable comes, with either an expression that calculates elements of the intended set from elements of the universal set, or a predicate that says which elements of the universal set are in the intended set.

The notations are either { universal | predicate } or { calculation | universal }.

Quantifiers

Section 2.4

Meanings

Paraphrase (∀ a ∈ ℤ)(a > a-1) in English

For every integer a, a > a - 1

If a is an integer, then a > a-1. Note that universally quantified statements correspond to conditionals.

Paraphrase (∃ x ∈ ℝ)(x² = 2) in English

There exists a real number x such that x² = 2

Some real number squares to 2

Next

A fuller look at quantifiers, including when quantified statements are true or false, negations of quantified statements, and proof methods for dealing with quantifiers.

To get ready, paraphrase (∀ x ∈ {4n | n ∈ ℕ}) ( (∃ y ∈ ℤ)(x = 2y) ) in English.

Then finish reading section 2.4, particularly the “Negations of Quantified Statements” subsection.

Next Lecture