\documentclass[UTF8, 11pt]{amsart}
\usepackage{hyperref}
\usepackage{amsthm}
\usepackage{tikz}

\title{MATH 3040: Homework 11}
\author{}
\date{November 15, 2017}

%----------Theorems----------

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{nondefinition}[theorem]{Non-Definition}
\newtheorem{exercise}[theorem]{Exercise}

\renewcommand{\P}{\mathcal{P}}
\newcommand{\N}{\textbf{N}}
\newcommand{\NN}{\textbf{N}}
\newcommand{\RR}{\textbf{R}}
\newcommand{\Z}{\textbf{Z}}

%Redefine the first level
\renewcommand{\theenumi}{(\alph{enumi})}
\renewcommand{\labelenumi}{\theenumi}

\begin{document}

\maketitle

All answers must be in complete sentences. All assertions must be proven, per the student contract. Remember that this is a writing class, so while correctness and thoroughness are most important, \textit{style} matters as well. 


\bigskip
\noindent
\textbf{1. (Practice in Posing Questions)} What is an interesting open-ended question you could ask, which is related to the material that we covered in class? What is a concrete mathematical question that could be used to approach an answer to the question? 


\bigskip
\noindent
\textbf{2. (Wrap-up: Uncountability of $(0,1)$)} The open interval $(0,1) \subset \RR$ is not countable.
Suppose for the sake of contradiction that there exists a bijection $f: \NN \to (0,1)$. For each $n \in \NN$ its image under $f$ is some number in $(0,1)$.
Let $f(n) := 0.a_{1n} a_{2n} a_{3n} \ldots$ where $a_{1n}$ is the first digit in decimal form, $a_{2n}$ is the second digit, etc. If $f(n)$ terminates after $k$ digits, then our convention will be to continue the decimal form with 0's. Now, define $b = 0.b_1 b_2 b_3 \ldots$ where
\[
b_i =
\begin{cases}
2, & \text{if $a_{ii} \neq 2$} \\
3, & \text{if $a_{ii} =2$}.	
\end{cases}
\]
\begin{enumerate}
  \item[(a)]{Prove that the decimal expansion that defines $b$ is in \textbf{standard form}, where there is no $k$ such that for all $i > k$, we have $b_i = 9$.}
  \item[(b)]{Prove that for all $n \in \NN$, we have $f(n) \neq b$. Explain why we have a contradiction.}
  \item[(c)]{Why does this imply that the real numbers are not countable?}
\end{enumerate}

\bigskip
\noindent
\textbf{3. (Wrap-up: infinite cardinalities)} Let $S$ be the set of infinite sequences of 0's and 1's. Is $S$ countable or uncountable?	

\bigskip
\noindent
\textbf{4. (Prove or Disprove and Salvage)} Let $S$ be a nonempty set, and suppose that $R_1$ and $R_2$ are relations on $S$.
\begin{enumerate}
  % a
  \item{If $R_1$ and $R_2$ are symmetric, then $R_1 \cup R_2$ is symmetric.}
  
  % b
  \item{If $R_1$ and $R_2$ are transitive, then $R_1 \cup R_2$ is transitive.}
  
  % c
  \item{If $R_1$ or $R_2$ is transitive, then $R_1 \cup R_2$ is transitive.}
  
  % d
  \item{If $R_1$ or $R_2$ is reflexive, then $R_1 \cap R_2$ is reflexive.}
  
  % e
  \item{If $R_1$ or $R_2$ is transitive, then $R_1 \cap R_2$ is transitive.}
\end{enumerate}


\bigskip
\noindent
\textbf{5. (Decomposition of Functions)} Here, we'll show that every function is the composition of a surjection with an injection. Let $f: A \to B$ be a function. Define a relation $\sim$ on $A$ by
$$
a_1 \sim a_2 \quad \text{if and only if} \quad f(a_1) = f(a_2)
$$
for all $a_1,a_2 \in A$. Let $A/\sim$ denote the set of equivalence classes of $A$ with respect to $\sim$.
\begin{enumerate}
 \item Prove that $\sim$ is an equivalence relation.
 \item Define a function $p: A \to A/\sim$ by $p(a) = [a]$ for all $a \in A$. Show that $p$ is surjective.
 \item Define a function $F: A/\sim \to B$ by $F([a]) = f(a)$. Prove that $F$ is a well-defined injection.
 \item Prove that $f = F \circ p$.
\end{enumerate}

\bigskip
\noindent
\textbf{6. (Equivalence Relations)}
\begin{enumerate}
  % a
  \item{Let $A$ be a non-empty set and $B$ a fixed subset of $A$. We define a relation on the powerset $\mathcal{P}(A)$ of $A$ by $X \sim Y$ if $X \cap B = Y \cap B$. Show that this is an equivalence relation.}	
  
  % b
  \item{Define a relation on the integers as follows: $a \sim b$ if $a+b$ is even. What properties does this relation satisfy? Is this an equivalence relation? What about if we change the condition to $a \sim b$ if $a+b$ is odd?}
  
  % c
  \item{Let $H = \{ 2^m : m \in \Z \}$. Define a relation on the set $\textbf{Q}^+$ of positive rational numbers by $a \sim b$ if $a/b \in H$. Show that $\sim$ is an equivalence relation and describe the equivalence class that contains the number 3.}
\end{enumerate}




\bigskip
\bigskip
\noindent
The following questions are to be done as a group.


 

\bigskip
\noindent
\textbf{7. (Groupwork) [Counting Cycles]} A graph on $n$ vertices is said to be \textbf{complete} if all pairs of distinct vertices are adjacent. 
\begin{enumerate}
  % a
  \item{If $G$ is a complete graph of $5$ vertices, how many cycles of length 3 are there? Length 4? Find and prove a formula for the number of cycles of length $k$ (they are called \textbf{$k$-cycles}). Note that no graph has cycles of length 1 or 2, and that for sufficiently large $k$, there are no $k$-cycles on $G$.}
  % b
  \item{Find and prove a formula for the number of $k$-cycles on a complete graph $G$ of $n$ vertices.}
  
  % c
  \item{Suppose that $G$ is obtained by taking a complete graph on $n$ vertices and removing an edge. How many $k$-cycles are in $G$?}	
\end{enumerate}


\bigskip
\noindent
\textbf{8. (Groupwork) [A Royal Party]}
\begin{enumerate}
  % a
  \item{When $n$ couples arrived at a party given by the King and Queen, a certain number of handshakes took place. The King asked each of the other people present how many people they shook hands with. (Assume that they do not shake hands with anybody except the King, the Queen, and each other. So the staff, guards, royal children, housepets, etc. are not involved in this handshaking process.) Surprisingly, all the answers were different! How many hands did the Queen shake? (We don't know who shook hands with whom, but we assume that if two people were in a couple, they did not shake each other's hand. That would be weird.)}	
  
  % b
  \item{Now, suppose that everyone (the $n$ couples, the King and Queen) take a seat around a round table for dinner. Tradition dictates that the Queen be served first, and then the servers move around the table clockwise and serve the \textit{second} person who has not been served yet. For example, if there are $n=2$ couples coming so that there are 6 people total and the spots in the table are numbered clockwise $1, 2, 3, 4, 5, 6$ where the Queen is at ``1," the servers serve spots 1, 3, 5, 2, 6, and 4, in that order. The King hates when his meal gets cold, and so wishes to be served last. If there are $n$ couples coming to the party, at what number place should the King sit?}
\end{enumerate}

\end{document}
