\documentclass{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{graphicx}

\newtheorem{thm}{Theorem}

\title{Infinite Sets}
\author{Doug Baldwin}
\date{Spring 2021}


\begin{document}

\maketitle

Here are some examples of proofs involving infinite sets.

The first deals with the union of countably infinite sets, and illustrates how bijections for new sets are sometimes constructed from bijections for component sets.

\begin{thm}
If $A$ and $B$ are disjoint countably infinite sets, then $A \cup B$ is also countably infinite.
\end{thm}

\begin{proof}
We prove that if $A$ and $B$ are disjoint countably infinite sets, then $A \cup B$ is also countably infinite by showing that there is a bijection between the natural numbers and $A \cup B$. Since $A$ and $B$ are countably infinite, there are bijections between them and the natural numbers. Let those bijections be $f : A \to \mathbb{N}$ and $g : B \to \mathbb{N}$, respectively. Now we define a new function $h : A \cup B \to \mathbb{N}$ by
\begin{equation}
\label{unionFn}
h(x) = \begin{cases}
    2 f(x) & \mathrm{\ if\ } x \in A \\
    2 g(x) - 1 & \mathrm{\ if\ } x \in B
  \end{cases}
\end{equation}
We can show that $h$ is a bijection between $A \cup B$ and $\mathbb{N}$ by showing that it is an injection and a surjection.

To show that $h$ is an injection, we show that $h(x) = h(y)$ implies that $x = y$. So suppose $x$ and $y$ are elements of $A \cup B$ such that $h(x) = h(y)$. Notice that $h$ produces an even number for elements of $A$ and an odd number for elements of $B$, so if $h(x) = h(y)$, $x$ and $y$ are both elements of the same set. Suppose both are elements of $A$. Then $h(x) = 2 f(x)$ and $h(y) = 2 f(y)$, so we have $2 f(x) = 2 f(y)$, or $f(x) = f(y)$. Now since $f$ is a bijection, this implies $x = y$. Similarly, if $x$ and $y$ are both elements of $B$, $2 g(x) - 1 = 2 g(y) - 1$, and again $g(x) = g(y)$ and so $x = y$.

To show that $h$ is a surjection, we show that for any natural number $n$, there is some $x \in A \cup B$ such that $h(x) = n$. So let $n$ be a natural number, and consider two cases, namely $n$ is even and $n$ is odd.

If $n$ is even, we need an $x \in A$ such that $2 f(x) = n$, or $f(x) = \tfrac{n}{2}$. Since $n$ is even and a natural number, $\tfrac{n}{2}$ is a natural number. Since $f$ is a bijection it is also a surjection, and thus there is some $x \in A$ for which $f(x) = \tfrac{n}{2}$, and so in turn $h(x) = n$.

On  the other hand, if $n$ is odd, then we seek an $x \in B$ such that $2 g(x) - 1 = n$. Algebra gives us
\begin{align*}
2 g(x) - 1 &= n \\
2 g(x) &= n + 1 \\
g(x) &= \frac{n+1}{2}
\end{align*}
Now since $n$ is odd, $n+1$ is even, and therefore $\tfrac{n+1}{2}$ is a natural number. Now since $g$ is a surjection, there is indeed an $x \in B$ such that $g(x) = \tfrac{n+1}{2}$ and thus $h(x) = n$.

We have now shown that $h$ as defined by (\ref{unionFn}) is a bijection from $A \cup B$ to $\mathbb{N}$, which in turn means that $A \cup B$ is countably infinite. We have therefore proven that if $A$ and $B$ are disjoint countably infinite sets, then $A \cup B$ is also countably infinite.
\end{proof}

The second example deals with Cartesian products of countably infinite sets. Such products are also countably infinite. The proof illustrates a common ``diagonal'' argument about pairs from countable sets.

\begin{thm}
If $A$ and $B$ are countably infinite sets then $A \times B$ is countably infinite.
\end{thm}

\begin{proof}
We assume that $A$ and $B$ are countably infinite sets, and will show that $A \times B$ is countably infinite. Since $A$ and $B$ are countable, they have the form $A = \{A_1,A_2,A_3,\ldots\}$ and $B = \{B_1,B_2,B_3,\ldots\}$.  We can then imagine writing the Cartesian product as a table whose rows correspond to elements of $B$ and columns to elements of $A$, like so:
\begin{center}
\includegraphics[scale=0.6]{Cartesian.png}
\end{center}

We then match every pair in the product with a natural number by traversing the table along lower-left-to-upper-right diagonals, starting in the upper left corner: $(A_1,B_1)$ forms the first diagonal, $(A_1,B_2)$ and $(A_2,B_1)$ the second, and so forth. We assign natural numbers to pairs in the order we reach those pairs in this traversal. Notice that this matching is a bijection. It is an injection because if two pairs match the same natural number, then they must appear in the same place in the traversal, i.e., they must be equal. The matching is also a surjection because any pair lies on some diagonal, and since every diagonal is finite the traversal will eventually reach that diagonal and pair and match the pair to a natural number.

We have now established a bijection between $A \times B$ and the natural numbers, and thereby shown that if $A$ and $B$ are countably infinite sets then $A \times B$ is countably infinite.
\end{proof}

\end{document}