diff options
Diffstat (limited to 'howard')
| -rw-r--r-- | howard/Makefile | 2 | ||||
| -rw-r--r-- | howard/hw4.tex | 235 |
2 files changed, 236 insertions, 1 deletions
diff --git a/howard/Makefile b/howard/Makefile index 8e5dd3a..7685eb6 100644 --- a/howard/Makefile +++ b/howard/Makefile @@ -6,7 +6,7 @@ PDFTEX = pdftex .tex.pdf: $(PDFTEX) $< -all: hw1.pdf hw2.pdf hw3.pdf +all: hw1.pdf hw2.pdf hw3.pdf hw4.pdf clean: rm -f *.pdf *.log 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 |