CMSC 250

Quiz #8 KEY

Monday, Oct. 29, 2001

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

1. [12 pnts.] Assuming $\Sigma$ is the set $\{a,b,c\}$ do each of the following:
   1. Give the value of $\Sigma^2$.
      
      
      
      
      $$\Sigma^2 = \{aa, ab, ac, ba, bb, bc, ca, cb, cc\}$$
      
      
      
      
      
      
   2. Give the power set of $\Sigma$.
      
      
      
      
      $$P(\Sigma) = \{\emptyset , \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$$
      
      
      
      
      
      
   3. Assuming $A = \{1,2\}$ - give $A \times \Sigma$.
      
      
      
      
      $$A \times \Sigma = \{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)\}$$
      
      
      
      
      
      
2. [8 pnts.] Give the lists of elements in each of the sets ($A$ and $B$) assuming $A-B = \{1,5,7,8\}$, $B-A = \{2,10\}$ and $A \intersect B = \{3,6,9\}$.
   
   
   
   
   $$A = \{1,5,7,8,3,6,9\}$$
   
   
   
   
   $$B = \{2,10,3,6,9\}$$
   
   
   
   
   
   
3. [10 pnts.] Prove or give a counter example to the following. For all sets A, B and C. If $A \subseteq B$ and $B \intersect C = \emptyset$, then $A \intersect C = \emptyset$. Suppose A, B and C are arbitrary sets.
   
   
   -----------DIRECT METHOD --------
   
   Assume $A \subseteq B$ and $B \intersect C = \emptyset$
   and an arbitrary x such that $x \in A$
   
   Since $x \in A$ and $A \subseteq B$, by the definition of subset $x \in B$.
   Since $B \intersect C = \emptyset$, B and C are disjoint sets.
   Since B and C are disjoint sets and $x \in B$, then $x \not \in C$.
   
   This means that $\forall x \in U, x \in A \rightarrow x \not \in C$.
   By the definition of complement, this is the same as: $\forall x \in U, x \in A \rightarrow x \in C^c$
   
   By the definition of subset, this means: $A \subseteq C^c$
   
   Therefore every member of $A$ would need to be in $C^c$.
   Since $C$ and $C^c$ are disjoint, $A$ and $C$ would also be disjoint.
   
   Therefore, $A \intersect C = \emptyset$. QED
   
   
   -------- USING CONTRADICTION ---------
   
   Assume $x \in (A \intersect C)$
   
   This means that $x \in A$ and $x \in C$ by the definition of intersection.
   $x \in A$ by conjunctive simplification.
   $x \in C$ by conjunctive simplification.
   
   Since $x \in A$ and $A \subseteq B$, then $x \in B$.
   $x \in B \and x \in C$ by conjunctive addition.
   $x \in (B \intersect C)$ by definition of intersection.
   
   contradiction because $x$ can't be in $B \intersect C$ if $B \intersect C = \emptyset$.
   Therefore our assumption that $x \in (A \intersect C)$ must be false.
   Since $x$ was arbitrarily chosen, it must be true that $\forall x \in U, x \not \in (A \intersect C)$.
   Therefore $A \intersect C = \emptyset$.

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode quiz8ans.tex

The translation was initiated by Deep Saraf on 2001-11-13