Other Questions and Solutions
Selected solutions to various questions I find interesting or elegant.
$ \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\RP}{\operatorname{Re}} \newcommand{\IP}{\operatorname{Im}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\p}[1]{\left( #1 \right)} \newcommand{\qed}{\blacksquare} $
Chapter 1: Example Chapter
Exercise 1.1 Prove that $\sqrt{2}$ is irrational.
Proof
Suppose that $\sqrt 2$ is rational. Then it can be written as a fraction $$ \sqrt 2 = \frac{a}{b} $$ where $\gcd(a,b)$ = 1. By squaring both sides we see $$ a^2 = 2 b^2. $$ Since $a^2$ is a multiple of $2$, and $2$ is prime, we can conclude $a$ is even. Let $a = 2k$ for some $k \in \Z$. We now have: $$ a^2 = (2k)^2 = 4k^2 = 2b^2 \implies b^2 = 2k^2. $$ For the same reasons, $b$ is also even. Thus $\gcd(a, b) \geq 2$, contradicting our initial assumption.
$\qed$
1989 Putnam Exam B4 Does there exist an uncountable set of subsets of postive integers such that any two distinct subsets have finite intersection?
Proof
Yes! Consider the subset $(0,1)$ of $\R$ (any interval will work). Now, for each $x \in (0,1)$, there exists a sequence of rationals converging to $x$ (by the definiton of the reals). Denote a sequence converging to $x$ by $(x_n)$. Now for each $x \in (0,1)$, take exactly one sequence converging to $x$. Let $S$ be the set of the ranges of these sequences (Axiom of Choice!). $S$ is uncountable because $(0,1)$ is uncountable. Furthermore, we claim the intersection of any two elements of $S$ is finite. This is because for any $\{x_n\}, \{y_n\} \in S$, we know they converge to distinct reals, call them $x,y \in (0,1)$ respectively. Now, let $\varepsilon = \abs{x - y} / 2$, then by defintion of convergence there exists a $N \in \N$ such that both $\abs{x_n - x} < \varepsilon$ and $\abs{y_n-y} < \varepsilon$ $\forall n \geq N$. That is, there is only finite $x_n$ and $y_n$ that can potentially intersect (since $(x- \varepsilon, x + \varepsilon) \cap (y - \varepsilon, y + \varepsilon) = \emptyset$). So, $S$ is uncountable and the intersection of any two elements of $S$ is finite. Finally, since $\Q$ is countable, take a bijection $f: \Q \to \N^+$ and apply it to every rational number in a range of $S$ and call this new set of "ranges" $S^*$. That is, $S^* = \{ f(\{x_n\}) \mid {x_n} \in S\}$ where $f(\{x_n\})$ is understood to be the application of $f$ to each $x_n$. $f$ is a bijection so both the pairwise finite intersection property and uncountability of $S$ are preserved, thus $S^*$ gives the desired result.
$\qed$