From 18a1af1b1fbc5ae3572e011b267caa7bef293f62 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Fri, 29 Apr 2022 18:54:17 -0400 Subject: added all new homework for Neha's class --- gupta/hw9.tex | 192 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 192 insertions(+) create mode 100644 gupta/hw9.tex (limited to 'gupta/hw9.tex') 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 -- cgit