Introduction to Set Theory

Learning Outcomes

  • Describe memberships of sets, including the empty set, using proper notation, and decide whether given items are members and determine the cardinality of a given set.
  • Describe the relations between sets regarding membership, equality, subset, and proper subset, using proper notation.
  • Perform the operations of union, intersection, complement, and difference on sets using proper notation.
  • Be able to draw and interpret Venn diagrams of set relations and operations and use Venn diagrams to solve problems.
  • Recognize when set theory is applicable to real-life situations, solve real-life problems, and communicate real-life problems and solutions to others.

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

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

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.

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

A proper subset is a subset that is not identical to the original set—it excludes at least one element of the original set.

If B is a proper subset of A, we write B ⊂ 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.

It is also true that B ⊂ C.

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

Try It

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}

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, 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 subsets.

Try It