Set Theory

Learning Outcomes

• Describe memberships of sets and relationships between sets, including the empty set, subsets, and proper subset, while using correct set notation.

An art collector might own a collection of paintings, while a music lover might keep a collection of CDs. Any collection of items can form a set.

recall sets of real numbers

Recall the sets of real numbers you studied previously. Each number contained in a set is an element of the set that contains it. For example, the number $1$ is an element of the set of counting numbers. The number $\dfrac{2}{3}$ is an element of the set of rational numbers. And so on. The same idea applies to any set of distinct objects, as described below.

Set

A set is a collection of distinct objects, called elements of the set

A set can be defined by describing the contents, or by listing the elements of the set, enclosed in curly brackets.

Example

Some examples of sets defined by describing the contents:

1. The set of all even numbers
2. The set of all books written about travel to Chile

Some examples of sets defined by listing the elements of the set:

1. {1, 3, 9, 12}
2. {red, orange, yellow, green, blue, indigo, purple}

Notation

Commonly, we will use a variable to represent a set, to make it easier to refer to that set later.

The symbol ∈ means “is an element of”.

A set that contains no elements, { }, is called the empty set and is notated ∅

Example

Let A = {1, 2, 3, 4}

To notate that 2 is element of the set, we’d write 2 ∈ A

Key Takeaways

A set simply specifies the contents; order is not important. The set represented by {1, 2, 3} is equivalent to the set {3, 1, 2}.

Subsets

Sometimes a collection might not contain all the elements of a set. For example, Chris owns three Madonna albums. While Chris’s collection is a set, we can also say it is a subset of the larger set of all Madonna albums.

Subsets of real numbers

The idea of subsets can also be applied to the sets of real numbers you studied previously. For example, the set of all whole numbers is a subset of the set of all integers. The set of integers in turn is contained within the set of rational numbers.

We say the integers are a subset of the rational numbers. You’ll see below in fact that the integers are a proper subset of the rational numbers.

Subset

A subset of a set A is another set that contains only elements from the set A, but may not contain all the elements of A.

If B is a subset of A, we write BA

A proper subset is a subset that is not identical to the original set—it contains fewer elements.

If B is a proper subset of A, we write BA

Example

Consider these three sets:

A = the set of all even numbers
B = {2, 4, 6}
C = {2, 3, 4, 6}

Here BA since every element of B is also an even number, so is an element of A.

More formally, we could say BA since if x ∈ B, then x A.

It is also true that BC.

C is not a subset of A, since C contains an element, 3, that is not contained in A

Example

Suppose a set contains the plays “Much Ado About Nothing,” “MacBeth,” and “A Midsummer’s Night Dream.” What is a larger set this might be a subset of?

Try It

Consider the set $A = \{1, 3, 5\}$. Which of the following sets is $A$ a subset of?
$X = \{1, 3, 7, 5\}$
$Y = \{1, 3 \}$
$Z = \{1, m, n, 3, 5\}$

Exercises

Given the set: A = {a, b, c, d}. List all of the subsets of A

Listing the sets is fine if you have only a few elements. However, if we were to list all of the subsets of a set containing many elements, it would be quite tedious. Instead, in the next example we will consider each element of the set separately.

Example

In the previous example, there are four elements. For the first element, a, either it’s in the set or it’s not. Thus there are 2 choices for that first element. Similarly, there are two choices for b—either it’s in the set or it’s not. Using just those two elements, list all the possible subsets of the set {a,b}

Recall exponential notation

Recall that the expression $a^{m}$ states that some real number $a$ is to be used as a factor $m$ times.
Ex. $2^{5} = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 32$

Now let’s include c, just for fun. List all the possible subsets of the new set {a,b,c}.
Again, either c is included or it isn’t, which gives us two choices. The outcomes are {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}. Note that there are $2^{3}=8$ subsets.

If you include four elements, there would be $2^{4}=16$ subsets. 15 of those subsets are proper, 1 subset, namely {a,b,c,d}, is not.

In general, if you have n elements in your set, then there are $2^{n}$ subsets and $2^{n}−1$ proper subsets.