\documentclass[letterpaper,12pt]{book}

\author{Jonathan J. White}
\title{Foundations of Advanced Mathematics, version 0.14}
\date{2/23/23}

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

\begin{document} 

\setcounter{page}{37}
\setcounter{chapter}{2}
\chapter{Functions \& Cardinality}
\section{Functions}
\noindent You already have considerable experience with functions.  This section will make sure you're familiar with some standard examples, and provide some groundwork for us to build on as we progress to a more sophisticated understanding and the results that can be based on it.\\
\\
Definition: A function from $A$ to $B$, denoted $f:A \to B$ is a rule associating a unique element of $B$ to each element of $A$.  The set $A$ is called the \textbf{domain} of the function, and the set $B$ is called the \textbf{codomain}.  An element $x \in A$ is referred to as a \textbf{pre-image}, and the corresponding element of $B$, denoted $f(x)$, is called the \textbf{image} associated with $x$.\\
\\
Example: In the last chapter we defined the absolute value function.  Note that it satisfies this definition of a function from $\mathbb R$ to $\mathbb R$.  It also would qualify, however, as a function from $\mathbb R$ to $S = \{x | x \in \mathbb R$ and $x \geq 0\}$, or as a function from $\mathbb Z$ to $\mathbb N$, among other possibilities.  This illustrates one part of why our definition of a function requires that the domain and codomain be stated explicitly.\\
\\
Example: For any sets $A$ and $B$, with $c \in B$, the function $f: A \to B$ defined by $f(x) = c$ for all $x \in A$, is called a \textbf{constant function}.\\
\\
Example: For any set $A$, the function $i:A \to A$ defined by $i(x) = x$ is called the \textbf{identity function} on $A$.  When necessary to avoid ambiguity we sometimes denote the identity function on $A$ as $i_A$.\\
\\
Example: For any set $A$ and another set $B$ such that $A \subseteq B$, the function $inc:A \to B$ defined by $inc(x) = x$ is called the \textbf{inclusion function} from $A$ to $B$.\\
\\
Definition: We say that functions $f$ and $g$ are \textbf{equal} iff they have the same domain and codomain, and also for each $x$ in the domain, $f(x) = g(x)$.\\
\\
Definition: Let $D \subseteq \mathbb R$.  A function $f:D \to \mathbb R$ is \textbf{even} iff $\forall x \in D, f(-x) = f(x)$.\\
\\
Definition: Let $D \subseteq \mathbb R$.  A function $f:D \to \mathbb R$ is \textbf{odd} iff $\forall x \in D, f(-x) = -f(x)$.\\
\\
Definition: A function $f:D \to \mathbb R$ is \textbf{increasing} iff $\forall x,y \in D, x < y \Rightarrow f(x) \leq f(y)$.\\
\\
Definition: A function $f:D \to \mathbb R$ is \textbf{strictly increasing} iff $\forall x,y \in D, x < y \Rightarrow f(x) < f(y)$.\\
\\
Definition: A function $f:D \to \mathbb R$ is \textbf{decreasing} iff $\forall x,y \in D, x < y \Rightarrow f(x) \geq f(y)$.\\
\\
Definition: A function $f:D \to \mathbb R$ is \textbf{strictly decreasing} iff $\forall x,y \in D, x < y \Rightarrow f(x) > f(y)$.\\
\\
Definition: A function $f: D \to \mathbb R$ is \textbf{bounded} iff $\exists M \in \mathbb R$ such that $\forall x \in D, |f(x)| \leq M$.\\
\\
{\Large Exercises}
\begin{enumerate}
\item Give an example of a function on $\mathbb{R}$ which is increasing but not strictly increasing.
\item Give an example of a function on $\mathbb{R}$ which is both even and odd.
\item Give an example of a function on (0,1) which is not bounded.
\item Give an example of a function on $\mathbb{R}$ which is strictly decreasing but bounded.
\end{enumerate}

\newpage
\section{Operations on Functions}
\noindent Definition: Let $D \subseteq \mathbb R$, and let $f: D \to \mathbb R$ and $g: D \to \mathbb R$ be functions.  Then define a new function $\textbf{(\textit{f} + \textit{g})}: D \to \mathbb R$ by $\textbf{(\textit{f} + \textit{g})(\textit{x})} = f(x) + g(x), \forall x \in D$.\\
\\
Definition: Let $D \subseteq \mathbb R$, and let $f: D \to \mathbb R$ and $g: D \to \mathbb R$ be functions.  Then define a new function $\textbf{(\textit{f} -- \textit{g})}: D \to \mathbb R$ by $\textbf{(\textit{f} -- \textit{g})(\textit{x})} = f(x) - g(x), \forall x \in D$.\\
\\
Definition: Let $D \subseteq \mathbb R$, and let $f: D \to \mathbb R$ and $g: D \to \mathbb R$ be functions.  Then define a new function $\textbf{(\textit{f} $\cdot$ \textit{g})}: D \to \mathbb R$ by $\textbf{(\textit{f} $\cdot$ \textit{g})(\textit{x})} = f(x) \cdot g(x), \forall x \in D$.\\
\\
Definition: Let $D \subseteq \mathbb R$, and let $f: D \to \mathbb R$ and $g: D \to \mathbb R$ be functions, with $g(x) \not = 0, \forall x \in D$.  Then define a new function $\textbf{(\textit{f} / \textit{g})}: D \to \mathbb R$ by $\textbf{(\textit{f} / \textit{g})(\textit{x})} = f(x) / g(x), \forall x \in D$.\\
\\
{\Large Exercises}
\begin{enumerate}
\item The sum of two even functions, both with domain $D$, is \rule{1 in}{1 pt}.
\item The sum of two odd functions, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The sum of an even function with an odd function, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The product of two even functions, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The product of two odd functions, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The product of an even function with an odd function, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The derivative of an even function is \rule{1 in}{1 pt}.
\item The derivative of an odd function is \rule{1 in}{1 pt}.
\item The sum of two increasing functions, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The sum of two decreasing functions, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The sum of an increasing function with a decreasing function, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The product of two increasing functions, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The product of two decreasing functions, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The product of an increasing function with a decreasing function, both with domain $D$, is  \rule{1 in}{1 pt}.
\item The derivative of a decreasing function is  \rule{1 in}{1 pt}.
\item The derivative of an increasing function is  \rule{1 in}{1 pt}.
\item Let $f$ be a constant function with codomain $\mathbb R$.  Then $f$ is bounded.
\item Let $f$ and $g$ be bounded functions, both with domain $D$.  Then $f + g$ is a bounded function.
\item Let $f$ and $g$ be bounded functions, both with domain $D$.  Then $f - g$ is a bounded function.
\item Let $f$ and $g$ be bounded functions, both with domain $D$.  Then $f \cdot g$ is a bounded function.
\item Let $f$ and $g$ be bounded functions, both with domain $D$.  Then $f / g$ is a bounded function.
\item Let $n \in \mathbb N$, and $f_i$ be a bounded function with domain $D$ for each $i \in \{x \in \mathbb N \, | \, 1 \leq x \leq n\}$.  Then $\sum_{i=1}^{n} f_i$ is a bounded function.
\item Let $f_i$ be a bounded function with domain $D$ for each $i \in \mathbb N$.  Then $\sum_{i=1}^\infty f_i$ is a bounded function.
\item Let $f + g$ be a bounded function.  Then $f$ and $g$ are bounded functions.
\end{enumerate}

\newpage
\section{Composition}

Definition: Let $f: A \to B$ and $g: B \to C$ be functions.  Then define a new function ${\textbf{(\textit{g} $\circ$ \textit{f})}}: A \to C$ by ${\textbf{(\textit{g} $\circ$ \textit{f})(\textit{x})} = g(f(x))}, \forall x \in A.$\\
\\
{\Large Exercises}
\begin{enumerate}
\item The composition of two even functions is \rule{1 in}{1 pt}.
\item The composition of two odd functions is \rule{1 in}{1 pt}.
\item The composition of an even function with an odd function is \rule{1 in}{1 pt}.
\item The composition of two increasing functions is \rule{1 in}{1 pt}.
\item The composition of two decreasing functions is \rule{1 in}{1 pt}.
\item The composition of an increasing function with a decreasing function is \rule{1 in}{1 pt}.
\item Let $f$ and $g$ be bounded functions.  Then $f \circ g$ is a bounded function.
\item Let $f:A \to B$, and $i_A$ and $i_B$ be the identity functions on $A$ and $B$, respectively.  Then $f \circ i_A = f$ and $i_B \circ f = f$.
\end{enumerate}

\newpage
\section{Injectivity and Surjectivity}
\noindent Some functions have special characteristics that make them particularly useful.  Among the most important of these are injectivity and surjectivity, which are also sometimes called one-to-one and onto, respectively.  We will avoid those older terms here in hopes of instilling good habits, but you should be aware that they are still in use.\\
\\
Definition: A function $f:A \to B$ is \textbf{injective} iff $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$.  We call such a function an \textbf{injection}.\\
\\
Example 1: Figure 1 below gives an example of a function which is injective, and Figure 2 gives an example of a function which is not injective (since the two lowest domain elements are mapped to the same codomain element). 
\begin{center}
\includegraphics{fndtextfigure341.jpg}
\end{center}
Example 2: The function $f: \mathbb R \to \mathbb R$ defined by $f(x) = x^2$ is not injective since, for instance, $f(2) = f(-2)$ but $2 \neq -2$.\\
\\
Definition: A function $f:A \to B$ is \textbf{surjective} iff $\forall b \in B, \exists a \in A$ such that $f(a) = b$.  We call such a function a \textbf{surjection}.\\
\\
Example 3: Figures 1 and 2 above both give examples of functions which are surjective.  Figures 3 and 4 below give two contrasting functions which are not surjective.
\begin{center}
\includegraphics{fndtextfigure343.jpg}
\end{center}
Example 4: The function $f: \mathbb R \to \mathbb R$ defined by $f(x) = x^2$ is not surjective.  The function $g: \mathbb R \to \{x \in \mathbb R | x \geq 0\}$ defined by $g(x) = x^2$, however, is surjective, demonstrating one aspect of why specifying the domain and codomain of a function can be significant.\\
\\
Example 5: The identity function on any set is surjective.  The inclusion function from any set $A$ to a set $B$ for which $A \subseteq B$, but $A \neq B$, is not surjective.\\
\\
Definition: A function $f: A \to B$ which is both injective and surjective is said to be \textbf{bijective}.  We call such a function a \textbf{bijection}.\\
\\
Example 6: The function represented in Figure 1 above is bijective.  The functions represented in Figures 2, 3, and 4 are not.\\
\\
Example 7: The identity function on any set is bijective.\\
\\
{\Large Exercises}
\begin{enumerate}
\item Construct a function from $A$ = \{1, 3, 4\} to $B$ = \{12, 18\} which is injective, or explain why it isn't possible.
\item Construct a function from $A$ = \{1, 3, 4\} to $B$ = \{12, 18\} which is surjective, or explain why it isn't possible.
\item Construct a function from $B$ = \{12, 18\} to $A$ = \{1, 3, 4\} which is injective, or explain why it isn't possible.
\item Construct a function from $B$ = \{12, 18\} to $A$ = \{1, 3, 4\} which is surjective, or explain why it isn't possible.
\item Construct a function from the set of natural numbers to the set of even natural numbers which is injective, or explain why it isn't possible.
\item Construct a function from the set of natural numbers to the set of even natural numbers which is surjective, or explain why it isn't possible.
\item Under what circumstances is a constant function injective?  Surjective?
\item A function $f:A \to B$ is injective iff $a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)$.
\item If $f:A \to B$ and $g:B \to C$ are injective functions, then $g \circ f$ is injective.
\item If $f:A \to B$ and $g:B \to C$ are surjective functions, then $g \circ f$ is surjective.
\item If $f:A \to B$ and $g:B \to C$ are functions, and $g \circ f$ is injective, then $g$ is injective.
\item If $f:A \to B$ and $g:B \to C$ are functions, and $g \circ f$ is surjective, then $g$ is surjective.
\end{enumerate}

\newpage
\section{Inverse Functions}
\noindent Although we will gain a more complete picture in Chapter 4, we need to assure a working understanding of the basics of inverse functions before our first serious encounter with the notion of infinity in the following section.\\
\\
Definition: Let $f:A \to B$ and $g:B \to A$ be functions.  We say that $g$ is an \textbf{inverse function} for $f$ iff $\forall a \in A, g\circ f(a) = a$ and $\forall b \in B, f \circ g(b) = b$.  If $f$ is a function for which an inverse function exists, we say that $f$ is \textbf{invertible}.\\
\\
Proposition 1: If $f:A \to B$ has an inverse function $g$, then $g$ has $f$ as an inverse function also.\\
\\
Proof: Exercise 1.\\
\\
Proposition 2: Let $f:A \to B$ be a bijective function.  Then there exists an inverse function $g$ for $f$.\\
\\
Proof: Exercise 2.\\
\\
Proposition 3: Let $f:A \to B$ be a bijective function.  Then the inverse function of $f$ is unique, i.e. if $g_1$ and $g_2$ are both inverse functions for $f$, then $g_1 = g_2$.\\
\\
Proof: Exercise 3.\\
\\
In light of the uniqueness guaranteed by Proposition 3, when $f$ is an invertible function we usually denote its inverse by $f^{-1}$.  Notice that without knowing inverse functions are unique, this would allow for significant confusion because two different functions might both have been written this way.\\
\\
Proposition 4: Let $f:A \to B$ be an invertible function.  Then $f$ is bijective.\\
\\
Proof: Exercise 4.\\
\\
{\Large Exercises}
\begin{enumerate}
\item Prove Proposition 1.
\item Prove Proposition 2.
\item Prove Proposition 3.
\item Prove Proposition 4.
\item The identity function on a set $A$ is its own inverse.
\item $f:A \to B$ is invertible iff $\exists g:B \to A$ such that $\forall a \in A$ and $\forall b \in B, f(a) = b \Leftrightarrow g(b) = a$.
\item If $f:A \to B$ and $g:B \to C$ are invertible functions, then $g \circ f$ is invertible and $(g \circ f )^{-1} = f^{-1} \circ g^{-1}$.
\end{enumerate}

\newpage
\section{Countability}
\noindent We have already dealt indirectly with some aspects of infinity, in particular with the unboundedness of the natural numbers (and hence other sets like the reals that contain them).  However, while what we have seen so far is true, it might have given you more confusion than clarity.  This section will begin the attempt to provide that lacking clarity.\\
\\
Definition: We say that a set $A$ is \textbf{equipollent} to a set $B$ iff there exists a bijection $f:A \to B$.\\
\\
Many books refer to a \textbf{one-to-one correspondence} existing when two sets are equipollent; we will avoid that language, but it can be a useful metaphor, suggesting pairing elements from two different sets with nothing left unmatched.  It is also sometimes said that equipollent sets have the \textbf{same cardinality}, particularly in courses that go farther with this material.\\
\\
Example 1: The sets \{1, 2, 3, 4\} and \{a, b, c, d\} are equipollent; the function $f:A \to B$ defined by $f(1) = a, f(2) = b, f(3) = d$, and $f(4) = c$ is one possible bijection.  Note that there is not necessarily a ''right'' bijection --- the question is only whether there exists at least one.  The sets \{one, two, three\} and \{ein, zwei, drei\} are also equipollent, which might suggest that in some sense equipollent sets are simply relabelings of one another.\\
\\
Definition: We say that a set $A$ is \textbf{denumerable} iff $A$ and $\mathbb N$ are equipollent.\\
\\
Definition: We say that a set $A$ is \textbf{countable} iff $A$ and some subset of $\mathbb N$ are equipollent.\\
\\
Definition: A set which is countable but not denumerable is called \textbf{finite}; a set which is not finite is called \textbf{infinite}.\\
\\
Note that there is significant variation in different texts about whether the term countable includes finite sets, so that some authors use the term ``countable'' for what we would call ``denumerable.''  There is no strong reason to prefer either use, except of course to avoid confusion.  We stick with the usage of Georg Cantor, who pioneered many of these ideas.\\
\\
{\Large Exercises}
\begin{enumerate}
\item A set $A$ is equipollent to itself.
\item If $A$ is equipollent to $B$, then $B$ is equipollent to $A$.
\item If $A$ is equipollent to $B$, and $B$ is equipollent to $C$, then $A$ is equipollent to $C$.
\item The set of odd natural numbers is denumerable.
\item The set of integers is denumerable.
\item For any $a, b \in \mathbb R$ with $a < b$, the sets $(0,1)$ and $(a,b)$ are equipollent.
\item The sets $(0,1)$ and $(- \infty, \infty)$ are equipollent.
\end{enumerate}

\newpage
\section{Uncountability}

\noindent Lemma 1: $\mathbb N \times \mathbb N$ is countable.\\
\\
Sketch of Proof: Well, we need a bijection from the naturals to the set of all ordered pairs of naturals.  The diagram below suggests how this can be accomplished, with Exercise 10 of section 1.10 providing the most important of the details of the proof.  The idea is that we imagine all of the ordered pairs laid out as shown, and then sweep through them in order along the indicated diagonals.  Each ordered pair will be reached exactly once.$\qed$ \\
\[
\begin{matrix}
  (0,0) &   & (0,1) &   & (0,2) & ...\\
           & \swarrow &   & \swarrow &   & \swarrow \\
  (1,0) &   & (1,1) &   & (1,2) & ...\\
           & \swarrow &   & \swarrow &   & \swarrow \\
  (2,0) &   & (2,1) &   & (2,2) & ... \\
  \vdots & \swarrow & \vdots & \swarrow & \vdots & \ddots 
 \end{matrix}
\] 
\\
Theorem 1: $\mathbb Q$ is countable.\\
\\
Proof: Exercise 1.\\
\\
Theorem 2 (Cantor): $\mathbb R$ is uncountable.\\
\\
Proof: Well suppose, in hopes of obtaining a contradiction, that there were some $f: \mathbb N \to (0,1)$ which was a bijection.  This suffices, by Exercise 7 in section 3.6, to show that there exists no bijection from $\mathbb N$ to $\mathbb R$.  We will show that $f$ is not in fact surjective by constructing an element $x \in \mathbb R$ which has no pre-image.  We do this in steps.  First, look at $f(0)$, and specifically look at the digit just to the right of the decimal point in its decimal expansion*.  If that digit happens to be a 7, then we make the digit just to the right of the decimal place in $x$ be a 3; if it's not a 7, then we make the corresponding digit in $x$ be a 7.  Next look at the digit one place over from the decimal point in $f(1)$, and similarly make that digit in $x$ a 3 or 7 so that it's different from $f(1)$.  Proceed with $f(2), f(3)$, and so on.  Then we have constructed an $x$ which has no pre-image under $f$, since it is different from $f(0)$ in at least the digit immediately after the decimal point, different from $f(1)$ in at least the digit one place to the right of the decimal point, and so forth.  This process disqualifies any purported bijection $f$, contradicting our supposition that such a bijection could exist.$\qed$\\
\\
*This presupposes some facts about real numbers and their decimal expansions, specifically that decimal expansions are unique (enough) --- the essential issue is that the same number can be written 0.7 or 0.6999999..., but that does not invalidate the reasoning here.\\
\pagebreak
\\
{\Large Exercises}
\begin{enumerate}
\item Prove Theorem 1.
\item If there is an injection from $\mathbb N$ to a set $A$, then $A$ is countable.
\item If there is an injection from a set $A$ to $\mathbb N$, then $A$ is countable.
\item If there is a surjection from a set $B$ to $\mathbb N$, then $B$ is countable.
\item If there is a surjection from $\mathbb N$ to a set $B$, then $B$ is countable.
\item If $A$ and $B$ are countable sets, then $A \cup B$ is countable.
\item If $A$ and $B$ are disjoint denumerable sets, then $A \cup B$ is denumerable.
\item If $A$ and $B$ are denumerable sets, then $A \cup B$ is denumerable.
\item If $A$ and $B$ are countable sets, then $A \cap B$ is countable.
\item If $A$ and $B$ are denumerable sets, then $A \cap B$ is denumerable.
\item If $A$ is a countable set, and $a \in A$, then $A - \{a\}$ is countable.
\item $\mathbb Z \times \mathbb Z$ is countable.
\item For any countable sets $A$ and $B$, $A \times B$ is countable.
\item The irrationals are uncountable.
\item $\mathbb R \times \mathbb R$ is uncountable.
\item The union of two uncountable sets $A$ and $B$ is uncountable.
\item The union of a finite collection of finite sets is finite.
\item The union of any collection of finite sets is finite.
\item The union of a finite collection of countable sets is countable.
\item The union of a countable collection of countable sets is countable.
\item The union of any collection of countable sets is countable.
\item Any infinite set can be put in a bijective correspondence to one of its proper subsets.
\item If $A$ is an infinite set, then $\mathcal{P}(A)$ is not equipollent to $A$.
\end{enumerate}

\end{document}