\documentclass[12pt]{article}
\usepackage[margin=0.7in]{geometry}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\usepackage{fancyhdr}
% lastpage may not be part of your installation; it's a somewhat
% nonstandard package that determines the page number of the last page
% of your document, and allows you to refer to it with
% \pageref{LastPage}. If you don't have it, it can be worked around.
\usepackage{lastpage}
% If you don't have this package, comment this line out and uncomment
% the following lines. It's more convenient with the actual spacing,
% however; that way, I can insert corrections more legibly.
\usepackage{setspace}
%\newcommand{\singlespacing}{}
%\newcommand{\onehalfspacing}{}
% Uncomment the following line and actually put your name into the
% second pair of braces. This will make LaTeX resolve \studentname
% throughout the document as whatever you put in the braces. Note that
% if you don't uncomment this line, your source will not compile!
\newcommand{\studentname}{}
\pagestyle{fancy}
\lhead{MATH 311-02}
\chead{Problem Set \#6}
% This next line will fail to compile unless you uncomment the
% \newcommand up above!
\rhead{\studentname}
\lfoot{}
% If you're not using lastpage, then comment this command out and use
% the simpler version which is commented out below.
\cfoot{Page \thepage\ of \pageref{LastPage}}
%\cfoot{Page \thepage}
\rfoot{\bf due April 25}
\begin{document}
\begin{enumerate}
\item \textbf{(24 points)} \emph{Demonstrate the existence of
bijections between the following pairs of sets.}
\begin{enumerate}
\item \textbf{(4 points)} \emph{The set $\mathbb Z$ and the set of
positive even integers $E=\{2,4,6,8,10,\ldots\}$.}
Let $f:\mathbb Z\rightarrow E$ be given by $f(x)=\left\{
\begin{aligned}
4x&\text{ if }x>0\\
2-4x&\text{ if }x\leq 0
\end{aligned}\right.$.
It is quite easy to see that this function is injective: if $x$
and $y$ were distinct positive integers, clearly $4x\neq 4y$;
likewise if they were distinct nonpositive integers, then
$2-4x\neq 2-4y$. Finally, if $x$ is positive and $y$ is
nonpositive, then $f(x)$ would be divisible by 4 whereas $f(y)$
would not be. Thus, if $x\neq y$, then $f(x)\neq f(y)$.
To see that it is surjective, let us consider an element $y$ of
$E$: if $4\mid y$, then $y=4k$ for some positive integer $k$ and
then $y=f(k)$. If $4\nmid y$, then since $2\mid y$, $y=4k+2$ for
some positive integer $k$, so $y=f(-k)$.
\item \textbf{(5 points)} \emph{The set $\mathbb N$ and the set $A$ of
quadratic functions with integer coefficients
$\{ax^2+bx+c:a,b,c\in\mathbb Z\}$}
Let us divide the quadratics into classes based on the sum of the
absolute value of their coefficients: let class
$A_n=\{ax^2+bx+c:a,b,c\in\mathbb Z,
|a|+|b|+|c|=n\}$. Significantly, each class is finite: $A_0$
contains only 1 polynomial; $A_1$ contains 6 polynomials, $A_2$
contains 18, $A_3$ contains 38, and so forth (we could
conservatively note that since every coefficient in $A_n$ is
between $-n$ and $n$, that $|A_n|\leq(2n+1)^3$; this is a sloppy
bound but enough to assure us each $A_n$ is finite. We may then
simply order each $A_n$ (any way we like) and simply list them
end-to-end to have an enumeration of all quadratics; that is, we
let $f(1)=0x^2+0x+0$, let $f(2)$ through $f(7)$ be the elements of
$A_1$ in any order we like, let $f(8)$ through $f(25)$ be the
elements of $A_2$ in any order we like, and so forth. This is
clearly both an injection and a surjection, since each quadratic
appears in exactly one $A_n$, and thus will be listed exactly
once.
\item \textbf{(5 points)} \emph{The set $\mathbb N$ and the set $S$ of
all \emph{finite} subsets of $\mathbb N$.}
We can use the same trick as in the previous part of dividing our
desired codomain into a countable number of finite parts which we
then list end-to-end: let $S_n$ contain those finite subsets $A$
of $\mathbb N$ for which $\sum_{i\in A}i=n$; so, for instance,
$\{1,3,4\}\in S_8$ since $1+3+4=8$. Significantly, each $S_n$ is
finite: $S_0$ contains only the empty set, $S_1$ contains only
$\{1\}$, $S_2$ contains only $\{2\}$, $S_3$ contains $\{3\}$ and
$\{1,2\}$, and so forth (conservatively, it's easy to show
$|S_n|\leq 2^n$; as above, this is massively inaccurate but
sufficient to show that each $S_n$ is finite). As above, given
this partition of $S$ into a countable number of finite parts, a
bijection $\mathbb N\rightarrow S$ is easy to craft: we just list
$S_0$, then $S_1$, then $S_2$, and so forth, and thus each natural
number is associated with a distinct element of $S$, and since
each $S_i$ is finite, any given element of $S$ will eventually be
reached in this listing.
An imaginative alternative solution involves associating a finite
subset $\{a_1,a_2,\ldots,a_n\}$ of $\mathbb N$ with the natural
number $2^{a_1}+2^{a_2}+2^{a_3}+\cdots+2^{a_n}$. Since binary
representations of natural numbers are uniquely associated with
the numbers they represent, this is clearly a bijection; for
instance, since $53$ is uniquely representable in binary as
$32+16+4+1=2^5+2^4+2^2+2^0$, it would be uniquely asssociated with
the set $\{5,4,2,0\}$.
\item \textbf{(5 points)} \emph{The set $\mathbb R$ and the closed
interval $[0,1]$.}
There are several possible ways to build a bijection here, most of
which are best achieved using two injections and invoking the
Cantor-Schr\"oder-Bernstein Theorem. For instance, we could invoke
$f(x)=\frac1\pi\arctan x+\frac12$ as an easy injection from
$\mathbb R$ to $[0,1]$; we know from precalculus that $\arctan x$
maps the domain $\mathbb R$ injectively into
$(\frac\pi2,\frac\pi2)$; the transformations included in the
statement of $f(x)$ guarantee that it has an image of $(0,1)$
instead. Since we bijectively map $\mathbb R$ into the open
interval $(0,1)$, it is easy to recontextualize this as an
injective map into $[0,1]$ by simply adding $0$ and $1$ to the
codomain (note that this will break surjectivity).
Now we craft the trivial injective map $g(x)=x$ from $[0,1]$ to
$\mathbb R$; at this point, since we have injective $f:\mathbb
R\rightarrow [0,1]$ and injective $g:[0,1]\rightarrow\mathbb R$,
the Cantor-Schr\"oder-Bernstein Theorem guarantees existence of a
bijection $h:\mathbb R\rightarrow [0,1]$.
\item \textbf{(5 points)} \emph{The half-open interval $[0,1)$ and the set
$[0,1)\times[0,1)$.}
It is possible to build an explicit bijeciton here, but far easier
to craft two injections and invoke Cantor-Schr\"oder-Bernstein. We
shall describe a real number $0\leq x<1$ as having a {\em standard
decimal representation} $0.x_1x_2x_3x_4\ldots$ if there is no
value $i$ such that for all $j>i$, $x_j=9$ (we define this
standard to specifically ensure that, for instance, $\frac{3}{20}$
has a unique representation under consideration, since both
$0.15000\ldots$ and $0.14999\ldots$ are decimal expansions
describing this specific number.
Based on this concept of standard representation, we can craft a
function $f:[0,1)\times[0,1)\rightarrow [0,1)$ via the rule
$f((x,y))=0.x_1y_1x_2y_2x_3y_3\ldots$. Clearly distinct values of
$x$ and $y$ lead to distinct standard decimal representaitons,
which produce distinct decimal sequences in $f((x,y))$;
furthermore, since neither $x$ nor $y$ ends in an infinite
sequence of 9s, neither will their interleaving, so we may be
assured distinct decimal representations in $f((x,y))$ describe
distinct real numbers; thus, given $(x,y)\neq (x',y')$, we may be
assured that $f((x,y))\neq f((x',y'))$, so the function $f$ is
injective. Note that due to our privileging of standard
representations (which was necessary to make this function
well-defined and certain to be injective), this function is
\emph{not} surjective: there is no pair $(x,y)$ yielding the
interlace decimal $0.1929392919090909\ldots$, for instance.
An injective function from $[0,1)$ to $[0,1)\times[0,1)$, however,
is easy to craft. Let $g(x)$ be defined as equal yo the ordered
pair $(0,x)$; this is trivially injective, so by the
Cantor-Schr\"oder-Bernstein Theorem, the existence of injective
$f:[0,1)\times[0,1)\rightarrow [0,1)$ and injective
$g:[0,1)\rightarrow[0,1)\times[0,1)$ guarantees the existence of a
bijection between $[0,1)$ and $[0,1)\times[0,1)$.
\end{enumerate}
\item \textbf{(6 points)} \emph{A real number is called
\emph{transcendental} if it is not a root of any polynomial with
integer coefficients. Prove that the set of transcendental numbers
is uncountable.}
We shall start by showing that the set of numbers which are roots of
polynomials is uncountable. Using the same techniques as seen in
questions 1(b) and 1(c), we may assert that the polynomials with
integer coefficients are denumerable: for any polynomial
$a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$, let us put its roots in the
class $A_i$ if $|a_n|+|a_{n-1}|+\cdots+|a_0|=i$. Clearly there are a
finite number of such polynomials (we could sloppily bound this
number with $(2i+1)^(2i+1)$, which is ridiculously large but still
finite) and since each polynomial has a finite number of roots, each
$A_i$ is finite, so we know that the $\bigcup_{i=0}^\infty A_i$ is
denumerable (a.k.a. countably infinite) since we may inject $\mathbb
N$ into a union of finite sets $A_1,A_2,\ldots$ by associating the
first $|A_1|$ natural nubers with elements of $A_1$, the next
$|A_2|$ with elements of $A_2$, and so forth.
Thus, the set of non-transcendental numbers is countable. If the set
of transcendental numbers were also countable, their union would
necessarily be countable; however, since $\mathbb R$ is in fact
uncountable, we know this is not the case.
\item \textbf{(6 points)} \emph{Prove that if $S$ and $T$ are
denumerable sets, so is $S\times T$.}
Since $S$ and $T$ are denumerable, there are injections
$f:S\rightarrow\mathbb N$ and $g:T\rightarrow\mathbb N$. Clearly we
can craft a function $h:S\times T\rightarrow\mathbb N\times\mathbb
N$ by letting $h((s,t))=(f(s),g(t))$; clearly $h$ is an injection,
since in order for $h((s,t))$ to equal $h((s',t'))$ it must be the
case that the ordered pairs $(f(s),g(t))$ and $(f(s'),g(t'))$ are
equal, which happens only when $f(s)=f(s')$ and $g(t)=g(t')$. By
injectivity of $f$ and $g$, this necessitates that $s=s'$ and
$t=t'$. Thus, $h((s,t))=h((s',t'))$ only if $(s,t)=(s',t')$, so $h$
is an injection.
To show denumerability of $S\times T$, however, we want an injection
from $S\times T$ to $\mathbb N$, not one to $\mathbb N\times\mathbb
N$. We shall thus make use of a canonical bijection from $\mathbb
N\times\mathbb N$ to $\mathbb N$: let $\phi:\mathbb N\times\mathbb
N\rightarrow\mathbb N$ be given by $\phi((1,1))=1$, $\phi((1,2))=2$,
$\phi((2,1))=3$, $\phi((3,1))=4$, $\phi((2,2))=5$, and so forth;
specifically, $\phi(i-n,1+n)=\frac{i(i+1)}+n$. This guarantees that
all ordered pairs $(a,b)$ with $a+b=i+1$ are associated with numbers
between the $(i-1)$th and $i$th triangular numbers. There are
straitforward canonical presentations of why this is a bijection;
since it is a bijection, $\phi\circ h$ is the desired injection from
$S\times T$ into $\mathbb N$.
\item \textbf{(4 points)} \emph{Show that given a set $S$ and
injective function $f:\mathcal P(S)\rightarrow\mathbb N$, $S$ must
be finite.}
Suppose $S$ is infinite; thus there is a surjection
$g:S\rightarrow\mathbb N$. By diagonalization we shall show that
there is no surjection $h:\mathbb N\rightarrow\mathcal
P(S)$. Suppose, contrariwise, that there is such an $h$. Now we
shall fabricate a set $A\in\mathcal P(S)$ which is guaranteed to not
be in the image of $h$. Let $s\in A$ if and only if $s\notin
h(g(s))$. Now we shall show that for each $n\in\mathbb N$, $A\neq
h(n)$. For any given $n\in\mathbb N$, surjectivity of $g$ guarantees
that some $s_0\in S$ is such that $g(s_0)=n$. Thus $s_0\in A$ if and
only if $s\notin h(n)$, so clearly $A\neq h(n)$, since they disagree
on membership of $s_0$. Thus, $A\neq h(n)$ for any $n$, so $A$ is
not in the image of $h$, so $h$ cannot be a surjeciton. Since there
is no surjection from $\mathbb N$ to $\mathcal P(S)$, there is no
injection from $\mathcal P(S)$ to $\mathbb N$.
\item \textbf{(4 point bonus)} \emph{Let a ``description'' of a
number be a finite string of letters that uniquely determines
its value: for instance, ``the positive square rrot of two'' and
``the positive root of the polynomial x squared minus two'' are
both descriptions for $\sqrt 2$, and ``the ratio of the
circumference of a circle to its diameter'' is a description for
$\pi$. Prove that almost all real numbers do not have
descriptions.}
A ``description consisting of $n$ characters'' is a string of $n$
letters and spaces that makes sense in English; there are $27^n$
strings of such letters and spaces in total, of which only a few
make sense, so clearly the set of numbers described by $n$-letter
descriptions is finite; call that set $A_n$. As seen several times
above, we can take the union of a countable collection of finite
sets to get a countable set, so the set of describable numbers
$\bigcup_{n=1}^\infty A_n$ is countable. Since the describable
numbers are a countable set whereas $\mathbb R$ is uncountable,
the describable numbers form an infinitesimal portion of the real
numbers.
From a philosophical point of view, this is rather unusual: having
asserted that there are a ``larger'' number of real numbers than
integers, we are in fact powerless to get a handle on the
\emph{kind} of numbers which make $\mathbb R$ a larger set ---
those numbers which contribute towards $\mathbb R$'s vastness are,
as we just saw above, in fact incapable of being described with
any number of words, and in spite of existing, are definitionally
incomprehensible to any of our mathematical or expository
faculties.
\begin{center}
\fbox{
\begin{minipage}{6in}
Hay un concepto que es el corruptor y el desatinador de los
otros. No hablo del mal cuyo limitado imperio es la \'etica;
hablo del infinito. [There is a concept which is the corruptor
and ruin of all others. I speak not of evil, whose realm is
limited to ethics; I speak of the infinite.]
\hfill ---Jorge Luis Borges, ``Avatares de la tortuga''
\end{minipage}
}
\end{center}
\end{enumerate}
\end{document}