Set Builder Notation

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Misc

Next Tuesday (March 2) is the semester’s first rejuvenation day. It doesn’t affect this course directly, but in the spirit of getting a bit of a break from academic worries, I’m discouraging individual meetings that day (well, slightly discouraging them — if you want one you can certainly have it, but if you’d rather not, I think that’s a good idea in the spirit of the day). I also won’t hand out a new problem set this Friday, so you’ll have a bit of a break from working on problem sets for the beginning of the week.

Set Builder Notation

Based on “Beginning Activity 2 (Variables),” “Variables and Open Sentences,” “Set Builder Notation,” and “When the Truth Set is the Universal Set” in section 2.3 of our textbook, plus this discussion of set builder notation.

Reading the Notation

What sets do the following describe? (These generally  have correct solutions in the discussion, but it’s worth looking for alternative phrasings of the descriptions.)

1. { x ∈ ℝ | x > 0 } is the positive real numbers.
2. { 2n + 1 | n ∈ ℤ } is the odd integers.
3. { n ∈ ℕ | n has no factors beside itself and 1 } is the prime numbers.
4. { x ∈ ℝ | x divided by 3 is an integer } is the integer multiples of 3.
5. { 3n | n ∈ ℤ } is also the integer multiples of 3, but phrased differently.

Symbols for standard sets of numbers, used in set builder notation and elsewhere:

• ℝ = reals
• ℕ = naturals
• ℤ = integers
• ℚ = rationals

Writing the Notation

How would you use set builder notation to describe the following sets?

1. The set of real numbers between 1 and 6, inclusive. This has a good solution in the discussion.
2. The set of integers that are multiples of 2 or of 5.
   1. { n ∈ ℤ  |  the last digit in n is either even or 5 } This is interesting because it uses the written form of the number rather than its value (in that vein, the predicate ought to mention base-10 notation when talking about the last digit in n).
   2. { n ∈ ℤ  |  n = 2k or n = 5k for some integer k }

The second suggestion for multiples of 2 or 5 is starting to look like formulas for computing the members of the set. Indeed, that’s often convenient, and there’s a form of set builder notation that makes it easy. There are 2 forms of set builder notation, one of which will sometimes be easier than the other for describing certain sets, and you can pick between them — but don’t mix them!

More examples of defining sets using set builder notation:

1. The set of integer powers of 2 (i.e., the set of numbers equal to 2ⁿ  for some integer n).
   1. { 2ⁿ |  n ∈ ℤ } This uses the function form of set builder notation; I find it simpler and clearer than the predicate version.
   2. { n ∈ ℤ | n = 2^k for some integer k } This uses the predicate form of the  notation; I find it less clear, largely because it requires introducing a second variable to do what is basically the computation that the function form is designed to express.
2. The set of perfect squares (i.e., integers that are the square of some other integer).
   1. { n² | n ∈ ℤ } 

Extending the Notation

Can you use set builder notation for sets that contain things other than numbers? What would it take to do it? What would be some examples?

You can, as long as you have a universal set to work with and predicates or functions on its members.

For example, if you didn’t need a universal set, you could define something like S = { x | x is a set that does not contain itself } to “define” the impossible paradox we talked about in the first class (S must either be a member of S or not, but it can’t be a member of S because then S would contain itself which violates the “not a member of itself” predicate, and it can’t not be a member, because then S would be a set that doesn’t contain itself, and so it would be  a member).

You can, particularly in situations that needn’t be highly rigorous mathematically, define plausible groups as sets. For example, you could define the set of all Geneseo students using set builder notation by assuming that a set of all the people in the world exists, say P, and writing…

{ x ∈ P | x is a student presently at Geneseo }

What about dodging the universal set issue by using ID numbers instead of actual people in the set? For example…

 { n∈ ℕ | n is the ID number of a student presently at Geneseo }

But I’d argue that these aren’t the same sets, because one is a set of people and the other is a set of numbers.

But there is a sense in which they are highly “similar”, even if not exactly the same, because there’s an obvious 1-to-1 mapping between them: every student has an ID number, and every ID number corresponds to a specific student. This idea of using 1-to-1 mappings to define a sense of similarity between sets will come back later in the semester when we talk about infinite sets.

Next

Now that we know about predicates, we can use them to talk rigorously about “quantifiers” (“for all” and “there exists”) and quantified statements.

Please read “Beginning Activity 1 (An Introduction to Quantifiers)” and “Forms of Quantified Statements in English” in section 2.4 of the textbook.

Please also contribute to this discussion of quantifiers.

Next Lecture