\chapter{Cardinality: To Infinity and Beyond}

\begin{exercise}
For sets $A_{1}, A_{2} \subset X$  show that 
$$X - (A_{1} \cup A_{2}) =  (X-A_{1}) \cap (X-A_{2}).$$
\end{exercise}

\oneperpage

\begin{thm}(DeMorgan's Laws)
Let $X$ be a set, and let $\{A_k\}_{k=1}^N$ be a finite collection of sets such that $A_k\subset X$ for each $k = 1, 2, \ldots, N$.  Then
$$X - \left( \bigcup_{k=1}^N A_k \right) = \bigcap_{k=1}^N(X-A_k)$$ and $$X - \left( \bigcap_{k=1}^N A_k \right) = \bigcup_{k=1}^N(X-A_k).$$
\end{thm}

\oneperpage

\begin{exercise}
For a function $f:X\rightarrow Y$, and sets $A, B \subset Y$,  show that 
$f^{-1}(A \cup B)= f^{-1}(A) \cup f^{-1}(B)$ and
$f^{-1}(A \cap B)= f^{-1}(A) \cap f^{-1}(B)$.
\end{exercise}

\oneperpage

\begin{exercise}
If $f:X\rightarrow Y$ is injective and $y\in Y$, then $f^{-1}(y)$ contains at most one point.
\end{exercise}

\oneperpage

\begin{exercise}
If $f:X\rightarrow Y$ is surjective and $y\in Y$, then $f^{-1}(y)$ contains at least one point.
\end{exercise}

\oneperpage

\begin{thm}   
Let $2\N$ denote the even positive integers $\{2, 4, 6, \ldots\}$.  Then $2\N$ has the same cardinality as $\N$, that is, $|2\N| = |\N|$.
\end{thm}

\oneperpage

\begin{thm}   
The set $\Z$ has the same cardinality as $\N$, that is, $|\Z| = |\N|$.
\end{thm}

\oneperpage

\begin{thm}
\label{subset-of-N}  
Every subset of $\N$ is either finite or has
the same cardinality as $\N$.
	
\end{thm}

\oneperpage

\begin{thm}   
Every infinite set has a countably infinite subset.
	
\end{thm}

\oneperpage

\begin{thm}
\label{inject-subset}
A set is infinite if and only if there is
an injection from the set into a proper subset of itself.
\end{thm}

\oneperpage

\begin{thm}   
The union of two countable sets is countable. 
	

\end{thm}

\oneperpage

\begin{thm}   
The union of countably many countable sets is countable.
\end{thm}

\oneperpage

\begin{thm}    
The set $\Q$ is countable.
	
\end{thm}

\oneperpage

\begin{thm}    
The set of all finite subsets of a countable set is countable.
\end{thm}

\oneperpage

\begin{exercise}
Suppose a submarine is moving in the plane along a straight line at a constant speed such that at each hour, the submarine is at a lattice point, that is, a point whose two coordinates are both integers.  Suppose at each hour you can explode one depth charge at a lattice point that will hit the submarine if it is there.  You do not know the submarine's direction, speed, or its current position.
Prove that you can explode one depth charge each hour in such a way that you will be guaranteed to eventually hit the submarine.
\end{exercise}

\oneperpage

\begin{thm}[Cantor's Theorem]
%\begin{Cantor's Theorem}%???
\label{cantors-thm} 
The cardinality of the set of natural numbers is not the same as the cardinality of the set of real numbers. That is, the set of real numbers is uncountable. 
%\end{Cantor's Theorem}
\end{thm}

\oneperpage

\begin{exercise}
Suppose $A=\{a,b,c\}$.  Explicitly write out $2^A$, the power set of $A$.
\end{exercise}

\oneperpage

\begin{thm}
If a set $A$ is finite, then the power set of $A$ has cardinality $2^{|A|}$, that is, $|2^A|=2^{|A|}$.
\end{thm}

\oneperpage

\begin{thm}    
For any set $A$, there is an injection from $A$ into $2^A$.
\end{thm}

\oneperpage

\begin{thm}   
For a set $A$, let $P$ be the set of all
functions from $A$ to the two point set $\{0,1\}$.  Then 
$|P| = | 2^A|$.
\end{thm}

\oneperpage

\begin{thm}    
There is a one-to-one correspondence between $2^{\N}$ and the set of all infinite sequences 
of $0$'s and $1$'s. 
\label{0-1fn}
\end{thm}

\oneperpage

\begin{thm}[Cantor's Power Set Theorem]
\label{cantors-power} 
There is no surjection from a set $A$ onto $2^A$. Thus for any set $A$, the cardinality of $A$ is not the same as the cardinality of its power set.  In other words, $|A|\not=|2^A|$.
\end{thm}

\oneperpage

\begin{exercise}
Consider $A=[0,1]$ and $B=[0,1)$ and injections $f(x)=x/3$ from $A$ to $B$ and $g(x)=x$ from $B$ to $A$.  Construct a bijection $h$ from $A$ to $B$ such that on some points of $A$, $h(x)=f(x)$, and for the other points of $A$, $h(x) = g^{-1}(x)$. 
\end{exercise}

\oneperpage

\begin{exercise}
Consider $A=[0,1]$ and $B=[0,1)$ and injections $f(x)=x/3$ from $A$ to $B$ and $g(x)=x/2$ from $B$ to $A$.  Construct a bijection $h$ from $A$ to $B$ such that on some points of $A$, $h(x)=f(x)$, and for the other points of $A$, $h(x) = g^{-1}(x)$. 
\end{exercise}

\oneperpage

\begin{thm}[Schroeder-Bernstein]
\index{Schroder-Bernstein theorem}
If $A$ and $B$ are sets such that there exist injections $f$ from
$A$ into $B$ and $g$ from $B$ into $A$, then $|A| =|B|$.
	
\end{thm}

\oneperpage

\begin{thm}[Schroeder-Bernstein]
If $A$ and $B$ are sets such that there exist a surjective function $f:A\to B$ and a surjective function $g:B\to A$, then $|A|=|B|$.
\end{thm}

\oneperpage

\begin{thm}    
$|\R|  = |(0,1)| = |[0,1]|$. 
\end{thm}

\oneperpage

\begin{thm}    
Let $[0,1]\times [0,1]$ denote the Cartesian product of two closed unit intervals.  Then 
$$|[0,1]\times[0,1]| = |[0,1]|.$$
\end{thm}

\oneperpage

\begin{thm}
\label{thm:cardinality-all-functions}
The set of all functions $f:\R\to\R$ has the same cardinality as $2^{\R}$.
\end{thm}

\oneperpage

\begin{thm}   
$|\R| = |2^{\N}|$. 
\end{thm}

\oneperpage

\begin{thm}
There are infinitely many different infinite cardinalities. 
\end{thm}

\oneperpage

\begin{Continuum}\index{Continuum Hypothesis} 
There is no uncountable set whose cardinality is greater than the cardinality of $\N$ yet less than the cardinality of $\R$.
\end{Continuum}

\oneperpage

\begin{exercise}
Given a set $X$, consider the poset $P$ of all subsets of $X$ partially ordered by inclusion.
Show that $X$ is the unique maximal element of $P$, and show that the empty set is the unique least element of $P$.
\end{exercise}

\oneperpage

\begin{exercise}
Construct an example of a poset with several maximal elements and several least elements.
\end{exercise}

\oneperpage

\begin{exercise}
Show that $\R$ with the $\leq$ relation is totally ordered but not well-ordered.
\end{exercise}

\oneperpage

\begin{Zorn}
\index{Zorn's lemma}  
Let $X$ be a partially ordered set in
which each totally ordered subset has an 
upper bound in $X$.  Then $X$
has a maximal element.
\end{Zorn}

\oneperpage

\begin{AxChoice}
\index{Axiom of Choice}  
Let $\{ A_\alpha\}_{\alpha\in\lambda}$
be a set of non-empty sets.  Then there is a function
$f: \lambda\to \bigcup_{\alpha\in\lambda} A_\alpha$ such that for each
$\alpha$ in $\lambda$, $f(\alpha)$ is an element of $A_\alpha$.
\end{AxChoice}

\oneperpage

\begin{WellOrPrin}
\index{Well-Ordering Principle}
Every set can be well-ordered. That is, every set can be put in one-to-one correspondence 
with a well-ordered set. 
\end{WellOrPrin}

\oneperpage

\begin{thm}
Zorn's Lemma, the Axiom of Choice, and the Well-Ordering Principle are equivalent.
\end{thm}

\oneperpage

\begin{thm} 
\begin{enumerate}
\item If $\alpha$ is an ordinal number, then any element of $\alpha$ is also an ordinal.
\item $S(\alpha):= \alpha \cup \{\alpha\}$, the \emph{successor} of $\alpha$, is also an ordinal.  
\item The union of any set of ordinals is an ordinal. 
\item The ordinal numbers are naturally ordered by inclusion.
\item The intersection of any set of ordinals is an ordinal contained in that set of ordinals and is the least element in the set. Hence, any set of ordinal numbers has a least element. Hence, ordinals are well-ordered.
\end{enumerate}
\end{thm}

\oneperpage

\begin{thm} 
Let $\{\alpha_i\}_{i\in\omega_0}$ be a countable set of countable ordinal numbers; 
that is, each $\alpha_i <\omega_1$. Then there is an ordinal $\beta$ such that 
$\alpha_i<\beta$ for each $i$ and $\beta<\omega_1$. 
\end{thm}

\oneperpage

\begin{thm}
For any countable set of countable ordinals $\{\alpha_i\}_{i \in \omega_0}$, there is a countable limit ordinal $\gamma$ such that for every ordinal $\beta < \gamma$, there exists an $\alpha_i$ such that $\beta < \alpha_i < \gamma$. 
\end{thm}

\oneperpage

\begin{thm}
Let $A$ and $B$ be unbounded\index{unbounded!ordinals} sets of ordinals in $\omega_1$, that is, for every ordinal $\delta \in \omega_1$, there is an ordinal $\alpha \in A$ such that $\delta < \alpha$ and an ordinal $\beta \in B$ such that $\delta < \beta$. Then there exists a limit ordinal $\gamma$ in $\omega_1$ such that $\gamma$ is a limit of ordinals from $A$ and is also a limit of ordinals from $B$. 
\end{thm}

\oneperpage

