From c3f574d1d486d755798b69030836061d37257de2 Mon Sep 17 00:00:00 2001
From: Harold <>
Date: Mon, 5 Jul 2010 16:37:06 +0000
Subject: added cardinalities and (hopefully) proofs for N=N*N, N=Q, R>N,
 R=(0,1), R=[0,1], and R=2^N

---
 Problem Set 2.page | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/Problem Set 2.page b/Problem Set 2.page
index a6ed816..f853de1 100644
--- a/Problem Set 2.page	
+++ b/Problem Set 2.page	
@@ -89,8 +89,13 @@ $$\int_0^{2\pi} \sin^4(x) dx = \sum |a_n|^2 = \frac{3 \pi}{4}$$
 
 ## Cardinality
 
-Cardinality of the natural numbers (countable): $\mathbf{N}$,$\mathbf{Z}$  
-Cardinality of the real numbers (continuum): $\mathbf{R}$
+Cardinality of the natural numbers (countable): $\mathbf{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\}$.
\ No newline at end of file
+- $\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 provides a good description thereof: http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument. 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{pi*n-pi/2}.
+-$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 natural 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}$.
\ No newline at end of file
-- 
cgit v1.2.3