Protected: FOM: PoW 3

This content is password protected. To view it please enter your password below:


Protected: FOM Test (due 10.16.15)

This content is password protected. To view it please enter your password below:

FOM Proof Challenge


By the start of class on Friday, September 25th, you should post on your blogs an attempt at proving the following:

\forall a \in \mathbb{Z}, a \text{ is even } \iff a^2 \text{ is even}

I should also point out that the definition of even is this: an integer z \in \mathbb{Z} is even if there exists n \in \mathbb{Z} such that z = 2n.

Note that this is not an assignment — you are not required to post this.  However, if everyone posts an attempt at this proof by the start of class on Friday, then your mid-term will be a very lovely experience.

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

FOM Assignment 2 (due 9.18.15)

Finish reading chapter 1 and begin reading pages 31-60 (Chapter 2)

  • Exercises 2, 4, 5, 6, 8, 12 from 1.7
  • Exercises 1, 4, 5, 9, 10a from 1.8
  • Exercises 1, 6, 12, 14 from 2.1
  • Exercises 1, 2, 3, 5, 14 from 2.2
  • Bonus 1: Is it true that \mathbb{R} \subseteq \mathbb{R}^2?  Is it true that \mathbb{R} \subseteq \mathbb{R}^3?
  • Bonus 2: Give any two sets, A and B, is it true that A \subseteq A \times B?
  • Bonus 3: When are Casey’s office hours?

Also, here is a link to an excellent paper on the crises in mathematics.

Also, check out this video as it may give you an even deeper, more comprehensive view of mathematics:

Second Day Musings

Our second day of class went fairly well, I thought.  Students appeared to be working well together, building consensus (or at least near-consensus) on the truth or falsity of four statements.  As a refresher, here they are:

  1. Given any triangle, there is always a circle that can be inscribed in it.
  2. For ever integer n \geq 2 it is possible to choose n points on a circle in such a way that if you connect every pair of points with straight line segments, the circle will be divided into 2^{n-1} regions.
  3. Let n \sharp be the product of the first n primes.  For every positive integer n, n \sharp+1 is prime.
  4. Every even number greater than 2 can be written as p+q, where p and q are both prime numbers.

Since this class is all about proving things, I offer the following image as proof that, indeed, students were working on these true or false statements:


As we discussed in class, no one yet has an answer to the fourth statement.  I don’t mean no one in our class, I mean no one, anywhere.  (I suppose its possible that someone out there has an argument that demonstrates whether this is true or false and has chosen not to share it… let’s ignore that unlikely possibility.)  Indeed, this is a famous conjecture, one called Goldbach’s Conjecture.

I think there is a good lesson here.  Perhaps even multiple lessons.  For instance, I think its important for FOM students to keep in mind that I might be trolling you.  Yes, I had heard of this conjecture before compiling this assignment.  Yes, I intentionally included it amongst other statements that can, actually, be argued true or false.  Another lesson (hopefully?) learned here: mathematics is incomplete.  There are lots and lots of mathematical statements that we can’t yet decide are true or false.  In fact, this is what mathematical research is all about, finding new statements and proving whether or not they are true or false.  What’s even better — and we’ll talk about this later in the semester — there are even mathematical statements that can never be proven true or false!  Its crazy, I know, but there it is: sometimes a statement can never be proven true nor can it ever be proven false.

I will probably post another entry concerning my Blue Eyed Faculty story, but for now I raise my glass to this year’s FOM class(es).  Cheers to an intoxicating semester!