Computing and Data Science

Set Theory

Sign in to Overleaf and use this template to write your solutions.

There are some notation rendering issues... you will sometimes see "not" as a bar, \(\bar{A}\), and sometimes as an apostrophe, \(A'\). That's notation for you!

  1. Find the power set of \(A = \{x,y,z\}\). The power set is the set of all possible subsets.
  2. Given the diagram below:
    1. Write the three sets by listing their elements.
    2. Write as many true statements as you can about the element 6.
  3. Given that \(|A|=10\) and \(|B|=7\), what is the largest and smallest possible size for \(|A \cup B|\)?
  4. Given: \[A = {2,4,6,8}\] \[B = {1,2,3,4} \] \[C = {0,3,6,9} \] Assume that every element in the universal set is an element of at least one these sets. Write the expression and draw the Venn diagram for each of:
    1. \( A \cup C \)
    2. \( A \cap B \)
    3. \( A \cup B \cup C \)
    4. \( \bar{B} \)
    5. \( A \cap (B \cup C) \)
  5. Given: \[ \mathcal{U} = \{ a,b,c,d,e,f,g,h\} \]
    1. Assign elements to sets \(A\) and \(B\) such that: \[|A| = 3\] \[|B| = 6\] \[|A \cap B| = 2\]
    2. Find \(|A \cup B|\).
    3. Find \(| (A \cup B)'|\).
    4. Compare your answers from parts b and c with others. Is it possible for these answers to be different? Explain why or why not.
  6. \(A=\{3,5,6,7,8\}\) and \(B=\{3,6,7,9,12\}\). Find each of the following sets.
    1. \(A \cup B \)
    2. \(A \cap B \)
    3. \(A \setminus B \)
    4. \(B \setminus A \)
  7. Find the following cardinalities:
    1. \(|A|\) when \(A=\{5,6,7,8,...,35\}\)
    2. \(|A|\) when \(A=\{x \in \mathbb{Z}: -2 \leq x \leq 97\}\)
    3. \(|A \cap B|\) when \(A = \{x \in \mathbb{Z}: x \leq 37\}\) and \(B = \{x \in \mathbb{Z}: x \text{ is prime }\}\)
  8. Let \(A = \{9,11,12,13,14\}\) and \(B = \{9, 18, 19, 27, 36\}\). Find a set of largest possible size that is a subset of both \(A\) and \(B\).
  9. Find a set of smallest possible size that has both \(\{2,3,7,9,10\}\) and \(\{4,8,9,10\}\) as subsets.
  10. Let \(A=\{2,3,9,13,15 \}\) and \(B=\{3,9,13 \}\). How many sets \(C\) have the property that \(C \subseteq A\) and \(B \subseteq C\)?
  11. Let \(A=\{3,4,5,6,7\}\), \(B=\{5,6,7,8,9\}\), and \(C=\{4,7,9\}\).
    1. Find \(A \cap B\)
    2. Find \(A \cup B\)
    3. Find \(A \setminus B\)
    4. Find \(A \cap (B \cup C)'\)
  12. The set of integers is \(\mathbb{Z} = \{..., -2, -1, 0 , 1, 2, ...\}\). Let \(\mathbb{Z}^{+}=\{1,2,3,...\}\) be the positive integers. Let \(2\mathbb{Z}\) be the even integers, \(3\mathbb{Z}\) be the muliples of 3, and so on.
    1. Is \(\mathbb{Z}^{+} \subseteq 2\mathbb{Z}\)? Explain.
    2. Is \(2\mathbb{Z} \subseteq \mathbb{Z}^{+}\)? Explain.
    3. Find \(2\mathbb{Z} \cap 3\mathbb{Z}\). Describe the set in words, and using set notation.
  13. Let \(A_2\) be the set of all multiples of \(2\) except for \(2\). Let \(A_3\) be the set of all multiples of \(3\) except for \(3\). And so on, so that \(A_n\) is the set of all multiples of \(n\) except for \(n\), for any \(n\geq 2\). Describe (in words) the set \((A_2 \cup A_3 \cup A_4 \cup \dots )'\text{.}\)
  14. Draw a Venn diagram to represent each of the following:
    1. \( A \cup B' \)
    2. \( (A \cup B)' \)
    3. \( A \cap (B \cup C) \)
    4. \( (A \cap B) \cup C \)
    5. \( A' \cap B \cap C' \)
    6. \( (A \cup B) \setminus C \)
  15. Consider the sets \(A\) and \(B\), where \(A=\{3, |B|\}\) and \(B=\{1,|A|,|B|\}\). What are the sets?
  16. Explain why no set \(A\) exists which satisfies \(A=\{2,|A|\}\).
  17. Find all sets \(A\), \(B\), and \(C\) which satisfy the following: \[ A = \{ 1, |B|, |C| \} \] \[B = \{ 2, |A|, |C| \}\] \[C = \{ 1, 2, |A|, |B| \}\]
  18. Consider the sets: \[B = \{1,2,3,4,5\}\] \[E = \{5, 17, E, 42\}\] \[T = \{4, 5, B, 13\}\] \[H = \{5,4,3,H,1\}\] Some sets contain themselves, e.g., \(E \in E\) and \(H \in H\). Let \(R\) be the set of all sets that do not contain themselves. Then \(B \in R\) and \(T \in R\), and \(E \notin R\) and \(H \notin R\). Is \(R \in R\)?
  19. Find more exercises in Levin 3rd Edition.