\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}