path: root/gupta/hw9.tex

\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