Set Operations

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Misc

Problem set 8 (a review of induction and proof by contradiction) technically doesn’t start until Monday, but if anyone wants an early look at it, it’s available through Canvas.

Set Operations

Based on section 5.1 of the textbook and this discussion of set operations.

Examples

Any questions about the examples in the discussion? No.

Give some real-world examples of sets (not from the discussion)

How about sets of people in a grocery store, for instance the people who carry purchases in a cart, the people who carry them in a basket, and the people who just carry them in their hands?

Then we can describe the sets as

• Baskets = { A, B, C, D }
• Carts = { E, F, G, H }
• None = { I, J }

This example is particularly good for talking about universal sets and complements.

A universal set is a “universe” of relevant possible set members. In this case the natural universal set is the set of all shoppers in the store, i.e., { A, B, C, D, E, F, G, H, I, J }

The complement of a set, written as the set’s name with a superscript “C,” is everything not in that set, but in the universal set. For instance, in our example None^C = { A, B, C, D, E, F, G, H }.

This example isn’t as interesting for illustrating intersections, unions, or differences though.

• The intersection of sets A and B is the set of things that are elements of both. So all the intersections of these example sets are empty, e.g., Carts ∩ Baskets = ∅.
• The difference of sets A and B, A - B, is the set of elements of A that are not in B. So all the differences of these example sets are the first set, e.g., Carts - Baskets = Carts = { E, F, G, H }
• The union of sets A and B is the set of things that are in A or in B (or both), so all the unions of these example sets look like the elements of one followed by the elements of the other, e.g., Carts ∪ Baskets = {E, F, G, H, A, B, C, D}.

To get some more varied examples of intersections and differences we divided the hypothetical shoppers up into 2 different sets, namely the set of shoppers who have 2 or more purchases (marked “>” below), and the set who have fewer (marked “<”):

So the sets of shoppers who have many items and few items are

• Many = { B, E, H, I }
• Few = { A, C, D, F, G, J }

And now we can talk about, for example,

• Carts ∩ Many = { E, H }
• Baskets - Few = { B }
• Etc.

Power Set and Cardinality

The power set of S is the set of all subsets of S.

Power set is often written as a script “P” used as a function, for example

Notice that this power set has “cardinality” (i.e., size) 4, which is somewhat bigger than the cardinality of set None.

How do cardinalities of some other power sets grow? For example

After working out the power set of Carts, where the power set had cardinality 16 and Carts has cardinality 4, we conjectured that maybe the power set of a set S has cardinality |S|² (“|S|” being a notation for the cardinality of a set).

But then we looked at a set of size 3, whose power set should have 9 elements according to that rule, but in fact only has 8.

Using 2^|S|as the formula for the cardinality of a power set would fit all three of these examples. Can we prove that this formula is in fact correct? Someone suggested that induction might be a promising way to do it, but the actual proof will be our next topic of discussion….

Next

The cardinality of the power set of set S in terms of the size of S

No new reading, but you can use this discussion of the proof to start thinking about it.

Next Lecture