Basic Ideas of Sets

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Sets and Roster Notation

Based on “Beginning Activity 1 (Sets and Set Notation),” “Some Set Notation,” and “The Empty Set” in section 2.3 of our textbook, and this discussion of basic set concepts.

Roster Notation

All of the following have good solutions in the discussion, except that many should also include 0 in the set because 0 is (surprisingly) a multiple of 3:

1. The set of all integer multiples of 3 between 0 and 9, inclusive. For example, this would be written {0, 3, 6, 9}.
2. The set of all integer multiples of 3 between 0 and 3000, inclusive. This would be {0, 3, 6, …, 3000}.
3. The set of all non-negative integer multiples of 3. {0, 3, 6, …}
4. The set of all integer multiples of 3. {…, -6, -3, 0, 3, 6, …}
5. The set of people who have posted to this discussion so far (include yourself, assuming you have or are about to post). See the discussion.
6. The set containing the sets {1,2}, {2,3}, and {3,4} (and nothing else). {{1,2}, {2,3}, {3,4}}
7. The empty set. {}
8. The set of integers between 1 and 6, inclusive. {1, 2, 3, 4, 5, 6}
9. The set of real numbers between 1 and 6, inclusive. Can’t be written in roster notation.

Key ideas about roster notation that these examples exercise:

• The central idea is to list the elements of a set between “{” and “}”
• Ellipsis (three periods, “…”) can be used to indicate that a hopefully obvious pattern continues
• But sets whose elements aren’t listable (e.g., the reals between 1 and 6) can’t be described via roster notation.

Set Concepts

The following true/false questions in the discussion also generally had good answers (with one clarification from me):

1. {a,b,c,a,d} is a set that contains 2 copies of the letter “a.” This is false, because sets don’t contain multiple copies of an element.
2. {1,3,5} = {5,3,1}. True
3. ∅ ⊆ {10,20}. True
4. 3 ∈ {1,3,5}. True
5. 3 ⊆ {1,3,5}. False. Something that is an element of a set generally isn’t a subset and vice versa. But {3} ⊆ {1,3,5} is true.

The relationships between 10, {10}, and {{10}} deserve talking about. What can you say about them?

The values are, respectively, the number 10, the set containing 10, and the set containing the set containing 10 (i.e., a set whose only element is another set). Each of these is a 1-element set, so it turns out the relationships  between them are all element relations, i.e.,

• 10 ∈ {10}
• {10} ∈ {{10}}

There are no subset relationships, except trivial ones such as {10} ∈ {10}.

Key ideas about sets that these questions bring out:

• Equality: 2 sets are equal if they have the same members; the order in which members are listed and any duplication of members don’t matter.
• Subset: A is a subset of B if all members of A are members of B
• Membership.

Proofs

Can you extend the basic ideas about sets that were introduced here into rigorous proofs. For example…

Can you prove that the set of integer multiples of 6 between 0 and 18, inclusive, is a subset of the set of integer multiples of 3 between 0 and 18, inclusive?

Basic idea: turn to the definition of subset: A ⊆ B if and only if every element of A is an element of B. (In general, “turn to the definition” is good advice for lots of direct proofs).

So we can simply see that every element of {0,6,12,18} is also an element of {0,3,6,9,12,15,18}, thus {0,6,12,18} ⊆ {0,3,6,9,12,15,18}.

We can also write a formal proof around this idea, and in fact we did — the first proof in this LaTeX source file and PDF document (remember that you’ll have to download the source file to your computer if you want to see the actual LaTeX source).

We can also use set-related definitions in proofs that can’t be done just by inspection. For example, proving that the set of all integer multiples of 6 is a subset of the set of all integer multiples of 3.

Basic idea: an integer of multiple of 6 = 6n for some integer n, and 6n = 3(2n) which is an integer multiple of 3.

We wrote a formal proof for this example too, namely the second proof in this LaTeX source file and PDF document.

Next

Some of the examples we looked at involve sets that we don’t really have good notations for describing, beyond English (e.g., “the set of all integer multiples of 3”). So let’s look at another notation for describing sets, “set builder notation.”

Please read “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.

Please also contribute to this discussion of set builder notation.

Next Lecture