Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

## Read the Online Textbook for the full content.

## Section 1.1 Set Notation and Relations

### Subsection 1.1.1 The notion of a set

Informal Definition: A set is a collection of objects that are called elements (of the set).

- For a set \(A\text{,}\) if \(x\) is an element of \(A\text{,}\) we will write \(x \in A\text{.}\).
- If \(x\) is not an element of \(A\text{,}\) we write \(x \notin A\text{.}\)
- The most convenient way of describing the elements of a set will vary depending on the specific set.

- Enumeration. set elements enumerated (or listed) between braces. E.g. the set of binary digits \(\{0, 1\}\); the set of decimal digits is \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\text{.}\)

- Names of sets should be meaningful to ease understanding. “logical” to call them \(B\) and \(D\text{,}\) respectively.
- Large sets may enumerated without listing all the elements: e.g. alphabet letter set is \(A = \{a, b, c,\ldots , x, y, z\}\text{,}\) "..." is called ellipsis. We use them when it is clear what elements are included but not listed.
- An ellipsis is used in two other situations:
  1. Enumerate positive integers: \(\{1, 2, 3,\ldots \}\text{,}\) indicating that the list goes on infinitely.
  2. Enumerate integers between 1 and \(n\text{,}\) where \(n\) is some undetermined positive integer, we might write \(\{1,\ldots ,n\}\text{.}\)

Standard Symbols. Sets frequently encountered have reserved names (identifiers)

- \(\mathbb{P}\text{:}\) the positive integers, \(\{1, 2, 3, 4, \ldots \}\)

- \(\mathbb{N}\text{:}\) the natural numbers, \(\{0, 1, 2, 3, \ldots \}\)

- \(\mathbb{Z}\text{:}\) the integers, \(\{\ldots , -3, -2, -1, 0, 1, 2, 3,\ldots \}\)

- \(\mathbb{Q}\text{:}\) the rational numbers

- \(\mathbb{R}\text{:}\) the real numbers

- \(\mathbb{C}\text{:}\) the complex numbers

Set-Builder Notation. For example, we could define the rational numbers as

\begin{equation*} \mathbb{Q}=\{a/b \mid a, b \in \mathbb{Z}, b\neq 0\}\text{.} \end{equation*}

Note that in the set-builder description for the rational numbers:

- \(a/b\) indicates that a typical element of the set is a “fraction.”

- The vertical line, \(\mid\text{,}\) is read “such that” or “where,” and is used interchangeably with a colon.

- \(a, b\in \mathbb{Z}\) is an abbreviated way of saying \(a\) and \(b\) are integers.

- Commas in mathematics are read as “and.”

For example, \(\{x\in \mathbb{R} \mid x^{2}-5x+6 =0\}\) and \(\{x \mid x \in \mathbb{R}, x^{2}-5x+6=0\}\) both describe the solution set \(\{2, 3\}\text{.}\)

For this course, the set of real numbers is the set of points on a number line. The set of complex numbers can be defined as \(\mathbb{C} = \{a + b i:a, b \in \mathbb{R}\}\text{,}\) where \(i^2 = -1\text{.}\)

In the following definition we will leave the word “finite” undefined.

#### Definition: Infinity

is a number greater than any assignable quantity or countable number (symbol ∞). .

#### Definition 1.1.1. Finite Set.

A set is a finite set if it has a finite number of elements. Any set that is not finite is an infinite set.

#### Definition 1.1.2. Cardinality.

Let \(A\) be a finite set. The number of different elements in \(A\) is called its cardinality. The cardinality of a finite set \(A\) is denoted \(\lvert A \rvert\text{.}\)

As we will see later, there are different infinite cardinalities. We can't make this distinction until Chapter 7, so we will restrict cardinality to finite sets for now.

### Subsection 1.1.2 Subsets

#### Definition 1.1.3. Subset.

Let \(A\) and \(B\) be sets. We say that \(A\) is a subset of \(B\) if and only if every element of \(A\) is an element of \(B\text{.}\) We write \(A \subseteq B\) to denote the fact that \(A\) is a subset of \(B\text{.}\)

#### Example 1.1.4. Some Subsets.

1. If \(A = \{3, 5, 8\}\) and \(B = \{5, 8, 3, 2, 6\}\text{,}\) then \(A\subseteq B\text{.}\)

2. \(\displaystyle \mathbb{N}\subseteq \mathbb{Z}\subseteq \mathbb{Q}\subseteq \mathbb{R}\subseteq \mathbb{C}\)

3. If \(S = \{3, 5, 8\}\) and \(T = \{5, 3, 8\}\text{,}\) then \(S \subseteq T\) and \(T \subseteq S\text{.}\)

#### Definition 1.1.5. Set Equality.

Let \(A\) and \(B\) be sets. We say that \(A\) is equal to \(B\) (notation \(A = B\)) if and only if every element of \(A\) is an element of \(B\) and conversely every element of \(B\) is an element of \(A\text{;}\) that is, \(A \subseteq B\) and \(B \subseteq A\text{.}\)

#### Example 1.1.6. Examples illustrating set equality.

1. In Example 1.1.4, \(S = T\text{.}\) Note that the ordering of the elements is unimportant.

2. The number of times that an element appears in an enumeration doesn't affect a set. For example, if \(A = \{1, 5, 3, 5\}\) and \(B = \{1, 5, 3\}\text{,}\) then \(A = B\text{.}\) Warning to readers of other texts: Some books introduce the concept of a multiset, in which the number of occurrences of an element matters.

Definitions:

- if and only if means “is equivalent to saying,” or more exactly, that the word (or concept) being defined can at any time be replaced by the defining expression. Conversely, the expression that defines the word (or concept) can be replaced by the word.

- The set that contains no elements is the empty set, \(\emptyset\), also called the null set.

- Given any set \(A\) \(A\subseteq A\) and \(\emptyset \subseteq A\text{.}\) If \(A\) is nonempty, then \(A\) is called an improper subset of \(A\text{.}\) All other subsets of \(A\text{,}\) including the empty set, are called proper subsets of \(A\text{.}\) The empty set is an improper subset of itself.

### Exercises 1.1.3 Exercises

#### 1.

List four elements of each of the following sets:

1. \(\displaystyle \{k \in \mathbb{P} \mid {k - 1} \textrm{ is a multiple of 7}\}\)

2. \(\displaystyle \{x \mid x \textrm{ is a fruit and its skin is normally eaten}\}\)

3. \(\displaystyle \{x \in \mathbb{Q}\mid \frac{1}{x} \in \mathbb{Z}\}\)

4. \(\displaystyle \{2n \mid n \in \mathbb{Z}, n < 0 \}\)

5. \(\displaystyle \{s \mid s = 1 + 2 + \cdots + n \textrm{ for some } n \in \mathbb{P}\}\)

Answer.

These answers are not unique.

1. \(\displaystyle 8, 15, 22, 29\)

2. \(\displaystyle \textrm{apple, pear, peach, plum}\)

3. \(\displaystyle 1/2, 1/3, 1/4, 1/5\)

4. \(\displaystyle -8, -6, -4, -2\)

5. \(\displaystyle 6, 10, 15, 21\)

#### 2.

List all elements of the following sets:

1. \(\displaystyle \{\frac{1}{n} \mid n \in \{3,4,5,6\}\}\)

2. \(\displaystyle \{\alpha \in \textrm{ the alphabet } \mid \alpha \textrm{ precedes F}\}\)

3. \(\displaystyle \{x \in \mathbb{Z} \mid x = x+1 \}\)

4. \(\displaystyle \{n^2 \mid n = -2, -1, 0, 1, 2\}\)

5. \(\displaystyle \{n \in \mathbb{P} \mid n \textrm{ is a factor of 24 }\}\)

#### 3.

Describe the following sets using set-builder notation.

1. \(\displaystyle \{ 5, 7, 9, \dots , 77, 79\}\)

2. the rational numbers that are strictly between \(-1\) and \(1\)

3. the even integers

4. \(\displaystyle \{-18, -9,0,9, 18,27, \dots \}\)

Answer.

1. \(\displaystyle \{2k + 1 \mid k \in \mathbb{Z}, 2 \leqslant k \leqslant 39\}\)

2. \(\displaystyle \{x \in \mathbb{Q}\mid -1 < x < 1\}\)

3. \(\displaystyle \{2n\mid n \in \mathbb{Z}\}\)

4. \(\displaystyle \{9n\mid n \in \mathbb{Z}, -2 \leq n\}\)

#### 4.

Use set-builder notation to describe the following sets:

1. \(\displaystyle \{1, 2, 3, 4, 5, 6, 7\}\)

2. \(\displaystyle \{1, 10, 100, 1000, 10000\}\)

3. \(\displaystyle \{1, 1/2, 1/3, 1/4, 1/5, . . .\}\)

4. \(\displaystyle \{0\}\)

#### 5.

Let \(A = \{0, 2, 3\}\text{,}\) \(B = \{2, 3\}\text{,}\) and \(C = \{1, 5, 9\}\text{.}\) Determine which of the following statements are true. Give reasons for your answers.

1. \(\displaystyle 3 \in A\)

2. \(\displaystyle \{3\} \in A\)

3. \(\displaystyle \{3\} \subseteq A\)

4. \(\displaystyle B\subseteq A\)

5. \(\displaystyle A\subseteq B\)

6. \(\displaystyle \emptyset \subseteq C\)

7. \(\displaystyle \emptyset \in A\)

8. \(\displaystyle A\subseteq A\)

Answer.

1. True

2. False

3. True

4. True

5. False

6. True

7. False

8. True