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

The term set is intuitively understood by most people to mean a collection of objects that are called elements (of the set). This concept is the starting point on which we will build more complex ideas, much as in geometry where the concepts of point and line are left undefined. Because a set is such a simple notion, you may be surprised to learn that it is one of the most difficult concepts for mathematicians to define to their own liking. For example, the description above is not a proper definition because it requires the definition of a collection. (How would you define “collection”?) Even deeper problems arise when you consider the possibility that a set could contain itself. Although these problems are of real concern to some mathematicians, they will not be of any concern to us. Our first concern will be how to describe a set; that is, how do we most conveniently describe a set and the elements that are in it? If we are going to discuss a set for any length of time, we usually give it a name in the form of a capital letter (or occasionally some other symbol). In discussing set \(A\text{,}\) if \(x\) is an element of \(A\text{,}\) then we will write \(x \in A\text{.}\) On the other hand, 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.

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

Caution: Some people (roughly half of the world?) call the set \(\{1, 2, 3, 4, \ldots \}\) the natural numbers. We are not among them. We take the *pythonic* approach that assumes that starting with zero is more natural than starting at one.

Set-Builder Notation. Another way of describing sets is to use 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.”

The important fact to keep in mind in set notation, or in any mathematical notation, is that it is meant to be a help, not a hindrance. We hope that notation will assist us in a more complete understanding of the collection of objects under consideration and will enable us to describe it in a concise manner. However, brevity of notation is not the aim of sets. If you prefer to write \(a\in \mathbb{Z}\) and \(b\in \mathbb{Z}\) instead of \(a, b\in \mathbb{Z}\text{,}\) you should do so. Also, there are frequently many different, and equally good, ways of describing sets. 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{.}\)

A proper definition of the real numbers is beyond the scope of this text. It is sufficient to think of the real numbers as the set of points on a number line. The complex numbers can be defined using set-builder notation 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.

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

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.

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

- If \(A = \{3, 5, 8\}\) and \(B = \{5, 8, 3, 2, 6\}\text{,}\) then \(A\subseteq B\text{.}\)
- \(\displaystyle \mathbb{N}\subseteq \mathbb{Z}\subseteq \mathbb{Q}\subseteq \mathbb{R}\subseteq \mathbb{C}\)
- If \(S = \{3, 5, 8\}\) and \(T = \{5, 3, 8\}\text{,}\) then \(S \subseteq T\) and \(T \subseteq S\text{.}\)

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

- In Example 1.1.4, \(S = T\text{.}\) Note that the ordering of the elements is unimportant.
- 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.

A few comments are in order about the expression “if and only if” as used in our definitions. This expression 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.

Occasionally there is need to discuss the set that contains no elements, namely the empty set, which is denoted by \(\emptyset\). This set is also called the null set.

It is clear, we hope, from the definition of a subset, that given any set \(A\) we have \(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.

Not everyone is in agreement on whether the empty set is a proper subset of any set. In fact earlier editions of this book sided with those who considered the empty set an improper subset. However, we bow to the emerging consensus at this time.

List four elements of each of the following sets:

- \(\displaystyle \{k \in \mathbb{P} \mid {k - 1} \textrm{ is a multiple of 7}\}\)
- \(\displaystyle \{x \mid x \textrm{ is a fruit and its skin is normally eaten}\}\)
- \(\displaystyle \{x \in \mathbb{Q}\mid \frac{1}{x} \in \mathbb{Z}\}\)
- \(\displaystyle \{2n \mid n \in \mathbb{Z}, n < 0 \}\)
- \(\displaystyle \{s \mid s = 1 + 2 + \cdots + n \textrm{ for some } n \in \mathbb{P}\}\)

Answer.

These answers are not unique.

- \(\displaystyle 8, 15, 22, 29\)
- \(\displaystyle \textrm{apple, pear, peach, plum}\)
- \(\displaystyle 1/2, 1/3, 1/4, 1/5\)
- \(\displaystyle -8, -6, -4, -2\)
- \(\displaystyle 6, 10, 15, 21\)

List all elements of the following sets:

- \(\displaystyle \{\frac{1}{n} \mid n \in \{3,4,5,6\}\}\)
- \(\displaystyle \{\alpha \in \textrm{ the alphabet } \mid \alpha \textrm{ precedes F}\}\)
- \(\displaystyle \{x \in \mathbb{Z} \mid x = x+1 \}\)
- \(\displaystyle \{n^2 \mid n = -2, -1, 0, 1, 2\}\)
- \(\displaystyle \{n \in \mathbb{P} \mid n \textrm{ is a factor of 24 }\}\)

Describe the following sets using set-builder notation.

- \(\displaystyle \{ 5, 7, 9, \dots , 77, 79\}\)
- the rational numbers that are strictly between \(-1\) and \(1\)
- the even integers
- \(\displaystyle \{-18, -9,0,9, 18,27, \dots \}\)

Answer.

- \(\displaystyle \{2k + 1 \mid k \in \mathbb{Z}, 2 \leqslant k \leqslant 39\}\)
- \(\displaystyle \{x \in \mathbb{Q}\mid -1 < x < 1\}\)
- \(\displaystyle \{2n\mid n \in \mathbb{Z}\}\)
- \(\displaystyle \{9n\mid n \in \mathbb{Z}, -2 \leq n\}\)

Use set-builder notation to describe the following sets:

- \(\displaystyle \{1, 2, 3, 4, 5, 6, 7\}\)
- \(\displaystyle \{1, 10, 100, 1000, 10000\}\)
- \(\displaystyle \{1, 1/2, 1/3, 1/4, 1/5, . . .\}\)
- \(\displaystyle \{0\}\)

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.

- \(\displaystyle 3 \in A\)
- \(\displaystyle \{3\} \in A\)
- \(\displaystyle \{3\} \subseteq A\)
- \(\displaystyle B\subseteq A\)
- \(\displaystyle A\subseteq B\)
- \(\displaystyle \emptyset \subseteq C\)
- \(\displaystyle \emptyset \in A\)
- \(\displaystyle A\subseteq A\)

Answer.

- True
- False
- True
- True
- False
- True
- False
- True