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