<gh_stars>1-10
\section{Finite Sets}

\begin{definition}
  A set is said to be \textbf{finite} if there is a bijective correspondence of
  $A$ with some section of the positive integers. That is, $A$ is finite if it
  is empty or if there is a bijection
  \begin{equation}
    f:A \to \pbrac{1, \dots, n}
  \end{equation}
  for some positive integer $n$. In the former case, we say that $A$ as
  \textbf{cardinality 0}, and in the latter case, we say that $A$ has
  \textbf{cardinality $n$}.
\end{definition}

\section*{Exercises}

\bx{
  \ea{
    \item There are $4 \times 3 \times 2 = 24$ injective mappings,
    \begin{align*}
      (1, 1), (2, 2), (3, 3)\\
      (1, 1), (2, 2), (3, 4)\\
      (1, 1), (2, 3), (3, 2)\\
      (1, 1), (2, 3), (3, 4)\\
      (1, 1), (2, 4), (3, 2)\\
      (1, 1), (2, 4), (3, 3)\\
      (1, 2), (2, 1), (3, 3)\\
      (1, 2), (2, 1), (3, 4)\\
      (1, 2), (2, 3), (3, 1)\\
      (1, 2), (2, 3), (3, 4)\\
      (1, 2), (2, 4), (3, 1)\\
      (1, 2), (2, 4), (3, 3)\\
      (1, 3), (2, 1), (3, 2)\\
      (1, 3), (2, 1), (3, 4)\\
      (1, 3), (2, 2), (3, 1)\\
      (1, 3), (2, 2), (3, 4)\\
      (1, 3), (2, 4), (3, 1)\\
      (1, 3), (2, 4), (3, 2)\\
      (1, 4), (2, 1), (3, 2)\\
      (1, 4), (2, 1), (3, 3)\\
      (1, 4), (2, 2), (3, 1)\\
      (1, 4), (2, 2), (3, 3)\\
      (1, 4), (2, 3), (3, 1)\\
      (1, 4), (2, 3), (3, 2)
    \end{align*}
    \item $10 \cdot 9 \cdot \dots \cdot 3 = 1814400$ \dots, you can tell this is not a fun time.
  }
}

\bx{
  AFSOC $A$ is finite. Then $B$ must be finite since it is a subset of $A$, but this is a contradiction since $b$ is not finite by assumption.
}

\bx{
  Let the propr subset be $X^\omega - {0, 0, \dots}$.
  Let the bijection be
  \begin{align*}
    f(000000\dots) &= 1000000\dots\\
    f(100000\dots) &= 0100000\dots\\
    f(110000\dots) &= 0010000\dots\\
    &\cdots
  \end{align*}
  It’s just binary written in R to L significant digits, + 1 to shift for the missing $000\dots$.
}

\bx{
  \ea{
    \item Induction from empty set as base case. Adding an element gives you two
    cases, either the new element is the largest, or the existing largest
    element remains the largest.
    \item \TODO: What is an order type? I think the idea here is map $A$ into $\mathbb{Z}$ in the order that the elements are in $A$, and then they will have the order type of the $\Zp$.
  }
}

\bx{
  No. $A = \emptyset$ and $B$ could be infinite.
}

\bx{
  \ea{
    \item $X^n$ is basically an $n$-tuple showing whether or not an element of A is included in the set, so you can make that bijection to $\mathcal{P}(A)$.
    \item $\mathcal{P}(A)$ has a bijection with $X^n$, which is finite, so $\mathcal{P}(A)$ is finite as well.
  }

  \label{chap1:sec6:prob6}
}

\bx{
  Consider $C = A \times B$. Any function $f$ is some subset of $C$. Then the
  set of all functions is a subset of $\mathcal{P}(C)$, which from \ref{chap1:sec6:prob6}
  we know is finite since $C$ is finite.
}
