# Discrete Mathematics: An Active Approach to Mathematical Reasoning

## Section1.2Introduction to Sets

Sets are collections of objects. They may be collections of mathematical objects, such as numbers or functions. They may be collections of any other type of object such as students in a class or times of day. We can even have sets of sets!
We will usually use capital letters for sets, such as $$S$$ or $$A\text{.}$$ If we want to talk about elements in a set $$S\text{,}$$ we use the notation $$x\in S$$. We read this notatation as “$$x$$ is in $$S$$” or “$$x$$ is an element of $$S\text{.}$$” If $$x$$ is not in $$S\text{,}$$ then we use the notation $$x\notin S$$.
If we want to list the specific elements of a set, we use curly brackets, $$\{\}\text{,}$$ around the elements of the set. We can also do this with a description of the elements in the set.

### Example1.2.1.Set roster notation.

$$S=\{1, 2, 3, 4, 5\}\text{.}$$ This is the set whose elements are 1, 2, 3, 4, 5.
$$A=\{x\in S : x \text{ is odd}\}\text{.}$$ This describes the odd numbers in $$S\text{,}$$ so 1, 3, 5.
$$A=\{x\in \text{reals} : 1\leq x\leq 5\}\text{.}$$ This describes the real numbers between 1 and 5 (which there are too many to list).
In general, if we use $$P(x)$$ to describe a property of $$x\text{,}$$ we use the notation
\begin{equation*} \{x\in S : P(x)\} \end{equation*}
and read the statement as “$$x$$ in $$S$$ such that $$x$$ has property $$P\text{.}$$

### Activity1.2.1.

Let $$S=\{1, 2, 3, 4, 5\}\text{.}$$ List the elements in each of the following sets.

#### (a)

$$\{x\in S : 2 <x\leq 5\}$$

#### (b)

$$\{x\in S: x \mbox{ is prime}\}$$

#### (c)

$$\{1/x: x \in S\}$$

### Definition1.2.2.

A subset, $$A\text{,}$$ of a set $$S$$ is a set of elements that are also in $$S\text{.}$$ We use the notation $$A\subseteq S\text{.}$$
If $$A$$ is not a subset of $$S\text{,}$$ then we use the notation $$A\nsubseteq S$$. Note, some books use $$A\subset S$$ as the notation for subset.

### Example1.2.3.Subset Notation.

We can see that $$\{1, 3\}\subseteq \{1, 2, 3, 4, 5\}$$ since every element of $$\{1, 3\}$$ is also in $$\{1, 2, 3, 4, 5\}\text{.}$$ However, $$\{0, 1, 2, 3\}\nsubseteq \{1, 2, 3, 4, 5\}$$ since $$0\notin \{1, 2, 3, 4, 5\}\text{.}$$
It is important to understand the difference between subset, $$\subseteq\text{,}$$ and element, $$\in\text{.}$$ For example, if $$S=\{1, 2, 3, 4, 5\}\text{,}$$ then $$1\in S\text{,}$$ but $$1\nsubseteq S\text{.}$$ This is because 1 is an element, not a set. Similarly, $$\{1\}\subseteq S\text{,}$$ but $$\{1\}\notin S\text{.}$$ This is because $$\{1\}$$ is a set, not an element. In general, when working with sets, you should identify the elements of the set. Then sets of those elements are subsets. The curly brackets are our way of saying “set.”
The distinction between elements and sets really gets fuzzy when we want to think about sets of sets.

### Example1.2.4.Example of a set with elements that are sets.

Let $$S=\{1, \{2, 3, 4\}, \{3\}, \{5\}, 6, 7\}$$
The six elements are $$1, \{2, 3, 4\}, \{3\}, \{5\}, 6, 7.$$ The following are examples of elements and subsets. In each of the examples, pay close attention to how the brackets are being used.
• $$\displaystyle 1\in S$$
• $$\displaystyle \{3\}\in S$$
• $$\displaystyle \{2, 3, 4\}\in S$$
• $$\displaystyle \{\{3\}\}\subseteq S$$
• $$\displaystyle \{1,\{3\}\}\subseteq S$$
It will also be useful to look at examples that are not elements or subsets.
• $$3\notin S\text{,}$$ 3 is not one of the six elements.
• $$\{6\}\notin S\text{,}$$ $$\{6\}$$ is not one of the six elements.
• $$\{4\}\notin S\text{,}$$ $$\{4\}$$ is not one of the six elements.
• $$1\nsubseteq S\text{,}$$ 1 is not a set.
• $$\{4\}\nsubseteq S\text{,}$$ since 4 is not an element, $$\{4\}$$ is not a subset.
• $$\{\{6\}\}\nsubseteq S\text{,}$$ since $$\{6\}$$ is not an element, $$\{\{6\}\}$$ is not a subset.
• $$\{1,\{2, 3\}\}\nsubseteq S\text{,}$$ since $$\{2, 3\}$$ is not an element, $$\{1,\{2, 3\}\}$$ is not a subset.
In each of the nonexamples of elements, the object listed is not one of the six elements. In each of the nonexamples of subsets, the set is not a set of elements.

### Activity1.2.2.

Determine if each of the following is true or false. If it is false, what small change in notation would make it true? Make sure you are able to distinguish between elements of a set and subsets of a set.

#### (a)

$$5\in \{2,3,5,7\}$$

#### (b)

$$\{2\} \in \{2,3,5,7\}$$

#### (c)

$$\{-1, -2, -3\}\subseteq \{-1, -2, -3\}$$

#### (d)

$$0\subseteq \{0, 2, 4\}$$

#### (e)

$$\{0\}\subseteq \{0, 2, 4\}$$

### Activity1.2.3.

When you have a set with elements that are sets you need to be really careful about the notation. For example, let $$S=\{1, 2, \{3, 4\}, \{5\}\}\text{.}$$ In this set, two of the elements are sets. Determine if the following are true or false for the set $$S\text{.}$$

#### (a)

$$2\in S$$

#### (b)

$$3\in S$$

#### (c)

$$5\in S$$

#### (d)

$$\{1, 2\}\subseteq S$$

#### (e)

$$\{3, 4\}\subseteq S$$

#### (f)

$$\{1, \{5\}\}\subseteq S$$

#### (g)

$$\{\{3, 4\}\}\subseteq S$$

### Definition1.2.5.

If $$A\subseteq B$$ and $$A\neq B\text{,}$$ then we say $$A$$ is a proper subset of $$B\text{.}$$
There are some special subsets that we will use throughout the course and, in fact, the rest of your mathematical career.
• $$\mathbb{R}$$, the set of real numbers. These are all the numbers your are familiar with from Calculus: whole numbers, positives, negatives, fractions, decimals, square roots, $$e\text{,}$$ $$\pi\text{,}$$ etc.
• $$\mathbb{Z}$$, the set integers. These are all the whole numbers: positive, negative, and zero.
• $$\mathbb{Q}$$, the set rational numbers. These are all the whole numbers and fractions: positive, negative, and zero. We will revisit this set in more detail later.
• $$\mathbb{N}$$, the set of natural numbers. These are all the positive whole numbers. Some books include zero, some do not. Since this can be confusing, we will avoid this notation in this class (but you might see it in future classes). Instead, we will use one of the next two notations, which more clearly denote inclusion of zero, or not.
• $$\mathbb{Z}^+$$, the set of positive integers. These are all the positive whole numbers. This set does NOT include zero.
• $$\mathbb{Z}^{nonneg}$$, the set of nonnegative integers. These are the whole numbers that are not negative. This set DOES include zero.
• $$\mathbb{R}^+$$, the set of positive real numbers.
• $$\mathbb{R}^{nonneg}$$, the set of nonnegative real numbers. These are the real numbers that are not negative.

### Activity1.2.4.

Based on the notations above, what would be a good notation for the set of integers less than zero?

### Activity1.2.5.

Which of the following sets do NOT contain zero: $$\mathbb{Q}, \mathbb{Z}, \mathbb{R}, \mathbb{R}^+, \mathbb{R}^{nonneg}\text{?}$$
We now define a new set.

### Definition1.2.6.

The Cartesian product of two sets $$A$$ and $$B$$ is the set of ordered pairs, where the first coordinate comes from set $$A$$ and the second coordinate comes from set $$B\text{.}$$ We use the notation
\begin{equation*} A\times B=\{(a, b) : a\in A, b\in B\}. \end{equation*}

### Example1.2.7.Cartesian Product of Sets.

Let $$A=\{2, 4\}, B=\{0, 1\}\text{.}$$ Then $$A\times B=\{(2, 0), (4, 0), (2, 1), (4, 1)\}\text{.}$$

### Example1.2.8.Cartesian Product of the Real Numbers.

When plotting points in a plane, you use the Cartesian product $$\mathbb{R}\times \mathbb{R}=\{(x, y) : x\in \mathbb{R}, y\in \mathbb{R}\}\text{.}$$ It is common to use the notation $$\mathbb{R}^2$$ for this set of ordered pairs.

### Activity1.2.6.

Let $$A=\{1, 2, 3\}$$ and $$B=\{4, 5\}\text{.}$$

#### (a)

List all the elements of $$A\times B\text{.}$$ Make sure your elements are ordered pairs.

#### (b)

List all the elements of $$B\times B\text{.}$$

#### (c)

Does $$A\times B= B\times A\text{?}$$

#### 1.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$4\in A\text{.}$$
• True.

• False.

#### 2.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$0\notin A\text{.}$$
• True.

• False.

#### 3.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$\{4\}\in A\text{.}$$
• True.

• False.

#### 4.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$\{2, 4\}\in A\text{.}$$
• True.

• False.

#### 5.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$\{2, 4\}\subseteq A\text{.}$$
• True.

• False.

#### 6.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$\{2, 3, 4\}\subseteq A\text{.}$$
• True.

• False.

#### 7.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$\{0, 2, 6\}\nsubseteq A\text{.}$$
• True.

• False.

#### 8.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$\{2, 4, 6, 8, 10\}\subseteq A\text{.}$$
• True.

• False.

#### 9.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$6\in A\times A\text{.}$$
• True.

• False.

#### 10.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$(2, 4)\in A\times A\text{.}$$
• True.

• False.

#### 11.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$\{2, 4\}\subseteq A\times A\text{.}$$
• True.

• False.

#### 12.

Let $$A=\{2, 4, 6, 8, 10\}\text{,}$$ then $$\{(2, 2), (4, 6), (10, 4)\}\subseteq A\times A\text{.}$$
• True.

• False.

### ExercisesExercises

#### 1.

Explain in your own words why $$2$$ does not equal $$\{2\}\text{.}$$

#### 2.

How many elements are in the set $$\{1, 2, 3, 1, 2, 1\}\text{?}$$

#### 3.

How many elements are in the set $$\{1, \{1\}, \{1, \{1\}\}\}\text{?}$$

#### 4.

Use set-roster notation to list the elements in each of the following sets.
1. $$\displaystyle S=\{n\in \mathbb{Z}: n=(-1)^k, \text{ for some integer } k\}$$
2. $$\displaystyle T=\{m\in \mathbb{Z}: m=1+(-1)^k, \text{ for some integer } k\}$$
3. $$\displaystyle U=\{r\in \mathbb{Z}: 2\leq r\leq -2\}$$
4. $$\displaystyle V=\{s\in \mathbb{Z}: s>2 \text{ or } s\leq 3\}$$

#### 5.

Determine whether the following statements are true or false.
1. $$\displaystyle 3\in \{1, 2, 3\}$$
2. $$\displaystyle 1\subseteq \{1, 2, 3\}$$
3. $$\displaystyle \{2\}\in \{1, 2, 3\}$$
4. $$\displaystyle \{3\}\in \{\{1\}, \{2\}, \{3\}\}$$
5. $$\displaystyle 1\in \{1\}$$
6. $$\displaystyle \{2\}\subseteq \{\{1\}, \{2\}, \{3\}\}$$
7. $$\displaystyle \{1\}\subseteq \{1, 2, 3\}$$
8. $$\displaystyle 1\in \{\{1\}, \{2\}, \{3\}\}$$
9. $$\displaystyle \{1\}\subseteq \{1, \{2\}\}$$
10. $$\displaystyle \{1\}\subseteq \{1\}$$

#### 6.

Let $$A=\{w, x, y, z\}\text{,}$$ $$B=\{a, b\}\text{,}$$ $$S=\{2, 4, 6\}\text{,}$$ $$T=\{1, 3, 5\}\text{.}$$ Use set-roster notation to write each of the following sets. Indicate the number of elements in each set.
1. $$\displaystyle A\times B$$
2. $$\displaystyle B\times A$$
3. $$\displaystyle B\times B$$
4. $$\displaystyle S\times T$$
5. $$\displaystyle T\times S$$
6. $$\displaystyle S\times S$$