\documentclass[12pt]{article}

\usepackage[margin=0.7in]{geometry}

\usepackage{amsmath,amsfonts,amssymb}

\usepackage{fancyhdr}

\usepackage{lastpage}

% 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 \#1 Solutions}
\rhead{\studentname}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{\today}

\begin{document}
\begin{enumerate}
\item \textbf{(10 points)} \emph{We observed in class that when $A$
    is a finite set, $|\mathcal P(A)|=2^{|A|}$. Explain in your own
    words why this is true.}

  We might be best served by looking at something specific but not
  overspecific: noting that, for instance, when $A=\{1,2,3\}$, we can
  compute $\mathcal P(A)$ to have 8 elements is overspecific, because
  it really generalizes, at best, to talking about other 3-element
  sets. Let's fix some natural number $n$, and discuss
  $A=\{1,2,3,\ldots,n\}$: this is a pretty general set, and if we want
  to talk about other sets of size $n$, we could just replace the $1$,
  $2$, and so forth with whatever the actual elements of $A$ are.

  So, with our specified but not over-specified choice of $A$, noting
  that $|A|=n$, we want to get down to the business of explaining why
  $|\mathcal P(A)|$ has $2^n$ elements. Or, more to the point, since
  the elements of $\mathcal P(A)$ are the subsets of $A$, our question
  becomes: why does $A$ have $2^n$ different subsets?

  Let's consider the different ways that we can build a subset $B$ of
  $\{1,2,3,\ldots,n\}$. $B$ can only have the elements of $A$ as
  elements, so we know it is uniquely determined by whether each of
  $1,2,3,\ldots,n$ is in $B$ or not in $B$. For example, there are two
  possible relationships between $1$ and $B$: either $1\in B$ or
  $1\notin B$. Likewise, there are two possible relationships between
  $2$ and $B$: either $2\in B$ or $2\notin B$. And so forth, with each
  number from 1 to $n$ being in one of two relationships with
  $B$. Thus, $B$ is determined by $n$ different choices between 2
  alternatives. This can be done in $2\times 2\times
  2\times\cdots\times 2=2^n$ ways, so there are $2^n$ different ways
  to construct a subset $B$ of $A$; thus $A$ has $2^n$ different
  subsets.

\item \textbf{(5 points)} \emph{Explain why, when $A\subseteq B$ and
    $A$ and $B$ are both finite sets, it follows that $|A|\leq|B|$.}

  If $A\subseteq B$, then every element of $A$ is in $B$. Since every
  element of $A$ is in $B$, then in the process of counting the
  elements of $B$, we would count every single element of $A$, so
  counting the elements in $B$ would necessarily produce a number as
  large or higher than the number of elements of $A$.

\item \textbf{(4 points)} \emph{Give examples of sets satisfying each
    of the conditions below:}
  \begin{enumerate}
  \item \emph{$S\subseteq\mathcal P(\mathbb N)$.}

    $\mathcal P(\mathbb N)$ is a set which has all subsets of $\mathbb
    N$ as elements. A subset $S$ of $\mathcal P(\mathbb N)$ is thus a set
    which has (not necessarily all) subsets of $\mathbb N$ as
    elements. A simple example of such a set would be $S=\bigl\{\{3\},\{1,4\},\{2\}\bigr\}$.

    Some more esoteric examples would be $S=\emptyset$ (which happens
    to contain zero subsets of $\mathbb N$),
    $S=\bigl\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\ldots\bigr\}$ (which contains an
    infinite number of two-element subsets of $\mathbb N$), or
    $S=\{\emptyset,\mathbb N\}$, which contains two subsets of
    $\mathbb N$: the empty set and $\mathbb N$ itself.

  \item \emph{$T\in\mathcal P(\mathbb N)$.}

    By way of contrast to the above question, while a subset of
    $\mathcal P(\mathbb N)$ was a set containing subsets of $\mathbb
    N$, an element of $\mathcal P(\mathbb N)$ is just a single subset
    of $\mathbb N$. There are plenty of these, and a simple example is
    $T=\{2,3,5,7\}$.

    Plenty of more exotic examples exist, such as $T=\emptyset$,
    $T=\{2,4,6,8,10,\ldots\}$, $T=\{1,4,9,16,25,36,49,\ldots\}$, and
    even $T=\mathbb N$.

  \item \emph{$A\subseteq\mathcal P(\mathbb N)$ and $|A|=5$.}

    This is very similar to part (a), only with the restriction
    that our chosen set must contain 5 elements. Since the elements
    are themselves subsets of $\mathbb N$, we need to just build a set
    containing five subsets of $\mathbb N$, such as $A=\{\{2,3\},
    \{1,5,7\}, \{1\}, \{6\},\emptyset\}$. You can make the individual
    subsets more exotic, if you prefer.

  \item \emph{$B\in\mathcal P(\mathbb N)$ and $|B|=5$.}

    This is very similar to part (b), only with the restriction that
    our chosen set must contain 5 elements. Since our set must be a
    subset of $\mathbb N$, we need to just build a five-element subset
    of $\mathbb N$, such as $B=\{1,3,6,10,15\}$.
  \end{enumerate}

\item \textbf{(6 points)} \emph{Explain why, for any sets $A$ and $B$,
    it must always be the case that $A\cap B\subseteq A\subseteq A\cup
    B$. Are there any situations where $A\cap B$ is not a proper
    subset of $A$, or where $A$ is not a proper subset of $A\cup B$?}

  There are two separate subset-relationships here: $A\cap B\subseteq
  A$, and $A\subseteq A\cup B$. We shall handle each of them
  separately.

  First, we want to justify the assertion $A\cap B\subseteq A$. We
  shall do so by unrolling each part of it until we arrive at a
  vacuously true statement. Let us start by noting that,
  definitionally, $X\subseteq Y$ means ``every element of $X$ is an
  element of $Y$'', so we can rephrase $A\cap B\subseteq A$ in words
  as ``every element of $A\cap B$ is an element of $A$''. We can now
  use another definition to expand this phrasing further: we know that
  to be an element of $A\cap B$, something must be an element of both
  $A$ and $B$, so our phrase above can be further expanded into the
  statement ``anything that is both an element of $A$ and an element
  of $B$ is an element of $A$'' --- a statement which is obviously
  true! We have thus demonstrated that $A\cap B\subseteq A$ is true,
  since written out in words it becomes a trivial statement.


  We can demonstrate $A\subseteq A\cup B$ in much the same way. Again
  making use of the definition of the subset relation, we can rephrase
  $A\subseteq A\cup B$ in words as ``every element of $A$ is an
  element of $A\cup B$''. We now use another definition to expand this
  phrasing further: to be an element of $A\cup B$,
  something must be an element of either $A$ or $B$ or both, so our phrase
  above can be further expanded into the statement ``anything that is
  an element of $A$ is either an element of $A$ or $B$ or both''
  --- again a statement which is self-evident.

  In answer to the final part of the question, we wonder when either
  of these subset-relationships can be nonproper. In order for
  $X\subseteq Y$ to {\em not} describe a proper subset, it must be the
  case that $X=Y$ (since if $X\neq Y$, the subset relationship is
  definitionally proper). So we are wondering when it is the case that
  $A\cap B=A$ or $A=A\cup B$.

  In order for $A\cap B$ and $A$ to be equal, their elements must be
  the same, so every element of $A$ must be an element of both $A$ and
  $B$; clearly every element of $A$ is an element of $A$, so the real
  restriction here is that every element of $A$ is an element of $B$,
  or, in other words, that $A$ is a subset of $B$. Thus $A\cap B=A$
  when $A\subseteq B$.

  In order for $A$ and $A\cup B$ to be equal, their elements must be
  the same, so everything that is an element of $A$ or an element of
  $B$ must be an element of $A$; clearly every element of $A$ is an
  element of $A$, so the real restriction here is that every element
  of $B$ is an element of $A$, or, in other words, that $B$ is a
  subset of $A$. Thus $A=A\cup B$ when $B\subseteq A$.

\item \textbf{(6 points)} \emph{For each real number $r$, define
    $A_r=\{r^2\}$, define $B_r$ as the closed interval $[r-1,r+1]$,
    and define $C_r$ as the open interval $(r,\infty)$. For
    $S=\{1,2,4\}$, evaluate the following expressions:}
  \begin{enumerate}
  \item \emph{$\bigcup_{\alpha\in S}A_\alpha$ and $\bigcap_{\alpha\in
        S}A_\alpha$.}

  \item \emph{$\bigcup_{\alpha\in S}B_\alpha$ and $\bigcap_{\alpha\in
        S}B_\alpha$.}

  \item \emph{$\bigcup_{\alpha\in S}C_\alpha$ and $\bigcap_{\alpha\in
        S}C_\alpha$.}
  \end{enumerate}

  Each of these will actually simplify to a cute finite intersection
  or union, since $S$ is a finite set, and thus:
  $$\bigcup_{\alpha\in S}A_\alpha=A_1\cup A_2\cup A_4=\{1\}\cup\{4\}\cup\{16\}=\{1,4,16\}$$
  $$\bigcap_{\alpha\in S}A_\alpha=A_1\cap A_2\cap A_4=\{1\}\cap\{4\}\cap\{16\}=\emptyset$$
  $$\bigcup_{\alpha\in S}B_\alpha=B_1\cup B_2\cup B_4=[0,2]\cup[1,3]\cup[3,5]=[0,5]$$
  $$\bigcap_{\alpha\in S}B_\alpha=B_1\cap B_2\cap B_4=[0,2]\cap[1,3]\cap[3,5]=\emptyset$$
  $$\bigcup_{\alpha\in S}C_\alpha=C_1\cup C_2\cup C_4=(1,\infty)\cup(2,\infty)\cup(4\infty)=(1,\infty)$$
  $$\bigcap_{\alpha\in S}C_\alpha=C_1\cap C_2\cap C_4=(1,\infty)\cap(2,\infty)\cap(4\infty)=(4,\infty)$$

\item \textbf{(4 points)} \emph{Find an indexed collection of distinct
    sets $\{A_n\}_{n\in\mathbb N}$ (so that no two sets are equal)
    satisfying the following two conditions: $$\bigcap_{n=1}^\infty
    A_n=\{-1,0,1\}\text{ and }\bigcup_{n=1}^\infty A_n=\mathbb Z$$}

  We can translate these two conditions into two simple properties. In
  order for $\bigcap_{n=1}^\infty A_n$ to be $\{-1,0,1\}$, it must be
  the case that $-1$, $0$, and $1$ are elements of \emph{each} $A_n$;
  in order for $\bigcup_{n=1}^\infty A_n$ to be $\mathbb Z$, every
  integer must appear in \emph{at least one} $A_n$. There are several
  ways to do this, but the most obvious way to do it is to let
  $A_n=\{-n,-n+1,-n+2,\ldots,-1,0,1,\ldots,n-2,n-1,n\}$. Then it is
  obvious that any integer $k$ is an element of $A_{|k|}$, and that
  $-1$, $0$, and $1$ are elements of every $A_n$ for integers $n\geq 1$.

\item \textbf{(5 points)} \emph{Give an example of a partition of
    $\mathbf Q$ into three subsets.}

  There are a great many ways to do this. One absurd way would be to
  select two rational numbers to be in their own partitions, and put
  everything else in the third, for example:
  $$\bigl\{\{0\},\{1\},\mathbb Q-\{0,1\}\}$$
  which is silly but is technically a partition. There is a more
  natural and less silly partition which makes use of a trichotomy of
  not just the rationals, but the reals and integers: each rational
  number must be exactly one of positive, negative, or zero, so
  there's an obvious partition into the three sets consisting of zero
  alone, the positive rationals, and the negative rationals:
  $$\bigl\{\{0\},\{x\in\mathbb Q:x>0\},\{x\in\mathbb Q:x<0\}\bigr\}$$

\item \textbf{(5 point bonus)} \emph{I briefly discussed
    self-reference as a problematic issue in class: here we can look
    at what makes it a problem. Let us consider, hypothetically, the
    concept of a set $A$ containing all sets. Since $A$ is itself a
    set, it would be the case that $A\in A$ (it would also be the case
    that $\emptyset\in A$ and $\mathcal P(A)\in A$, for those are both
    sets too).}
  
  \emph{So far this is not a problem. But now let us consider $S=\{X\in
    A:X\notin X\}$. Clearly, for example, $A\notin S$, because as we saw
    above, $A\in A$. On the other hand, for instance, $\emptyset$ and
    $\mathbb Z$ would be in $S$, since neither the empty set nor the
    integers have themselves as members.}
    
  \emph{The key question: is it true or false that $S\in S$, and what would
    investigating this question tell us?}

  The question of whether $S$ is an element of itself is intrinsically
  unanswerable. $S$ consists of those sets which are not elements of
  themselves, by its definition. Then, $S\in S$ only if $S\notin S$,
  and vice versa, which suggests that neither $S\in S$ nor $S\notin S$
  can be true.

  This is a problem which haunted the early twientieth century under a
  number of guises, spawning theory and philosophy too wide-ranging to
  be gone into here. The immediate practical upshot of this
  investigation was to force mathematics to diminish its definition of
  what a ``set'' was considerably, to avoid such paradoxes as
  presented here.

  For further elaboration on this problem, do research on either of
  its common names in literature, where it is usually referred to as
  \emph{the Barber Paradox} or \emph{Russell's Paradox}.

\end{enumerate}
\end{document}