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:
    ABC35812467
    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. Find more exercises in Levin 3rd Edition.