\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Discussion 1 -- Set Operations}
\centerline{\it September 8, 2004}
\bigskip
\noindent
{\it Background}
\bigskip
The language of (modern) mathematics is the language of 
{\it sets}.  Today, we want to review some of the basic ideas
about sets and the most common operations on sets.
Recall that a set is essentially just a {\it collection of
objects}.  To specify a set, we can either list the elements,
e.g. $A = \{1,2,3,4\}$ for the set of natural numbers less than
5, or we can give a ``test'' for determining which
objects are in the set.  The usual notation for this is 
called ``set-builder'' notation.  Here is an example:
$$A = \{x : x {\rm\ is\ a\ natural\ number\ and\ } x < 5\},$$
or 
$$A = \{x : x \in {\bf N} {\rm\ and\ } x < 5\},$$
(${\bf N}$ is a common name used for the set of natural numbers.
Similarly, we often write ${\bf Z}$ for the set of integers,
${\bf Q}$ for the set of all rational numbers, 
${\bf R}$ for the set of all real numbers.)
Either of these equations is read as ``A is the set of all $x$ such that $x$ is a 
natural number and $x < 5$.''

\bigskip
The proposition that an object $x$ is an element
of the set $A$ is written symbolically as $x \in A$, and 
its negation is written as $x \notin A$.  We emphasize
that $x\in A$ should be a {\it proposition} -- unambiguously
true or false, and not both.  For instance ``I am an element
of the set of tall people'' does not qualify (at least not
without a more precise definition of what the set of tall
people is, or what the exact criterion for tallness is).   
The set with no elements (i.e. the set where $x \in A$
is always false) is called the {\it empty set}, written $\emptyset$.

\bigskip
\noindent
Some additional notation:  Given sets $A,B$, we can form
\smallskip
\item{$\bullet$} the {\it union}
$$A \cup B = \{x : x \in A {\rm\ or\ } x \in B\},$$
\item{$\bullet$} the {\it intersection}
$$A \cap B = \{x : x \in A {\rm\ and\ } x \in B\},$$
\item{$\bullet$} the {\it set difference}
$$A\ \backslash\ B = \{x : x \in A {\rm\ and\ } x \notin B\}.$$
\smallskip
\noindent
Note the logical connectives used here.

\bigskip
For example, let $A = \{1,2,5,6\}, B = \{2,5,7\}, C = \{2,3,4\}$
(all subsets of the set of natural numbers).  Then 
$$\eqalign{A \cup B &= \{1,2,5,6,7\}\cr
           B \cap C &= \{2\}\cr
           A\ \backslash\ C &= \{1,5,6\}\cr}$$
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
I.  Using set-builder notation, how would you write:
\item{A)} The set of all real numbers between 1 and 3 (inclusive)?
\item{B)} The set of all natural numbers that satisfy $x^2 - 5x + 6 = 0$.
\bigskip
\noindent
II. Let $A =\{2,3,6\}$, $B =\{x : x {\rm\ is\ an\ even\ natural\ number\ and\ }
3 < x < 7\}$, $C = \{1,3,6,8\}$.  Find
\item{A)}  $A \cup B$.
\item{B)}  $B \ \backslash\ (A \cap C)$
\item{C)}  $(B\ \backslash\ A) \cap C$.
\bigskip
\noindent
III.  Using the same $A,B,C$ from question II, 
decide whether the following statements are true or false, and 
give a reason for your conclusion in each case.
Notation:  $X \subseteq Y$ is the proposition ``the set $X$ is
contained in the set $Y$'' -- that is, every element in $X$ is also
an element of $Y$.  
\bigskip
\item{A)}  $(A \cap B) \subseteq C$
\item{B)}  $\emptyset \in A$  (What is the difference between
saying $\emptyset \subseteq A$ and $\emptyset \in A$?)
\item{C)}  $(B\ \backslash\ A) \subseteq C$
\item{D)}  $A \cap B \cap C = 6$.  (Careful, what ``type of object''
is 6?  Is it the same type of object as the left side of the equation?)
\bigskip
\noindent
IV.  The set operations above satisfy a number of different 
properties that will be useful to us.  See Theorem 5.13 in the 
text for a few.  To practice some of the ideas about proofs
we discussed for the past few days, let's consider 5.13 g:
For all sets $A,B,C$, 
$$A\ \backslash\ (B \cap C) = (A\ \backslash\ B) \cup (A\ \backslash\ C)
\leqno(1)$$
(one of ``DeMorgan's Laws'').  To prove an equality of sets $X = Y$, one
basic approach is to show both inclusions $X \subseteq Y$
and $Y \subseteq X$.  This will give the basic outline of the 
proof, one paragraph to show each inclusion.  Within each paragraph
we will use another standard idea about showing inclusions:
\item{A)}  Explain why the statement $X \subseteq Y$ is 
equivalent to the statement $x \in X \Rightarrow x \in Y$.
\item{B)}  ``Fill in the blanks'' to give a complete proof of (1):
\bigskip
\noindent
{\it Proof:}  First we show $A\ \backslash\ (B \cap C) 
\subseteq (A\ \backslash\ B) \cup (A\ \backslash\ C)$.  Let
$x \in A\ \backslash\ (B \cap C)$.  We want to show
that $x \in (A\ \backslash\ B) \cup (A\ \backslash\ C)$
follows from this.  By the
definition of set difference, $x \in A\ \backslash\ (B \cap C)$
means $x \in \underline{\ \ \ }$ and 
$x \notin \underline{\ \ \ \ \ \ \ \ \ \ \ \ \ }$.  
By 1.6 a on page 6 of the text,
$x \notin B \cap C$
is equivalent to $x \notin B$ $\underline{\ \ \ }$ $x \notin C$.
But then $x \in A$ and $x\notin B$, or $x\in A$ and $x \notin C$.
By definition, again, this means $x \in A\ \backslash B$, or
$x \in A\ \backslash C$.  Hence by the definition of the union,
$\underline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }$.

Next, we show $(A\ \backslash\ B) \cup (A\ \backslash\ C)
\subseteq A\ \backslash\ (B \cap C)$.  Let 
$\underline{\ \ \ \ \ \ \ \ \ \ \ }$.
Then $x\in A$ and $x \notin B$, or $x\in A$ and 
$\underline{\ \ \ \ \ \ \ \ \ }$.  By the definition
of the set difference, this says $x \in A$ and either $x\notin B$,
or $x\notin C$ (or both).  By 1.6 a again,
we get $x \in A \backslash (B \cap C)$.  
\bigskip
\item{C)}  Develop your own proof that if $A,B$ are any sets
and $A \cap B = A$, then $A \subseteq B$, and conversely 
if $A \subseteq B$, then $A \cap B = A$. 
\bigskip
\noindent
{\it Assignment}
\bigskip
Group write-ups due Monday, September 13. 
\bye
 