Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 8.5 Indexed sets

Our usual set notation works well when we have a small number of sets; if our work involves three sets, we can just denote them \(A,B\) and \(C\text{.}\) However, this quickly becomes inconvenient when we have even a moderate number of sets; what should we use to denote the \(17^\mathrm{th}\) set? One solution it to use indices to distinguish between sets:
\begin{equation*} A_1, A_2, A_3, \dots \end{equation*}
More generally, our indices do not need to be natural numbers, but instead come from any set. So, for example, we could define a family of sets indexed by elements of another set \(S\)
\begin{equation*} \set{ A_\alpha \st \alpha \in S} \end{equation*}
In this context 103  we call \(S\) the indexing set, and the sets \(A_\alpha\) the indexed sets. Typically, the indexing set is a subset of the natural numbers.
Now, recall that we defined the intersection of sets \(A\) and \(B\) to be the set of all elements that are in both sets. Similarly the union of \(A\) and \(B\) is the set of all elements that are in at least one of the sets. It is not hard to extend this to the intersection and union of three sets:
\begin{equation*} A \cap B \cap C = \set{x \st x \text{ is every one of }A,B,C} \end{equation*}
and
\begin{equation*} A \cup B \cup C = \set{x \st x \text{ is in at least one of }A,B,C} \end{equation*}
Writing the intersection and union this way, shows how we can extend them to intersections and unions of large numbers of sets. Indeed we define,

Definition 8.5.1.

Let \(N \in \mathbb{N}\) and let \(A_1, A_2, \dots, A_{N}\) be a collection of sets. We define the intersection of \(A_1, A_2, \dots, A_{N}\) as
\begin{equation*} \bigcap_{k=1}^N A_k = \set{x \st x \in A_j \text{ for all } j \in \set{1,2,\dots,N} }. \end{equation*}
We similarly define their union to be
\begin{equation*} \bigcup_{k=1}^N A_k = \set{x \st x \in A_j \text{ for some } j \in \set{1,2,\dots,N} }. \end{equation*}
This notation is very useful when we have to work with lots of sets 104 . We can generalise it further. For example, these unions and intersections need not start at index 1. Nor do they need to be unions and intersections over finite collections of sets.

Definition 8.5.2.

Let \(m,M \in \mathbb{N}\) with \(m \leq M\text{,}\) and let \(A_k\) be a set for all \(k=m,m+1,\dots,M\text{.}\) Then
\begin{align*} \bigcap_{k=m}^M A_k \amp= \set{x \st \forall j \in \set{m,m+1,\dots,M}, x \in A_j } \\ \bigcup_{k=m}^M A_k \amp= \set{x \st \exists j \in \set{m,m+1,\dots,M} \text{ s.t. } x \in A_j } \end{align*}
Further, let \(B_m, B_{m+1}, B_{m+2},\dots\) be sets, then
\begin{align*} \bigcap_{k=m}^\infty B_k \amp = \set{x \st \forall j \in \mathbb{N} \text{ with } j \geq m, x \in B_j } \\ \bigcup_{k=m}^\infty B_k \amp = \set{x \st \exists j \in \mathbb{N} \text{ with } j \geq m \text{ s.t. } x \in B_j } \end{align*}
These definitions tell us that if \(x \in \bigcap_{n=m}^\infty A_n\text{,}\) then \(x \in A_k\) for every single \(k \geq m\text{.}\) On the other hand, if we know that \(x \not \in \bigcap_{n=m}^\infty A_n\text{,}\) then there must be at least one index \(k \geq m\) so that \(x \not\in A_k\text{.}\) Similarly, if \(x \in \bigcup_{n=m}^\infty A_n\text{,}\) then there is at least one index \(k \geq m\) so that \(x \in A_k\text{.}\) And if \(x \not\in \bigcup_{n=m}^\infty A_n\text{,}\) then \(x \not\in A_k\) for every single \(k \geq m\text{.}\)

Example 8.5.3.

Consider the indexed sets, \(A_n=\left( -\dfrac 1n,\dfrac 1n \right)\) for \(n\in\mathbb{N}\text{.}\) So that, for example,
\begin{equation*} A_2=\left( -\dfrac 12,\dfrac 12\right) \qquad \text{ and }\qquad A_{27}=\left( -\dfrac {1}{27},\dfrac {1}{27} \right). \end{equation*}
Then
\begin{equation*} 0 \in \bigcap_{n=1}^\infty A_n \end{equation*}
but
\begin{equation*} \dfrac{1}{e} \not\in \bigcap_{n=1}^\infty A_n. \end{equation*}
The first of these is true since \(0 \in A_n=\left(-\dfrac 1n,\dfrac 1n\right)\) for all \(n \in \mathbb{N}\text{.}\) The second follows 105  since \(e \lt 3\) and so \(\frac{1}{e} \gt \frac{1}{3}\) and so \(\frac{1}{e} \not\in A_3\text{;}\) since it is not in one of the sets, it cannot be in the intersection of those sets.
Actually we have something a little stronger here. We have \(\frac 1e\notin \left(-\frac 1n,\frac 1n\right)\) for any \(n\geq 3\text{.}\) But since we want to show that \(\frac 1e\) is not in the intersection, it is enough to show that it is not in at least one of the intersecting sets.
In general, we don’t have to take our indices from the natural numbers. We can index sets with rational numbers, real number, matrices, colours — just about any set. For example, for any real number \(x \in (0,10)\) we can define
\begin{equation*} A_x = [-x,x^2] = \set{t \in \mathbb{R} \st -x \leq t \leq x^2}. \end{equation*}
So that \(A_5 = [5,25]\) and \(A_\pi = [-\pi, \pi^2]\text{.}\) So the \(A_x\) form a family of sets indexed by real numbers. Sometimes we might need to take the union and intersection of all the sets in such a family, and so we generalise the notation even more.

Definition 8.5.4.

Let \(\mathcal{S}\) be a set, and let \(A_s\) be a set for all \(s \in \mathcal{S}\text{.}\) Then we can define the intersection and union over all of these sets:
\begin{equation*} \bigcap_{s \in \mathcal{S} } A_s = \set{x \st \forall s \in \mathcal{S}, x \in A_s}, \end{equation*}
and
\begin{equation*} \bigcup_{s \in \mathcal{S} } A_s = \set{x \st \exists s \in \mathcal{S} \text{ s.t. } x \in A_s}, \end{equation*}

Remark 8.5.5.

When we do have sets indexed by the natural numbers, say \(A_m, A_{m+1}, A_{m+2}, \dots\) etc, it can be convenient to write their intersection and union as
\begin{equation*} A_m\cap A_{m+1}\cap A_{m+2}\cap \cdots \qquad \text{and} \qquad A_m\cup A_{m+1}\cup A_{m+2}\cup \cdots \end{equation*}
It is arguably better to avoid this notation in favour of the more precise notation above. We should make sure that things are clear for our reader.
A more subtle, but very important point, is that when sets are indexed by real numbers it can, in fact, be impossible to write the union or intersection of those sets in this way. This is because the real numbers are not countable. There is simply no way to write out the real numbers in an ordered list in this way. The interested reader should jump ahead to Chapter 12 for more on the uncountability of the reals.

Example 8.5.6.

Determine whether or not the following statements are true or false.
  1. \(\displaystyle \ds \bigcap\limits_{n=1}^\infty \left(-\dfrac 1n,\dfrac 1n\right)=\emptyset\)
  2. \(\displaystyle \ds 3\in \bigcup\limits_{n=3}^\infty \left(2+\dfrac 1n,3-\dfrac 1n\right]\)
  3. Given the indexed sets \(A_x=[-x,x^2]\text{,}\) for \(x\in\mathbb R, x>0\text{,}\) we have
    \begin{equation*} 0\in \bigcap\limits_{x\in (0,1)} A_x. \end{equation*}
  4. Given the indexed sets \(A_y=\big(-e^y,1-\frac 1y\big]\text{,}\) for \(y\in\mathbb R\text{,}\) we have
    \begin{equation*} 1\in \bigcup\limits_{y\in (1,\infty)} A_y. \end{equation*}
  5. \(\displaystyle \ds [-1,0)\subseteq \bigcup\limits_{n=2}^\infty \left[-1, -\dfrac 1n\right]\)
  6. \(\displaystyle \ds \bigcap\limits_{n=5}^\infty \left[0, 1+\dfrac 1n\right)\subseteq [0,1)\)
Solution.
  1. This statement is false since for all \(n\in\mathbb N\text{,}\) we have \(\ds 0\in \left(-\dfrac 1n,\dfrac 1n\right)\text{.}\) Therefore \(\ds \bigcap\limits_{n=1}^\infty \left(-\dfrac 1n,\dfrac 1n\right)\neq\emptyset\text{.}\)
    Notice that we see that our indexed sets are getting smaller and smaller as \(n\) grows larger and larger. We also see that
    \begin{equation*} \bigcap_{n=1}^k \left(-\dfrac 1n,\dfrac 1n\right)=\left(-\dfrac 1k,\dfrac 1k\right). \end{equation*}
    One might take this to suggest that we can understand \(\ds \bigcap\limits_{n=1}^\infty \left(-\dfrac 1n,\dfrac 1n\right)\text{,}\) by just looking at what happens to \(A_k\) as \(k\) goes to infinity. This is a dangerous line of reasoning. Since \(-\frac{1}{k}\) and \(\frac{1}{k}\) both go to \(0\) as \(k\) goes to infinity, we are tempted to say that \(\ds \bigcap\limits_{n=1}^\infty \left(-\dfrac 1n,\dfrac 1n\right)=(0,0)=\emptyset\text{.}\) But we have already shown the intersection is not empty since it contains \(0\text{.}\) It is important to use the definitions carefully to determine what the intersections or unions contain.
  2. We see that this statement is false since in order for \(3\) to be in \(\ds \bigcup\limits_{n=3}^\infty \left(2+\dfrac 1n,3-\dfrac 1n\right]\text{,}\) it must be in at least one of the sets \(\left(2+\dfrac 1n,3-\dfrac 1n\right]\) for \(n\in\set{3,4,5,\ldots}\text{.}\)
    But, we see that for all \(n\in\set{3,4,5,\ldots}\text{,}\) \(3-\dfrac 1n \lt 3\text{,}\) which implies that \(\ds 3\notin \left(2+\dfrac 1n,3-\dfrac 1n\right]\) for any \(n\in\set {3,4,5,\ldots}\text{.}\) Therefore \(\ds 3\notin \bigcup\limits_{n=3}^\infty \left(2+\dfrac 1n,3-\dfrac 1n\right]\text{.}\)
  3. We see that for all \(x\in(0,1)\text{,}\) we have \(-x \lt 0\) and \(x^2 \gt 0\text{.}\) Thus, this statement is true since we have \(0\in [-x,x^2]\text{,}\) for all \(x\in(0,1)\text{.}\)
  4. This statement is false since for all \(y\in (1,\infty)\text{,}\) we see \(1-\dfrac 1n \lt 1\text{,}\) and hence \(\ds 1\notin \big(-e^y,1-\frac 1y\big]\) for any \(y\in (1,\infty)\text{.}\)
  5. This statement is true. To show it let \(x\in[-1,0)\text{.}\) Then, all we have to do is to show that \(x\in \left[-1, -\dfrac 1n\right]\) for at least one \(n\in\set{2,3,4,\ldots}\text{.}\) For that, it is sufficient to show that \(x\leq -\dfrac 1n\) for some \(n\in\set{2,3,4,\ldots}\) (since we already know that \(x \geq -1\)).
    We can find such \(n\) by choosing \(N=\ceil{\frac {1}{|x|}}\text{,}\) where \(\ceil{t}\) denotes the ceiling function — ie the first integer greater or equal to \(t\text{.}\) By using the ceiling function we are really just rounding up the value of \(\frac {1}{|x|}\text{.}\) With that choice of \(N\text{,}\) we know that \(x\leq -\dfrac 1N\) and hence \(\ds x\in [-1, \frac 1N]\text{.}\) Therefore \(\ds [-1,0)\subseteq \bigcup\limits_{n=2}^\infty \left[-1, -\dfrac 1n\right]\text{.}\)
  6. Since \(1+\dfrac 1n\) goes to \(1\) as \(n\) goes to infinity, it is tempting to say that the statement is true. Unfortunately 106 , this it not correct.
    This statement is actually false because, similar to the argument we used in Item a, \(\ds 1\in \bigcap\limits_{n=5}^\infty \left[0, 1+\dfrac 1n\right)\text{.}\) Thus, \(\ds 1\in \bigcap\limits_{n=5}^\infty \left[0, 1+\dfrac 1n\right)\text{,}\) but \(\ds 1\notin [0,1)\text{.}\) Therefore \(\ds \bigcap\limits_{n=5}^\infty \left[0, 1+\dfrac 1n\right)\not\subseteq [0,1)\text{.}\)
Before we go on to the next example, let’s prove a useful lemma.
We prove the contrapositive of this statement. Namely, if \(x \gt 0\) then there is some \(k \in \mathbb{N}\) so that \(x \geq \frac{1}{k}\text{.}\) So assume that \(x \gt 0\text{.}\) Then \(0 \lt \frac{1}{x} \leq \ceil{\frac{1}{x}} = \ell\text{,}\) where \(\ell \in \mathbb{N}\text{.}\) Then \(x \geq \frac{1}{\ell}\) as required.

Example 8.5.8.

For \(k\in\mathbb N\) let \(A_k\) be the intervals \(A_k=[\frac{1}{k+1},1+\frac{1}{k+1})\text{.}\)
  1. Show that \(\bigcup_{k=1}^\infty A_k=(0,\frac32)\text{.}\)
  2. Show that \(\bigcap_{k=1}^\infty A_k=[\frac12,1]\)
Solution.
Let us show the two inclusions in turn.
  • Let \(x\in\bigcup_{k=1}^\infty A_k\text{.}\) Then \(x\in A_k\) for some \(k\in \mathbb N\) so that \(\frac{1}{k+1} \leq x \lt 1 + \frac{1}{k+1}\) from which we get that \(0 \lt x \lt \frac{3}{2}\text{,}\) so that \(x\in (0,\frac32)\text{.}\)
  • Now let \(x\in(0,\frac32)\text{.}\) Then let us consider two cases, \(x\geq \frac{1}{2}\) or \(x \lt \frac12\text{.}\)
    1. First case: Suppose that \(x\geq \frac{1}{2}\text{.}\) Then because of the assumption on \(x\) we have \(\frac12\leq x \lt \frac32\text{,}\) and so \(x\in A_1\text{,}\) so \(x\in\bigcup_{k=1}^\infty A_k\text{.}\)
    2. Second case: Suppose that \(x \lt \frac12\text{.}\) Then if we let \(n=\ceil{\frac1x}\) then we have \(\frac1x \lt n+1\) and so \(x \gt \frac{1}{n+1}\text{.}\) This is enough to show that \(x\in A_n\) with \(n\in \mathbb N\) and so \(x\in\bigcup_{k=1}^\infty A_k\text{.}\)
Again, we prove the two inclusions in turn.
  • Let \(x\in\bigcap_{k=1}^\infty A_k\text{.}\) Then for any \(k\in \mathbb N\) we have \(x\in A_k\) so that the inequality \(\frac{1}{k+1}\leq x \lt 1+\frac{1}{k+1}\) holds for any \(k\in \mathbb N\text{.}\) In particular, \(x\geq \frac{1}{2}\text{.}\)
    Now we can use Lemma 8.5.7 to show that \(x \leq 1\text{.}\) Since we know that \(x-1 \lt \frac{1}{k+1}\text{,}\) Lemma 8.5.7 implies that \(x-1 \lt 0\) and hence \(x \leq 1\text{.}\)
    So we have now shown that \(x \geq \frac{1}{2}\) and \(x \leq 1\) and thus \(x \in [\frac{1}{2},1]\text{.}\)
  • Now let \(x\in[\frac12,1]\text{.}\) So \(\frac12 \leq x \leq 1\text{.}\) Let \(k\in \mathbb N\text{,}\) we can check that \(\frac{1}{k+1} \leq \frac{1}{2}\) and \(1+\frac{1}{k+1} \gt 1\text{,}\) hence \(\frac{1}{k+1}\leq x \lt 1 + \frac{1}{k+1}\) so \(x\in A_k\text{.}\) In the end, for any \(k\in \mathbb N\) we have \(x\in A_k\text{,}\) so that \(x\in\bigcap_{k=1}^\infty A_k\text{.}\)
We hope the reader will forgive the authors for not making a formal definition here.
As you can see, this notation is very similar to the \(\Sigma, \Pi\) notation we use to denote sums and products.
We are assuming that we know \(e = 2.71828\dots\text{.}\) It is not too hard to show that \(2 \lt e \lt 3\text{,}\) but it does take some calculus.
Well, actually it is fortunate. The authors have constructed this example with precisely that in mind. The reader should not give in to the temptation of a quick limit to solve all their set problems.
<Prev^TopNext>