👈 Back to problem set index.
Optional Fun Problem: Infinite Deviation
On each problem set, we'll provide at least one Optional Fun Problem. These are problems that can be solved purely using the techniques you’ve learned so far, but which will require more thought than the other problems on the problem set. Each problem, in our opinion, has a beautiful solution that will give you a much deeper understanding of core concepts, so we strongly encourage you to play around with them if you get the chance.
These Optional Fun Problems have no bearing on your grade. However, if you successfully complete at least one Optional Fun Problem on five or more of the problem sets this quarter, we'll send you a certificate attesting to that fact and saying how impressed we are. (These certificates carry no official weight with the university, but are something we could mention in a recommendation letter.)
As a matter of course policy, we don't provide any hints on the Optional Fun Problems – after all, they're supposed to be a challenge! However, we're happy to chat about them after the problem sets come due.
In our first class, we sketched a proof of Cantor’s theorem. This proof assumed there was a pairing between the elements of a set $S$ and the subsets of $S$, then constructed a set that was different in at least one position from each of the paired sets.
Show that, no matter how you pair the elements of $\mathbb{N}$ with the subsets of $\mathbb{N}$, there’s always at least one set $X \subseteq \mathbb{N}$ that differs in infinitely many positions from each of the paired sets. Justify your answer, but no formal proof is necessary.