1. Some Practise with Sequences
Table of Contents | 2. Countability ≫Back when the dinosaurs still ruled the Earth, early Man knew of the natural numbers. Somewhere along the way, people started understanding the operation of division, giving rise to fractions and rational numbers.
The Greeks knew of the existence of irrational numbers. Long after the dinosaurs disappeared, American primary education defined an irrational number to be a (real) number that was not rational. But then what is a real number? Many American primary school textbooks define a real numbers to be number that is either rational or irrational.
Perhaps you have noticed that this is rather circular, and thus we are faced with a dilemma: either irrational numbers do not actually exist and the Greeks were wrong, or they do exist but must be constructed or characterised by their relation to rational numbers. As the Greeks were undeniably infallible, the latter must be true.
Perhaps some of you have seen an alternative definition of real numbers that isn’t circular: it can be defined (loosely) as any number that admits a (potentially infinite) decimal expansion. Put another way, a real number is anything that can be approximated by a rational number to an arbitrary degree of precision. For instance, \(\pi\) is the “limit” of the sequence \(3, 3.1, 3.14, 3.141, 3.1415, \ldots\)
In a sense, the rational numbers \(\mathbb{Q}\) have a lot of “holes” in them — numbers that “should” exist like \(\pi\), but don’t (yet).
Remark 1.
If you have studied topology before (Math 121), one way to describe how “holey” \(\mathbb{Q}\) is by showing that \(\mathbb{Q}\) is totally disconnected under the subspace topology inherited from \(\mathbb{R}\)!
We’ll be “filling in” these holes later, as this will be important to even define things such as infinite series and integrals. For now, we’ll be doing some practise problems that involve sequences and limits.
Problem 1.
Suppose \(a_n\leq M\) for some fixed \(M\) and for all \(n\). Suppose additionally that \(a_1\leq a_2\leq a_3\leq\cdots\). Show that given any \(\epsilon>0\) that \(\exists n_\epsilon\) such that \(\left\lvert a _{n_1} - a _{n_2} \right\rvert< \epsilon\) for all \(n_1, n_2\geq n _{\epsilon}\).
Hint
Use a proof by contraposition! Keep the assumptions of the statement, but negate the conclusion. Suppose that \(\left\lbrace a_n \right\rbrace\) is as in the problem statement, but suppose that there exists some \(\epsilon > 0\) such that for every \(n\), there exist \(n_1, n_2\geq n\) such that \(\left\lvert a _{n_1} - a _{n_2} \right\rvert \geq \epsilon\).
The main idea of a proof by contraposition is: if you are trying to prove the statement “\(P\) implies \(Q\)”, it’s the same thing as proving “not \(Q\) implies not \(P\)”. (This is the contrapositive of the original statement.)
A good trick for negating statements is that you should turn every “for all” into a “there exists” and replace every “there exists” with a “for all” in the conclusion. Of course, you also need to flip all the inequalities.
Note: I originally called this a proof by contradiction, but it’s really not that — here, we show “not (Q) implies not (P)”, whereas a proof by contradiction is “show that (P) and not (Q) is never true”. They are very slightly different, and I’m sorry for the mistake!
Solution (Using Contrapositive)
Suppose that there exists some \(\epsilon > 0\) such that for every \(n\), there exist \(n_1, n_2\geq n\) such that \(\left\lvert a _{n_1} - a _{n_2} \right\rvert \geq \epsilon\). Fix such an \(\epsilon\).
Let \(m_1=1\). By assumption, there exists some \(n_1,n_2\geq m_1\) such that \(\left\lvert a _{n_1}-a _{n_2} \right\rvert \geq \epsilon\); let \(m_2=\max \left( n_1,n_2 \right)\). Then \(a _{m_2}- a _{m_1} \geq \epsilon\). (Why?)
Inductively continue this sequence: given some \(m_i\), one may define a \(m _{i+1}\) by repeating the above process. By assumption, there exist some \(n_1,n_2\geq m_i\) such that \(\left\lvert a _{n_1}- a _{n_2} \right\rvert> \epsilon\). After selecting \(m _{i+1}=\max \left( n_1, n_2 \right)\), we get \(a _{m_{i+1}} - a _{m_i} \geq \epsilon\).
We have now found a subsequence \(\left\lbrace a _{m_i} \right\rbrace\) such that each term increases by at least \(\epsilon\). But this means that the sequence \( \left\lbrace a_n \right\rbrace\) is unbounded! This proves the contrapositive of the problem. \(\square\)
Solution (Direct Proof)
Fix any \(\epsilon>0\). Let \(j\) be the largest integer such that \(M-j\epsilon\) is still an upper bound for the sequence \(\left\lbrace a_n \right\rbrace\). Such a \(j\) does exist: \(j\) is at least \(0\) since \(M\) is already an upper bound, and \(j\) cannot be larger than \(\frac{M-a_n}{\epsilon}\) for any \(n\). (We are, at some level, applying the well-ordering principle here.)
Let \(M’=M-j\epsilon\), which is an upper bound of \(\left\lbrace a_n \right\rbrace\). By construction, \(M’-\epsilon=M-(j+1)\epsilon\) cannot be an upper bound of \(\left\lbrace a_n \right\rbrace\), so there exists some \(n_\epsilon\) such that \(a _{n_\epsilon}\geq M’-\epsilon\). But then \(a_n\) is between \(M’-\epsilon\) and \(M’\) for all \(n\geq n_\epsilon\)! It follows that for any \(n_1\geq n_2\geq n_\epsilon\), \[\left\lvert a _{n_1}-a _{n_2} \right\rvert=a _{n_1}-a _{n_2}\leq M’-\left( M’-\epsilon \right)=\epsilon.\] \(\square\)
Some Comments
Some people tried using a direct proof that used a least upper bound of the sequence. This is good because if \(M_0\) is the least upper bound, then for every \(\epsilon>0\), there exists an \(n_\epsilon\) such that \(a _{n_\epsilon}>M_0-\epsilon\); this is what makes our argument work. However, we have not constructed the real numbers yet, and we cannot use least upper bounds!
At the end of the day, the two proofs have very similar flavours. The first proof argues that if the conclusion is false, then the sequence will “step up” by \(\epsilon\) infinitely many times, contradicting boundedness. The second proof argues that if the sequence is bounded, one can lower the bound to “within an \(\epsilon\)” of the sequence, which allows us to control how spread out the sequence is.
Problem 2.
Given two monotone nondecreasing sequences \(\left\lbrace a_n \right\rbrace\) and \(\left\lbrace b_n \right\rbrace\) each bounded above, define a relation \(\left\lbrace a_n \right\rbrace\sim \left\lbrace b_n \right\rbrace\) if \(\lim _{n\to\infty} \left\lvert a_n-b_n \right\rvert=0\). Determine if the following statement is true or false:
If \(\left\lbrace a_n \right\rbrace\sim \left\lbrace b_n \right\rbrace\) and \(\left\lbrace c_n \right\rbrace\sim \left\lbrace d_n \right\rbrace\), then \(\left\lbrace a_n+c_n \right\rbrace\sim \left\lbrace b_n+d_n \right\rbrace\).
Hint
Solution
By definition, \(\left\lbrace a_n+c_n \right\rbrace\sim \left\lbrace b_n+d_n \right\rbrace\) if \(\lim _{n\to\infty} \left\lvert \left( a_n+c_n \right)-\left( b_n+d_n \right) \right\rvert=0\). By definition, this means that for each \(\epsilon>0\) there exists some \(n _{\epsilon}\) such that for all \(n > n _{\epsilon}\), \[\left\lvert \left( a_n+c_n \right)-\left( b_n+d_n \right) \right\rvert< \epsilon.\] By the triangle inequality (see the hint above), we have that \[\left\lvert \left( a_n+c_n \right)- \left( b_n+d_n \right) \right\rvert = \left\lvert \left( a_n-b_n \right) + \left( c_n-d_n \right) \right\rvert \leq \left\lvert a_n-b_n \right\rvert+ \left\lvert c_n-d_n \right\rvert.\] The idea is that both quantities at the very right should “eventually be very small”, and this forces the quantity at the left to be “eventually be very small” as well. This is what we want!
Fix an \(\epsilon>0\). Since \(\left\lbrace a_n \right\rbrace\sim \left\lbrace b_n \right\rbrace\), \(\lim _{n\to\infty} \left\lvert a_n-b_n \right\rvert=0\). Thus, there exists some \(N_1\) such that whenever \(n\geq N_1\), \(\left\lvert a_n-b_n \right\rvert < \frac{\epsilon}{2} \). Similarly, since \(\left\lbrace c_n \right\rbrace\sim \left\lbrace d_n \right\rbrace\), \(\lim _{n\to\infty}\left\lvert c_n-d_n \right\rvert=0\), so there exists some \(N_2\) so that whenever \(n\geq N_2\), \(\left\lvert c_n-d_n \right\rvert< \frac{\epsilon}{2} \).
Let \(n _{\epsilon}=\max\left( N_1,N_2 \right)\). If \(n \geq n _{\epsilon}\), then \(n\geq N_1\), so \(\left\lvert a_n-b_n \right\rvert < \frac{\epsilon}{2}\). Similarly, if \(n\geq n _{\epsilon}\), then \(n\geq N_2\), so \(\left\lvert c_n-d_n \right\rvert< \frac{\epsilon}{2}\) as well. Using the triangle inequality from before, we get that for all \(n \geq n _{\epsilon}\) that \[\left\lvert \left( a_n+c_n \right)-\left( b_n+d_n \right) \right\rvert <= \left\lvert a_n-b_n \right\rvert+\left\lvert c_n-d_n \right\rvert< \frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon.\] This works for any \(\epsilon>0\), so we conclude that \(\lim _{n\to\infty}\left\lvert \left( a_n+c_n \right)-\left( b_n+d_n \right) \right\rvert=0\). Thus, \(\left\lbrace a_n+b_n \right\rbrace\sim \left\lbrace c_n+d_n \right\rbrace\) by definition. \(\square\)
Problem 3.
This problem is not directly related to this class, but it is a fun exercise that demonstrates a method of proof the other problems don’t use.
In a set of any six people named \(A, B, C, D, E, F\), show that there is a subset of three people that either all know each other or are all strangers to each other.
Hint
Solution
Let’s consider two cases:
- \(A\) knows at least \(3\) other people.
- \(A\) knows fewer than \(3\) other people. Necessarily, this means that \(A\) doesn’t know at least \(3\) other people.
Case 1: Suppose \(A\) knows at least \(3\) other people. Without loss of generality, we may assume that \(A\) knows \(B\), \(C\), and \(D\). If \(B\), \(C\), and \(D\) all don’t know each other, then we’ve found three people that don’t know each other. Otherwise, at least two of them know each other, say \(B\) and \(C\), hence \(A, B\), and \(C\) all know each other!
The second case is more or less the same argument.
Case 2: Suppose \(A\) doesn’t know at least \(3\) other people. Again, we may assume that \(A\) doesn’t recognise \(B\), \(C\), and \(D\). If these three strangers to \(A\) all know each other, we’re done! Otherwise, at least two of them don’t know each other, say \(B\) and \(C\); thus \(A\), \(B\), and \(C\) are all strangers to each other. \(\square\)
Problem 4.
Let \(\left\lbrace a_n \right\rbrace\) be any sequence such that \(\left\lvert a_n \right\rvert\leq M\) for some \(M\) and all \(n\). Show that there exists a subsequence \(\left\lbrace a _{n_j} \right\rbrace\) that is either monotone nonincreasing or monotone nondecreasing.
Note: this statement is often described as the “scenic viewpoint theorem”. Where do you think the name comes from?
Hint
Solution
Following the hint, we’ll consider two cases:
- The sequence \(\left\lbrace a_n \right\rbrace\) has infinitely many scenic viewpoints.
- The sequence \(\left\lbrace a_n \right\rbrace\) has finitely many scenic viewpoints.
Case 1: Let \(n_1\) be the first scenic viewpoint, \(n_2\) be the second scenic viewpoint, etc. Then \(\left\lbrace a _{n_j} \right\rbrace\) is a monotone nonincreasing subsequence — each scenic viewpoint “overlooks” the rest of them!
Case 2: Let \(N\) be the last scenic viewpoint in the sequence. Let \(n_1>N\). \(n_1\) can’t be a scenic viewpoint since it’s beyond the last scenic viewpoint in the sequence. Thus, there exists some \(n_2>n_1\) with \(a _{n_2} > a _{n_1}\). But \(n_2\) is also past the last scenic viewpoint, so it isn’t a scenic viewpoint!
We can repeat this construction inductively to produce a monotone increasing subsequence. Given the \(j\)-th term \(n_j\) of the subsequence, we know that it must be past the last scenic viewpoint and hence isn’t a scenic viewpoint itself. Thus, there exists some \(n _{j+1}> n_j\) such that \(a _{n _{j+1}} > a _{n_j}\).
By construction, we see that \(\left\lbrace a _{n_j} \right\rbrace\) is a monotone increasing subsequence, concluding the second case. \(\square\)