Set Operations

Return to Course Outline

Previous Lecture

Questions?

Sets

Section 5.1.

Basic Operations

Create a universal set of people from this class, and subsets A and B of it.

U = { JK, IP, DB, JA, FM, RK, LK }

A = {JK, IP, DB, JA }

B = {JA, FM, RK, LK }

What are

• A ∪ B. Union. The elements in A or in B, so { JK, IP, DB, JA, FM, RK, LK }
• A ∩ B. Intersection. The elements in A and in B, so { JA } (Note that this set is not the same as the element JA, sets and their elements are different things)
• A - B. Difference. The elements in A but not in B, so { JK, IP, DB }
• A^C. Complement. The elements in U but not in A, so U - A = { FM, RK, LK }
• (B - A) ∪ B^C = { FM, RK, LK } ∪ { JK, IP, DB } = { FM, RK, LK, JK, IP, DB }
• The power set of B. The set of all subsets of B, so { {}, {JA}, {FM}, {RK}, {LK}, {JA,FM}, {JA,RK}, {JA,LK}, {FM,RK}, {FM,LK}, {RK,LK}, {JA,FM,RK}, {JA,FM,LK}, {FM,RK,LK},{JA,RK,LK}, {JA, FM, RK, LK } }

A Theorem

Motivation: Why do we constantly need to define these universal sets, why not just implicitly take the “set of everything” as the universal set?

Answer: Because there is no “set of everything,” as established by the following theorem and corollary.

Theorem: there is no set of all sets.

Proof: We will prove by contradiction that there is no set of all sets. Assume for the sake of contradiction that there is a set of all sets, call it A. Given that A exists, we can use it to define another set P as

In words, P is the set of sets that do not contain themselves. Now either P is in P or it isn’t.

Case 1: P is in P, i.e., P contains itself, so P cannot be in P. This is a contradiction.

Case 2: P is not in P. Therefore P does not contain itelf, and so is in P. This is also a contradiction.

Since both cases lead to contradictions, P must not exist, which in turn implies that A cannot exist. We have thus shown by contradiction that there is no set of all sets. QED.

Another way to phrase the contradiction is P is in P iff P is not in P.

Corollary: there is no “set of everything,” since it would contain the set of all sets as a subset.

Key Points

Basic operations on sets and their names and definitions; the ability to make expressions from them.

The concepts of subset and power set.

Another example of proof by contradiction, more subtle than examples we’ve seen so far, and of a theorem that both touches on limits to mathematics (e.g., the apparently simple notion of “set” can’t encompass some intuitively reasonable sets) and on why we are doing certain things the way we do (e.g., why we have to explicitly specify universal sets).

Problem Set

See handout for details.

Next

Proofs about subset and equality relationships between sets.

Read section 5.2.

Next Lecture