1  Background: Sets

In this chapter, we introduce the notation and terminology about sets that will be used this semester. There are two common ways to write down a set:

1. Listing All Items in the Set: To list all the items, separate them with commas and enclose the list in curly brackets: ‘\(\{\)’ and ‘\(\}\)’. For example:

   • \(\{a, b, c, e\}\) represents the set consisting of the first five letters of the alphabet.
   • \(\{1, 3, 5\}\) represents the set consisting of the first three odd numbers.

2. Defining a Property of the Set: Instead of listing every item, you can define a property that all items in the set have in common. This method is useful when listing all the elements is too long or impossible. For example:

   • The set of all positive integers can be written as \({x \mid x \text{ is an integer and } x \geq 0}\). This is read as “the set of all \(x\) such that \(x\) is an integer and \(x\) is greater than or equal to zero.”

Note

Sometimes, when the pattern of a set is clear, we use ellipses (‘\(\ldots\)’) to represent the continuation of the pattern. For example, the following are different but equivalent ways to write the set of the first ten positive integers:

• \(\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\)
• \(\{1, 2, \ldots, 10\}\)
• \(\{x \mid x \text{ is an integer and } 1 \leq x \leq 10\}\)

There are two common ways to discuss what is contained in a set:

Definition 1.1 (Element) Suppose that \(A\) is a set. We write \(x \in A\) when \(x\) is an element of \(A\), and we write \(x \notin A\) when \(x\) is not an element of \(A\).

Definition 1.2 (Subset) Suppose that \(A\) and \(B\) are both sets. We can describe the relationship between \(A\) and \(B\) in the following ways:

• \(A\) is a subset of \(B\), denoted \(A \subseteq B\), if for all \(x\), if \(x \in A\), then \(x \in B\).
• \(A\) is not a subset of \(B\), denoted \(A \not\subseteq B\), if there is some \(x \in A\) such that \(x \notin B\).
• \(A\) is a proper subset of \(B\), denoted \(A \subsetneq B\), if \(A \subseteq B\) and there is some \(x \in B\) such that \(x \notin A\).

Here are some examples to illustrate these definitions:

• \(0 \in \{0, 1, 3\}\)
• \(2 \notin \{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\}\)

Important Note: The notation “\(A \subseteq B\)” should only be used when \(A\) and \(B\) are both sets. For example, if \(X = \{1, 2, 3\}\), then it is incorrect to write “\(1 \subseteq X\)” because \(1\) is not a set.

Warning

We often use the phrase “…is contained in” when talking about both elements and subsets. For example, if \(A = \{1, 2, 3\}\), it is common to say that “\(A\) contains \(1\)” or “\(1\) is contained in \(A\).” However, it can be confusing for beginners that we also say “the set \(\{1, 2\}\) is contained in \(A\),” since each element in \(\{1, 2\}\) is contained in \(A\).

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

Definition 1.3 (Empty Set) 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: that is, 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, there is no element that is contained in \(\varnothing\) but not in \(X\).

Note that it is possible for a set to contain an element that is itself a set. That is, a set can contain other sets as members. For instance, the set \(X=\{a, \{b, c\}\}\) contains two elements: \(a\in X\) and \(\{b,c\}\in X\); on the other hand, the set \(Y=\{a, b, c\}\) contains three elements: \(a\in Y\), \(b\in Y\) and \(c\in Y\).

Given a set \(A\), we will often be interested in the set of all subsets of \(A\):

Definition 1.4 (Powerset) The power set of a set \(A\) is the set of all subsets of \(A\). If \(A\) is a set, then the power set of \(A\) is the set \(\wp(A)=\{B\ |\ B\subseteq A\}\).

Note that \(\varnothing\in\wp(A)\) for any set \(A\). To illustrate the power set operation, suppose that \(A=\{1, 2, 3\}\). Then the power set of \(A\) is:

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

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

Definition 1.5 (Cardinality) : The cardinality of a finite set \(A\), denoted \(|A|\), is the number of elements in \(A\).

Note

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.

1.1 Notation

The following sets will be discussed this semester.

Notation	Set
\(\mathbb{N}\)	The set of all non-negative integers \(\{0, 1, 2, \ldots\}\)
\(\mathbb{Z}\)	The set of all integers \(\{\ldots, -2, -1, 0, 1, 2, \ldots\}\)
\(\mathbb{R}\)	The set of all real numbers
\([0,1]\)	The set of all real numbers between (and including) \(0\) and \(1\): \([0,1]=\{x\mid x\in \mathbb{R}, 0\le x\le 1\}\)
\((0,1)\)	The set of all real numbers strictly between \(0\) and \(1\): \((0,1)=\{x\mid x\in \mathbb{R}, 0 < x < 1\}\)
\(\mathbb{Q}\)	The set of all rational numbers \(\{x\mid x=\frac{a}{b}\), where \(a, b\) are integers\(\}\)

1.2 Exercises

1. Suppose that \(X=\{a\}\) and \(Y=\{a, c\}\).

   1. True or False: \(\varnothing\in X\)
   2. True or False: \(\varnothing \subseteq X\)
   3. True or False: \(X\subseteq \varnothing\)
   4. True or False: \(a\in\varnothing\)
   5. True or False: \(a\in X\)
   6. True or False: \(a\subseteq X\).
   7. True or False: \(\{a, b\} \subseteq Y\).
   8. True or False: \(a \in \{X, Y\}\).
   9. True or False: \(\{a\}\subseteq \{X, Y\}\).
   10. True or False: \(\{a\}\in \{X, Y\}\).

2. Answer the following:

   1. True or False: \(\varnothing \subseteq\varnothing\)
   2. True or False: \(\mathbb{Z}\subseteq\mathbb{N}\)
   3. True or False: \((0, 1)\subseteq \mathbb{Q}\)
   4. True or False: \([0, 1]\subseteq (0, 1)\)
   5. True or False: \((0, 1)\subseteq [0, 1]\)

3. 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\).

4. Find the following sets: \(\wp(\varnothing)\), \(\wp(\{a\})\), and \(\wp(\{a, \{a\}\})\).

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

   1. True or False: For all sets \(A\) and \(B\), if \(A\subseteq B\), then \(|A|\le |B|\).
      
   2. True or False: For all sets \(A\) and \(B\), if \(|A|\le |B|\), then \(A\subseteq B\).

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

7. Suppose that \(|A| = n\). What is \(|\wp(A)|\)?

Solutions

1. Suppose that \(X=\{a\}\) and \(Y=\{a, c\}\).

   1. False: \(\varnothing\in X\)

      The single element of \(X\) is \(a\), not \(\varnothing\).

   2. True: \(\varnothing \subseteq X\)

      The empty set is a subset of any set. Since there is no element of \(\varnothing\), there is no element of \(\varnothing\) that is not an element of \(X\).

   3. False: \(X\subseteq \varnothing\)

      \(a\in X\) but \(a\notin \varnothing\).

   4. False: \(a\in\varnothing\)

      The emptyset \(\varnothing\) does not contain any elements.

   5. True: \(a\in X\)

      \(a\in X=\{a\}\)

   6. False: \(a\subseteq X\).

      \(a\) does not contain any elements so cannot be a subset of \(X\).

   7. False: \(\{a, b\} \subseteq Y\).

      \(b\in \{a, b\}\). but \(b\notin Y=\{a, c\}\).

   8. False: \(a \in \{X, Y\}\).

      \(a\) is not an element of the set \(\{X, Y\} = \{\{a\}, \{a, c\}\}\).

   9. False: \(\{a\}\subseteq \{X, Y\}\).

      \(a\in\{a\}\), but \(a\) is not an element of the set \(\{X, Y\} = \{\{a\}, \{a, c\}\}\).

   10. True: \(\{a\}\in \{X, Y\}\).

       \(\{a\}\) is an element of the set \(\{X, Y\} = \{\{a\}, \{a, c\}\}\).

2. Answer the following:

   1. True or False: \(\varnothing \subseteq\varnothing\)

      True: Since there is no element of \(\varnothing\), there is no element of \(\varnothing\) that is not an element of \(\varnothing\).

   2. True or False: \(\mathbb{Z}\subseteq\mathbb{N}\)

      False: \(-1\in \mathbb{Z}\), but \(-1\notin\mathbb{N}\).

   3. True or False: \((0, 1)\subseteq \mathbb{Q}\)

      False: \(\sqrt{2}/2 \in (0, 1)\), but \(\sqrt{2}/2\notin\mathbb{Q}\) (since \(\sqrt{2}\) is an irrational number, \(\sqrt{2}/2\) cannot be written as \(a/b\) where \(a\) and \(b\) are integers).

   4. True or False: \([0, 1]\subseteq (0, 1)\)

      False: \(0\in [0, 1]\), but \(0\notin (0, 1)\).

   5. True or False: \((0, 1)\subseteq [0, 1]\)

      True: Every real number strictly between \(0\) and \(1\) is an element of \([0, 1]\).
      

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

   1. True or False: \(\varnothing\in A\).

      \(\varnothing\in A\) is true: The emptyset is the single element contained in \(A\).

   2. True or False: \(\varnothing\in B\).

      \(\varnothing\in B\) is false: Note that \(B=\{\{\varnothing\}\}\), so \(B\) contains the set containing the emptyset, but does not contain \(\varnothing\).

   3. True or False: \(A\subseteq B\).

      \(A\subseteq B\) is false: Since \(\varnothing\not\in B\), we have \(A\not\subseteq B\).

   4. True or False: \(\varnothing\subseteq B\).

      \(\varnothing\subseteq B\) is true: The emptyset is a subset of every set.

   5. True or False: \(\varnothing\in B\).

      \(\varnothing\in B\) is false: The single element of \(B\) is \(\{\varnothing\}\) which is not the empty set.
      

   6. True or False: \(B\in C\).

      \(B\in C\) is true: \(C=\{\{\{\varnothing\}\}, \varnothing\}\) and \(B=\{\{\varnothing\}\}\).

   7. True or False: \(A\in C\).

      \(A\in C\) is false: \(C=\{\{\{\varnothing\}\}, \varnothing\}\) and \(\{\varnothing\}\not\in \{\{\{\varnothing\}\}, \varnothing\}\).

4. Find the following sets: \(\wp(\varnothing)\), \(\wp(\{a\})\), and \(\wp(\{a, \{a\}\})\).

   • \(\wp(\varnothing) = \{\varnothing\}\)
   • \(\wp(\{a\}) = \{\varnothing, \{a\}\}\)
   • \(\wp(\{a, \{a\}\}) = \{\varnothing, \{a\}, \{\{a\}\}, \{a, \{a\}\}\)

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

   1. True or False: For all sets \(A\) and \(B\), if \(A\subseteq B\), then \(|A|\le |B|\).

      True: Suppose that \(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\), i.e., \(|A|\leq |B|\).

   2. True or False: For all sets \(A\) and \(B\), if \(|A|\le |B|\), then \(A\subseteq B\).

      False: Let \(A=\{1\}\) and \(B=\{2, 3\}\). Then \(|A|=1\le |B|=2\), but \(A\not\subseteq B\).

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

   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\).

7. Suppose that \(|A| = n\). What is \(|\wp(A)|\)?

   If \(|A|=n\), then \(|\wp(A)|=2^n\). For example, if \(|A|=3\), then the powerset of \(A\) has \(2^3=8\) elements. To illustrate this, suppose that \(A=\{a, b, c\}\). Then \(|A|=3\) and \[|\wp(A)|=|\{\varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}|=8\]