Sequentially Compact --> Compact

Recently in our UCLA summer analysis course we discussed the equivalence of compactness and sequential compactness for subsets of a metric space. I thought of a proof which I thought to be considerably shorter and simpler than those usually given. However it requires Zorn's Lemma, so it is perhaps not as fundamental.

Theorem. A sequentially compact subset of a metric space is compact.

Proof. Suppose $A \subset M$ (where $M$ is a metric space) has an open cover with no finite subcover. Let this cover be given by $C=\{O_i\}_{i\in I}$, where $I$ is an arbitrary indexing set (could be uncountable). Subcovers of $C$ are partially ordered by inclusion, and every chain of subcovers has a minimal element (given by the intersection of all of its elements). Thus by Zorn's Lemma we can assume that ${C}$ has a minimal subcover, which we will call ${C}'=\{O_k\}_{k\in K}$.

We now argue that each $O_k \in C'$ has an element $x_k$ such that $x_k \in {O}_j$ if and only if $j=k$. Indeed if we had an open set $O_k$ such that every element $x \in O_k$ was contained in some other open set in $C'$, the collection ${C}''={C}'-\{O_k\}$ would be an open cover and obviously a proper subset of ${C}'$, contradicting the assumption that ${C}'$ is a minimal subcover.

By the axiom of choice ${C}'$ has a countable subset $\{O_1,\ldots \}$. Out of each $O_i$ we pick an element $o_i$ such that $o_i \in O_j$ if and only if $i=j$ (guaranteed to exist by previous paragraph). Thus $\{o_i\}_{i=1}^\infty$ is a sequence. It could not have a convergent subsequence because then the limit point $o$ would be in some set $O_m \in {C}'$, which would then necessarily contain some $o_i$ with $i \ne m$.

On Approximating Continuous Functions by Polynomials

In theoretical analysis and also numerical work, we often would like to approximate complicated functions with ones that are more easily managed. It turns out that, given a continuous function $f: [0,1] \rightarrow \mathbb{R}$, the sequence of Bernstein polynomials given by $p_n(x)=\sum_{k=0}^n {n \choose k}f(\frac{k}{n})x^k (1-x)^{n-k}$ converges uniformly to $f$ as $n \rightarrow \infty$. Here ${n \choose k}$ is the familiar binomial coefficient, given by ${n \choose k} = \frac{n!}{k!(n-k)!}$

Before validating this assertion with a proof, it is worthwhile to explain what might have motivated it in the first place. Indeed, the quantity ${n \choose k} x^k (1-x)^{n-k}$ is simply the probability of $k$ successes in $n$ Bernoulli trials, where a success occurs with probability $x$.

We can thus view ${n \choose k} x^k (1-x)^{n-k}$ as the probability of getting $k$ heads in $n$ flips of a coin (not necessarily fair), where the probability of a head is $x$. And $f(\frac{k}{n})$ can be seen as representing the payout when exactly $k$ heads are flipped. The expected value of the payout is thus $p_n(x)=\sum_{k=0}^n {n \choose k}f(\frac{k}{n})x^k (1-x)^{n-k}$.

Now, as $n$ gets bigger and bigger, the law of large numbers states that the probability of getting $k$ heads will be very small for most $k$, but large for $k/n$ close to $x$. Thus as $n$ increases, the payout clusters around $f(x)$. So for large $n$, we would expect $p_n(x)$, the expected value of the payout, to be $f(x)$.

Our intuition seems reasonable, but what we have written is hardly a rigorous proof. Rather than providing one, we refer the reader to the standard treatment given in Elementary Classical Analysis by Marsden and Hoffman.

Diagonalization Proofs and the Existence of Uncountable Sets

Many students encounter the proof that the cardinality of the power set of a set $S$ is strictly greater than the cardinality of $S$. The proof of this may at first appear somewhat contrived and lends itself to being forgotten easily. I will try to introduce the subject in a way that makes it seem more intuitive and also easier to remember.

First we consider the set $S$ of all binary sequences (strings of zeroes and ones), and we ask if $S$ is countable. It turns out that it isn't, and the most intuitive way to prove this is by contradiction. Thus, we shall suppose that $S$ is countable, pick an enumeration, and then show that there exists a binary sequence that is not in the enumeration.

Let $s_1, s_2, \ldots$ be an enumeration of $S$, and let $s_{ij}$ denote the $j$th term of the $i$th sequence.

Let $(t_k)$ be the sequence given by $t_k=0$ if $s_{kk}$=1 and $t_k=1$ if $s_{kk}=0$. By construction this is a binary sequence, and so must be in $S$, but it can't be in the above enumeration because it differs from $s_i$ in the $s_{ii}$ term.

This is our desired contradiction, and so it follows that $S$ is uncountable.

From this follows pretty easily the uncountability of the real numbers (by producing the appropriate injections and applying the Cantor-Bernstein Theorem).

In general, we have the following theorem:

Theorem. $|P(S)|>|S|$

Proof. It is fairly easy to see that $|P(S)| \geq |S|$. Suppose for contradiction that $|S| = |P(S)|$. Thus there exists a bijective function $f:S \rightarrow P(S)$. Similarly to the above argument, we will construct a set that cannot be in the range of this function. Let $A_0$ be the set consisting of all elements $n$ that satisfy $n \notin f(n)$. This is rather similar to what we did with the binary sequences - if an element is not contained in its image under $f$, we put it in the set, and otherwise we leave it out. This way our set differs from $f(n)$ for each $n$.

We thus suspect that $A_0$ cannot be in the range of $f$. Suppose it is. Then $A_0 = f(N)$ for some $N$. But then we can ask if $N\in A_0$, and we get the contradictions $N \in A_0 \rightarrow N \notin A_0$ (and vice versa).