## Countability

1. Group the following sets according to their cardinality:

    a. $\mathbb{N} = \{ 1,2,3,4,\dots \}$
    - $\mathbb{Z} = \{ \dots, -2, -1,0,1,2, \dots \}$
    - $\mathbb{N} \times \mathbb{N}$
    - $\mathbb{Q}$ = Set of all fractions $\frac{n}{m}$ where $n,m \in \mathbb{Z}$
    - $\mathbb{R}$
    - The open interval $(0,1) = \{ x \in \mathbb{R} : 1 < x < 1 \}$
    - The closed interval $[0,1] = \{ x \in \mathbb{R} : 0 \leq x \leq 1 \}$
    - $2^{\mathbb{N}}$ = Set of all subsets of $\mathbb{N}$.
    - $2^{\mathbb{R}}$ = Set of all subsets of $\mathbb{R}$.
    - $\mathbb{R}^{\mathbb{R}}$ = Set of all functions from $\mathbb{R}$ to itself.

Cook up other examples and post them on the wiki!

2. Let $X$ be any set.  Show that the cardinality of $2^{X}$ is larger than the cardinality of $X$.  
(Hint: Let $f: X \to 2^X$ be a bijection.  Consider the set of all elements $x \in X$ such that $x$ is not an element of $f(x)$.)

## Fourier Series


1. Compute the Fourier Series of the following functions.  Do both the exponential and sin/cos expansions.
    a. $f(x) = \sin^3(3x)\cos^2(4x)$
    - $g(x) = x(x-2\pi)$  
      (Hint: Use integration by parts)

2. Show that  
$$\int_0^{2\pi} \sin^4(x) dx = \frac{3 \pi}{4}$$  
(Hint: write out the exponential fourier expansion of $\sin^4(x)$.)

3. Compute the exponential Fourier coefficients of $\sin^2(x)$:  
$$a_n = \frac{1}{\sqrt 2\pi} \int_0^{2\pi} \sin^2(x) e^{-inx} dx$$  
and use this to verify that  
$$\int_0^{2\pi} |\sin^2(x)|^2 dx = \sum |a_n|^2.$$  

# Solutions

##Fourier Series
2. Since $\sin x = \frac{e^{ix}-e^{-ix}}{2}$,

$$\begin{array}{ccl} \sin^4 x &=& \frac{{( e^{ix}-e^{-ix} )}^4}{16} \\
  &=& \frac{e^{i 4x}+e^{-i 4x}-4 e^{i 2x} -4 e^{-i 2x}+6}{16}. \end{array} $$

If we express any periodic function $f(x)$ as 

$$f(x) = \sum a_n f_n(x),$$

where $f_n(x) = \frac{e^{inx}}{\sqrt{2\pi}}$ and $f_0(x) = \frac{1}{\sqrt{2\pi}}$, then the Fourier coefficients for the above functions are:

$$\begin{array}{rcl} a_{-4} = a_{4} &=& \sqrt{2\pi} \times 1/16, \\
 a_{-2} = a_{2} &=& - \sqrt{2\pi} \times 4/16 \\
 a_0 &=& \sqrt{2\pi} \times 6/16 \end{array} $$


Since $a_m = < f_m, f >$ and setting $f(x) = \sin^4(x)$,

$$ \begin{array}{ccl} \int_0^{2\pi} \sin^4(x) dx = <1, f> &=& \sqrt{2\pi} \times < f_0, f > \\
&=& \sqrt{2\pi} \times a_0 \\ 
 &=& \frac{3 \pi}{4} \end{array} $$


3. Since $\sin x = \frac{e^{ix}-e^{-ix}}{2}$, we have $\sin^2 x = \frac{e^{i 2x}+e^{-i 2x}-2}{4}$.  Therefore,

$$ \begin{array}{ccl} a_m &=& \frac{1}{\sqrt 2\pi} \int_0^{2\pi} \sin^2(x) e^{-imx} dx \\
  &=& \frac{1}{\sqrt 2\pi} \int_0^{2\pi} \frac{e^{i 2x}+e^{-i 2x}-2}{4} e^{-imx} dx \\
  &=& \frac{1}{\sqrt 2\pi} \int_0^{2\pi} \frac{e^{-i (m-2)x}+e^{-i (m+2)x}-2e^{-imx}}{4} dx.  \end{array} $$

Because $\int_0^{2\pi} e^{inx} dx = 2\pi$ for $n = 0$ and $\int_0^{2\pi} e^{inx} dx = 0$ for $n \neq 0$, we have

$$a_2 = \frac{1}{4 \sqrt{2\pi}} \times 2\pi = \frac{\sqrt{2\pi}}{4},$$

$$a_0 = \frac{1}{4 \sqrt{2\pi}} \times 2\pi \times (-2) = - \frac{\sqrt{2\pi}}{2},$$

and

$$a_{-2} = \frac{1}{4 \sqrt{2\pi}} \times 2\pi = \frac{\sqrt{2\pi}}{4}.$$

It follows that

$$\sum |a_n|^2 = {(\sqrt{2\pi}/4)}^2 + {(- \sqrt{2\pi}/2)}^2 + {(\sqrt{2\pi}/4)}^2 = \frac{3 \pi}{4}$$.

It was shown in Prob 2 that $\int_0^{2\pi} \sin^4(x) dx = \frac{3 \pi}{4}$, so therefore, 

$$\int_0^{2\pi} \sin^4(x) dx = \sum |a_n|^2 = \frac{3 \pi}{4}$$



## Cardinality

1. Cardinality of the natural numbers (countable): $\mathbb{N}$,$\mathbf{Z}$,$\mathbb{N} \times \mathbb{N}$,$\mathbb{Q}$

Cardinality of the real numbers (continuum): $\mathbf{R}$,the open interval $(0,1)$,the closed interval $[0,1]$,$2^{\mathbb{N}}$

Proofs:  
- $\mathbf{Z}=\mathbf{N}$ under the bijection $n \mapsto 2n+1$ for nonnegative $n$ and $n \mapsto 2|n|$ for negative $n$. For example, $\{-2,-1,0,1,2\} \mapsto \{4,2,1,3,5\}$.

-$\mathbb{N} \times \mathbb{N}=\mathbf{N}$ under the bijection $n \mapsto {(n_1+n_2-1)\choose 2}+n_1$. For example, $\{(1,1),(1,2),(2,1),(1,3),(2,2),(3,1)\} \mapsto \{1,2,3,4,5,6\}$.

-$\mathbb{Q}=\mathbf{N}$ by combining the bijections from $\mathbf{N}$ to $\mathbf{Z}$ and from $\mathbf{N}$ to $\mathbb{N} \times \mathbb{N}$. This provides a bijection from $\mathbf{N}$ to $\mathbb{Z} \times \mathbb{Z}$, and since every element of $\mathbb{Q}$ can be represented as the ratio of the two components of an ordered pair of integers, we have a bijection from $\mathbb{Z} \times \mathbb{Z}$ to $\mathbb{Q}$.

-Josh explained Cantor's proof of the uncountability of the real numbers on the 28th; [Wikipedia](http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument) provides a good description thereof. In a nutshell, you assume you can have an ordered list of the reals (i.e., a bijection to the naturals), then construct a real number not on that list by having its nth digit be different from the nth digit of the nth number on the list.

-$(0,1)=\mathbf{R}$ and $[0,1]=\mathbf{R}$ under the same bijection: $n \mapsto \tan\left (\pi n - \pi/2 \right)$.

-$2^{\mathbb{N}} = \mathbf{R}$ by writing a given real number $r$ as a (possibly infinite) set of natural numbers. For example, write $pi$ as the set of rational numbers $\{3,0.1,0.04,0.001,0.005,...\}$, then replace each number with the natural number it would map to under the bijection $\mathbb{Q}=\mathbf{N}$.

2. So we assume that there is some bijection $f$ between all the elements in $X$ and $2^X$. This means that we can map every element in $X$ to an element in $2^X$. For all the $x \in X$ atleast one $x$ must map to a set in $2^X$ that does not contain itself. This is true since, we know that the empty set is a member of $2^X$, so one of the elements in $X$ must map to the empty set.So lets look at all the $x \in X$ that map to sets in $2^X$ that do not contain the element x. All of these elements that map to an element in $2^X$ that do not contain themselves must be contained in another set that is a member of $2^X$. Since there is a bijection between $X$ and $2^X$, there must be some other  
$x \in X$ that points to this set we just created. However, if some other $x \in X$ points to this set, it also points to a set that does not contain itself. Therefore there must be some other set that contains just this element and an $x \in X$ must point to this set. Each time you try to create this set, you create another element that does not point to itself. Therefore, in order to have a bijection between $X$ and $2^X$ all $x \ in X$ must point to sets in $2^X$ that contain themselves, but we know that this isn't true since atleast one element in $X$ should point to the empty set.  

# Comments

Here are some issues with the above solutions.  Feel free to make corrections, even if you weren't the original poster.  However, if you do decide to redo a solution, please don't delete the old one, so that people can see where the old idea went wrong and how it was fixed.

- The map from $\mathbb{Z} \times \mathbb{Z}$ to $\mathbb{Q}$ sending a pair $(a,b)$ to a ratio $\frac{a}{b}$ is right in principle, but not exactly right.  One minor problem with it is that the map is not defined when $b = 0$.  Another more serious issue is that multiple pairs can map to the same rational.  For example the pairs $(2,1)$ and $(4,2)$ each map to the rational number $2$.  So, while it's true that every rational number is a ratio of some pair, it's not true that there's a \emph{unique} such pair.  To make it unique, you might demand that the pair be in lowest terms (and there's also an issue with negative numbers that you'd have to incorporate into the idea of lowest terms) but then you would have a bijection between some of $\mathbb{Q}$ with some subset of $\mathbb{Z} \times \mathbb{Z}$ rather than all of $\mathbb{Z} \times \mathbb{Z}$.  So a little bit more is needed to make this work.

- The bijection from $[0,1]$ to $\mathbb{R}$ doesn't work because the function given would send $0$ to $- \infty$ and $1$ to $+ \infty$.  Somehow there are two extra points you have to sneak in.  It might be helpful to consider the bijection from $\{0,1,2,3, \dots \}$ and $\mathbb{N} = \{1,2,3,\dots \}$ given by sending $n$ to $n+1$.  How could you modify this idea to put $[0,1)$ in bijection with $(0,1)$?

- The map from $\mathbf{R}$ to $2^{\mathbb{Q}}$ is not a bijection, since not every subset of the natural numbers is obtained in this way.  For example, the number $\frac{1}{3}$ is never contained in any of the subsets, since it has a repeating decimal expansion instead of a terminating one.  So for example the subset containing just the element $\frac{1}{3}$ is never hit by the map.  A hint for this problem is to think about binary expansions.