\documentclass[letterpaper,12pt]{book}

\author{Jonathan J. White}
\title{Foundations of Advanced Mathematics, version 0.7}
\date{3/24/16}

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

\begin{document} 

\setcounter{page}{53}
\setcounter{chapter}{3}
\chapter{Relations \& Graphs}
\section{Relations}
\noindent Definition: Let $A$ and $B$ be sets.  A \textbf{relation} from $A$ to $B$ is a subset of $A \times B$.  When we have a relation from $A$ to $A$ we often call it a \textbf{relation on $A$}.  When we have a relation $R$ on $A \times B$, instead of writing $(x, y) \in R$ we often write $x\,R\,y$.\\
\\
Example 1: We define a relation $N$ on $\mathbb R$ as follows: $N = \{(x, y) \in \mathbb{R} \times \mathbb{R} | x = -y\}$.  Then for instance $(-3,3) \in N$, which could also be written $-3\,N\,3$.  This relation is a more formal version of what might be expressed as ''is the negative of'' as in, ''$-3$ is the negative of 3.''\\
\\
Example 2: We define a relation $\sim$ on $\mathbb Z$ as follows: $\sim = \{(n, m) \in \mathbb Z \times \mathbb Z \, | \, \exists k \in \mathbb Z, n - m = 2k\}$.  Then for instance $3 \sim 5$ and $6 \sim 20$, but it is not the case that $3 \sim 4$; which might naturally be denoted $3 \nsim 4$.  You should recognize that $m \sim n$ when either both values are even or both values are odd.\\
\\
{\Large Exercises}\\
For each of the relations specified below:
\begin{enumerate}
\item[(a)]	Pick an element $t$ of the set in question and find (if possible) three other elements of the set which are related to it.
\item[(b)]	For your element $t$ from part a, find three other elements of the set which are not related to it.
\end{enumerate}
\begin{enumerate}
\item Let $\sim$ be the relation on $\mathbb N$ defined by $x \sim y$ iff $x - y$ is throdd.
\item Let $\approx$ be the relation on $\mathbb R$ defined by $x \approx y$ iff $x - y \in \mathbb Z$.
\item Let $\simeq$ be the relation on $\mathbb R$ defined by $x \simeq y$ iff $x - y \in \mathbb Q$.
\item Let $\cong$ be the relation on $\mathbb Z$ defined by $x \cong y$ iff $|x - y| = 5$.
\item Let $\circeq$ be the relation on the set $P(\mathbb R)$ of all polynomials with real coefficients defined by $f \circeq g$ iff $f$ and $g$ have a root in common.
\item Let $\asymp$ be the relation on the set $R(I)$ of integrable functions from $[0,1]$ to $\mathbb R$ defined by $f \asymp g$ iff $\int_0^1 f(x) \, dx = \int_0^1 g(x) \, dx$.
\item Let $\succ$ be the relation on the set $\mathbb R$ defined by $x \succ y$ iff $x > y + 5$.
\item Let $\ggg$ be the relation on the set $\mathbb R$ defined by $x \ggg y$ iff $x > 3y$.
\item Let $\subseteq$ be the usual subset relation on $\mathcal{P}(\mathbb N)$, the power set of the natural numbers.
\item Let $\bowtie$ be the relation on $\mathcal{P} (\mathbb N)$ defined by $A \bowtie B$ iff $A \cap B \neq \varnothing$.
\end{enumerate}

\newpage
\section{Properties of Relations}
\noindent Simply put, some relations are more interesting than others.  This section explores properties that are often shared by some of the more interesting (and useful) relations used in mathematics.\\
\\
Definition: A relation $\sim$ on a set $S$ is \textbf{reflexive} iff $\forall a \in S, a \sim a$.\\
Definition: A relation $\sim$ on a set $S$ is \textbf{symmetric} iff $\forall a, b \in S, a \sim b \Rightarrow b \sim a$.\\
Definition: A relation $\sim$ on a set $S$ is \textbf{transitive} iff $\forall a, b, c \in S, a \sim b \wedge b \sim c \Rightarrow a \sim c$.\\
\\
{\Large Exercises}
\begin{enumerate}
\item Determine whether each of the relations from Exercises 1-10 in §4.1 is reflexive, symmetric, or transitive.
\item Consider the relation $B$ on the set of all people defined by $a B b$ iff $a$ is a brother of $b$.  Is this relation reflexive, symmetric, or transitive?
\item Consider the relation $S$ on the set of all people defined by $a S b$ iff $a$ is a sibling of $b$.  Is this relation reflexive, symmetric, or transitive?
\end{enumerate}
\noindent For 4-11, let $S = \{a, b, c\}$.  Give an example, if possible, of a relation on $S$ which is:
\begin{enumerate}[resume]
\item Reflexive, symmetric, transitive.
\item Reflexive, symmetric, not transitive.
\item Reflexive, not symmetric, transitive.
\item Reflexive, not symmetric, not transitive.
\item Not reflexive, symmetric, transitive.
\item Not reflexive, symmetric, not transitive.
\item Not reflexive, not symmetric, transitive.
\item Not reflexive, not symmetric, not transitive.
\item If two relations $R$ and $S$ on $A$ are reflexive, is $R \cup S$ reflexive?  $R \cap S$?
\item If two relations $R$ and $S$ on $A$ are symmetric, is $R \cup S$ symmetric?  $R \cap S$?
\item If two relations $R$ and $S$ on $A$ are transitive, is $R \cup S$ transitive?  $R \cap S$?
\end{enumerate}

\newpage
\section{Equivalence Relations}
\noindent As noted in the last section, some relations are more useful than others.  Particularly useful are ones with some common characteristics that in turn lead to other properties, as developed below.\\
\\
Definition: A relation which is reflexive, symmetric, and transitive is called an \textbf{equivalence relation}.\\
\\
Example 1: Congruence of triangles, which should be familiar to you from high school geometry, is an equivalence relation.\\
\\
Example 2: We defined congruence modulo n in section 1.5; note that Exercises 14-16 in that section amount to a proof that this gives an equivalence relation on $\mathbb Z$.\\
\\
Example 3: Exercises 1-3 in section 3.6 prove that equipollence provides an equivalence relation on the set of all subsets of any universal set.\\
\\
Definition: Given a set $S$, an element $a \in S$, and an equivalence relation $\sim$ on $S$, the set of elements of $S$ that are related to $a$ is called the \textbf{equivalence class} of $a$ and denoted $[a]$, i.e. $[a] = \{x \in S \, | \, x \sim a\}$.\\
\\
Example 4: If we consider, as in Example 2 above, the equivalence relation of congruence modulo 2, then the equivalence class of 1 includes 3 since $3 - 1 = 2$, and $2 = 2 \cdot 1$ where $1 \in \mathbb Z$.  In fact, [1] is exactly the odd integers.\\
\\
Example 5: For the equivalence relation of equipollence on some collection of sets mentioned in Example 3 above, the equivalence class of a set with, say, 2 elements will be all of the other sets having exactly 2 elements.  If the collection of sets included $\mathbb R$ and all of its subsets, then the equivalence class of $\mathbb R$ itself would include the set of irrationals (among many others), and the equivalence class of $\mathbb N$ would include $\mathbb Z$ and $\mathbb Q$ (among many others).\\
\\
Definition: A set $C$ of sets is \textbf{pairwise disjoint} iff $\forall S_1, S_2 \in C, S_1 \cap S_2 = \varnothing$ or $S_1 = S_2$.\\
Definition: A \textbf{partition} of a set $S$ is a set of pairwise disjoint non-empty subsets of $S$ whose union is all of $S$.\\
\\
Theorem 1: Let $S$ be a set and $\Pi$ a partition of $S$.  The relation on $S$ defined by $a \sim b$ iff $\exists P \in \Pi$ for which $a, b \in P$ is an equivalence relation.\\
\\
Proof: Exercises 10-12.\\
\\
\nopagebreak
Theorem 2: Let $S$ be a set and $\sim$ be an equivalence relation on $S$.  The set $\{[a] \, | \, a \in S\}$ is a partition of $S$.\\
\\
Proof: Exercise 13.\\
\\
{\Large Exercises}
\begin{enumerate}
\item Consider the relation $|||$ on $\mathbb Z$ defined by $a ||| b$ iff $a - b$ is threven.  Determine whether $|||$ is an equivalence relation.
\item Consider the relation $\sim$ on $\mathbb Z$ defined by $a \sim b$ iff $|a| = |b|$.  Determine whether $\sim$ is an equivalence relation.
\item Consider the relation $\approx$ on $\mathbb R \times \mathbb R$ defined by $(x_1, y_1) \approx (x_2, y_2)$ iff $x_1^2 + y_1^2 = x_2^2 + y_2^2$.  Determine whether $\approx$ is an equivalence relation.
\item Consider the relation $\nearrow$ on $\mathbb R \times \mathbb R$ defined by $(x_1, y_1) \nearrow (x_2, y_2)$ iff $x_1 > x_2 \vee (x_1 = x_2 \wedge y_1 \geq y_2)$.  Determine whether $\nearrow$ is an equivalence relation.
\item For any of the relations in Exercises 1-4 which are equivalence relations, describe the equivalence classes.
\item A collection $C$ of sets $S_i$ indexed by some set $I$ is pairwise disjoint iff $\bigcap_{i \in I} S_i = \varnothing$.
\item Let $S = \{1, 2, 3, 4\}$.  Then $R =\{(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)\}$ is a relation on $S$.  Write the equivalence classes of $S$ associated with $R$.
\item Let $S = \{1, 2, 3, 4\}$.  Suppose that $\sim$ is an equivalence relation with $1 \sim 2 \sim 3$, but $1 \not \sim 4$.  What is the partition associated with $\sim$?
\item Let $S = \{1, 2, 3, 4\}$.  Suppose that $\sim$ is an equivalence relation with $1 \sim 4$.  What are the possible partitions associated with $\sim$?
\item Show that the relation defined in Theorem 1 is reflexive.
\item Show that the relation defined in Theorem 1 is symmetric.
\item Show that the relation defined in Theorem 1 is transitive.
\item Prove Theorem 2.
\end{enumerate}

\newpage
\section{Functions as Relations}
\noindent Chapter 3 was devoted to functions (and their implications via equipollence), but only gave a limited version of what functions actually are.  This section gives the mature version.\\
\\
Definition: A relation $R$ from $A$ to $B$ is a \textbf{function} from $A$ to $B$ iff for all $a \in A$ there exists a unique $b \in B$ for which $(a, b) \in R$.  Due to this uniqueness we often write $R(a) = b$ when $(a, b) \in R$.\\
\\
While technically it's improper to give a new definition of a term that was previously defined (in section 3.1), in fact our previous definition was vague on exactly the point this new version allows us to make precise.  Before there was reference to a “rule” without any specification of what might be allowable as a rule (can you roll dice, for instance?).  This new version specifies, and in terms of material (set theory) that we have previously developed.\\
\\
Example 1: Consider $f = \{(x, y) \in \mathbb R \times \mathbb R \, | \, x^2 = y\}$ as a function from $\mathbb R$ to $\mathbb R$.  This is the standard parabola familiar to all Calc 1 students, but presented in a more formal manner.\\
\\
Example 2: Consider $i_A = \{(a, a) \, | \, a \in A\}$ as a function from $A$ to $A$.  This is the identity function on $A$ defined in section 3.1, now presented in a more sophisticated way.\\
\\
{\Large Exercises}
\begin{enumerate}
\item Express the constant function $f(x) = c$ from $\mathbb R$ to $\mathbb R$ formally as a set of ordered pairs.
\item Express the inclusion function from $A$ to $B$ formally as a set of ordered pairs.
\item Express the definition of an even function in terms of ordered pairs.
\item Express the definition of an odd function in terms of ordered pairs.
\item Express the definition of an increasing function in terms of ordered pairs.
\item Express the definition of a decreasing function in terms of ordered pairs.
\item Express the definition of a bounded function in terms of ordered pairs.
\item Express the definition of the sum of two functions in terms of ordered pairs.
\item Express the definition of the product of two functions in terms of ordered pairs.
\item Express the definition of the composition of two functions in terms of ordered pairs.
\item Express the definition of a surjective function in terms of ordered pairs.
\item Express the definition of an injective function in terms of ordered pairs.
\item Express the definition of an inverse function in terms of ordered pairs.
\item Suppose that $f$ and $g$ are functions from $A$ to $B$.  Is $f \cup g$ a function from $A$ to $B$?  $f \cap g$?
\end{enumerate}

\newpage
\section{Graph Theory}
\noindent First, a disclaimer: the graphs in the section are not the graphs of Calculus or high school algebra, but instead the graphs involved in the area of mathematics and computer science called graph theory.  Although we will not explore this area in much depth, it fits naturally with the rest of the material in this chapter and is so widely seen in applications of mathematics to interesting situations that any serious math student should be acquainted with it.\\
\\ 
Definition: A \textbf{graph} $G$ is a set $V$ of vertices along with a set $E$ of edges, where each \textbf{edge} is a set containing exactly two vertices.\\
\\
You should note that this is almost identical to the definition of a relation on a set $V$ -- see Exercise 3.\\
\\
Definition: The \textbf{degree} of a vertex $v$ in a graph, sometimes denoted $\boldsymbol{d(v)}$, is the number of edges containing $v$.\\
\\
Definition: A \textbf{walk} is a sequence $v_0, e_1, v_1, e_2, v_2, ... , e_n, v_n$, alternating vertices and edges, starting  and ending with vertices, and where each edge is adjacent to the preceding and succeeding vertices.  A \textbf{path} is a walk in which all the vertices are distinct.  A \textbf{cycle} is a walk in which all vertices except the first and last are distinct, $v_0 = v_n$ and $n \geq 3$.\\
\\
Definition: A graph $G$ is said to be \textbf{connected} iff every pair of points is joined by a walk.\\
\\
Definition: A \textbf{tree} is a connected graph with no cycles.\\
\\
{\Large Exercises}
\begin{enumerate}
\item How many different graphs are there with three vertices?
\item How many different graphs are there with four vertices?
\item Describe the connection between a relation $R$ on a set $V$ and a graph $G$ with the set $V$ of vertices.
\item Create a relation based on a graph $G$ by saying elements $v_1, v_2 \in V$ are related iff there exists a walk from $v_1$ to $v_2$.  Is the resulting relation reflexive?  Symmetric?  Transitive?
\item The maximum possible number of edges in a graph with $n$ vertices is \rule{1 in}{1 pt}.
\item The number of edges in a tree with $n$ vertices is \rule{1 in}{1 pt}.
\item The minimum number of edges in a connected graph with $n$ vertices is \rule{1 in}{1 pt}.
\item The sum of the degrees of the vertices in a graph is twice the number of edges in the graph.
\item In any graph, the number of vertices of odd degree is even.
\item A graph with all vertices of degree 3 is \textbf{cubic}.  Every cubic graph has an even number of vertices.
\item The maximum number of vertices of degree 1 in a tree with $n$ vertices is \rule{1 in}{1 pt}.
\item The minimum number of vertices of degree 1 in a tree with $n$ vertices is \rule{1 in}{1 pt}.
\item The maximum number of vertices of degree 2 in a tree with $n$ vertices is \rule{1 in}{1 pt}.
\item The minimum number of vertices of degree 2 in a tree with $n$ vertices is \rule{1 in}{1 pt}.
\item Find all trees with $n \leq 6$ vertices.
\item Find all trees with $n = 7$ vertices.
\item Find all trees with $n = 8$ vertices.
\item Any graph where each vertex has degree at least 2 is connected.
\item Any graph where each vertex has degree at least 3 is connected.
\item Any graph where each vertex is part of a cycle is connected.
\item Any graph where some vertex $v_0$ is joined to each other vertex in the graph by a walk is connected.
\item If a graph $G$ is connected, then the graph $G'$ having the same vertex set and an edge set with exactly one fewer element is also connected.
\item If a graph $G$ is connected, then the graph $G'$ having a vertex set with exactly one fewer element and an edge set with all elements not including that removed vertex is also connected.
\item An \textbf{Euler path} in a graph $G$ is a path which passes through each edge of $G$ exactly once.  An Euler path exists in a connected graph $G$ iff there are exactly two vertices of odd degree in $G$.
\item A \textbf{planar graph} is one which can be drawn in the plane without any edges crossing each other.  In any planar, connected graph with $v$ vertices and $e$ edges, where $v \geq 3, e \leq 3v - 6$.
\item In any planar, connected graph with $v$ vertices and $e$ edges, dividing the plane into $f$ distinct regions (including the exterior), $v - e + f = 2$.
\item Let  $\boldsymbol{K_n}$ denote the \textbf{complete graph} on $n$ vertices, a graph with $n$ vertices and edges connecting every pair of vertices.  Find the number of edges in $K_n$.
\item $K_4$ is planar.
\item $K_5$ is planar.
\item A \textbf{subgraph} $H$ of a graph $G$ is a graph with the vertex set of $H$ a subset of the vertex set of $G$, and the edge set of $H$ all edges from $G$ for which both vertices are in the vertex set of $H$.  A subgraph of a connected graph is connected.
\item If a graph $G$ has all of its subgraphs connected, then $G$ is connected.
\item A subgraph of a planar graph is planar.
\item If a graph $G$ has all of its subgraphs planar, then $G$ is planar.
\item A \textbf{spanning tree} for a graph $G$ is a subgraph of $G$ which is a tree containing all vertices of $G$.  Any graph $G$ has a spanning tree.
\item Any connected graph has a unique spanning tree.
\item Any graph with a spanning tree is connected.

\end{enumerate}

\newpage
\section{Directed Graphs}
\noindent A natural extension of the graphs considered in the previous section allows for one-way connections.  The real-world situations that can be considered with such tools are abundant, but here we consider them abstractly.\\
\\ 
Definition: A \textbf{directed graph} $D$ (sometimes called a \textbf{digraph}) is a set $V$ of vertices along with a set $A$ of arcs, where each \textbf{arc} is an ordered pair of distinct vertices.\\
\\
Obviously this is very similar to the definition of a graph, to the point where they can easily be confused -- sometimes you need to read carefully to see which is being considered.  We think of the arcs in a directed graph as one-way connections from the first vertex to the second vertex.\\
\\
Definition: The \textbf{outdegree} of a vertex $v$ in a graph, sometimes denoted $\boldsymbol{od(v)}$, is the number of arcs with first element $v$.  The \textbf{indegree} of a vertex $v$ in a graph, sometimes denoted $\boldsymbol{id(v)}$, is the number of arcs with second element $v$.\\
\\
Definition: A \textbf{walk} in a directed graph is a sequence $v_0, a_1, v_1, a_2, v_2, ... , a_n, v_n$, alternating vertices and arcs, starting  and ending with vertices, and where each arc has the preceding vertex as its first element and the succeeding vertix as its second element.  A \textbf{path} is a walk in which all the vertices are distinct.  A \textbf{cycle} is a walk in which $v_0 = v_n$ and $n \geq 2$.\\
\\
Definition: A directed graph $D$ is said to be \textbf{strongly connected} iff every pair of points is joined by a walk.\\
\\
{\Large Exercises}
\begin{enumerate}
\item How many different directed graphs are there with two vertices?
\item How many different directed graphs are there with three vertices?
\item How many different directed graphs are there with four vertices?
\item The maximum possible number of edges in a digraph with $n$ vertices is \rule{1 in}{1 pt}.
\item What is the relation between the total indegree and total outdegree of the vertices in a digraph?
\item The minimum number of edges in a strongly connected digraph with $n$ vertices is \rule{1 in}{1 pt}.
\item Any digraph where each vertex has indegree at least 1 is connected.
\item Any digraph where each vertex has indegree and outdegree at least 1 is connected.
\end{enumerate}

\newpage
\section{More on Graphs}
\noindent Definition: Given vertices $u$ and $v$, the \textbf{distance} from $u$ to $v$ is the length of the shortest path from $u$ to $v$.   The \textbf{diameter}, $\boldsymbol{d(G)}$,  of a graph $G$ is the maximum distance between points in $G$. The \textbf{eccentricity}, $\boldsymbol{e(v)}$, of a vertex $v$ in a connected graph is the maximum distance between $v$ and other points $u$ in the graph.  The \textbf{radius}, $\boldsymbol{r(G)}$, of a graph is the minimum eccentricity over all points in a graph.  A point $v$ is a \textbf{central point} if $e(v) = r(v)$.  The \textbf{center} of a graph $G$ is the set of all central points in $G$.\\
\\
{\Large Exercises}
\begin{enumerate}
\item Give an example of a graph with radius 3 and diameter 4.
\item Give an example of a graph with radius 3 and diameter 3.
\item Give an example of a graph with radius 3 and diameter 7.
\item The diameter $d(G)$  of a graph $G$ is the length of the longest path between points in $G$.
\item Find the radius and diameter of $K_n$.
\item Find the radius and diameter of $C_n$.
\item How large can the center of a graph be?
\item How large can the center of a tree be?
\item What is the connection between eccentricity and diameter?
\end{enumerate}
\end{document}