\documentclass{article}

\usepackage[english]{babel}

\usepackage{amsmath}
% for symbols such as /implies
\usepackage{amssymb}
% for symbols such as /subsetneq
\usepackage{amsthm}
% for commands such as \newtheorem

\theoremstyle{definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{axiom}{Axiom}

\begin{document}

\section{Cardinality}

\begin{definition}
  Sets $A$ and $B$ have the same \emph{cardinality}, denoted $|A|=|B|$, if there exists a bijective function $f:A\to B$.
  If $A$ and $B$ do not have the same cardinality, we write $|A|\neq|B|$.
\end{definition}
    
\begin{theorem}
  If there exist injective functions $f:A\to B$ and $g:B\to A$, then $|A|=|B|$.
\end{theorem}

\begin{theorem}
  For any sets $A$ and $B$, there is an injection from $A$ into $B$ or there is an injection from $B$ into $A$.
  \begin{proof}
    Uses axiom of choice.
  \end{proof}
\end{theorem}

\begin{example}
  $|\mathbb{Q}|=|\mathbb{Z}|=|\mathbb{N}|$
\end{example}

\begin{definition}
  A set $A$ is \emph{infinite} if there exists an injective function $f:\mathbb{N}\to A$.
  A set is \emph{finite} if it is not infinite.
\end{definition}

\begin{theorem}
  A set $A$ is finite if and only if there exists $n\in\mathbb{N}$ such that $|A|=|\{k\in\mathbb{N}: 1\leq k\leq n\}|$. This value of $n$ is unique.
\end{theorem}

\begin{definition}
  If $A$ is a finite set, we say that the cardinality of $A$ is the value $n\in\mathbb{N}$ from the previous theorem and write $|A|=n$.
\end{definition}

\begin{example}
  $|\emptyset|=0$, $|\{1\}|=1$, $|\{1,2\}|=2$, etc.
\end{example}

\begin{theorem}
  If $A$ is a finite set and $B\subset A$ is a proper subset, then $|B|<|A|$.
\end{theorem}

\begin{definition}
  A set $A$ is \emph{countable} if there exists an injective function $f:A\to\mathbb{N}$.
  A set is \emph{uncountable} if it is not countable.
  If $A$ is countable, it may be \emph{enumerated} by denoting each $a\in A$ by $a_{f(a)}$
  $$
    A = \{a_1, a_2, \dots \}
  $$
\end{definition}

\begin{theorem}
  A finite product of countable sets is countable.
\end{theorem}

\begin{theorem}
  A countable union of countable sets is countable.
\end{theorem}

\begin{example}
  The countable product $\prod_{n\in\mathbb{N}} \{0,1\}$ is uncountable.
\end{example}

\begin{lemma}
  If $A$ is an infinite set and $B$ is a finite set, then
  $$
    |A\cup B| = |A\setminus B| = |A|
  $$
  \begin{proof}
    Let $A$ be infinite and $B$ be finite. Let $n=|B|$ and suppose $B=\{b_1,\dots,b_n\}$. Let $\{a_k\}_{k=1}^\infty \subseteq A$. Define $f:A\to A\cup B$ by
    $$
      f(a) = \begin{cases}
        b_k & a = a_k, 1\leq k\leq n \\
        a_{k-n} & a = a_k, k > n \\
        a & \text{otherwise}.
      \end{cases}
    $$

  \end{proof}
\end{lemma}

\begin{lemma}
  If $A$ is an uncountable set and $E$ is a countable set, then
  $$
    |A\cup E| = |A\setminus E| = |A|
  $$
  \begin{proof}
    Let $A$ be uncountable and $E$ be countable. Let $G = E\setminus A$. Then $G$ is countable. 
    Assume $G$ is infinite with $G=\{g_n\}_{n=1}^\infty$. Let $\{a_n\}_{n=1}^\infty \subseteq A$.
    Define $f: A\to A\cup G$ by
    $$
      f(a) = \begin{cases}
        g_n & a = a_{2k} \\
        a_n & a = a_{2n-1} \\
        a & \text{otherwise}.
      \end{cases}
    $$
    Then $f$ is bijective and $A\cup G = A\cup E\setminus A = A\cup E$, hence
    $$
      |A| = |A\cup E|.
    $$
  \end{proof}
\end{lemma}

\begin{example}
  As subsets of $\mathbb{R}$
  $$
    |[0,1]| = |[0,1)| = |(0,1]| = |(0,1)|
  $$
\end{example}

\begin{theorem}
  If a set $S$ is nonempty, then $|S|\neq |\mathcal{P}(S)|$.
  \begin{proof}
    Let $f: S\to\mathcal{P}(S)$ be a function. Let
    $$
      B = \{s\in S : s\notin f(s)\}.
    $$
    Suppose towards a contradiction that there is $x\in S$ with $f(x)=B$.

    \textbf{Case 1:} Suppose $x\in B$. Then $x\notin f(x)$ and $f(x)=B$ so that $x\notin B$, contradiction.

    \textbf{Case 2:} Suppose $x\notin B$. Then $x\in f(x)$ and $f(x)=B$ so that $x\in B$, contradiction.

    Then $B$ is not in the range of $f$, and $f$ is not surjective.
  \end{proof}
\end{theorem}

\begin{example}
  The set of real numbers $\mathbb{R}$ is uncountable.
  $$
    |\mathbb{N}| < |\mathcal{P}(\mathbb{N})| = |\{0,1\}^\mathbb{N}| = |[0,1)| = |(0,1)| = |\mathbb{R}|
  $$
\end{example}



\end{document}