\newfam\bbold
\def\bb#1{{\fam\bbold #1}}
\font\bbten=msbm10
\font\bbsev=msbm7
\font\bbfiv=msbm5
\textfont\bbold=\bbten
\scriptfont\bbold=\bbsev
\scriptscriptfont\bbold=\bbfiv

\newcount\indentlevel
\newcount\itno
\def\reset{\itno=1}\reset
\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
\aftergroup\afterstartlist}
\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
    i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
    s\or t\or u\or v\or w\or x\or y\or z\fi}
\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or
                                  \alph\itno)\else
                                  (\number\itno)\fi
                           }%
         #1\smallskip\advance\itno by 1\relax}
\def\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}}
\let\endul\egroup
\def\hline{\noalign{\hrule}}
\let\impl\rightarrow
\newskip\tableskip
\tableskip=10pt plus 10pt
\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt
depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}}

\def\oldcomma{,}
\catcode`\,=13
\def,{%
    \ifmmode
        \oldcomma\mskip\medmuskip\discretionary{}{}{}%
    \else
        \oldcomma
    \fi
}

\li Determine whether these statements are true or false.

{\startlist

\li $\emptyset \in \emptyset.$

False. No item is in the empty set.

\li $\emptyset \subset \emptyset.$

False. These two sets are equal, so they can't be a proper subset.

\li $\emptyset \subseteq \emptyset.$

True. These two sets are equal, so they form a subset.

\li $\{\emptyset\} \in \{\emptyset\}.$

False. This isn't an element.

\li $\{\emptyset\} \in \{\emptyset, \{\emptyset\}\}.$

True. This is an element.

\li $\{\{\emptyset\}\} \subseteq \{\{\emptyset\}, \{\emptyset\}\}.$

True. These two sets are equal to each other.
}

\li Determine the cardinality of the following sets.

{\startlist

\li $\emptyset$

0.

\li $\{U\}$

1.

\li $\{a,\{b\},a,b\}$

3.

\li $\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$

3.
}

\li State whether the following is True or False and explain your
reasoning for full credit:

{\startlist

\li The cardinality of every set is always less than the cardinality of
its powerset.

True. If $a$ is an element of a set, $\{a\}$ is an element of its
powerset, and $\emptyset$ is always in the powerset, so the size of the
powerset is at least $n+1$ if the cardinality of the set is $n.$

\li The Cartesian product of two sets is the null set if and only if
both sets are also the null set.

False. $\emptyset\times A$ is always the null set, even if $A$ is
non-empty.

\li Given 3 sets $A,$ $B,$ and $C,$ $|A\cup B\cup C| = |A| + |B| + |C| -
|A\cap B| - |A\cap B| - |B\cap C|.$

False.
Let $A = B = C = \{\emptyset\}.$
$|A\cup B\cup C| = 1,$ but the right side evaluates to 0.
}

\li Let $A = \{a,b,c,d,e\},$ $B = \{a,b,c,d,e,f,g,h\},$ and $U$
represent a universal set of $\{a,b,c,d,e,f,g,h,i,j,k,l\}.$ Find:

{\startlist

\li $A\cup B\cup \emptyset.$

$\{a,b,c,d,e,f,g,h\}.$

\li $U\cap B\cap A.$

$\{a,b,c,d,e\}.$

\li $A - B$

$\emptyset.$

\li $B - A$

$\{f,g,h\}.$

\li $A\times B$

$\{(a,a), (a,b), (a,c), (a,d), (a,e), (a,f), (a,g), (a,h),
   (b,a), (b,b), (b,c), (b,d), (b,e), (b,f), (b,g), (b,h),
   (c,a), (c,b), (c,c), (c,d), (c,e), (c,f), (c,g), (c,h),
   (d,a), (d,b), (d,c), (d,d), (d,e), (d,f), (d,g), (d,h),
   (e,a), (e,b), (e,c), (e,d), (e,e), (e,f), (e,g), (e,h)\}.$

\li $B\times A$

$\{(a,a), (b,a), (c,a), (d,a), (e,a), (f,a), (g,a), (h,a),
   (a,b), (b,b), (c,b), (d,b), (e,b), (f,b), (g,b), (h,b),
   (a,c), (b,c), (c,c), (d,c), (e,c), (f,c), (g,c), (h,c),
   (a,d), (b,d), (c,d), (d,d), (e,d), (f,d), (g,d), (h,d),
   (a,e), (b,e), (c,e), (d,e), (e,e), (f,e), (g,e), (h,e)\}.$

\li $A^c$

$\{f,g,h,i,j,k,l\}.$

\li ${\cal P}(A)$

$\{\emptyset, \{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{a,b\}, \{a,c\},
\{a,d\}, \{a,e\}, \{b,c\}, \{b,d\}, \{b,e\}, \{c,d\}, \{c,e\}, \{d,e\},
\{a,b,c\}, \{a,b,d\}, \{a,b,e\}, \{a,c,d\}, \{a,c,e\}, \{a,d,e\},
\{b,c,d\}, \{b,c,e\}, \{b,d,e\}, \{c,d,e\}, \{a,b,c,d\}, \{a,b,c,e\},
\{a,b,d,e\}, \{a,c,d,e\}, \{b,c,d,e\}, \{a,b,c,d,e\}\}.$

}

\li Prove or disprove the following statements, for all sets A, B, and
C.

{\startlist

\li $\overline{A\cup B} = \overline A \cap \overline B.$

The complement notation requires a universal set $U,$ which is
implicitly defined here.

We start from $\overline{A\cup B}.$
\smallskip
\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in
\halign{\vrule\strut#\tabskip\tableskip&#\hfil&#\hfil&#\tabskip0pt&#\vrule\cr\hline
    &$\{x|x\in \overline{A\cup B}\}$&Set Builder Notation&&\cr
    &$\{x|x\in U\land x\not\in A\cup B\}$&Def'n of complement&&\cr
    &$\{x|x\in U\land \lnot(x\in A\lor x\in B)\}$&Def'n of union&&\cr
    &$\{x|x\in U\land x\not\in A\land x\not\in B)\}$&DeMorgan's Law&&\cr
    &$\{x|x\in U\land x\in U\land x\not\in A\land x\not\in B\}$&Idempotent Law&&\cr
    &$\{x|x\in U\land x\not\in A\land x\in U\land x\not\in B\}$&Commutative Law&&\cr
    &$\{x|(x\in U\land x\not\in A)\land(x\in U\land x\not\in B)\}$&Associative Law&&\cr
    &$\{x|x\in\overline A\land(x\in U\land x\not\in B)\}$&Def'n of complement&&\cr
    &$\{x|x\in\overline A\land x\in\overline B\}$&Def'n of complement&&\cr
    &$\{x|x\in\overline A\cap \overline B\}$&Def'n of intersection&&\cr
    &$\overline A\cap \overline B$&Def'n of set builder&&\cr
    \hline
}
\smallskip

\iffalse
To show equality, we will show $\overline{A\cup B} \subseteq \overline A
\cap \overline B$ and $\overline{A\cup B} \supseteq \overline A \cap
\overline B.$

$(\subseteq)$
\smallskip

Let $x\in \overline{A \cup B}.$ $x\in U$ and $x\not\in A \cup B,$ so
$x\not\in A$ and $x\not\in B$ (contrapositively, $x\in A\lor x\in B
\to x\in A \cup B.$)
If $x\in U$ and $x\not\in A,$ $x\in\overline A,$ and similarly,
$x\not\in B,$ so $x\in\overline B.$
Therefore, $x\in \overline A \cap \overline B.$

$(\supseteq)$
\smallskip

Let $x\in \overline A \cap \overline B.$ This implies $x\in\overline A$
and $x\in\overline B.$
$x\in\overline A$ only if $x\in U$ and $x\not\in A.$
Similarly, $x\in\overline B$ implies $x\not\in B.$
Together, this gives $x\not\in A \cup B.$
Therefore, $x\in \overline{A\cup B}$ because $x\in U.$

\smallskip
We have now shown that these sets are equal.
\fi

\li $A \cup (B \cup A) = A.$

False. Let $A = \emptyset$ and $B = \{\emptyset\}.$
The set $A \cup B = \{\emptyset\},$ so $A \cup (B \cup A) =
\{\emptyset\} \neq A = \emptyset.$
}

\bye
