\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% I made this problem up for spring 2001. We only used the three first
% problem parts on the problem set. I fear that the two last ones are
% a bit too hard, although the have nice connections to the construction
% of the closure and the application of algebras to probability. /Lars
%
\newcommand{\F}{\mathcal{F}}
\newcommand{\G}{\mathcal{G}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\power}{\mathcal{P}}
\newcommand{\I}{\mathcal{I}}
\problem Suppose that $\Omega$~is a finite set. A collection $\F \subseteq
\power(\Omega)$ is called an \emph{algebra} if
\begin{enumerate}
\item $\Omega \in \F$,\label{algebra:non-empty}
\item $\omega \in \F \implies \overline{\omega} \in \F$,\label{algebra:complement}
\item $\omega_1 \in \F \land \omega_2 \in \F \implies \omega_1 \union
  \omega_2 \in \F$.\label{algebra:union}
\end{enumerate}
(The complement in item~\ref{algebra:complement} above is with respect
the universe~$\Omega$.)


For instance, if $\Omega = \{1,2,3\}$, the collection
$\{\{1,3\},\{2\}\}$ is \emph{not} an algebra, but the collection
$\{\emptyset,\{1,3\},\{2\},\{1,2,3\}\}$ is.

\solution{%
\begin{quote}\small
  A special type of algebras---so called $\sigma$-algebras---is the
  foundation of axiomatic probability theory. They are defined by
  basically the same axioms as above, but $\Omega$~does not have to be
  a finite set and the algebra has to be closed under the union of a
  countably infinite number of sets instead of the union of just two
  sets. The elements of~$\F$ are the possible \emph{events}, i.e., the
  information we can get about the outcome of the random experiment.
  Then a positive number $P(\omega)$ is assigned to every element
  of~$\F$ in such a way that $P(\Omega) = 1$ and $P(\omega_1 \union
  \omega_2) = P(\omega_1) + P(\omega_2)$ for disjoint
  $\omega_1,\omega_2 \in \F$. This number is the \emph{probability} of
  the events in~$\F$. The triple $(\Omega, P, \F)$ is usually called a
  \emph{probability space}. For the example above, with $\Omega =
  \{1,2,3\}$ and the algebra $\F =
  \{\emptyset,\{1,3\},\{2\},\{1,2,3\}\}$, we could for instance set
  $P(\{1,3\}) = 2/3$ and $P(\{2\}) = 1/3$. That would model the
  situation ``choose a number in $\{1,2,3\}$ uniformly'' where the
  only information we can observe about the outcome is if the number
  is odd or not.
\end{quote}
}

\begin{problemparts}
  \problempart Prove that if $\F$~is an algebra, $\omega_1 \in \F
  \land \omega_2 \in \F \implies \omega_1 \intersect \omega_2 \in \F$.

  \solution{%
    \begin{proof}
      By property~\ref{algebra:complement}, $\overline{\omega_1} \in
      \F$ and $\overline{\omega_2} \in \F$.  By the
      property~\ref{algebra:union}, this implies that
      $\overline{\omega_1} \union \overline{\omega_2} \in \F$. By
      property~\ref{algebra:complement}, this inplies that
      $\overline{\overline{\omega_1} \union \overline{\omega_2}} \in
      \F$. By DeMorgan, this implies that $\omega_1 \intersect
      \omega_2 \in F$.
    \end{proof}
    }

  \problempart Prove that if $\F_1 \subseteq \power(\Omega)$ and $\F_2
  \subseteq \power(\Omega)$ are algebras, then $\F_1 \intersect \F_2$ is
  also an algebra.

  \solution{%
    \begin{proof}
      Let $\F_1$ and~$\F_2$ be algebras. We now show that $\F_1
      \intersect \F_2$ satisfies the definition of an algebra.
      
      Since $\F_1$ is an algebra $\Omega \in \F_1$; since $\F_2$ is an
      algebra $\Omega \in \F_2$. Thus $\Omega \in \F_1 \intersect
      \F_2$ by the definition of intersection.
      
      Suppose that $\omega \in \F_1 \intersect \F_2$. Then $\omega \in
      \F_1 \land \omega \in \F_2$. If $\omega \in F_1$, then
      $\overline{\omega} \in \F_1$ since $\F_1$~is an algebra. If
      $\omega \in F_2$, then $\overline{\omega} \in \F_2$ since
      $\F_2$~is an algebra. Thus $\overline{\omega} \in \F_1
      \intersect \F_2$.
      
      Suppose that $\omega_1 \in \F_1 \intersect \F_2$ and that
      $\omega_2 \in \F_1 \intersect \F_2$. This implies that both
      $\omega_1$ and~$\omega_2$ are in~$\F_1$; and that both
      $\omega_1$ and~$\omega_2$ are in~$\F_2$.  Since both $\omega_1$
      and~$\omega_2$ are in~$\F_1$ and $\F_1$ is an algebra, $\omega_1
      \union \omega_2$ is also in~$\F_1$.  Since both $\omega_1$
      and~$\omega_2$ are in~$\F_2$ and $\F_2$ is an algebra, $\omega_1
      \union \omega_2$ is also in~$\F_2$. Thus $\omega_1 \union
      \omega_2$ is both in $\F_1$ and in~$\F_2$, which is the same
      thing as saying that $\omega_1 \union \omega_2 \in \F_1
      \intersect \F_2$.
    \end{proof}
    }
  
  \problempart Prove that if $\F_i \subseteq \power(\Omega)$ are algebras
  for $i = 1,\ldots,n$, then $\bigcap_{i=1}^n \F_i$ is also an
  algebra.
  
  \solution{%
    \begin{proof}
      We prove the claim by induction on~$n$. The base case ($n=1$) is
      clear. We now assume that $\bigcap_{i=1}^n \F_i$ is an
      algebra and rewrite
      \begin{displaymath}
        \bigcap_{i=1}^{n+1} \F_i = 
        \biggl(\bigcap_{i=1}^n \F_i\biggr) \intersect \F_{n+1}
      \end{displaymath}
      Thus, $\bigcap_{i=1}^{n+1} \F_i$ is---by the assumption---the
      intersection of two algebras. Since we proved above that the
      intersection of two algebras is also an algebra, we have thus
      proven that $\bigcap_{i=1}^{n+1} \F_i$ is an algebra.
    \end{proof}
    }
  
  \problempart Consider a collection $\G \subseteq \power(\Omega)$ that
  might not be an algebra. Consider the set
  \begin{displaymath}
    \I = \{\F_i \suchthat
    \mbox{$\G \subseteq \F_i$ and $\F_i$ is an algebra}\bigr\}
  \end{displaymath}
  of all algebras containing~$\G$. Note, that since $\power(\Omega)$ is
  itself an algebra, $\power(\Omega) \in \I$, and thus $\I$~is non-empty.
  By the result you proved above, $\F = \bigcap \I$ is an algebra.
  Moreover, $\G \subseteq \F$ since $\G \subseteq \F_i$ for all $\F_i
  \in \I$. Prove that $\F$~is the smallest algebra containing~$\G$. In
  other words, prove that there cannot exist any $\H \subseteq
  \power(\Omega)$ such that $\H$~is an algebra and $\G \subseteq \H \subset
  \F$.

  \solution{%
    \begin{proof}
      Suppose that there exists an $\H \subseteq \power(\Omega)$ such that
      $\H$~is an algebra and $\G \subseteq \H \subset \F$. Since $\H$
      is an algebra that contains~$\G$, $\H \in \I$. Thus, by the
      definition of~$\F$, $\F \subseteq \H$, which is a contradicion.
    \end{proof}
    }
  
  \problempart Consider an algebra $\F \subseteq \Omega$. The members
  of~$\F$ form a partial order with respect to the subset operation,
  i.e., $(\F,\subseteq)$ is a partial order. Since $\Omega \in \F$ by
  the definition of an algebra, we also have $\F \ni \bar{\Omega} =
  \emptyset$, which implies that the partial order $(\F,\subseteq)$
  has one unique minimal element, $\emptyset$. Now consider the set
  \begin{displaymath}
    \G = \bigl\{\omega \in \F \bigm| (\forall \omega' \in \F)
    (\omega' \subset \omega \implies \omega' = \emptyset)\bigr\},
  \end{displaymath}
  i.e., the family of sets in~$\F$ that are immediately
  above~$\emptyset$ in the partial order. Prove that the elements
  of~$\G$ form a partition of~$\Omega$.

  \solution{%
    \begin{proof}
      We first prove that there are no two sets in~$\G$ that
      intersect. Suppose that there are two such sets~$G_1$ and~$G_2$
      such that $G_1 \neq G_2$ and $G_1 \intersect G_2 \neq
      \emptyset$. Since $\F$~is an algebra, $G_1 \intersect G_2 \in
      \F$. Moreover, either $G_1 \intersect G_2 \subset G_1$ or $G_1
      \intersect G_2 \subset G_2$ since $G_1 \neq \G_2$. This
      contradicts the fact that both $G_1$ and~$G_2$ are members
      of~$\G$.
      
      Fix some $a \in \Omega$. We now show that $a$~occurs in exactly
      one member of~$\G$. Assume the contrary, i.e., that $a$~does not
      occur in any member of~$\G$---we now by the above reasoning that
      no sets in~$\G$ intersect, so this is the only remaining
      possibility. Since $\Omega \in \F$, there exists at least one
      set in~$\F$ containing~$a$. Let $\omega$~be the smallest such
      set---by well-ordering, such an~$\omega$ always exists. By our
      assumption, $\omega \notin \G$. Consider the case $|\omega| =
      1$. Then the only proper subset of~$\omega$ is~$\emptyset$,
      which implies that $\omega \in \G$---a contradiction.
      
      Now assume that $|\omega| > 1$. Since $\omega \notin \G$, there
      must exist some~$\omega' \in \F$ satisfying $\emptyset \subset
      \omega' \subset \omega$. Moreover, since $\omega$~is the
      smallest set in~$\F$ that contains~$a$, $a \notin \omega'$. But
      since $\omega,\omega' \in \F$, the set $\omega - \omega'$, which
      contains~$a$, is also in~$\F$ and has a size smaller
      than~$|\omega|$. This is a contradiction.
    \end{proof}
    }

\end{problemparts}  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%BEGIN Joe's problems
\problem %source: spring00 ps3
% topic: Cartesian products, disjoint, direct proof
% source: Velleman 4.1.8

Prove that for any sets $A$, $B$, $C$, and $D$, if 
$A \times B$ and $C \times D$ 
are disjoint, then either $A$ and $C$ are disjoint or $B$ and $D$ are disjoint.

\omitsolution{%
\begin{solution}

We will prove the contrapositive.  In other words,
\newline 
prove: 
$[(A \intersect C) \neq \emptyset \land (B \intersect D) \neq \emptyset] 
\implies [(A \times B) \intersect (C \times D) \neq \emptyset]$
\newline
assume:
$[(A \intersect C) \neq \emptyset \land (B \intersect D) \neq \emptyset]$
\newline
$\therefore \exists a (a \in A \land a \in C) \land 
\exists b (b \in B \land b \in D)$.
\newline
then, $(a, b) \in A \times B$   by definition of Cartesian product, 
Velleman 158.
\newline
and, $(a, b) \in C \times D$   by definition of Cartesian product, 
Velleman 158.
\newline
$\therefore (a, b) \in [(A \times B) \intersect (C \times D)]$ so 
$[(A \times B) \intersect (C \times D) \neq \emptyset]$
\newline
$QED$

\end{solution}
}

%END   Joe's problems

%BEGIN Ray's problems
<<<<<<< Sets.tex
%END   Ray's problems

%BEGIN Ivan's problems
%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

\problem \textbf{Relations}
\bparts
\ppart Velleman \S 4.2, Exercise 3 parts a,b and c.\\
Suppose $A=\{1,2,3\}, B=\{4,5,6\}, R=\{(1,4), (1,5), (2,5), (3,6)\}$, and 
$S=\{(4,5), (4,6), (5,4), (6,6)\}.$  Note that $R$ is a relation from $A$ to $B$ and
$S$ is a relation from $B$ to $B$.  Find the following relations:\\
\medskip
a. $S\circ R$\\
b. $S\circ S$\\
c. $S^{-1}\circ R$ 

\solution{
Suppose $A=\{1,2,3\}, B=\{4,5,6\}, R=\{(1,4), (1,5), (2,5), (3,6)\}$, and 
$S=\{(4,5), (4,6), (5,4), (6,6)\}.$  Note that $R$ is a relation from $A$ to $B$ and
$S$ is a relation from $B$ to $B$.  Find the following relations:\\

\medskip
\textbf{Solutions:}\\
a. $S\circ R = \{(1,5), (1,6), (1,4), (2,4), (3,6)\}$\\
b. $S\circ S = \{(4,4), (4,6), (5,5), (5,6), (6,6)\}$\\
c. $S^{-1}\circ R = \{(1,5), (1,4), (2,4), (3,4), (3,6)\}$\\
%%%
%d.
%%% 
}
%%%
%\ppart Velleman \S 4.2, Exercise 7
%%%
\eparts

%%%
%\problem \textbf{Relations --- Ordering}
%Velleman \S 4.3, Exercise 9.
%%%
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Relations --- Properties}
\bparts
\ppart Velleman \S 4.4, Exercise 1. %[[[Good finger exercise.]]]


\noindent In each case, say whether or not $R$ is a partial order on $A$.  If so, is it a total order?\\
a. $A=\{a,b,c\}, R=\{(a,a),(b,a),(b,b),(b,c),(c,c)\}.$\\
b. $A=\{$ the set of all words in English, $R = \{(x,y\}\in A \times
A\  \nand \ $the word $x$ comes before the word $y$ alphabetically$\}$.\\
c. $A=\reals, R=\{(x,y) \in \reals \times \reals \ \nand \ |x|\leq |y|\}$.\\
d. $A=\reals, R=\{(x,y) \in \reals \times \reals \ \nand \ |x| < |y|$
or $x=y\}$.\\
\medskip
\solution{
\textbf{Solutions:}\\
a. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$ is a partial order on $A$.  However, it is not a total order on $A$ since neither the pair $(a,c)$ nor $(c,a)$ is in $R$.\\
b. $R$ is not reflexive (although it is transitive and antisymmetric), and thus it is not a partial order on $A$.\\
c. $R$ is reflexive and transitive. However, it is not antisymmetric. As a counterexample, \\
$|-3| \leq |3|, |3| \leq |-3|$, but $3 \neq -3$. \\
d. $R$ is reflexive, transitive, and antisymmetric.  Therefore, $R$ is a partial order on $A$. However, $R$ is not a total order on $A$. As a counterexample, if x = 5, y = -5, then none of the following holds: $x = y, |x| < |y|, |y| < |x|$.  
}


%%%
%\ppart Velleman \S 4.4, Exercise 5. %[[[Good]]]
%%%

\eparts   
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Relations --- Equivalence relations}
\bparts
\ppart Velleman \S 4.6, Exercise 3. \\
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Which of the following relations are equivalence relations?  For those that are equivalence\\
relations, what are the equivalence classes?\\
\>a. $R=\{(x,y) \in W \times W \ \nand \ $ the words $x$ and $y$ start with the same letter$\}$,\\
\>\>where $W=$ the set of all words in teh English language.\\
\>b. $S=\{(x,y) \in W \times W \ \nand \ $ the words $x$ and $y$ have at least one letter in\\
\>\>common$\}$, where $W=$ the set of all words in teh English language.\\
\>c. $R=\{(x,y) \in \reals \times \reals \ \nand \ x-y \in \rationals\}$.\\
\>d. $R=\{(x,y) \in \reals \times \reals \ \nand \ \exists n \in \integers$ such that $(y=x\cdot 10^n)\}$.\\
\end{tabbing}
\solution{
\textbf{Solutions:}\\
\renewcommand{\labelenumi}{\alph{enumi}.}
\begin{enumerate}

\item 
$R$ is an equivalence relation since it is reflexive, symmetric, and transitive.  The equivalence class of $x$ with respect to $R$ is the set $[x]_R = $ the set of words $y$, such that $y$ has the same first letter as $x$.

\item
 $S$ is reflexive and symmetric, but it is not transitive.  Therefore, $S$ is not an equivalence relation.  For example, let $w_1$ be the word ``scream,'' let $w_2$ be the word ``and,'' and let $w_3$ be the word ``shout.''  Then $w_3 S w_1$, and $w_1 S w_2$, but it is \textbf{not} the case that $w_3 S w_2$.

\item
$R$ is reflexive since, for any $x\in R$, $x-x=0$.  $R$ is symmetric because if $(x-y)$ is rational, then $(y-x)=-(x-y)$ is rational as well.  Finally, $R$ is also transitive.  To see this, consider $(x,y)\in R$ and $(y,z)\in R$.  We would like to know if $(x,z)$ is also in $R$.  We start by noting that $(x-y)\in \rationals$ and $(y-z)\in \rationals$ by definition of our relation $R$.  Now, we can express $(x-z) = (x-y)+(y-z)$.  Since the sum of any two rational numbers is another rational number, and we have written $(x-z)$ as such, we have shown that $(x,z)\in \rationals$.  Therefore, $R$ is transitive.  Since $R$ is also reflexive and symmetric, $R$ is an equivalence relations on $\reals$.\\
The equivalence class for x is $[x]_R = \{y\ |\ y$ can be written in the form $x + r$, for some rational number $r\}$

\item
$R$ is reflexive, since we can set $n=0$.  $R$ is symmetric because if $y=x*10^k$, for some $k\in \integers$, then $x=y*10^{-k}$, so if $(x,y)\in R$, then $(y,x)\in R$.  We can show that $R$ is transitive as follows: consider pairs $(x,y)\in R$ and $(y,z)\in R$.  $y=x*10^n$ and $z=y*10^m$, for $m,n\in \integers$.   Then, substituting, we have that $z=y*10^{m+n}$.  Since $m+n$ is also $\in \integers$, $(x,z)$ is $\in R$.\\
The equivalence class for x is $[x]_R = \{ y\ |\ y  = x*10^n$, for some $n\in \integers\}$
\end{enumerate}
\renewcommand{\labelenumi}{\arabic{enumi}.}
%%someone should check this... it's getting late and this just seems silly to me
}

\ppart Velleman \S 4.6, Exercise 5. \\
Given $T$, the set of all triangles, and $S=\{(s,t)\in T\times T$ $|$ the triangles $s$ and $t$ are similar$\}$, prove that $S$ is an equivalence relation.\\
\medskip
\medskip
\solution{
\textbf{Solution:}\\
\textbf{Proof:} To prove this, we need to show that $S$ is reflexive, symmetric, and transitive.  Here we go:\\
First of all, two triangles $s$ and $t$ are said to be \textit{similar} if they have three pairs of equal-degree vertices.\\
$S$ is reflexive because every triangle is similar to itself.  That is, every triangle $s$ has three angles of equivalent size to its own three angles.\\
$S$ is symmetric because if $s$ is similar to $t$, then $s$ and $t$ have vertices of the same size, so $t$ is similar to $s$ as well.\\
Finally, $S$ is transitive because if triangle $s$ is similar to triangle $t$, and triangle $t$ is similar to triangle $r$ then triangles $s$ and $t$ have three pairs of equal-degree vertices, and triangles $t$ and $r$ also have three pairs of equal-degree vertices.  $s$ and $r$ must share these three pairs of equal-degree vertices since triangles only have three vertices. $\qed$.
}

%%%
%\ppart Velleman \S 4.6, Exercise 12. 
%%%
\eparts

%%%
%\problem \textbf{Relations --- Topological sorting}
%\bparts
%\ppart Find two total orders that are topological sorts of the divisibility
%relation for the set of natural numbers 1-8:\\
%(i) One with as many as you can pairs out of numerical order.\\
%(ii) One with the FEWEST POSSIBLE pairs out of numerical order.\\
%\eparts
%%%
                                        
        
%END   George's problems

<<<<<<< Sets.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55

=======


=======
%%%%%%%%%%%%%  S99 ps1


>>>>>>> 1.9
\problem (\S 1.4, Exercise 12) We will prove that if the power sets of
$A$ and $B$ are equal, then sets $A$ and $B$ are equal.  In
particular, we will prove $A = B$ by showing that each set is
contained in the other.

First, we show that $A \subseteq B$.  Let $x$ be an element of $A$.
Then $\{ x \}$ is an element of $P(A)$, the power set of $A$.  By the
assumption that $P(A)= P(B)$, we know that $\{ x \}$ is an element of
$P(B)$.  This implies that $x \in B$.  Therefore $A \subseteq B$.  The
argument that $B \subseteq A$ is symmetric.  Therefore, $A = B$ as
claimed.

\problem Prove that $\card{A \oplus B} = \card{A} + \card{B} - 2\card{A
\cap B}$.  \hint See \S1.5, paragraph following Example 5.


\solution Note that $|A| + |B|$ counts each element that is in $A$ but
not in $B$ or in $B$ but not in $A$ exactly once, and each element
that is in both $A$ and $B$ exactly twice.  Thus, $|A| + |B| - 2 |A
\cap B|$ counts only elements that are in $A$ but not in $B$ or in $B$
but not in $A$.  This is precisely the set $A \oplus B$, so we have

\begin{eqnarray*}
|A \oplus B| & = & |A| + |B| - 2 |A \cap B|.
\end{eqnarray*}

\problem (\S 1.5, Exercise 26)  We prove that

\begin{eqnarray*}
A \oplus B & = & (A - B) \cup (B - A)
\end{eqnarray*}

by showing that each set contains the other.  Let $S$ be the set on
the left side of the equation, and let $T$ be the set on the right
side.  Our goal is then to prove that $S = T$.

First, we prove that $S \subseteq T$.  If $x \in S$, then either $x
\in A$ and $x \not\in B$ or else $x \not\in A$ and $x \in B$.  In the
former case, $x \in A - B$, and so $x \in T$.  In the latter case, $x
\in B - A$, and so $x \in T$ again.  Thus, $S \subseteq T$.

Now, we prove that $T \subseteq S$.  If $x \in T$, then there are two
cases: either $x$ is only an element of $A - B$ or only an element of
$B - A$.  (Note that $x$ can not be an element of both sets; they are
disjoint.)  In the first case, $x$ is an element of $A$, but not $B$,
so $x \in S$.  In the second case, $x$ is an element of $B$, but not
$A$, so $x \in S$ again.  Thus, $T \subseteq S$.

Since each set contains the other, $S = T$ as claimed.


%END   Ray's problems
<<<<<<< Sets.tex
>>>>>>> 1.6


=======

%BEGIN Ivan's problems (Spring '98)

%%%%%
%pset1, problem1 in spring98 (variant of F97)
\problem\hfill

\bparts

\ppart

The {\em symmetric difference}, $A \oplus B$, of two sets, $A$
and~$B$, is defined by
\[A \oplus B = (A \cup B)-(A \cap B).\]

Show that $A \oplus B = (A-B) \cup (B-A)$.

\ppart Prove that $\oplus$ is associative.

\eparts

%%%%% SOLUTION
%pset1, problem1 in spring98 (variant of F97)

\solution{
\bparts

\ppart

The {\em symmetric difference}, $A \oplus B$, of two sets
$A$ and~$B$, is defined by
\[A \oplus B = (A \cup B)-(A \cap B).\]

Show that $A \oplus B = (A-B) \cup (B-A)$.

First we show that  $(A-B) \cup (B-A) \subseteq (A \cup B)-(A \cap B)$.

Let $x \in (A-B) \cup (B-A)$. Then $x \in (A-B) \vee x \in (B-A)$.
So, $x \in A$, but $x \not\in B$, or $x \in B$, but $x \not\in A$
from which it follows that $x \in A \vee x \in B$, but $x$ is not in both
$A$ and $B$. So, $x \in A \cup B$, but $x \not\in A \cap B$, therefore
$x \in  (A \cup B)-(A \cap B)$.\\

Now we show that $(A \cup B)-(A \cap B) \subseteq (A-B) \cup (B-A)$.

Let $x \in (A \cup B)-(A \cap B)$.  Then $x \in A \cup B$, but
$x \not\in A \cap B$. So  $x \in A \vee x \in  B$, but $x$ is not in both
$A$ and $B$.
We take cases.
Case 1:
If $x \in A$, then since $x$ is not in $A \cap B$, we conclude that
$x$ is not in $B$.  Therefore $x \in A-B$.\\
Case 2:
If $x \in B$, then by the same argument, $x$ is not in $A$,
therefore $x \in B-A$. So $ x \in A-B \vee x \in B-A$, therefore
$x \in (A-B) \cup (B-A)$.\\

The two inclusions establish the set equality.

\ppart Prove that $\oplus$ is associative.\\

Using membership tables:

\begin{center}
\begin{tabular}{||c|c|c|c|c||}\hline
$A$ $B$ $C$& $A \oplus B$ & $B \oplus C$ & $A \oplus (B \oplus C)$ & $(A \oplus B) \oplus C$ \\ \hline
1 1 1 & 0 & 0 & 1 & 1 \\ \hline
1 1 0 & 0 & 1 & 0 & 0 \\ \hline
1 0 1 & 1 & 1 & 0 & 0 \\ \hline
1 0 0 & 1 & 0 & 1 & 1 \\ \hline
0 1 1 & 1 & 0 & 0 & 0 \\ \hline
0 1 0 & 1 & 1 & 1 & 1 \\ \hline
0 0 1 & 0 & 1 & 1 & 1 \\ \hline
0 0 0 & 0 & 0 & 0 & 0 \\ \hline

\end{tabular}
\end{center}

\eparts
} %solution

%END   Ivan's problems

%BEGIN George's problems
>>>>>>> 1.9
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems

%problems for Fall 99
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Pset 1, problem 2
\problem  \textbf{Sets}
\bparts
\ppart \S 1.4, Exercise 14.  Prove it or give a counterexample.

\solution{The union of all the sets in the power set of a set $X$ must be exactly
$X$. In other words, we can recover $X$ from its power set, uniquely. 
Therefore the answer is yes.}

\ppart \S 1.5, Exercise 12(e).

\solution{To establish the equality, we need to prove inclusion in both
directions. To prove that $(B-A)\cup(C-A)\subseteq(B\cup C)-A$, 
suppose that $x\in(B-A)\cup(C-A)$.
Then either $x\in(B-A)$ or $x\in(C-A)$. Without loss of generality, assume the
former (the proof in the latter case is exactly parallel.) Then $x\in B$
and $x\not\in A$. From the first of these assertions, it follows that
$x\in B\cup C$. Thus we can conclude that $x\in (B\cup C)-A$, as desired. For the
converse, that is, to show that $(B\cup C) -A\subseteq (B-A)\cup (C-A)$, suppose that
$x\in (B\cup C)-A$. This means that $x\in (B\cup C)$ and $x\not\in A$. 
The first of these
assertions tells us that either $x\in B$ or $x \in C$. Thus either $x\in B-A$ or
$x\in C-A$. In either case, $x\in (B-A)\cup (C-A)$. (An alternative proof could be
given by using Venn diagrams, showing both sides represent the same
region.)}

\ppart \S 1.5, Exercise 14.

\solution{That $A\subseteq(A\cap B)\cup (A\cap \bar{B})$ follows from the 
fact that every element $x\in A$ is an
element of either $A\cap B$ (if $x\in B$) or $A\cap \bar{B}$ (if $x\not\in B$). 
On the other hand, if
$x\in (A\cap B)\cup (A\cap \bar{B})$, 
then either $x\in A\cap B$ or $x\in A\cap \bar{B}$. 
In either case, $x\in A$ by the definition of intersection.}

\ppart \S 1.5, Exercise 36.

\solution{We note that these sets are decreasing, that is 
$A_1\supseteq A_2 \supseteq A_3 \supseteq \ldots$.
Therefore the union of any collection of these sets is just the
one with the smallest subscript, and the intersection is just the one
with the largest subscript.\\
a) $A_1=\{1,2,3,\ldots\}$   \ \ \ b) $A_n=\{n, n+1, n+2,\ldots\}$}

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%pset 6, well-ordering on sets
\problem \textbf{Well-orderings}

Prove that for any finite set $S$, $(P(S),\subseteq)$ is a
partially-ordered set and moreover, every nonempty subset of $P(S)$ has a
minimal element.  (Recall that $P(S)$ stands for the power set of $S$.
Also, from the notes on well-founded posets (S99, H18): A \emph{minimal}
element, $m$, in a partial order has the property that no element is
strictly below it.  That is, if $s \preceq m$, then $s = m$, for all $s$
in the partialy ordered set.  For example, the set of three sets
\[
\set{\set{0,1}, \set{0,2,3}, \set{0,1,2,3}}
\]
partially ordered by containment has two minimal elements, namely, the
first two.)

\solution{
We need to show that $\subseteq$ is reflexive, transitive, and
antisymmetric over the elements of $2^S$, and that every nonempty subset
of $P(S)$ has a minimal element.

Reflexive: $B\subseteq B$ since $B=B$.

Transitive: Assume $A\subseteq B$ and $B\subseteq C$.  Then $x\in
A\Rightarrow x\in B\Rightarrow x\in C$, so $A\subseteq C$.

Antisymmetric: If $A\subseteq B$ and $B\subseteq A$, then clearly they 
have the same elements, so $A=B$.

Let $\emptyset\neq T\subseteq P(S)$. 
Define $A=\{|B|:B\in T\}$. Now by the well ordering principle, $A$ has
a least element, say $a$ (since $A$ is a subset of natural numbers.) 
Pick $C\in T$ such that $|C|=a$. Then $C$ is a minimal element in $T$.

%Pick any element, say $T_0\in T$, 
%then if $T_0$ is
%a minimal element then we are done, otherwise assume $T_1\in T$, s.t. 
%$T_1\subset T_0$. If $T_1$ is a minimal element then we are done, otherwise
%pick an element $T_2\in T$ s.t. $T_2\subset T_1$. Notice that we cannot 
%continue
%this procedure an infinite number of times since $P(S)$ has finite cardinality,
%say $k$. Therefore in a finite number of steps, say $k_0\le k$, we pick set
%$T_{k_0}$ such that $\not\exists R\in T \cdot R\subset T_{k_0}$. That is 
%$T_{k_0}$ is a minimal element.
}


%%%%%%%%%%%%%%%%

%END   Tina's problems



\end{problems}

\end{document}



