% 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 \#1\answer{ solutions}}
\rhead{}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due January 19, 2017}}

\begin{document}
For each question, explain your reasoning in full sentences.
\begin{enumerate}
\item \question{For two sets $A$ and $B$, suppose that all you know
    about the two of them is that $|A|=6$ and $|B|=4$.}

  \begin{enumerate}
  \item \question{What is the largest possible value of $|A\cup B|$?
      What is its smallest possible value?}

    \answer{Since elements which appear in both sets would only appear
      once in $A\cup B$, and since $A\cup B$ contains those elements
      which are in either $A$ or $B$, this set's size is minimized by
      letting $A$ and $B$ overlap as much as possible,
      e.g. $A=\{1,2,3,4,5,6\}$ and $B=\{1,2,3,4\}$. Under such a
      circumstance, we can see that $|A\cup B|=6$.

      Likewise, in order to maximize the union, we would want to make
      sure that each element of $A$ and each element of $B$
      contributes to the number of elements in $A\cup B$; this is
      achieved by minimizing the overlap. So, for instance, if
      $A=\{1,2,3,4,5,6\}$ and $B=\{7,8,9,10\}$, then $|A\cup B|=10$.}

  \item \question{What is the largest possible value of $|A\cap B|$?
      What is its smallest possible value?}

    \answer{Since $A\cap B$ consists of those elements which appear
      in both sets, it is maximized when the overlap between the two
      sets is maximized, as in the example above where
      $A=\{1,2,3,4,5,6\}$ and $B=\{1,2,3,4\}$; under this circumstance
      $|A\cap B|=4$.

      Two sets of arbitrasry size can certainly be disjoint, and if
      two sets are disjoint then their intersection is the set of
      smallest possible size, to wit, the empty set, with 0
      elements. As in the previous question, we might look at the
      specific example of $A=\{1,2,3,4,5,6\}$ and $B=\{7,8,9,10\}$ to
      get $|A\cap B|=0$.}

  \item \question{What is the largest possible value of $|A-B|$?
      What is its smallest possible value?}

    \answer{If $B$ is disjoint from $A$, then $A-B$ will simply be the
      same set as $A$, since removing the elements of $B$ removes
      nothing at all. This is going to be the largest that $A-B$ can
      be, so $|A-B|=6$ in this case. If, however, $B$ is a subset of
      $A$, then $A-B$ will lack four elements of $A$, so $|A-B|$ will
      be 2, as small as possible.}

  \item \question{What is the largest possible value of $|B-A|$?
      What is its smallest possible value?}

    \answer{As above, if $A$ and $B$ are disjoint, then $B-A$ will
      simply be the same set as $B$, since removing the elements of
      $A$ removes nothing at all. This is going to be the largest that
      $B-A$ can be, so $|B-A|=4$ in this case. If, however, $B$ is a
      subset of $A$, then $B-A$ will be empty, since every element of
      $B$ is an element of $A$ and is thus excised from $B-A$. Thus
      $|B-A|=0$, the smallest it (or any set's cardinality) can be.}
  \end{enumerate}

\item \question{Describe two sets $S$ and $T$ such that $S$ is both an
    element \emph{and} a subset of $T$.}

  \answer{There are many possible answers. The most absurdly simple is
    $S=\emptyset$ and $T=\{\emptyset\}$; then $S\subseteq T$ since the
    empty set is a subset of every set, and $S\in T$ because $T$'s
    sole element is in fact the empty set. A more conventional answer
    would be something akin to letting $S=\{1,2\}$ and
    $T=\bigl\{1,2,\{1,2\}\bigr\}$.}

\item \question{If $X$ is an infinite set and $X\in Y$, can you be
    certain that $Y$ is also infinite?}

  \answer{No! Since $X$ is an \emph{element} of $Y$, it contributes
    exactly one to the number of elements in $Y$, which might well be
    finite. Indeed, as a simple example we might consider when $X$ is
    the infinite set $\mathbb N$, and $Y$ is the one-element (and thus
    finite) set $\{\mathbb N\}$.}

\item \question{If $X$ is an infinite set and $X\subseteq Y$, can you be
    certain that $Y$ is also infinite?}

  \answer{This is very different from the case above! Subset inclusion
    forces the superset $Y$'s elements to include every element of its
    subset $X$. If $X$ has more elements than can be enumerated with a
    finite value, all of these elements are then elements of $Y$,
    causing $Y$ to be an infinite set.}

\item \question{Does it appear to be possible or meaningful to you for
    there to be a set $S$ which is an element of itself, that is, a
    set $S$ such that $S\in S$? Does this appear to be either a useful
    or problematic concept? Your response to this need not be
    ``mathematically justified'', but should express a personal
    consideration of the ramifications of such an idea.}

  \answer{This is not an issue on which set theory constructions are
    unified. Historically, the notion of ``a set'' has simply been ``a
    test for membersip, applicable to every object conceivable'',
    which would allow a set to contain itself --- just let it answer
    ``yes'' when tested for membership of itself! But this simplistic
    notion of what kind of set can be defined is fraught with peril:
    Bertrand Russell proposed the definition of a set $S$ whose
    criterion for membership is that it contains all sets which do not
    contain themselves. This definition, known as \emph{Russell's
      paradox}, is a variation on an older puzzle known as the
    \emph{barber paradox}, and ends with the self-contradictory notion
    that $S$ contains itself if and only if it does not contain
    itself!

    The solution to Russell's paradox has required a much more
    rigorous definition of how sets can be defined, and a constraint
    on the extent to which their definitions can refer to
    themselves. However, depending on the underlying assumptions of
    the set theory, self-containment can be either forbidden outright
    or allowed in a heavily controlled form. The most conventional
    set-theoretical systems used today are the Zermelo-Fraenkel (ZF)
    and Zermelo-Fraenkel-Choice (ZFC) axiom sets, which specifically
    forbid self-containment. Quine's New Foundations (NF) system,
    among other unconventional set theories, does allow
    self-containment of sets, but uses additional restrictions to
    avoid falling afoul of Russell's papradox.

    Fortunately, the question of whether self-containment is possible
    will have no impact on our ability to do anything we need ot do in
    this course, but for my own part, I find that self-containment is
    an insufficiently useful concept to justify the paradoxical
    behavior which seems to be a near-inevitable byproduct of allowing
    it.}
\end{enumerate}

\end{document}
