Skip to content

Set Theory

Set theory is a mathematical language to reason about collections of objects, called sets. In this tutorial, we introduce the notation and terminology that will be used this semester to reason about sets. There are two ways to denote a set:

  1. List all the items in the set. The items should be separated by a comma and the list shouuld be written between curly brackets: '\(\}\)' and '\(\{\)'. For example, \(\{a,b,c,e\}\) is the set consisting of the first 5 letters of the alphabet, and \(\{1, 3, 5\}\) is the set consisting of the first 3 odd numbers.
  2. Define a property that all items in the set have in common. This is useful when listing all the elements of the set is too cumbersome or impossible. For example, the set of all positive integers is \(\{x\ |\ x \text{ is an integer} \text{ and } x\geq 0 \}\). This is read "the set of all \(x\) such that \(x\) is an integer and \(x\) is greater than or equal to zero".

Note

In these notes, sets are denoted with uppercase letters. However, there is no standard notation for sets. For instance, some texts may use lowercase letters to denote sets.

There are two ways that we can talk about the items that are contained in a set.

Element

Suppose that \(A\) is a set. We write \(x\in A\) when \(x\) is an element of \(A\) and \(x\not\in A\) when \(x\) is not an element of \(A\).

Subset

Suppose that \(A\) and \(B\) are both sets. We say \(A\) is a subset of a set \(B\), denoted \(A\subseteq B\), provided that for all \(x\), if \(x\in A\), then \(x\in B\). We write \(A\not\subseteq B\) when \(A\) is not a subset of \(B\), and \(A\subsetneq B\) when \(A\) is a proper subset of \(B\): \(A\subseteq B\) and there is some \(x\) such that \(x\in B\) and \(x\not\in A\).

Example

  • \(0\in \{0, 1, 3\}\)
  • \(2\not\in \{0, 1, 3\}\)
  • \(\{0, 1, 3\}\subseteq \{0, 1, 2, 3, 4\}\)
  • \(\{0, 1, 3\}\not\subseteq \{0, 2, 4\}\)
  • \(\{0, 1, 3\}\subseteq \{0, 1, 3\}\)
  • \(\{0, 1\}\subsetneq \{0, 1, 3\}\)

It will be useful to introduce notation for a set containing no elements.

Emptyset

The set that contains no elements is called the emptyset, or null set. We write \(\varnothing\) to denote the emptyset.

A key fact about the empty set is that it is a subset of any set: for all sets \(X\), \(\varnothing\subseteq X\). The reason why \(\varnothing \subseteq X\) for any set \(X\) is that since \(\varnothing\) does not contain any elements, so there is no element that is contained in \(\varnothing\) but not in \(X\).

Note that it is possible for a set to contain other sets as elements. For instance, the set \(X=\{a, b, c\}\) has three elements: \(a\in X\), \(b\in X\) and \(c\in X\), but \(Y=\{a, \{b, c\}\}\) has two elements: \(a\in Y\) and \(\{b,c\}\in Y\).

Can a set contain an element that is also a subset?

Yes. Let \(Z=\{a, \{a\}\}\). Then, \(\{a\}\in Z\) and \(\{a\}\subseteq Z\) (since \(a\in Z\)). So, \(\{a\}\) is both an element of \(Z\) and a subset of \(Z\).

Caution

We use the phrase "...is contained in" when talking about both elements and subsets. If \(A=\{1,2,3\}\), then it is common to say that "\(A\) contains \(1\)" or "\(1\) is contained in \(A\)". Something that can be confusing for beginners is that it is also common to say that "the set \(\{1,2\}\) is contained in \(A\)".

Given a set \(A\), the powerset of \(A\) is the set containing all the subsets of \(A\):

Powerset

Suppose that \(A\) is a set. The powerset of \(A\) is the set \(\wp(A)=\{B\ |\ B\subseteq A\}.\)

Note that for any set \(A\), \(\varnothing\in\wp(A)\).

Example

Suppose that \(A=\{1, 2, 3\}\). The powerset of \(A\) is:

\[ \wp(A)=\{\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}. \]

Operations on Sets

There are two basic operations that combine a set \(A\) and a set \(B\) to form another set:

  • The union of \(A\) and \(B\), denoted \(A\cup B\), is the set of all elements in either \(A\) or \(B\).
  • The intersection of \(A\) and \(B\), denoted \(A\cap B\), is the set of all elements in both \(A\) and \(B\).

Union

Suppose that \(A\) and \(B\) are two sets. The union of \(A\) and \(B\), denoted \(A\cup B\), is the set \(A\cup B=\{x\ |\ x\in A\text{ or } x\in B\}.\) More generally, if \(\mathcal{S}\) is any collection of sets, then

\[ \bigcup \mathcal{S} = \{x\ |\ x\in A \mbox{ for some } A\in\mathcal{S}\}. \]

Intersection

Suppose that \(A\) and \(B\) are two sets. The intersection of \(A\) and \(B\), denoted \(A\cap B\), is the set \(A\cap B=\{x\ |\ x\in A\text{ and } x\in B\}.\) More generally, if \(\mathcal{S}\) is any collection of sets, then

\[ \bigcap \mathcal{S} = \{x\ |\ x\in A \text{ for all $A\in\mathcal{S}$}\}. \]

Example of union and intersection

  • If \(A=\{1,2,3\}\) and \(B=\{a,b\}\), then \(A\cup B=\{1,2,3,a,b\}\).
  • If \(A=\{1,2,3\}\) and \(B=\{1,3,4\}\), then \(A\cup B=\{ 1, 2, 3, 4\}\).
  • If \(A=\{1,2, 3\}\) and \(B=\{\{1,3\}, 4\}\), then \(A\cup B=\{ 1, 2, 3, \{1,3\}, 4\}\).
  • If \(A=\{1,2\}\), \(B=\{2,3\}\) and \(C=\{1,2, 4\}\), then \(A\cup (B\cup C) = \{1, 2, 3, 4\}\)
  • If \(A=\{1,2,3\}\) and \(B=\{1\}\), then \(A\cap B=\{1\}\).
  • If \(A=\{1,2, 3\}\) and \(B=\{\{1,3\}, 2\}\), then \(A\cap B=\{ 2\}\).
  • If \(A=\{1, 2\}\) and \(B=\{3, 4\}\), then \(A\cap B=\varnothing\) (i.e., there are no elements in \(A\cap B\)).
  • If \(A=\{1,2\}\), \(B=\{2,3\}\) and \(C=\{1,2, 4\}\), then \(A\cap (B\cap C) = \{2\}\)

The next operations on sets are:

  • The complement of \(A\), denoted \(\overline{A}\) or \(A^C\), is the set of all elements not contained in \(A\).d
  • The difference of \(A\) minus \(B\), denoted \(A\setminus B\), is the set of all the elements in \(A\) but not in \(B\).
  • The symmetric difference of \(A\) and \(B\), denoted \(A\mathop{\Delta}B\), is the set of all elements in either \(A\) or \(B\), but not in both.

To define the complement of a set, it is assumed that there is a universal set, also called the domain of discourse, so that a set is a collection of objects from the universal set.

Set Difference

Suppose that \(A\) and \(B\) are sets. The difference between \(A\) and \(B\) (\(A\) minus \(B\)), denoted \(A\setminus B\), is:

\[ A\setminus B=\{x\ |\ x\in A\text{ and } x\not\in B\}. \]

Complement

Suppose that \(A\) is a set. The complement of \(A\), denoted \(\overline{A}\) or \(A^C\), is:

\[ \overline{A}=\{x\ |\ x\text{ is in the universal set and } x\not\in A\}. \]

Symmetric Difference

Suppose that \(A\) and \(B\) are sets. The symmetric difference of \(A\) and \(B\), denoted \(A\mathrel{\Delta} B\), is:

\[ A\mathrel{\Delta} B=(A-B)\cup (B-A). \]

Example of set difference, symmetric difference and complement

The following examples illustrates the operations of set difference and complement:

  • If \(A=\{1,2, 3\}\) and \(B=\{1, 2, 4\}\), then \(A - B=\{ 3\}\) and \(B-A=\{4\}\).
  • If \(A=\{1,2,3\}\) and \(B=\{1\}\), then \(A - B=\{2, 3\}\) and \(B-A\) is the empty set.
  • If the universal set is \(\{0,1, 2, 3, 4, 5, 6, 7, 8, 9\}\) and \(A=\{1, 2, 3\}\), then \(A^C=\{0, 4, 5, 6, 7, 8, 9\}\).
  • The symmetric difference of \(A=\{1,2, 3\}\) and \(B=\{1, 2, 4\}\) is \(\{ 3, 4\}\).
  • The symmetric difference \(A=\{1,2,3\}\) and \(B=\{1\}\) is \(\{2, 3\}\).

Finally, it will be useful to introduce notation to represent the number of elements in a set.

Cardinality

The cardinality of a finite set \(A\), denoted \(|A|\), is the total number of elements in \(A\).

The notion of cardinality can be applied to infinite sets as well. However, a discussion of this is beyond the scope of these introductory notes.

Additional Reading

Exercises

  1. What is \(\wp(\emptyset)\)?

    Show Answer

    \(\wp(\emptyset) = \{\emptyset\}\).

  2. Suppose that \(A=\{1, 2, 3\}\), \(B=\{2, 3, 4\}\) and \(C=\{1, 2, 4, 6\}\). Find the following sets:

    1. \((A\cap B)\cup C\)
    2. \((A\cup B)\setminus (A\cup C)\)
    3. \((A\cup B)\Delta (A\cup C)\)
    4. \((A\cup B)\setminus (A\cap B)\)
    5. \(A\cap (B\cup C)\)
    Show Answer
    1. \((A\cap B)\cup C=\{2, 3\} \cup \{1, 2, 4, 6\} = \{1, 2, 3, 4, 6\}\)
    2. \((A\cup B)\setminus (A\cup C) = \{1, 2, 3, 4\}\setminus \{ 1, 2, 3, 4, 6\} = \varnothing\)
    3. \((A\cup C)\setminus (A\cup B) = \{ 1, 2, 3, 4, 6\}\setminus \{1, 2, 3, 4\} = \{6\}\)
    4. \((A\cup B)\Delta (A\cup C) = \varnothing\cup \{6\}=\{6\}\)
    5. \((A\cup B)\setminus (A\cap B) = \{1, 2, 3, 4\}\setminus \{2, 3\}=\{1, 4\}\)
    6. \(A\cap (B\cup C) = \{1, 2, 3\} \cap \{1,2, 3,4, 6\}=\{1,2,3\}\)

  3. Suppose that \(A=\{1\}\) and \(B=\{1, 3\}\).

    1. True or False: \(1\subseteq A\).
    2. True or False: \(1\in A\cap B\).
    3. True or False: \(1 \in \{A,B\}\).
    4. True or False: \(\{2\}\in A\cap B\).
    5. True or False: \(\{2\}\subseteq A\cap B\).
    Show Answer
    1. \(1\subseteq A\) is False: \(1\) is an element of \(A\), but not a subset of \(A\).
    2. \(1\in A\cap B\) is True: \(A\cap B=\{1\}\), so \(1\in\{1\} = A\cap B\).
    3. \(1 \in \{A,B\}\) is False: \(\{A,B\}=\{\{1\}, \{2,3\}\}\), and \(1\not\in \{\{1\}, \{2,3\}\}\). (Note that we do have that \(\{1\}\in\{A,B\}\) and of course \(1\in\{1\}\).)
    4. \(\{2\}\in A\cap B\) is False: \(A\cap B=\{1\}\) which does not contain \(2\).
    5. \(\{2\}\subseteq A\cap B\) is False: Since \(2\not\in \{1\}=A\cap B=\), we have that \(\{2\}\not\subseteq A\cap B\).

  4. Consider the sets \(A=\{\varnothing\}\), \(B=\{A\}\) and \(C=\{B, \varnothing\}\).

    1. True or False: \(\varnothing\in A\).
    2. True or False: \(\varnothing\in B\).
    3. True or False: \(A\subseteq B\).
    4. True or False: \(\varnothing\subseteq B\).
    5. True or False: \(\varnothing\in B\).
    6. True or False: \(B\in C\).
    7. True or False: \(A\in C\).
    Show Answer
    1. \(\varnothing\in A\) is true: The emptyset is the single element contained in \(A\).
    2. \(\varnothing\in B\) is false: Note that \(B=\{\{\varnothing\}\}\), so \(B\) contains the set containing the emptyset, but does not contain \(\varnothing\).
    3. \(A\subseteq B\) is false: Since \(\varnothing\not\in B\), we have \(A\not\subseteq B\).
    4. \(\varnothing\subseteq B\) is true: The emptyset is a subset of every set.
    5. \(\varnothing\in B\) is false: The single element of \(B\) is \(\{\varnothing\}\) which is not the empty set.
    6. \(B\in C\) is true: \(C=\{\{\{\varnothing\}\}, \varnothing\}\) and \(B=\{\{\varnothing\}\}\).
    7. \(A\in C\) is false: \(C=\{\{\{\varnothing\}\}, \varnothing\}\) and \(\{\varnothing\}\not\in \{\{\{\varnothing\}\}, \varnothing\}\).

  5. Suppose that \(A\) and \(B\) are sets and that \(A\subseteq B\). What else can you conclude about the sets \(A\) and \(B\)?

    1. \(A\cap B=A\)
    2. \(A\cap B=B\)
    3. \(A\cup B=A\)
    4. \(A\cup B=B\)
    Show Answer

    For all sets \(A\) and \(B\), the following are true:

    1. If \(A\subseteq B\), then \(A\cap B=A\)
    2. If \(A\subseteq B\), then \(A\cup B=B\)

  6. Suppose that \(A\) is a set. Select all of the following that are true.

    1. \(A\Delta A = A\)
    2. \(A\Delta A = \varnothing\)
    3. \(A\Delta \varnothing = A\)
    4. \(A\Delta \varnothing = \varnothing\)
    Show Answer
    1. \(A\Delta A = A\) is false. Let \(A=\{1\}\), then \(A\setminus A = \varnothing\), so \(A\Delta A=\varnothing\cup \varnothing = \varnothing\)
    2. \(A\Delta A = \varnothing\) is true. For any set \(A\), \(A\setminus A=\varnothing\).
    3. \(A\Delta \varnothing = A\) is true. For any set \(A\), \(A\setminus \varnothing = A\) and \(\varnothing \setminus A=\varnothing\); so \(A\Delta\varnothing = A\)
    4. \(A\Delta \varnothing = \varnothing\) is false. Let \(A=\{1\}\), then \(A\Delta \varnothing = \{1\}\ne\varnothing\).

  7. Suppose that \(A\) and \(B\) are sets.

    1. True or False: If \(A\subseteq B\), then \(|A|\le |B|\).
    2. True or False: If \(|A|\le |B|\), then \(A\subseteq B\).
    3. True or False: \(|A\cup B| = |A| + |B|\).
    Show Answer
    1. True: If \(A\subseteq B\), then \(|A|\le |B|\). If \(A\subseteq B\), then every element of \(A\) is an element of \(B\). Clearly this means that \(B\) has at least as many elements as \(A\).
    2. False: If \(|A|\le |B|\), then \(A\subseteq B\). Let \(A=\{1\}\) and \(B=\{2, 3\}\). Then \(|A|=1\le |B|=2\), but \(A\not\subseteq B\).
    3. False: \(|A\cup B| = |A| + |B|\). Let \(A=\{1, 2\}\) and \(B=\{2, 3\}\). Then \(|A\cup B|=|\{1, 2, 3\}|=3\ne |\{1, 2\}| + \{2, 3\}| = 2 + 2 = 4\)

  8. If \(|A| = n\), then what is \(|\wp(A)|\)?

    Show Answer

    If \(|A|=n\), then \(|\wp(A)|=2^n\). So for example, if \(|A|=3\), then the powerset has \(2^3=8\) elements. We will prove this later in the semester.


https://umd.instructure.com/courses/1301043/assignments/5494663