CMSC 250 Homework 10 Spring 2006

Due Wed April 12 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. Prove each statement is true or find a specific counterexample. Assume all sets are subsets of a universal set U.
   1. $\forall A,B \in \{sets\},\,\, A-B \neq B-A$

      FALSE.
      

      Let $A = B = \emptyset$.
      Then $A-B = \emptyset - \emptyset = \emptyset$, and $B-A = \emptyset - \emptyset = \emptyset$.
      But $\emptyset = \emptyset$.

   2. $\forall A,B,C \in \{sets\},\,\, (A \cup (B \cap C)) \subseteq (A \cup B \cup C)$

      TRUE.

      Proof.

      Let $A,B,C$ be arbitrary $\in \{sets\}$.

      Let $x$ be an arbitrary element of the universe $U$.

      $\vert$ Assume $x \in A \cup (B \cap C)$.

      $\vert$ $x \in A ~\vee ~ x \in (B \cap C)$ by Definition of Union.

      $\vert$

      $\vert$ Case $x \in A$:

      $\vert$ $x \in A \vee x \in B$ by Disjunctive Addition.

      $\vert$ $x \in A \vee x \in B \vee x \in C$ by Disjunctive Addition.

      $\vert$ $x \in A \vee x \in (B \cup C)$ by Definition of Union.

      $\vert$ $x \in A \cup (B \cup C)$ by Definition of Union.

      $\vert$

      $\vert$ Case $x \in (B \cap C)$:

      $\vert$ $x \in B \wedge x \in C$ by Definition of Intersection.

      $\vert$ $x \in B$ by Conjunctive Simplification.

      $\vert$ $x \in B \vee x \in C$ by Disjunctive Addition.

      $\vert$ $x \in A \vee (x \in B \vee x \in C)$ by Disjunctive Addition.

      $\vert$ $x \in A \vee x \in (B \cup C)$ by Definition of Union.

      $\vert$ $x \in A \cup (B \cup C)$ by Definition of Union.

      $\vert$

      $\vert$ Therefore, $x \in A \cup (B \cup C)$ by Proof by Division into Cases.

      $\vert$ $x \in A \cup B \cup C$ by Associative Law.

      $x \in A \cup (B \cap C) ~\rightarrow~ (x \in A \cup B \cup C)$ by CCW without a Contradiction.

      $\forall x \in U,\,\, x \in A \cup (B \cap C) ~\rightarrow~ (x \in A \cup B \cup C)$ by Universal Generalization.

      $(A \cup (B \cap C)) \subseteq (A \cup B \cup C)$ by Definition of Subset.

      $\forall A,B,C \in \{sets\},\,\, (A \cup (B \cap C)) \subseteq (A \cup B \cup C)$ by Universal Generalization.

      QED

      Alternative proof (of same theorem).

      Let $A,B,C$ be arbitrary $\in \{sets\}$.

      Let $x$ be an arbitrary element of the universe $U$.

      $\vert$ Assume $x \in A \cup (B \cap C)$.

      $\vert$ $x \in \left( (A \cup B) \cap (A \cup C) \right)$ by Distributive Law.

      $\vert$ $x \in (A \cup B) \wedge x \in (A \cup C)$ by Definition of Intersection.

      $\vert$ $x \in (A \cup B)$ by Conjunctive Simplification.

      $\vert$ $x \in (A \cup B) \vee x \in C$ by Disjunctive Addition.

      $\vert$ $x \in (A \cup B) \cup C$ by Definition of Union.

      $\vert$ $x \in A \cup B \cup C$ by Associative Law.

      $x \in A \cup (B \cap C) ~\rightarrow~ (x \in A \cup B \cup C)$ by CCW without a Contradiction.

      $\forall x \in U,\,\, x \in A \cup (B \cap C) ~\rightarrow~ (x \in A \cup B \cup C)$ by Universal Generalization.

      $(A \cup (B \cap C)) \subseteq (A \cup B \cup C)$ by Definition of Subset.

      $\forall A,B,C \in \{sets\},\,\, (A \cup (B \cap C)) \subseteq (A \cup B \cup C)$ by Universal Generalization.

      QED

   3. $\forall A, B, C \in \{sets\}, \,\, (A-B)-C \subseteq (A-C)$

      TRUE.

      Proof.

      Let $A,B,C$ be arbitrary $\in \{sets\}$.

      Let $x$ be an arbitrary element of the universe $U$.

      $\vert$ Assume $x \in (A-B)-C$.

      $\vert$ $x \in (A-B) \cap C^{\prime}$ by Definition of Set Difference.

      $\vert$ $x \in (A \cap B^{\prime}) \cap C^{\prime}$ by Definition of Set Difference.

      $\vert$ $x \in (A \cap B^{\prime}) \wedge x \in C^{\prime}$ by Definition of Intersection.

      $\vert$ $x \in (A \cap B^{\prime})$ by Conjunctive Simplification.

      $\vert$ $x \in A \wedge x \in B^{\prime}$ by Definition of Intersection.

      $\vert$ $x \in A$ by Conjunctive Simplification.

      $\vert$ $x \in C^{\prime}$ by Conjunctive Simplification.

      $\vert$ $x \in A \wedge x \in C^{\prime}$ by Conjunctive Addition.

      $\vert$ $x \in A \cap C^{\prime}$ by Definition of Intersection.

      $\vert$ $x \in A - C$ by Definition of Set Difference.

      $x \in (A-B)-C \rightarrow x \in A - C$ by CCW without a Contradiction.

      $\forall x \in U,\,\, x \in (A-B)-C \rightarrow x \in A - C$ by Universal Generalization.

      $(A-B)-C \subseteq A - C$ by Definition of Subset.

      $\forall A,B,C \in \{sets\},\,\, (A-B)-C \subseteq A - C$ by Universal Generalization.

      QED

   4. $\forall A, B, C \in \{sets\}, \,\, (A \times B) \times C = A \times (B \times C)$

      FALSE.

      Let $U = \{u\}$. Then
      

      $$(A \times B) \times C ~=~ \{ (u,u),u \}$$
      
      
      and
      
      $$A \times (B \times C) ~=~ \{ u,(u,u) \}.$$
      
      
      The two sets each have one element, but $((u,u),u) \ne (u,(u,u))$.

   5. $\forall A,B,C \in \{sets\}, \,\, A-(B\cup (A \cap C)) = (A-(B \cup C)) \cup (A \cap B \cap C)$

      FALSE.
      

      Let $A = B = \{ x \}$.
      Then the LHS

      $$\begin{eqnarray*} A-(B\cup (A \cap C)) & ~=~ & \{x\} -(\{x\} \cup (\{x\} \cap \{... ...} \cup (\{x\} ) \\ & ~=~ & \{x\} - \{x\} \\ & ~=~ & \emptyset \end{eqnarray*}$$
      
      
      
      
      
      And the RHS
      $$\begin{eqnarray*} (A-(B \cup C)) \cup (A \cap B \cap C) & ~=~ & (\{x\}-(\{x\} \c... ...}) \cup \{x\} \\ & ~=~ & \emptyset \cup \{x\} \\ & ~=~ & \{x\} \end{eqnarray*}$$
      
      
      
      
      
      LHS $\ne$ RHS.

2. Find each of the following assuming $A = \{\{1\},a\}$ and $B=\{A,1\}$
   1. Find ${\cal{P}}(A)$

      ${\cal{P}}(A) ~=~ \{\emptyset , \{\{1\}\}, \{a\}, \{\{1\},a\} \}$

   2. Find ${\cal{P}}(B)$

      ${\cal{P}}(B) ~=~ \{\emptyset , \{A\}, \{1\}, \{A,1\} \}$

   3. Answer the following questions:
      1. Is $A \in {\cal{P}}(B)$?     No.
      2. Is $A \subseteq {\cal{P}}(B)$?     No.
      3. Is $A \subseteq B$?     No.
      4. Is $A \in B$?     Yes.

3. Let $A = \{ a,b,c,d,e,f\},\, A_1 = \{a, c\},\, A_2 = \{b, d\},\, A_3 = \{e, f\}, \, A_4 = \{a,c,d\}$.
   1. Explain why $\{A_1, A_2, A_3, A_4\}$ does not form a partition of $A$.

      The elements $a,c$ are in both $A_1$ and $A_4$. Also, the element $d$ is in both $A_2$ and $A_4$.

   2. Explain why $\{A_3, A_4\}$ does not form a partition of $A$.

      The element $b$ is not in any set.

   3. Explain why $\{A_1, A_2, A_3\}$ does form a partition of $A$.

      Every element occurs in some set exactly once.

   4. Alter the set $A_{3}$ in two different ways so that the new collection of subsets $\{A_1, A_2, A_3\}$ fails to be a partition of $A$ for a different reason for each of the alterations.

      Remove $e$ (from $A_3$): Then $e$ does not occur in any set.
      Add $a$ (into $A_3$): Then $a$ occurs in both $A_1$ and $A_3$.
      

4. Your UMCP student ID is an 8 digit number.
   1. How many different ID's are possible (assuming no other restrictions)?

      $10^8$

   2. How many different ID's are possible if there can be no 0's in the number?

      $9^8$

   3. How many different ID's are possible if the number can neither start nor end with a 0?

      $9^2 10^6$

   4. What is the probability that a ID chosen at random contains no 0's?

      $\frac{9^8}{10^8} ~=~ (9/10)^8$

Web Accessibility