1 files changed, 192 insertions, 0 deletions
diff --git a/gupta/hw9.tex b/gupta/hw9.tex
new file mode 100644
index 0000000..161e2a1
--- /dev/null
+++ b/gupta/hw9.tex
@@ -0,0 +1,192 @@
+\newfam\bbold
+\def\bb#1{{\fam\bbold #1}}
+\font\bbten=msbm10
+\font\bbsev=msbm7
+\font\bbfiv=msbm5
+\textfont\bbold=\bbten
+\scriptfont\bbold=\bbsev
+\scriptscriptfont\bbold=\bbfiv
+\font\bigbf=cmbx12 at 24pt
+
+\def\answer{\smallskip{\bf Answer.}\par}
+\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt
+depth 0pt{\parfillskip0pt\medskip}}
+\let\endanswer\endproof
+\def\section#1{\vskip18pt plus 6pt minus 6pt\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in%
+\noindent{\bf #1}}
+\let\impl\to
+\def\nmid{\hskip-3pt\not\hskip2.5pt\mid}
+\def\problem#1{\bigskip\par\penalty-100\item{#1}}
+
+\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday
+2022-03-17 at 11:59 pm}\hrule height .5pt}}
+
+\centerline{\bigbf Homework 8 - Holden Rohrer}
+\bigskip
+
+\noindent{\bf Collaborators:} None
+
+\section{Hammack 13.2: 4, 6, 8, 13}
+
+\problem{4.}
+Prove that the set of all irrational numbers is uncountable.
+(Suggestion: consider proof by contradiction using Theorems 13.4 and
+13.6)
+
+\answer
+Theorem 13.4 tells us that the rationals are a countably infinite set.
+Assume for the sake of contradiction that the irrational numbers are
+countable.
+By definition of the irrational numbers, the union of the rationals and
+irrationals are the real numbers.
+By theorem 13.6, the real numbers must then be a countable set.
+However, we know that $\bb R$ is uncountably infinite, giving a
+contradiction.
+Therefore, the irrational numbers are uncountable.
+\endanswer
+
+\problem{6.}
+Prove or disprove: There exists a bijective function $f: \bb Q\to\bb
+R.$
+
+\answer
+{\bf Disproof.}
+
+By the textbook, $\bb Q$ is countably infinite, so we have a bijection
+$g: \bb N\to \bb Q.$
+For the sake of contradiction, assume there exists a bijective function
+$f: \bb Q\to \bb R.$
+
+We now have a bijection $g\circ f:\bb N\to \bb R,$ because the
+composition of bijections is bijective.
+However, this function cannot be surjective because we can construct a
+real number $r$ not in the image of $g\circ f$ by setting the $i$th
+digit of $r$ to be different from the $i$th digit of $g(f(i))$ (e.g. by
+choosing 0 unless the $i$th digit of $g(f(i))$ is 0).
+We have reached a contradiction, so $f$ must not exist.
+
+\endanswer
+
+\problem{8.}
+Prove or disprove: The set $\bb Z\times\bb Q$ is countably infinite.
+
+\answer
+{\bf Proof.}
+
+$\bb Q$ is countably infinite, and $\bb Z$ is countably infinite because
+$\bb Z$ is the union of $\{1-n : n\in\bb N\}\cup \bb N,$ ($\bb Z$ is
+countably infinite since the union of countably infinite sets is
+countably infinite) so by a theorem proved in the textbook, $\bb
+Z\times\bb Q$ is countably infinite.
+
+\endanswer
+
+\problem{13.}
+Prove or disprove: If $A = \{X\subseteq\bb N : X\hbox{ is
+finite}\},$ then $|A| = \aleph_0.$
+
+\answer
+{\bf Proof.}
+
+To all finite sets of natural numbers, we can bijectively assign a
+corresponding whole number ($\bb N\cup\{0\}$) defined by its binary
+representation (if $i\in X,$ the $i$th least significant bit is one,
+otherwise zero).
+This is necessarily surjective because all finite numbers have a finite
+number of ones in binary and thus a corresponding set in $A.$
+It is also injective because any sets which differ by an element must
+also differ in their binary representation by a one or a zero.
+
+Therefore $|A| = 1+|\bb N| = \aleph_0.$
+
+\endanswer
+
+\section{Hammack 13.3: 8, 10}
+
+\problem{8.}
+Prove or disprove: If $A\subseteq B$ and $A$ is countably infinite and
+$B$ is uncountable, then $B-A$ is uncountable.
+
+\answer % assume contrapositive. b-a is countable.
+We will prove this by assuming the contrapositive and showing that $B$
+is countable.
+Let $B-A$ and $A\subseteq B$ be countable sets.
+By theorem 13.6 and $(B-A)\cup A = B,$ (since $A\subseteq B$) $B$ is
+countable.
+\endanswer
+
+\problem{10.}
+Prove that if $A$ and $B$ are finite sets with $|A|=|B|,$ then any
+surjection $f:A\to B$ is also an injection. Show this is not necessarily
+true if $A$ and $B$ are not finite.
+
+\answer
+
+Let $A$ and $B$ be finite sets with $|A|=|B|=n.$
+We enumerate the elements of $A$ as $a_1,a_2,\ldots,a_n.$
+Let us have some surjection $f:A\to B.$
+We then let $f(a_i) = b_i.$
+Since this is a surjection, all $n$ elements of $B$ must be listed in
+$b_1,b_2,\ldots,b_n.$
+If $b_i = b_j,$ we must have $i=j$ because otherwise we have
+double-counted an element in $B,$ so $B$ would contain less than $n$
+elements.
+Then, we have $f(a_i) = f(a_j)$ implies $i = j$ so $a_i = a_j.$
+
+\endanswer
+
+\section{Hammack 13.4: 4, 5}
+
+\problem{4.}
+Let ${\cal F}$ be the set of all functions $\bb R\to\{0,1\}.$ Show that
+$|\bb R|<|{\cal F}|.$
+
+\answer
+We will show that $|\bb R| < |{\cal F}|$ by showing a bijection between
+${\cal F}$ and ${\cal P}(\bb R).$
+Let $f,g\in{\cal F}.$
+Let us define corresponding sets $R,S.$ $r\in R$ if and only if
+$f(r)=1,$ and $S$ similarly defined with respect to $g.$
+This is injective because if $R=S,$ $f(r)=g(r)$ for all reals, so $f=g.$
+This is surjective because any $R\subseteq\bb R$ has a corresponding $f$
+where $f(r) = 1$ if and only if $r\in R.$
+\endanswer
+
+\problem{5.}
+Consider the subset $B = \{(x,y): x^2+y^2\leq 1\}\subseteq\bb R^2.$ Show
+that $|B| = |\bb R^2|.$
+
+\answer
+
+We will show this by the Cantor-Bernstein-Schr\"oeder theorem.
+We start with the trivial injection $f:B\to \bb R^2,$ defined $f(x,y) =
+(x,y).$
+
+Then we use the injection $g:\bb R^2\to B,$ defined $g(x,y) =
+{(x,y)\over 1+(x^2+y^2)}.$
+We will show this is injective.
+Let $g(x,y) = g(w,z).$
+${(x,y)\over 1+(x^2+y^2)} = {(w,z)\over 1+(w^2+z^2)}.$
+
+${(x,y)\over 1+(x^2+y^2)} = {(w,z)\over 1+(w^2+z^2)}.$
+
+\endanswer
+
+\section{Problem not from the textbook}
+
+\problem{1.} Write out the multiplication table for the group $(\bb
+Z_{12}^*,
+\cdot).$ (Recall that $\bb Z_{12}^* = \{[k]:\gcd(k,12)=1\}.$)
+
+\answer
+\halign{\strut#\quad\vrule&&\quad#\quad\cr
+    $*$ &1 &5 &7 &11\cr\noalign{\hrule}
+    1  &1 &5 &7 &11\cr
+    5  &5 &1 &11&7 \cr
+    7  &7 &11&1 &5 \cr
+    11 &11&7 &5 &1 \cr
+}
+
+\endanswer
+
+\bye