Set Builder Notation

Return to List of Lectures

Previous Lecture

Misc

Exam 1

Next Monday (Feb. 13)

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

Note that problem set 4 is to 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 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.

Problem Set 2 Solutions

PDF file and LaTeX source are available in the “Solutions” folder under “Files” in Canvas (or via the links in this sentence).

Questions?

Can formal proofs include truth tables?

Yes, with framing text to explain the truth table (e.g., “...we will prove with a truth table that ...”, “...from columns 3 and 7 of this truth table we see that ...”

Set Builder Notation

First Form

Skeleton example from last time: { x ∈ ℝ | ...some open sentence about x... }

Standard sets:

• ℝ = the real numbers
• ℚ = the rational numbers
• ℤ = the integers
• ℕ = the natural numbers

The set builder expression above means the set of elements of universal set ℝ for which the open sentence is true

Set builder notation is a good way to describe infinite sets

What expression appears on what side of the vertical bar matters

Another example: Give another description (e.g., in English, roster notation) of { x ∈ ℕ | x > -1 ∧ x < 8}

“The natural numbers 1 through 7”

{ 1, 2, 3, 4, 5, 6, 7}

Writing example: Use set builder notation to describe the set of non-negative integers.

{ x ∈ ℤ | x ≥ 0 }

Another writing example: Use set builder notation to describe the set of real numbers whose square roots are real and less than the number itself.

{ x ∈ ℝ | x > 1 }

or { x ∈ ℝ | √x ∈ ℝ and √x < x }

or { x ∈ ℝ | x ≥ 0 and √x < x }

or (ugly and second form) { x | x ∈ { y ∈ ℝ | y > 1 } }

• This illustrates that you can nest set builder notation.

Second Form

Skeleton example: { ...expression involving x... | x ∈ U }

For instance, the set of perfect squares is { x² | x ∈ ℤ }

Or, in first form { x ∈ ℤ | √x ∈ ℕ ∪ {0} }

Usage: Use the second form when it’s most natural to describe how to calculate the elements of the set.

Use the first form when it’s most natural to describe how to test whether an element of the universal set is also an element of the set you’re describing.

Next

Quantifiers

Read section 2.4

Next Lecture