\documentclass[letterpaper,11pt]{article}
\title{18.100B Lecture Notes}
\renewcommand{\today}{February 12, 2006}

\input{../share/100B.tex}

\begin{document}
\maketitle

\theorem{
  \mbox{}
  \renewcommand{\labelenumi}{\alph{enumi})}
  \begin{enumerate}
  \item $\forall x \in \R \exists n \in \Z \st n > x$
  \item $\forall x,y \in R \st x < y, \exists p \in \Q \st x < p < y $
  \end{enumerate}

}

\proof{
  We proved (a) proved last class \\
  Choose a $n \in \Z > (y-x)^{-1} \Rightarrow \frac{1}{n} < y-x$ \\
  Now choose $m \in Z \st m-1 \leq nx < m $
  $$ \frac{m-1}{n} \leq x < \frac{m}{n} $$
  $$ \frac{m-1}{n} + \frac{1}{n} < x + y - x \Rightarrow \frac{m}{n}
  < y$$
}


\definition{$f:A \to B$ is
  \begin{description}
  \item[\dt{injective (1:1)}] if $f(a_1) = f(a_2) \implies a_1 = a_2$
  \item[\dt{surjective (onto)}] if $f^{-1}(b) \ne \emptyset \forall b\in B$
  \item[\dt{bijective}] if it is injective and surjective
  \end{description}
}


\definition{$A$ and $B$ can be put in \dt{1-1 correspondence} iff
  $\exists f:A\to B $ \st f is bijective.
  We write $A \sim B$ to indicate this.\\
  $\sim$ is reflexive, transitive, and symmetric. Thus, $\sim$ is an
  equivalence relation
}


\definition{Let $J_n = \{1,2,3,...n\}.\mbox{ } J = \N$
  \renewcommand{\labelenumi}{\alph{enumi})}
  \begin{enumerate}
  \item $A$ is \dt{finite} iff $A \sim J_n$ or $A = \emptyset$
  \item $A$ is \dt{countable} iff $A \sim J$
  \item $A$ is \dt{uncountable} iff A is infinite and not countable
  \end{enumerate}
}

\example{ $\Z$ is countable}

\theorem{If $A$ is countable, any infinite $E \subset A$ is countable}
\proof{We have a bijection $f:J \to A$. Define $g:J \to E$: \\
  $g(1) = f(n_1) $ Where $n_1$ is the first number in $f^{-1}(E)$ \\
  $g(k) = f(n_k) $ Where $n_k$ is the $k^{th}$ number in $f^{-1}(E)$
  \\
  $g$ is well-defined, surjective, and injective
}

\theorem{$\R$ is uncountable}
\proof{
  Consider $S$ defined as the set of infinite sequences of 0s and
  1s. Every $s \in S$ can be taken to represent a real number, so $S
  \subset R$.\\
  Let $s_i, i \in \N$ be a sequence of such sequences. Construct $s$
  to differ from each $s_i$ in the $i^{th}$ element. Clearly, $\forall
  i, s \ne s_i$.
}

\theorem{Let $\{E_n\}, n\in\N$ be a sequence of countable sets. Then
  $S = \bigcup_{n=1}^{\infty} E_n$ is countable.
}

\corollary{$\Q$ is countable.}
\proof{
  Define $E_n = \{\frac{m}{n} \forall m \in \Z \}$. $\Q =
  \union_{n=1}^{\infty} E_n$ Therefore, $\Q$ is countable.
}


\end{document}