# Leftovers: subsets of integers and indexed sets

On Monday’s FOM class we discussed some homework problems, all of them dealing with sets.  One question was raised by Alexis (I believe), and sounded something like this:

Which integers are in the set $S = \{2a + 5b : a, b \in \mathbb{Z} \}$?

For starters, we should note that this set is, indeed, a subset of $\mathbb{Z}$ (why?).  However, the actual question at hand does not have an obvious answer.  Setting $a = 0 = b$, we see that $0 \in S$.  Similarly, by choosing $a = -1$ and $b = 1$, we see that $3 \in S$.

For the purposes of comparison, consider the set $A = \{3a + 6b : a, b \in \mathbb{Z}\} \subseteq \mathbb{Z}$.  Several sample values for the integers $a, b \in \mathbb{Z}$ suggest that not all integers are in $a$.  In fact, it is pretty clear that

$A = \{\dots -9, -6, -3, 0, 3, 6, 9 \dots \} = \{\text{all multiples of } \, \pm 3\}$.

No such pattern appears to emerge when we work with the original set $S$, though, and so what might this suggest?  I think — and this is only an opinion — this suggests a slight rephrasing of the original question: Which integers can I build using combinations of $2$ and $5$?  If you can answer this question (or at least develop an intuitive answer), then the original question is all done, too.

## Indexed Sets

Another point of discussion yesterday concerned an indexed union.  Although this is described quite well in our textbook (and you should re-read it for yourselves!), it seems like its worth exploring a bit further.  In fact, I’ll even do this in well-organized sections (including the one containing this very paragraph).  Note, however, that our focus will be on indexed unions, and you should keep in mind that we also care about indexed intersections and indexed other-operations.

### A Finite Amount of Unions

Suppose I have five sets.  “Sets of what?” you ask, to which I reply “Sets of anything!”  Each individual set may be an interval of real numbers or a set of cats or a set of pictures or whatever.  The important part is that they’re sets, and since I have five of them I’ll name them like this: $A_1, A_2, A_3, A_4$ and $A_5$.

Then, of course, we can form the union of these sets, which we like to notate as

$A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5$.

We can notate this new set more efficiently (i.e. using less horizontal space) by adopting the following notation:

$\displaystyle \bigcup_{i=1}^5 \, A_i$

This notation should remind us of so-called “sigma summation” notation that one first encounters in calculus (often when learning about Riemann sums).  However, the notation is a bit incomplete, at least technically.  The reader has to infer that the expression “\latex i” runs through the first $5$ natural numbers, starting at $i =1$, contenting through $i = 2, i=3, i=4$, and $i = 5$.  If we wanted to be clearer, we could spell this out a bit more by using the notation

$\displaystyle \bigcup_{i \in \{1, 2, 3, 4, 5\}} A_i$

The expression above can be translated into the following English: “for every natural number between (and including) 1 and 5 we have a set, $A_i$, and now we are union-ing them all together.”  The expression $i$ is referred to as the index, and the set of elements it “runs through” is referred to as the index set; that is the set $\{1, 2, 3, 4, 5\}$ above is the index set.  In slightly shorter English, then, the above set is the union of a collection of sets that is indexed by the first five natural numbers.

Example (1).  Suppose $A_1 = \{\square\}, A_2 = \mathbb{Z}, A_3 = \emptyset, A_4 = \{b, c\},$ and $A_5 = \{a, b\}$.  Then it follows that

$\displaystyle \bigcup_{i \in \{1, 2, 3, 4, 5\}} A_i = \{\square\} \cup \mathbb{Z} \cup \emptyset \cup \{b, c\} \cup \{a, b\} = \{\square, a, b, c\}\cup\mathbb{Z}$

Two important observations to make about this (finite) indexed union.  First, the index $i$ is not required or used in the description of the final set.  Second, the sets being unioned, the $A_i$‘s, have absolutely nothing to do with the index set $\{1, 2, 3, 4, 5\}$.

Example (2).  Here is an example, like your homework problems, where the description of the sets being unioned depend on the index $i$.  Let’s use $A_i = \{i, i^2\}$ for each set so that $A_1 = \{1\}, A_2 = \{2, 4\}$ and so on.  (Note that since the index $i \in \{1, 2, 3, 4, 5\}$ is a natural number, it makes sense to write down $i^2$.  Had we used a different index set it likely would not be possible to make sense of $i^2$.)  It then follows

$\displaystyle \bigcup_{i \in \{1, 2, 3, 4, 5\}} A_i = \{1\} \cup \{2, 4\} \cup \{3, 9\} \cup \{4, 16\} \cup \{5, 25\} = \{1, 2, 3, 4, 5, 9, 16, 25\}$

Example (3).  Here is a strange-looking example, one that uses a bizarre (and rather arbitrary) index set.  This example is important but silly, I should point out, but let’s discuss that after its all done.  We’ll use the index set $\mathcal{I} = \{\pi, -4, \\}$.  Note that $\mathcal{I}$ is a three-element set (that is $\left| \mathcal{I} \right| = 3$), and so it would have made much more notational sense to instead use the set $\{1, 2, 3\}$, but we’re being weird on purpose here.  We use this 3-element index set $\mathcal{I}$ to keep track of three sets which we shall notate using the given indices; that is, we will use a set $A_{\pi}$, a set $A_{-4}$, and, finally, a set $A_{\}$.  We then have

$\displaystyle \bigcup_{i\in\mathcal{I}} A_i = \bigcup_{i \in \{\pi, -4, \\}} = A_{\pi} \cup A_{-4} \cup A_{\}$

To write this out in any more meaningful or concrete way, I’d have to tell you what each set $A_{\pi}, A_{-4}$ and $A_{\}$ is, but before doing anything like that, take note: again, there is no relationship (necessarily) between the kinds of sets being unioned and the index set $\mathcal{I}$.  How could there be?  We haven’t even specified which three sets we’re union-ing above!  We’ve only (bizarrely) named them according to the index $i \in \mathcal{I} = \{\pi, -4, \\}$.  And, indeed, this is the important part of main point of this example, that the index set $\mathcal{I}$, no matter what it is, is used to keep track of the sets we are union-ing (or intersecting or whatever-else-ing), it is just a way to help name or (sometimes) describe the sets.  If $i$ is a natural number, that doesn’t stop $A_i$ from containing real numbers, rational numbers, abstract symbols or whatever else.  If $i$ is an arbitrary symbol, $A_i$ is still free to contain whatever kinds of elements we wish.

For the sake of completing this example, then, let’s go ahead and say that $A_{\pi} = [-1/2, 1]$ — i.e. the closed interval of real numbers between negative one half and one — and $A_{-4} = [0, \infty)$ and $A_{\} = (-\infty, -1/2]$.  We then have

$\displaystyle \bigcup_{i\in\mathcal{I}} A_i = \bigcup_{i \in \{\pi, -4, \\}} =[-1/2,1] \cup [0, \infty) \cup (-\infty, -1/2] = \mathbb{R}$

### Infinitely Indexed

Of course, this process of union-ing over a finitely-indexed collection of sets works similarly for any sized index set, and, indeed, even for index sets that are not finite.  Suppose we have a large collection of sets, one for each element in the counting or natural numbers $\mathbb{N}$.  We can then use our index, $i \in \mathbb{N}$ to name each set as, say, $A_i$, and then we can form the infinite union

$\displaystyle \bigcup_{i\in\mathbb{N}} A_i = \bigcup_{i=1}^{\infty} A_i = A_1 \cup A_2 \cup A_3 \cup \cdots = \{x : x \in A_i \text{ for at least one } i \in \mathbb{N}\}$

While certain flavors of philosophers and logicians may contest this process, we, as budding mathematicians, are perfectly comfortable with it.  Union-ing together an infinite collection of sets results in a new set, one with elements that came from at least one of the indexed sets (it could have also come from multiple).

Again, it is important to note that the sets $A_i$ may have absolutely nothing to do with the index set $\mathcal{I} = \mathbb{N}$.  The $A_i$‘s may be sets of real numbers, sets of rationals, sets of matrices, sets of words, etc; the index set is simply keeping track of these sets, it is not (necessarily) telling us anything about the elements in each set.  Let’s explore two examples, one where the sets $A_i$ have nothing to do with the index $i \in \mathbb{N}$, and one where the sets $A_i$ are, in fact, described in terms of the parameter $i \in \mathbb{N}$.

Example (4).  Let’s use the sets $A_1 = \mathbb{R}, A_2 = \{ ! \}, A_3 = \emptyset, A_4 = \mathbb{R}, A_5 = \{ ! \}, A_6 = \emptyset$ and so on.  That is, our infinite collection of sets repeats itself according to the indicated pattern.  We then have

$\displaystyle \bigcup_{i\in\mathbb{N}} A_i =\mathbb{R} \cup \{!\} \cup \emptyset \cup \mathbb{R} \cup \{!\} \cup \emptyset \cup \mathbb{R} \cup \{!\} \cup \emptyset \cdots = \mathbb{R} \cup \{!\}$

In some ways this was a very silly example.  After all, we didn’t have infinitely many distinct sets to union, we just unioned together the same three sets over and over again.  Still, this example helps solidify our two main points, which are worth repeating here.

1. The index parameter $i$ is not (necessarily) needed to write out the final set.
2. The index set (in this case $\mathcal{I} = \mathbb{N}$) does not (necessarily) determine the elements of any of the sets $A_i$.

Example (5).  Let us create an infinite family of sets each of which is described using the index $i \in \mathcal{I} = \mathbb{N}$.  Similar to our homework problems, let’s use

$\displaystyle A_i = [0, 1/i] = \{x \in \mathbb{R} : 0 \leq x \leq 1/i\} \subseteq \mathbb{R}$.

For example, here are a few of the (infinitely many) sets we’ll be union-ing together:

$A_1 = [0, 1] = \{x \in \mathbb{R} : 0 \leq x \leq 1\}, A_{20} = [0, 20] = \{x \in \mathbb{R} : 0 \leq x \leq 1/20\}$, and $A_{10000} = \left[0, \frac{1}{10000}\right].$

In this example, the index $i \in \mathbb{N}$ still has the responsibility of keeping track of the individual sets being unioned, but it also serves another purpose: each set $A_i$ is not just labelled with an $i$, but its elements are also described in terms of the value of $i$.

The index here is a natural number, $i \in \mathbb{N}$, that is being used to label our sets and to define or describe our sets.  However, the fact that $i$ is a whole number does not change or impact the fact that the sets being unioned contain elements that are not just whole numbers.

It is not too difficult o convince yourself that the larger $i$ becomes, the smaller the interval of real numbers $A_i$ becomes.  Indeed, one can see that for any value of our index, it follows that $A_{i+1} \subseteq A_i$ (perhaps the easiest way to see this is to draw some pictures of these intervals).  It then follows that

$\displaystyle \bigcup_{i\in\mathbb{N}} A_i = [0, 1] \cup [0, 1/2] \cup [0, 1/3] \cup \cdots = [0, 1]$

### A Super-Infinite Union?

We now come to what I think is an especially tricky example, at least upon first glance.  Although we are blessed / cursed with finite minds, thinking of an infinite collection of sets indexed by the counting numbers is not altogether too terrible.  In Examples (4) and (5) above, we could have used the words

$\displaystyle \bigcup_{i\in\mathbb{N}} A_i = \text{ an } \mathbb{N}\text{'s worth of sets unioned together}$

to describe the process by which we produced the new, big-unioned set.  Another way to talk about it is to say that we performed a discretely infinite union; after all, the natural numbers can be thought of as a discrete (albeit infinite) set of points that go on forever.

What happens, though, when our index set is even more complicated?  For instance, what happens when we have a collection of sets $A_i$ not only for each natural number but for each real number, $i \in \mathbb{R}$?  In this instance we could say something like this:

$\displaystyle \bigcup_{i\in\mathbb{R}} A_i = \text{ an } \mathbb{R}\text{'s worth of sets unioned together} = \text{ a real line's worth of sets unioned together}.$

We could also describe it as a continuous union of infinitely many sets.  The main issue we have with this union / indexing is that we cannot write out something like

$\displaystyle \bigcup_{i\in\mathbb{R}} A_i = A_1 \cup A_2 \cup A_3 \cdots$

since doing so excludes the real-number-indexed sets like $A_{1/2}$ and $A_{e}$.  In other words, because we cannot (yet?  ever?) list out the real numbers like we can the naturals, we are not able to write this union as an infinite list of unions.  This, of course, is troublesome, but depending on the sets $A_i$ being used, the difficulties can be avoided.

Example 6.  If we use, for example, $A_i = \{1, \, g\}$ for every value of $i$ — that is, we have a “constant set”, then it follows

$\displaystyle \bigcup_{i\in\mathbb{R}} A_i = \bigcup_{i\in\mathbb{R}} \{1, \, g\} = \{1, \, g\}$

As in our examples that use finitely many indices and/or a natural-number’s worth of indices, the final set can be written out explicitly (and also without use of the index $i$).

Example 7.  Let’s consider a real line’s worth of one-element sets $A_i = \{i\}$.  For example, $A_0 = \{0\}, A_1 = \{1\}$, and $A_{\sqrt{2}} = \{\sqrt{2}\}$.  Can you explain why

$\displaystyle \bigcup_{i\in\mathbb{R}} A_i = \mathbb{R} \text{ ?}$

Example 8.  In this example we’ll use a real line’s worth of interval-subsets of the real numbers, specifically setting $A_i = [0, i^2]$.  Then

$\displaystyle \bigcup_{i\in\mathbb{R}} A_i = \bigcup_{i\in\mathbb{R}} [0,i^2] = [0, \infty)$.

You should be able to convince yourself that this is true by thinking about the facts that (1) $A_i \subseteq A_{i+1}$ for every value of the index $i \geq 1$, (2) $[0, i^2] \subseteq [0, (i+1)^2]$ for $i \geq 1$.  A picture of several of these intervals $A_i$ will likely help.

Example 9.  We can, of course, also use not an entire real-line’s worth of sets, but, say, an intervals worth of sets.  If we use $\mathcal{I} = [0, 1] = \{x \in \mathbb{R} : 0 \leq x \leq 1\}$, then we can use any of the $A_i$‘s from the previous examples to form

$\displaystyle \bigcup_{i \in [0,1]} A_i$

For example, if we use the sets from Example 8 so that each $A_i = [0, i^2]$ is itself an interval of real numbers, you should be able to convince yourself that

$\displaystyle \bigcup_{i\in[0,1]} A_i = [0, 1]$.