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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s