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.

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 braces (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

Capital letters are generally used to represent sets, 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 an element of the set, we’d write 2 ∈ A

A set simply specifies the contents; order is not important. The set represented by {1, 2, 3} is equal to the set {3, 1, 2}.  Also, only distinct elements are recognized so {1, 2, 2, 2, 3} is equal to the set {1, 2, 3}.

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.

Subset

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

If B is a subset of A, we write B ⊆ A

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 B ⊂ A

A set is always a subset of itself.  We can write A ⊆ A.  However, A is not a proper subset of itself.

Finally, the empty set is a subset of every set.  For example, ∅ ⊆ A.

Example

Consider these three sets:

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

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

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

Additionally, it is true that B ⊂ A since if x ∈ B, then x ∈ A and B has fewer elements than A.

It is also true that B ⊆ C and B ⊂ C.

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 [latex]A = \{1, 3, 5\}[/latex]. Which of the following sets is [latex]A[/latex] a subset of?
[latex]X = \{1, 3, 7, 5\}[/latex]
[latex]Y = \{1, 3 \}[/latex]
[latex]Z = \{1, m, n, 3, 5\}[/latex]

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 [latex]a^{m}[/latex] states that some real number [latex]a[/latex] is to be used as a factor [latex]m[/latex] times.
Ex. [latex]2^{5} = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 32[/latex]

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 [latex]2^{3}=8[/latex] subsets.

If you include four elements, there would be [latex]2^{4}=16[/latex] subsets. 15 of those subsets are proper (or distinct), 1 subset, namely {a,b,c,d}, is not.

In general, if you have n elements in your set, then there are [latex]2^{n}[/latex] subsets and [latex]2^{n}−1[/latex] proper (or distinct) subsets.

Try It