\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}

\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

 
\begin{document}
\begin{flushright}
    \StrBefore{\currfilename}{.}
\end{flushright} \section*{Cardinality recap}



The set of positive integers $\mathbb{Z}^{+}$ is countably infinite.

The set of integers $\mathbb{Z}$ is countably infinite and is a proper superset of $\mathbb{Z}^{+}$. 
In fact, the set difference 
$$\mathbb{Z} \setminus \mathbb{Z}^{+} = \{ x \in \mathbb{Z} \mid x \notin \mathbb{Z}^+\} 
= \{ x \in \mathbb{Z} \mid x \leq 0 \}$$ is countably infinite.

The set of rationals 
$\mathbb{Q} = \left\{ \frac{p}{q} \mid p \in \mathbb{Z}  \text{ and  } 
q  \in \mathbb{Z} \text{ and } q \neq  0 \right\}$ is countably infinite.


The set of real numbers $\mathbb{R}$ is uncountable. In fact, the closed 
interval $\{x \in \mathbb{R} ~|~ 0 \leq x \leq 1\}$, 
any other nonempty closed interval of real numbers whose endpoints are 
unequal, as well as the related intervals that exclude one or both of the endpoints are
each uncountable.
The set of {\bf irrational} numbers $\overline{\mathbb{Q}} = \mathbb{R} - \mathbb{Q}
= \{ x \in \mathbb{R} \mid x \notin \mathbb{Q} \}$ is uncountable.

\vfill

We can classify any set as 
\begin{itemize}
\item {\bf Finite} size. Fact: For each positive number $n$, for any sets $X$ and $Y$ each 
size $n$, there is a bijection between $X$ and $Y$.
\item {\bf Countably Infinite}. Fact: for any countably infinite sets $X$ and $Y$, there is a bijection
between $X$ and $Y$.
\item {\bf Uncountable}. Examples: $\mathcal{P}(\mathbb{N})$, the power set of any infinite set, 
the set of real numbers, any nonempty interval of real numbers. Fact: there are (many) examples 
of uncountable sets that do not have a bijection between them.
\end{itemize} \vfill
\section*{Cardinality rationale for functions}


{\bf Key idea for cardinality}: Counting 
distinct elements is a way of labelling elements
with natural numbers. This is a function!
In general, functions let us 
associate elements of one set with those
of another. If the association is ``{\it good}", 
we get a correspondence between the elements of the subsets
which can relate the sizes of the sets. \vfill
\section*{Musical chairs analogy}


{\it Analogy}: Musical chairs

\begin{multicols}{2}
\includegraphics[width=1.8in]{../../resources/images/musicalchairs.png}
\columnbreak

People try to sit down when the music stops

Person\sun~ sits in Chair 1,
Person\smiley~ sits in Chair 2,

Person\frownie~  is left standing!
\end{multicols}
What does this say about the number of chairs and the number of people?

\vspace{100pt} \vfill
\section*{Injective functions visually}


Informally, a function being one-to-one means ``no duplicate images''.

\phantom{Draw finite domain, finite codomain picture with duplicate image.}
\vspace{50pt} \vfill
\section*{Cardinality lower bound definition}


{\bf Definition}:  For nonempty sets $A, B$, we say that {\bf the  cardinality of $A$ is  no  bigger than the cardinality of $B$}, 
and write $|A| \leq |B|$, to mean there is a  one-to-one function  with domain $A$  and codomain $B$.
Also, we define $|\emptyset| \leq |B|$ for all sets $B$. \vfill
\section*{Injective cardinality musical chairs}


{\it In the analogy}: The function $sitter: \{ Chair1, Chair2\} \to \{ Person\sun, Person\smiley, Person\frownie \}$ given
by $sitter(Chair1) = Person\sun$,  $sitter(Chair2) = Person\smiley$, is one-to-one and witnesses that 
\[
| \{ Chair1, Chair2\} | \leq |\{ Person\sun, Person\smiley, Person\frownie \}|
\] \vfill
\section*{Cardinality upper bound definition}


{\bf Definition}:  For nonempty sets $A, B$, we say that {\bf the  cardinality of $A$ is  no  smaller than 
the cardinality of  $B$}, and 
write $|A| \geq |B|$, to mean there is an onto function  with domain $A$  and codomain $B$.
Also, we define $|A| \geq |\emptyset|$ for all sets $A$.
 \vfill
\section*{Surjective cardinality musical chairs}


{\it In the analogy}: The function $triedToSit: \{ Person\sun, Person\smiley, Person\frownie \} \to  \{ Chair1, Chair2\} $ given
by $triedToSit(Person\sun) = Chair1$,  $triedToSit(Person\smiley) = Chair2$, 
$triedToSit(Person\frownie) = Chair2$, is onto and witnesses that 
\[
 |\{ Person\sun, Person\smiley, Person\frownie \}| \geq | \{ Chair1, Chair2\} |
\] \vfill
\section*{Cardinality properties}


{\bf Properties of cardinality}
\begin{align*}
&\forall A ~ (~  |A| = |A| ~)\\
&\forall A ~ \forall B ~(~ |A| = |B|  ~\to ~ |B| = |A|~)\\
&\forall A ~ \forall B ~ \forall C~ (~ (|A| = |B| ~\wedge~ |B| = |C|) ~\to ~ |A| = |C|~)
\end{align*}

{\it Extra practice with proofs:} Use the definitions of bijections to prove these properties. \vfill
\section*{Cardinality power sets}


{\it Recall}: When $U$ is a set, $\mathcal{P}(U) = \{ X \mid X \subseteq U\}$

{\it Key idea}: For finite sets, the power set of a set has strictly greater size than the set itself.
Does this extend to infinite sets?

{\bf Definition}: For two sets $A, B$, we use the notation $|A| < |B|$ to denote
$(~|A| \leq |B| ~) \land \lnot (~|A| = |B|)$.

\begin{alignat*}{4}
    &\emptyset = \{ \} \qquad &&\mathcal{P}(\emptyset) = \{ \emptyset \} \qquad &&|\emptyset| < |\mathcal{P}(\emptyset)| \\
    &\{1 \} \qquad &&\mathcal{P}(\{1\}) = \{ \emptyset, \{1\} \} \qquad &&|\{1\}| < |\mathcal{P}(\{1\})| \\
    &\{1,2 \} \qquad &&\mathcal{P}(\{1,2\}) = \{ \emptyset, \{1\}, \{2\}, \{1,2\} \} \qquad &&|\{1,2\}| < |\mathcal{P}(\{1,2\})| \\
\end{alignat*}

{\bf $\mathbb{N}$ and its power set}

Example elements of $\mathbb{N}$ 

\vspace{20pt}

Example elements of $\mathcal{P}(\mathbb{N})$

\vspace{20pt}

{\bf Claim}: $| \mathbb{N} | \leq |\mathcal{P} ( \mathbb{N} ) |$

\vspace{100pt}
\newpage
{\bf Claim}: There is an uncountable set.  Example: $\underline{\phantom{~~~\mathcal{P}(\mathbb{N})~~~}}$

{\bf Proof}:  By definition of countable, since $\underline{\phantom{~~~\mathcal{P}(\mathbb{N})~~~}}$
is not finite, {\bf to show} is $|\mathbb{N}| \neq  |\mathcal{P}(\mathbb{N})|$ .

Rewriting using  the definition of  cardinality, {\bf to show} is

\phantom{$\neg \exists f : \mathbb{N} \to \mathcal{P}(\mathbb{N})  ~~(f \text{ is a bijection})~~$}

\phantom{or equivalently $\forall f : \mathbb{N} \to \mathcal{P}(\mathbb{N})  ~~(f \text{ is not a bijection})~~$}


Towards a proof by  universal generalization,  consider  an arbitrary function $f:  \mathbb{N} \to\mathcal{P}(\mathbb{N})$.

{\bf To show}: $f$ is not a bijection.  It's enough to show that $f$ is not onto.

Rewriting using the definition of  onto, {\bf to show}:
\[
\neg  \forall  B \in  \mathcal{P}(\mathbb{N}) ~\exists a \in \mathbb{N}  ~(~f(a) =  B~)
\]
. By logical  equivalence, we can write this as an existential statement:
\[
\underline{\phantom{\qquad\qquad\exists B \in  \mathcal{P}(\mathbb{N}) ~\forall a \in \mathbb{N}  ~(~f(a) \neq  B~)\qquad\qquad}}
\]
In search of a witness, define the following  collection of nonnegative integers:
\[
D_f = \{ n \in \mathbb{N}  ~\mid~  n \notin f(n)  \}
\]
. By  definition  of power  set, since  all elements  of  $D_f$ are  in  $\mathbb{N}$,   $D_f \in \mathcal{P}(\mathbb{N})$.  It's enough to prove the following Lemma: 

{\bf Lemma}: $\forall a \in \mathbb{N}  ~(~f(a) \neq  D_f~)$.


{\bf Proof  of lemma}: \phantom{Towards universal  generalization, consider an arbitrary  $a \in \mathbb{N}$.
By definition  of set equality, {\bf to show} is  $\exists  x ( \neg  (x \in f(a)~  \leftrightarrow  ~x \in D_f))$.
For a witness, consider $x = a$.  There are two cases:  $a \in  f(a)~\vee~a \notin f(a)$. By definition 
of $D_f$, each guarantees that $f(a) \neq  D_f$.}\\

\vspace{50pt}

By  the Lemma, we  have proved that $f$ is not onto, and since $f$ was arbitrary, there are no onto
functions from $\mathbb{N}$ to $\mathcal{P}(\mathbb{N})$. QED


{\bf Where does $D_f$ come from?} The idea is to build a set that would ``disagree" with 
each of the images of $f$ about some element. 

\begin{center}
\begin{tabular}{c|c|ccccccc}
$n \in \mathbb{N}$ & $f(n) = X_n$ &  Is $0   \in X_n$?   & Is $1 \in X_n$?  &  Is $2 \in X_n$?  &  Is $3 \in X_n$?  &
 Is $4 \in X_n$?  &  \ldots & Is $n \in D_f$?\\
\hline
$0$ & $f(0) = X_0$ & {\bf  Y~/~N}  & Y~/~N & Y~/~N & Y~/~N &Y~/~N & \ldots & {\bf  N~/~Y }\\
$1$ & $f(1) = X_1$ & Y~/~N  & {\bf  Y~/~N} & Y~/~N & Y~/~N & Y~/~N & \ldots & {\bf  N~/~Y }\\
$2$ & $f(2) = X_2$ & Y~/~N  & Y~/~N & {\bf  Y~/~N} & Y~/~N &Y~/~N & \ldots & {\bf  N~/~Y }\\
$3$ & $f(3) = X_3$ & Y~/~N  & Y~/~N & Y~/~N & {\bf  Y~/~N} & Y~/~N & \ldots & {\bf  N~/~Y }\\
$4$ & $f(4) = X_4$ & Y~/~N  & Y~/~N & Y~/~N & Y~/~N &{\bf  Y~/~N} & \ldots & {\bf  N~/~Y }\\
\vdots
\end{tabular}
\end{center} \vfill
\section*{Cardinality rationals reals}


{\bf Comparing $\mathbb{Q}$ and $\mathbb{R}$} 


Both $\mathbb{Q}$ and $\mathbb{R}$ have no greatest element.

Both $\mathbb{Q}$ and $\mathbb{R}$ have no least element.

The quantified statement 
\[
    \forall x \forall y (x < y \to \exists z ( x < z < y) )
\]
is true about both $\mathbb{Q}$ and $\mathbb{R}$.

Both $\mathbb{Q}$ and $\mathbb{R}$ are infinite. But, $\mathbb{Q}$ is countably infinite
whereas $\mathbb{R}$ is uncountable.\\


{\bf The set of real numbers}

$\mathbb{Z} \subsetneq \mathbb{Q} \subsetneq \mathbb{R}$


{\bf  Order axioms} (Rosen Appendix 1): 

\begin{center}
\begin{tabular}{p{1.2in}p{4in}}
Reflexivity &  $\forall a \in  \mathbb{R} (a \leq a)$\\
Antisymmetry &  $\forall a \in  \mathbb{R}~\forall b \in \mathbb{R}~(~(a \leq b~ \wedge ~b \leq a) \to (a=b)~)$\\
Transitivity &  $\forall a \in  \mathbb{R}~\forall b \in \mathbb{R}~\forall c \in \mathbb{R}~
(~(a \leq b \wedge b \leq c) ~\to  ~(a \leq c)~)$ \\
Trichotomy & 
$\forall a \in \mathbb{R}~\forall b \in \mathbb{R}~ ( ~(a=b ~\vee~ b > a ~\vee~ a  < b)  $
\end{tabular}
\end{center}


{\bf  Completeness axioms} (Rosen Appendix 1): 


\begin{center}
\begin{tabular}{p{1.4in}p{6in}}
Least upper bound &  Every nonempty set of real numbers that 
is bounded  above has  a  least upper bound  
\\
Nested intervals &  For each sequence  of intervals  $[a_n , b_n]$
where, for each $n$, $a_n < a_{n+1} < b_{n+1} < b_n$, there
is at least one  real number $x$ such that, for all $n$, 
$a_n \leq x \leq b_n$.\\
\end{tabular}
\end{center}

Each real  number $r  \in  \mathbb{R}$ is described by a function to give better and better approximations
\[
x_r: \mathbb{Z}^+ \to \{0,1\}  \qquad  \text{where  $x_r(n ) =  n^{th} $ bit in  binary expansion of $r$}
\]
\begin{center}
\begin{tabular}{|c|c|p{3.9in}|}
\hline
$r$ & Binary expansion & $x_r$ \\
\hline
$0.1$ & $0.00011001 \ldots$ &  $x_{0.1}(n) = \begin{cases} 0&\text{if $n > 1$ and $(n~\text{\bf mod}~4) =2$} \\
0&\text{if $n=1$ or if $n > 1$ and $(n~\text{\bf mod}~4) =3$} \\1&\text{if $n > 1$ and $(n~\text{\bf mod}~4) =0$} \\
1&\text{if $n > 1$ and $(n~\text{\bf mod}~4) =1$} \end{cases}$  \\
&&  \\
\hline
$\sqrt{2} - 1 = 0.4142135 \ldots$  &$0.01101010\ldots$& Use linear approximations
(tangent lines from calculus) to get algorithm for bounding error of successive operations. Define 
$x_{\sqrt{2}-1}(n)$ to be  $n^{th}$ bit in approximation  that has error less than  $2^{-(n+1)}$.
\\
&& \\
\hline
\end{tabular}
\end{center}

\newpage 

{\bf Claim}: $\{  r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}$ is uncountable.

{\it Approach 1}: Mimic proof that $\mathcal{P}(\mathbb{Z}^+)$ is uncountable.


{\bf Proof}:  By definition of countable, since $\{  r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}$
is not finite, {\bf to show} is $|\mathbb{N}| \neq  |\{  r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}|$ .


{\bf To show} is
$\forall f : \mathbb{Z}^+ \to \{  r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}  ~~(f \text{ is not a bijection})~~$.
Towards a proof by  universal generalization, consider  an arbitrary function 
$f:  \mathbb{Z}^+ \to \{  r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}$.
{\bf To show}: $f$ is not a bijection.  It's enough to show that $f$ is not onto.
Rewriting using the definition of  onto, {\bf to show}:
\[
\exists x \in \{  r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \} ~\forall a \in \mathbb{N}  ~(~f(a) \neq  x~)
\]
In search of a witness, define the following  real number by defining its binary expansion
\[
d_f = 0.b_1 b_2 b_3 \cdots
\]
where $b_i = 1-b_{ii}$ where $b_{jk}$ is the coefficient of $2^{-k}$ in the binary expansion of $f(j)$.
Since\footnote{There's a subtle imprecision in this part of the proof as presented, but it can be fixed.} $d_f \neq f(a)$ for any positive integer $a$, $f$ is not onto.


{\it Approach 2}: Nested closed interval property

{\bf To show} $f: \mathbb{N} \to \{  r \in \mathbb{R} ~\mid~ 0  \leq r ~\wedge~ r \leq 1 \}$ is not onto. 
{\bf  Strategy}: Build
a sequence of nested closed intervals that each avoid some $f(n)$.   Then  the real
number that is in all of the intervals  can't be $f(n)$ for any $n$. Hence,  $f$ is not  onto.

Consider the function $f: \mathbb{N} \to \{  r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}$ with  $f(n) = \frac{1+\sin(n)}{2}$

\begin{center}
\begin{tabular}{c||p{1.65in} || p{3in} }
$n$ &  $f(n)$& Interval that avoids $f(n)$ \\
\hline
$0$ & $0.5$ &  \\
$1$ &$0.920735\ldots$  &  \\
$2$ &$0.954649\ldots$ &  \\
$3$ &$0.570560\ldots$ & \\
$4$ &$0.121599\ldots $&  \\
\vdots &  &\\
\end{tabular}
\end{center}
  \vfill
\end{document}