
\documentclass[11pt]{article}
\addtolength{\textwidth}{\oddsidemargin}  %i.e., left margin
\addtolength{\textwidth}{0.75in}
\addtolength{\textheight}{1in}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}

\begin{document}
\begin{center}
Intro to Mathematical Reasoning (Math 300) -- 
Homework 4\footnote{Version 2/5/04}
\end{center}

\begin{enumerate}

\item Textbook: exercise 2.4.4

\item 
Recall the following definition: For any two sets $A$ and $B$, 
the {\em difference set} $A\backslash B$
is the set consisting of those objects that are members of $A$
but not members of $B$.
\begin{enumerate}
\item Prove or disprove: For all sets $A,B,C$, if
$A \backslash C=B \backslash C$ then $A=B$.
\item Prove or disprove: For all sets $A,B,C$,
if $A \backslash C = B \backslash C$ and $C \backslash A=C \backslash B$
then $A=B$.
\end{enumerate}

\item Prove or disprove: For any three sets $X,Y,Z$, if
$X \cap Y \neq \emptyset$, $X \cap Z \neq \emptyset$ and
$Y \cap Z \neq \emptyset$ then $X \cap Y \cap Z \neq \emptyset$.

\item  Textbook: Prove Theorem 2.5.5

\item Textbook: end of chapter 2, problem 4.

\item 
If $S$ is a set, a {\em partition} of $S$ is a set 
$\mathcal{P}$ of subsets of $S$ satisfying the following three conditions:
(i) $\emptyset \not\in \mathcal{P}$,
(ii) for each $s \in S$, there is an $M \in \mathcal{P}$ such that
$s \in M$, and (iii) For each pair $M_1,M_2 \in \mathcal{P}$ such
that $M_1 \neq M_2$, we have $M_1 \cap M_2 = \emptyset$.
The purpose of this problem is for you to explore this
definition.

\begin{enumerate}
\item Give three examples of  a partition of $\{A,B,C,D,E\}$.
In each of your examples, briefly explain
why conditions (i), (ii) and (iii) hold.
\item What partition
of $\{A,B,C,D,E\}$ has the most number of members?  What partition of 
$\{A,B,C,D,E\}$
has the least number of members?
\item 
Give an example of a set $\mathcal{P}$ of subsets of $\{A,B,C,D,E\}$ 
that satisfies
conditions (i) and (ii) but not (iii).
\item 
Give an example of a collection $P$ of subsets of $\{A,B,C,D,E\}$ 
that satisfies
conditions (i) and (iii) but not (ii).
\item 
Give an example of a collection $P$ of subsets of $\{A,B,C,D,E\}$ 
that satisfies
conditions (ii) and (iii) but not (i).
\item 
Is it possible to have a partition of a set $S$ if $S$ has
exactly one element.
Briefly explain.
\item Is it possible to have a partition of a set $S$ if $S$ is
the empty set.
Briefly explain.
\end{enumerate}


\item
Let $X$ be a set and let $\mathcal{H}$ be a set of
of subsets of $X$. For
elements $s,t$ of $X$ we define the notation
$s \approx_{\mathcal{H}} t$, to mean that there is a member of
$\mathcal{H}$ that has both $s$ and $t$ as a member.

\begin{enumerate}
\item
Prove: For any set $S$ and
for  any partition $\mathcal{P}$ of $S$ 
and for any $s,t,u \in S$,
if $s \approx_{\mathcal{P}} t$ and
$t \approx_{\mathcal{P}}u$ then
$s \approx_{\mathcal{P}} u$.
\item 
Suppose that in the previous statement, we replace
the phrase
``for  any partition $\mathcal{P}$ of $S$''
by ``for any set $\mathcal{P}$ of subsets of $S$''.
Prove that the resulting statement is false.
\item
Now go back to your proof of part a.  Suppose
that you tried to modify your proof for part a, so that
it proves the statement in part b.  
Since the statement in part b is false, this should be impossible,
which means that somewhere in your proof there must be a point
where it is crucial that $\mathcal{P}$ is a partition and
not just a set of subsets of $S$.  Find where this occurs in your proof.
(Note: If you can't do this, then there's something wrong with your
proof and you should fix it!)
\end{enumerate} 

\item 
We begin with some definitions.
We say that {\em $A$ is a neighbor
of $B$} 
if $(A\backslash B) \cup (B\backslash A)$ consists of exactly one element. 

A list of sets is a {\em neighborly list of sets}
if each set on the list (other than the set that begins the list)
is a neighbor of the set   that immediately precedes it on the list.
(Here the word {\em list} means a finite sequence of items. 
For example, (3,14,6,3,29,14)  is a list consisting
of 6 items (which, in this example, are integers).   Unlike
sets, the order in which items appear is important, and the
same object may appear more than once as an item of the list.
Notice that 14 appears twice on the list.  The first time
14 appears, it is immediately preceded by 3.  The second
time 14 appears it is immediately preceded by 29.)


Here is an interesting theorem: For all positive integers
$n$, there is a list  consisting  of subsets of
$\{1,\ldots, n\}$ such that (1) every subset of $\{1,\ldots,n\}$ 
appears {\em precisely
once} on the list and (2) the list is neighborly.


Prove the special cases of the theorem with $n=1$, $n=2$, $n=3$
and $n=4$.

(Note: A very important part of doing this problem 
is to carefully read and understand the definitions in the first
two paragraphs.  If you are having trouble understanding definitions, 
then one way to help yourself is to do examples.  For example,
to help yourself understand the definition of neighbor, 
write down any two sets.
Use the definition of neighbors to determine whether the first
is a neighbor of the second.  
Do a few more examples until you understand what neighbors means.
Make sure you can construct examples of two sets that are neighbors
and of two sets that are not neighbors.
To help yourself understand the definition of a neighborly list of
sets, write down a list of sets and use the definition to test 
whether the list you wrote down is a neighborly list of sets.
Again, do enough examples to be sure you understand this definition.
Once you understand the definitions, you can start thinking about
the proofs that you are asked to give.)






\end{enumerate}



\end{document}










