1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
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
|
