% If you are working from this template to just write up your own
% solutions, I'm trying to keep it simple for you and there are only a
% few places you need to edit. On line 43 there's a place where the
% phrase "YOUR NAME HERE" appears; change it to your actual
% name. Several places below there are places where the phrase "YOUR
% ANSWER HERE" appears, and directly below (or replacing) those lines
% are good places to put your answers.
%
% One important thing you need to do, however (due to the complicated
% way I use a single form to produce both the question sheets and
% solution writeups) is to make sure that you keep the word 'solution'
% in your filename, or else your answers won't be printed at all.
\documentclass[12pt]{article}
 
\usepackage[margin=0.7in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsfonts}
\usepackage{tikz}
\usepackage{substr}

\IfSubStringInString{\detokenize{solution}}{\jobname}{%
  % Solutions
  \newcommand\qfill{}
  \newcommand\qpage{}
  \newcommand\qonly[1]{}
  \newcommand\answer[1]{#1}
  \newcommand\question[1]{{\em #1}}
  \newcommand\rubric[1]{}
}
{%
  % Question sheets
  \newcommand\qfill{\vfill}
  \newcommand\qpage{\newpage}
  \newcommand\qonly[1]{#1}
  \newcommand\answer[1]{}
  \newcommand\question[1]{#1}
  \newcommand\rubric[1]{}
}

\pagestyle{fancy}
\lhead{MATH 311-01}
\chead{Problem Set \#2\answer{ solutions}}
\rhead{\answer{}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due January 26, 2017}}

\begin{document}
For each question, explain your reasoning in full sentences.
\begin{enumerate}
\item \question{For each of the following conditions, either find a
    partition of $\mathbb N$ satisfying that condition, or explain why
    such a thing is impossible.}
  \begin{enumerate}
  \item \question{A finite partition $\mathcal A$ such that each
      element of $\mathcal A$ is an infinite set.}

    \answer{There are many ways to do this, but the most
      straightforward way to partition $\mathbb N$ into a finite
      number of parts is to bisect it along the lines of
      \emph{parity}, putting all even nubmers in one part and all odd
      numbers in the other. This could be written as
      \[\mathcal
      A=\bigl\{\{1,3,5,7,\ldots\},\{2,4,6,8,\ldots\}\bigr\},\]
      or more explicitly as
      \[\mathcal A=\bigl\{\{2n:n\in\mathbb N\},\{2n-1:n\in\mathbb N\}\bigr\}.\]
      Note that $|\mathcal A|=2$, and that each of the two elements of
      $\mathcal A$ are themselves infinite sets; these two sets indeed
      are disjoint and have $\mathbb N$ as their union, verifying that
      $\mathcal A$ is a partition.

      An even simpler (and arguably trivial) choice would be to let
      $\mathcal A=\{\mathbb N\}$.}

  \item \question{An infinite partition $\mathcal B$ such that each
      element of $\mathcal B$ is an infinite set.}

    \answer{This is fairly difficult, although there are a great many
      ways to do it. The most straightforward approach is to further
      ramify the classification by parity presented above. Above we
      divided the numbers into those which are divisible by 2 and
      those which are not. We could further carve out of the first
      class those which are and are not divisible by 4; then we could
      further split this divisible-by-4 group into those individisble
      and divisible by 8, and so forth. This particular approach will
      yield the partition
      \begin{align*}
        \mathcal B=\bigl\{&\{1,3,5,7,\ldots\},\{2,6,10,14,\ldots\},\\
        &\{4,12,20,28,\ldots\},\{8,24,40,56,\ldots\},\ldots\bigr\},
      \end{align*}
      which could also be written more explicitly as
      \[\mathcal B=\{B_i:i\in\mathbb N\}\text{ where }B_i=\{2^i(2n-1):n\in\mathbb N\}.\]
    }

  \item \question{A finite partition $\mathcal C$ such that
      $\mathcal C$ has both infinite and finite sets as elements.}

    \answer{The easiest way to do this would be to carve a finite set
      out of one of the parts of $\mathcal A$ above. For instance, one
      could pull a finite number of odd elements out of the pdd part
      to get
      \[\mathcal C=\bigl\{\{1,3\},\{5,7,9,11,\ldots\},\{2,4,6,8,\ldots\}\bigr\}\]
      or, even more simply, to make a collection with some finite set
      $S$ of natural numbers and the infinite set $\mathbb N-S$ as
      elements, e.g., with $S=\{1\}$, this would be
      \[\mathcal C=\bigl\{\{1\},\mathbb N-\{1\}\bigr\}\bigl\{\{1\},\{2,3,4,5,6,\ldots\}\bigr\}.\]
    }

  \item \question{An infinite partition $\mathcal D$ such that 
      $\mathcal D$ has both infinite and finite sets as elements.}

    \answer{ One way to do this would be to take a partition with two
      or more infinite parts, such as the partition by parity, and
      ramify one of the infinite parts into an infinite quantity of
      single-element parts. For instance, we might put every odd
      number in the same part, and give each even number its own part
      to have the partition
      \[\mathcal D=\bigl\{\{1,3,5,7,9,\ldots\},\{2\},\{4\},\{6\},\{8\},\{10\},\ldots\bigr\}\]
      If we wanted to write this more explicitly, without ellipses, we
      could say
    \[\mathcal D=\{D_i:i\in\mathbb N\}\text{ where }D_1=\{2n-1:n\in\mathbb N\}\text{ and }D_i=\{2i-2\}\text{ for each }i>1.\]
}

  \item \question{A finite partition $\mathcal E$ such that each
      element of $\mathcal E$ is a finite set.}

    \answer{ This is impossible. Suppose that $\mathcal
      E=\{E_1,E_2,\ldots, E_n\}$ where each $E_i$ is a finite nonempty
      set. Thus each $E_i$ has a greatest element $e_i$; taking the
      maximum of this finite list of $e_i$s, we get an element $N$
      which is the largest appearing in any $E_i$. Then $N+1$ isn't in
      any $E_i$, so $N+1\notin\bigcup_{i=1}^nE_i=\bigcup_{E\in\mathcal
        E}E$. But in order for $\mathcal E$ to be a partition of
      $\mathbb N$, every element of $\mathbb N$ would have to be an
      element of $\bigcup_{E\in\mathcal E}E$.}

  \item \question{An infinite partition $\mathcal F$ such that each
      element of $\mathcal F$ is a finite set.}

    \answer{One straightforward possibility is to partition every
      element of $\mathbb N$ into its own single-element part, for
      instance by letting
      \[\mathcal F=\bigl\{\{1\},\{2\},\{3\},\{4\},\ldots\bigr\},\]
      or more explicitly as
      \[\mathcal F=\bigl\{\{i\}:i\in\mathbb N\bigr\}.\]}

  \end{enumerate}

\item \question{Explain (in whatever words appear to constitute a
    convincing argument) why it should generally be the case that
    $A\times (B\cup C)=(A\times B)\cup (A\times C)$ for sets $A$, $B$,
    and $C$.}

  \answer{Let's look at what sort of objects are elements of $A\times
    (B\cup C)$. Since this is a Cartesian product on its outermost level,
    the objects in question will all be ordered pairs, each of whose
    abscissa\footnote{A high-falutin' term for the first coordinate in
      an ordered pair} is an element of $A$ with an
    ordinate\footnote{Same, but for the second coordinate} drawn from
    $Bcup C$; that is to say, from $B$ or $C$.

    Now let's look at $(A\times B)\cup (A\times C)$; we hope that it
    will have elements meeting the same criteria. On its outermost
    level, it is not a Cartesian product but is a union; It is
    specifically a union, however, of Cartesian products. Thus the
    elements of this set are elements of either $A\times B$ or
    $A\times C$, both of which are sets of ordered pairs. Elements
    from either set will have abscissas drawn from the set $A$, while
    their ordinates might be from $B$ or $C$. Thus this union
    describes the same set of ordered pairs as above.}
\end{enumerate}

\end{document}
