Set Constructions

The set constructions I've considered so far --- things like $A \cup B$ , $\overline{C}$ , $D \cap E$ --- have involved finite numbers of sets. It's often necessary to work with infinite collections of sets, and to do this, you need a way of naming thme and keeping track of them.

Let I be a set. A collection of sets indexed by I consists of a collection of sets , one set for each element $i \in I$ .

Example. Let $I = \{1, 2, 3, 4\}$ . A collection of sets indexed by I consists of four sets , , , and . For example,

$S_1 = \{1, 2, 3\}, \quad S_2 = \{a, b, c\}, \quad S_3 = \real, \quad S_4 = \{1, 2, 3\}.$

Note that ; some of the sets in the collection may be identical.

Here's another collection of sets indexed by I:

$S_1 = \emptyset, \quad S_2 = \integer, \quad S_3 = \{\pi, e\}, \quad S_4 = \{\hbox{pepperoni}, \hbox{sausage}\}.\quad\halmos$

Example. Let $I = \natural = \{1, 2, 3, \ldots\}$ . A collection of sets indexed by I is an infinite collection of sets , , , ....

Here is a collection of sets indexed by I:

$S_1 = (0,1), \quad S_2 = \left(0,\dfrac{1}{2}\right), \quad S_3 = \left(0,\dfrac{1}{3}\right), \ldots.$

In general, if n is a positive integer, then $S_n = \left(0,\dfrac{1}{n}\right)$ .

Here's another collection of sets indexed by I:

$\eqalign{S_1 &= \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}, \cr S_2 &= \{\ldots, -6, -4, -2, 0, 2, 4, 6, \ldots\}, \cr S_3 &= \{\ldots, -9, -6, -3, 0, 3, 6, 9, \ldots\}, \cr &\vdots \cr}$

In general, consists of the integers which are divisible by n.

Example. Let $I = \real$ . Here's a collection of sets indexed by I:

$S_x = \{x, -x\} \quad\hbox{for}\quad x \in \real.$

Since $\real$ is uncountable, I can't list the sets in this collection. Here are a couple of the sets:

$S_{\sqrt{2}} = \{\sqrt{2}, -\sqrt{2}\}, \quad S_{42} = \{42, -42\}.\quad\halmos$

Definition. Let I be a set, and let $\{S_i\}$ be a collection of sets indexed by I.

The union $\bigcup_{i\in I} S_i$ of the is the set

$\bigcup_{i\in I} S_i = \{s \mid s \in S_i \quad\hbox{for some}\quad i \in I\}.$

The intersection $\bigcap_{i\in I} S_i$ of the is the set

$\bigcap_{i\in I} S_i = \{s \mid s \in S_i \quad\hbox{for all}\quad i \in I\}.$

Notation. If you have a collection of sets indexed by the natural numbers

$S_1, S_2, S_3, \ldots,$

you usually write

$\bigcup_{n=1}^\infty S_n \quad\hbox{and}\quad \bigcap_{n=1}^\infty S_n$

for the union and intersection, respectively.

Example. Consider the following collection of sets indexed by $\natural$ :

$S_1 = (0,1), \quad S_2 = \left(0,\dfrac{1}{2}\right), \quad S_3 = \left(0,\dfrac{1}{3}\right), \ldots, S_n = \left(0,\dfrac{1}{n}\right), \ldots.$

This is a collection of intervals, which I've drawn below. They actually lie on top of one another on the x-axis; I've "pulled them up" so you can see them separately.

$\hbox{\epsfysize=2.5in \epsffile{setcons1.eps}}$

In this case,

$\bigcup_{n=1}^\infty \left(0,\dfrac{1}{n}\right) = (0,1) \quad\hbox{and}\quad \bigcap_{n=1}^\infty \left(0,\dfrac{1}{n}\right) = \emptyset.$

The first statement is pretty clear, since all the intervals are contained in , and ; I won't write out the proof.

For the second statement, I have to show that $\displaystyle \bigcap_{n=1}^\infty \left(0,\dfrac{1}{n}\right)$ contains no elements. I'll give a proof by contradiction.

Suppose on the contrary that $\displaystyle x \in \bigcap_{n=1}^\infty \left(0,\dfrac{1}{n}\right)$ . In particular, $x \in (0,1)$ , so I know .

Choose a positive integer n such that $\dfrac{1}{n} < x$ ; I can do this because $\displaystyle \lim_{n\to \infty} \dfrac{1}{n} = 0$ . Then $x \notin \left(0,\dfrac{1}{n}\right)$ , which contradicts $\displaystyle x \in \bigcap_{n=1}^\infty \left(0,\dfrac{1}{n}\right)$ .

This shows that there is no such element x, so the intersection is empty.

Example. Prove that $\displaystyle \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right) = \{0\}$ .

A common technique in set equality proofs is to show that the left side is contained in the right side and the right side is contained in the left side. This is what I'll do here.

First, I'll do the easy inclusion --- the right side is contained in the left side. The only element of the right side is 0. For every $n \ge 1$ , I have

$-\dfrac{1}{n} < 0 < \dfrac{1}{n}, \quad\hbox{so}\quad 0 \in \left(-\dfrac{1}{n}, \dfrac{1}{n}\right).$

Since this is true for all $n \ge 1$ , it follows that $\displaystyle 0 \in \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right)$ . Therefore, $\displaystyle \{0\} \subset \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right)$ .

Next, I have to show that $\displaystyle \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right) \subset \{0\}$ . Let $\displaystyle x \in \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right)$ . I have to show that $x \in \{0\}$ , i.e. that .

First, suppose . Since $\displaystyle \lim_{n\to \infty} \dfrac{1}{n} = 0$ , there is an integer $n \ge 1$ such that $\dfrac{1}{n} < x$ . (Since the numbers $\dfrac{1}{1}$ , $\dfrac{1}{2}$ , $\dfrac{1}{3}$ , ... approach 0, eventually they become less than any positive number.) Then $x \notin \left(-\dfrac{1}{n}, \dfrac{1}{n}\right)$ , contrary to my assumption that $\displaystyle x \in \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right)$ . Therefore, is ruled out.

Next, suppose . Since $\displaystyle \lim_{n\to \infty} -\dfrac{1}{n} = 0$ , there is an integer $n \ge 1$ such that $x < -\dfrac{1}{n}$ . Then $x \notin \left(-\dfrac{1}{n}, \dfrac{1}{n}\right)$ , contrary to my assumption that $\displaystyle x \in \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right)$ . Therefore, is ruled out.

Since I've ruled out and , it follows that . This is what I wanted to prove. Hence, $\displaystyle \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right) \subset \{0\}$ .

This completes the proof that $\displaystyle \bigcap_{n=1}^\infty \left(-\dfrac{1}{n}, \dfrac{1}{n}\right) = \{0\}$ .

Example. Prove that $\displaystyle \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 1}\right] = [0, 1)$ .

First, I'll show that the left side is contained in the right side. Let $\displaystyle x \in \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 1}\right]$ . I have to show that $x \in [0, 1)$ .

Since $\displaystyle x \in \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 1}\right]$ , I know that $x \in \left[0, \dfrac{n}{n + 1}\right]$ for some $n \ge 1$ . This means that

$0 \le x \le \dfrac{n}{n + 1}.$

But $\dfrac{n}{n + 1} < 1$ --- the proof is

$1 > 0, \quad n + 1 > n, \quad 1 > \dfrac{n}{n + 1}.$

Therefore, $0 \le x < 1$ . This means that $x \in [0, 1)$ . Hence, $\displaystyle \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 1}\right] \subset [0, 1)$ .

Next, I'll show that the right side is contained in the left side. Suppose $x \in [0, 1)$ . I have to show that $\displaystyle x \in \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 1}\right]$ .

Since $x \in [0, 1)$ , I have $0 \le x < 1$ . Now $\displaystyle \lim_{n\to \infty} \dfrac{n}{n + 1} = 1$ , so for some $n \ge 1$ I must have $x < \dfrac{n}{n + 1}$ . Note that this automatically implies that $x \le \dfrac{n}{n + 1}$ . Since I already know $x \ge 0$ , I have $0 \le x \le \dfrac{n}{n + 1}$ . This means that $x \in \left[0, \dfrac{n}{n + 1}\right)$ . Hence, $\displaystyle x \in \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 1}\right]$ . Therefore, $\displaystyle [0, 1) \subset \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 1}\right]$ .

This completes the proof that $\displaystyle \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 1}\right] = [0, 1)$ .

Definition. Let S and T be sets. The Cartesian product of S and T is the set $S \times T$ consisting of all ordered pairs , where $s \in S$ and $t \in T$ .