1 files changed, 235 insertions, 0 deletions
diff --git a/howard/hw4.tex b/howard/hw4.tex
new file mode 100644
index 0000000..aad88c0
--- /dev/null
+++ b/howard/hw4.tex
@@ -0,0 +1,235 @@
+\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