1  Sets

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

  1. List all the items in the set. The items should be separated by a comma and the list should 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, we denote the set of all positive integers by \(\{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

We sometimes use ellipses ‘\(\ldots\)’ when the common property of the elements of a set can be inferred. For instance, the following are equivalent ways to denote the set consisting of the first 10 positive integers:

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

There are two ways that we can talk about what is contained in a set.

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

Definition 1.2 (Subset) Suppose that \(A\) and \(B\) are both sets. We say that:

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

The following examples illustrate the above definitions:

It is important to remember that 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\)” since \(1\) is not a set.

Warning

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\)” 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)|\)?

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

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