\documentclass[letterpaper,12pt]{book}

\author{Jonathan J. White}
\title{Foundations of Advanced Mathematics, version 0.13}
\date{4/15/22}

\usepackage{amsfonts,amssymb,amsmath,amsthm,txfonts,pxfonts,mathrsfs,fullpage,enumitem}
\usepackage{fancyhdr}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{lmodern}
\pagestyle{fancy}
\setlength{\headheight}{6pt}
\lhead{Foundations of Advanced Mathematics, v. 0.13}
\rhead{Jonathan J. White    \today}
\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.25pt}
\setlength{\headsep}{6pt}

\begin{document} 

\setcounter{page}{63}
\setcounter{chapter}{4}
\chapter{Counting}
\section{Combinatorics}
\noindent The area of mathematics dealing with counting (sometimes very large) collections is called Combinatorics.  This section gives a very brief introduction to the basic tools of Combinatorics, and the next section puts some of these to use.\\
\\
Theorem (The Multiplication Principle): If one choice can be made in $m$ different possible ways and a second choice can be made in $n$ different possible ways, then the two choices can be made in $m \cdot n$ total ways.\\
\\
Proof: Exercise 1.\\
\\
Definition: Let $\mathbb Z_n = \{m \in \mathbb Z \, | \, 0 \leq m < n\}$.\\
\\
Definition: Let $A$ be a set with $n$ elements.  A bijection $f : \mathbb Z_n \to A$ is called a \textbf{permutation}.\\
\\
Definition: Let $A$ be a set with $n$ elements.  A \textbf{permutation of size k of n elements} is an injection from $\mathbb Z_k$ to $A$.  We denote the number of these distinct injections $\mathbf{P(n, k)}$.\\
\\
Definition: The number of distinct $k$-element subsets of a set with $n$ elements is denoted $\mathbf{C(n, k)}$ or $\dbinom {n}{k}$, read ``$n$ choose $k$''.\\
\\
{\Large Exercises}
\begin{enumerate}
\item Prove The Multiplication Principle.
\item The number of distinct permutations of a set $A$ having $n$ elements is $n!$.
\item Find the number of orders in which 6 books can be arranged on a shelf.
\item Find the number of orders in which a deck of 52 cards can be arranged.
\item $P(n, k) = \dfrac {n!}{(n-k)!}$.
\item Find the number of orders in which 3 runners can finish first, second, and third out of 10.
\item Find the number of orders in which 3 letters from the set \{a, e, i, o, u\} can be chosen.
\item $P(n, n) = n!$.
\item For $n \geq 1, P(n, n) = P(n, n - 1)$.
\item For $n \geq k \geq 0, C(n, k) = \dfrac{n!}{k!(n-k)!}$.
\item Find the number of 5-card poker hands that can be dealt from a deck of 52.
\item Find the number of ways 2 faculty members can be chosen from a department of 5 to represent the department at a reception for prospective students.
\item For $n \geq 0, C(n, 0) = 1 = C(n, n)$.
\item For $n \geq 1, C(n, 1) = n$.
\item For $n \geq k \geq 1, C(n + 1, k) = C(n, k) + C(n, k - 1)$.
\item For $n \geq k \geq 1, k \cdot C(n, k) = n \cdot C(n - 1, k - 1)$.
\item For $n \geq 1$ and $n \geq k \geq 0, (n-k) \cdot C(n, k) = n \cdot C(n - 1, k)$.
\item For $n \geq k \geq 0, C(n, k) = C(n, n - k)$.
\item The Banana Theorem: Let $A$ be a set with $n$ elements of $k$ different types (such that elements of the same type are regarded as indistinguishable from one another for purposes of orderings).  Let $n_i$ be the number of elements of type $i$ for each integer $i$ from 1 to $k$.  Then the number of different arrangements of the elements in $A$ will be $$\dfrac{n!}{\prod_{i=1}^{k} (n_i !)}$$.
\item How many distinguishable ways can the letters in the word banana be arranged?
\item How many distinguishable ways can the letters in the word Mississippi be arranged?
\item How many numbers between 1 and 1,000,000 have no 9's among their digits?
\end{enumerate}

\section{Probability}
\noindent This section introduces the serious study of probability, both because every math student should have some familiarity with it and because it provides perfect uses for the counting tools introduced in the previous section.\\
\\
Definition: $\mathbf{Probability=\frac{number \, of \, favorable \, events}{number \, of \, total \, events}}$.\\
\\
Example 1: If a standard die is tossed, the probability of rolling a 2 or less is 1/3, because the number of favorable events is 2 (the number of elements in the set \{1,2\}) and the number of total possible events is 6 (the number of elements in the set $\{1,2,3,4,5,6\}$), and we can reduce $2/6$ to $1/3$.\\
\\
Example 2: If two standard dice are tossed, the probability that the second one is at least twice the first is 1/4, because the number of favorable events is 9 (indicated by the boxed entries in the table below) and the number of total possible events is 36 (indicated by all of the entries in the table below), and 9/36 reduces to 1/4.\\
\[
\begin{matrix}
  1,1 & 1,2  & 1,3 & 1,4  & 1,5 & 1,6 \\
  \boxed{2,1} & 2,2  & 2,3 & 2,4  & 2,5 & 2,6 \\
  \boxed{3,1} & 3,2  & 3,3 & 3,4  & 3,5 & 3,6 \\
  \boxed{4,1} & \boxed{4,2}  & 4,3 & 4,4  & 4,5 & 4,6 \\
  \boxed{5,1} & \boxed{5,2}  & 5,3 & 5,4  & 5,5 & 5,6 \\
  \boxed{6,1} & \boxed{6,2}  & \boxed{6,3} & 6,4  & 6,5 & 6,6 \\ 
 \end{matrix}
\] 
\\
{\Large Exercises}
\begin{enumerate}
\item When a fair coin is tossed twice, what is the probability of two heads?
\item When a fair coin is tossed twice, what is the probability of one head and one tail?
\item When a fair coin is tossed three times, what is the probability of exactly two tails?
\item When a fair coin is tossed 100 times, what is the probability of exactly two tails?
\item A coin is tossed 3 times.  What is the probability of all three tosses being heads if you know that at least one of the tosses came up heads?
\item If a jar contains four balls, one red, two blue, and one white, and two balls are drawn at random from the jar (without replacement), what is the probability that neither ball is blue?
\item If a jar contains four balls, one red, two blue, and one white, and two balls are drawn at random from the jar (without replacement), what is the probability that neither ball is blue if you know that the white ball is one of the two drawn?
\item If a jar contains five balls, one red, two blue, and two white, and three balls are drawn at random from the jar (replacing each after it's drawn), what is the probability that the balls are drawn red, blue, and white in that order?
\item If a jar contains five balls, one red, two blue, and two white, and three balls are drawn at random from the jar (replacing each after it's drawn), what is the probability that the balls are drawn red, blue, and white, not necessarily in that order?
\item If two cards are drawn from a standard deck, what is the probability of both cards being clubs?
\item If two cards are drawn from a standard deck, what is the probability of both cards being face cards?
\item If two cards are drawn from a standard deck, what is the probability of both cards being red aces?
\item If a standard die is tossed, what is the probability that the result is at least 5?
\item If a standard die is tossed twice, what is the probability that the total is exactly 5?
\item What is the probability that when a die is tossed twice, the difference between the two rolls is exactly two?
\item A standard die is tossed twice.  What is the probability that the second roll is higher than the first?
\item If a standard die is tossed three times consecutively, what is the probability that each result is higher than the one before?
\item If three standard dice are tossed, what is the probability that the total on all three dice is at least 17?
\item If someone knows your password is a six-character string of letters, what is their probability of guessing it in a single try?
\item If someone knows your password is a case-sensitive six-character string of letters, what is their probability of guessing it in a single try?
\item If someone knows your password is a case-sensitive six-character string of letters and numerals, what is their probability of guessing it in a single try?
\item If someone knows your password is a six-character string of letters, and that it has a ``g'' in it, what is their probability of guessing it in a single try?
\item If someone knows your password is a case-sensitive six-character string of letters and numerals, and that at least one of the letters was required to be capitalized, what is their probability of guessing it in a single try?
\end{enumerate}

\section{The Peano Axioms I}
\noindent You should have wondered at some point in your life exactly how many things need to be accepted "on faith" as just obviously true in order to make the rest of the things commonly done in mathematics follow.  The answer, technically, is none -- mathematics proceeds in a hypothetical way, deducing the consequences if some collection of axioms holds.  But for a more satisfying answer, this and the following sections provide an instance of developing a great deal of familiar material from a very short list of principles.\\
\\
Definition: We call a set $N$ a \textbf{Peano system} iff the following conditions are satisfied:
\begin{itemize}
\item[P1.] $0 \in N$
\item[P2.] For each $x \in N$, there is a unique element $x' \in N$ (we call $x'$ the \textbf{successor} of $x$)
\item[P3.] $\forall x \in N, x' \neq 0$
\item [P4.] $\forall x, y \in N, x' = y' \Rightarrow x = y$
\item [P5.] If $M \subseteq N$ for which $0 \in M$ and $\forall x \in M, x' \in M$, then $M = N$
\end{itemize}
\noindent Definition: Given a Peano system $N$ and $x, y \in N$, define their \textbf{sum} $x + y$ by
\begin{itemize}
\item[A1.] $x + 0 = x$
\item [A2.] $x + y' = (x + y)'$
\end{itemize}

\noindent {\Large Exercises}\\
Prove the following statements, given that $N$ is a Peano system.
\begin{enumerate}
\item $\forall x, y \in N, x + (y + 0) = (x + y) + 0$
\item $\forall x, y, z \in N, x + (y + z) = (x + y) + z \Rightarrow x + (y + z') = (x + y) + z'$
\item $\forall x, y, z \in N, x + (y + z) = (x + y) + z$
\item 0 + 0 = 0
\item $\forall y \in N, 0 + y = y \Rightarrow 0 + y' = y'$
\item $\forall y \in N, 0 + y = y$
\item $\forall x \in N, x' + 0 = (x + 0)'$
\item $\forall x, y \in N, x' + y = (x + y)' \Rightarrow x' + y' = (x + y')'$
\item $\forall x, y \in N, x' + y = (x + y)'$
\item $\forall y \in N, 0 + y = y + 0$
\item $\forall x, y \in N, x + y = y + x \Rightarrow x' + y = y + x'$
\item $\forall x, y \in N, x + y = y + x$
\end{enumerate}

\section{The Peano Axioms II}
\noindent The previous section developed the basic additive properties of the natural number system.  This section extends that development to multiplication.\\
\\
Definition: Given a Peano system $N$ and $x, y \in N$, define their \textbf{product} $x \cdot y$ by
\begin{itemize}
\item[M1.] $x \cdot 0 = 0$
\item[M2.] $x \cdot y' = (x \cdot y) + x$
\end{itemize}

\noindent {\Large Exercises}\\
Prove the following statements, given that $N$ is a Peano system.
\begin{enumerate}
\item $\forall x, y \in N, x \cdot (y + 0) = x \cdot y + x \cdot 0$
\item $\forall x, y, z \in N, x \cdot (y + z) = x \cdot y + x \cdot z \Rightarrow x \cdot (y + z') = x \cdot y + x \cdot z'$
\item $\forall x, y, z \in N, x \cdot (y + z) = x \cdot y + x \cdot z$
\item $\forall x, y \in N, x \cdot (y \cdot 0) = (x \cdot y) \cdot 0$
\item $\forall x, y, z \in N, x \cdot (y \cdot z) = (x \cdot y) \cdot z \Rightarrow x \cdot (y \cdot z') = (x \cdot y) \cdot z'$
\item $\forall x, y, z \in N, x \cdot (y \cdot z) = (x \cdot y) \cdot z$
\item $0 \cdot 0 = 0$.
\item $\forall y \in N, 0 \cdot y = 0 \Rightarrow 0 \cdot y' = 0$.
\item $\forall y \in N, 0 \cdot y = 0$.
\item $\forall x \in N, x' \cdot 0 = 0$.
\item $\forall x, y \in N, x' \cdot y = x \cdot y + y \Rightarrow x' \cdot y' = x \cdot y' + y'$.
\item $\forall x, y \in N, x' \cdot y = x \cdot y + y$.
\item $\forall y \in N, 0 \cdot y = y \cdot 0$.
\item $\forall x, y \in N, x \cdot y = y \cdot x \Rightarrow x' \cdot y = y \cdot x'$.
\item $\forall x, y \in N, x \cdot y = y \cdot x$.
\end{enumerate}

\section{The Peano Axioms III}
\noindent Here we include a few additional results that can be developed from the axioms already given.  While it is impossible to list all the consequences of these axioms, these should dispel any impression that the results given previously are exhaustive.\\
\\
Definition: We henceforth adopt the convention that $0' = 1, 1' = 2,$ and so on.\\
\\
\noindent {\Large Exercises}\\
Prove the following statements, given that $N$ is a Peano system.
\begin{enumerate}
\item $\forall y \in N$, with $y \neq 0, 0 \neq 0 + y$.
\item $\forall x, y \in N$, with $y \neq 0, x \neq x + y \Rightarrow x' \neq x' + y$.
\item $\forall x, y \in N$, with $y \neq 0, x \neq x + y$.
\item $\forall y, z \in N, 0 + y = 0 + z \Rightarrow y = z$.
\item $\forall x, y, z \in N, (x + y = x + z \Rightarrow y = z) \Rightarrow (x' + y = x' + z \Rightarrow y = z)$.
\item $\forall x, y, z \in N, x + y = x + z \Rightarrow y = z$.
\item $\forall y \in N$, with $y \neq 1, 1 \neq 1 \cdot y$.
\item $\forall x, y \in N$, with $y \neq 1, x \neq x \cdot y \Rightarrow x' \neq x' \cdot y$.
\item $\forall x, y \in N$, with $y \neq 1, x \neq x \cdot y$.
\item $\forall y, z \in N, 1 \cdot y = 1 \cdot z \Rightarrow y = z$.
\item $\forall x, y, z \in N, (x \cdot y = x \cdot z \Rightarrow y = z) \Rightarrow (x' \cdot y = x' \cdot z \Rightarrow y = z)$.
\item $\forall x, y, z \in N, x \cdot y = x \cdot z \Rightarrow y = z$.
\end{enumerate}

\newpage
\section{The Peano Axioms IV}
\noindent A sceptic might look at the previous sections and worry that, although they possess internal consistency, there is no particular reason to accept the axioms in their somewhat convoluted form as self-evident.  Said differently, whether nine things or a thousand are taken on faith, we still might like to think that mathematics is based on something other than faith.  This section addresses that concern.\\
\\
Definition: Given a set $A$, define \textbf{\textit{S(A)}} = $A \cup \{A\}$.\\
\\
Definition: Let $\mathfrak{N}$ be the collection of all sets $N$ containing $\varnothing$ and such that $\forall x\in N, S(x) \in N$.  Let $\mathbb N$ be the intersection of all sets in $\mathfrak{N}$.\\
\\
\noindent {\Large Exercises}\\
\begin{enumerate}
\item Write $S(\varnothing), S(S(\varnothing))$, and $S(S(S(\varnothing)))$ explicitly.  How many elements does each of these have?
\item Show that $\varnothing \in \mathbb N$.
\item Show that for each $x \in \mathbb N$, there is a unique element $S(x) \in \mathbb N$.
\item Show that for any set $A, S(A) \neq \varnothing$.
\item Show that for any $x, y \in \mathbb N, S(x) = S(y) \Rightarrow x = y$.
\item Show that if $M \subseteq \mathbb N$ for which $\varnothing \in M$ and $\forall x \in M, S(x) \in M$, then $M = \mathbb N$.
\item Show that $\mathbb N$ is a Peano system.
\item Show that $1 + 1 = 2$.
\item Show that $2 + 2 = 4$.

\end{enumerate}

\end{document}