Tasks 02 - Sets

Mathematics for Master Students

These problems accompany Session 02 of the tutorial. Work through them at your own pace before the next session. We start Session 03 with your questions. On the website, every problem has a fully worked solution you can expand to check yourself. The PDF version contains only the problems, so you can print it and use it as a worksheet.

The problems are staged: the first two are warm-ups, the middle ones practice the core techniques, and the last two are at the level of the mock exam.

Problem 1: Element or Subset?

A freight forwarder offers containers with the capacities (in tons) \(D = \{2, 4, 8, 16\}\). Decide for each statement whether it is true or false, and justify your answer in one sentence. The key question is always: does the symbol relate an element to a set, or two sets?

  1. \(4 \in D\)
  2. \(\{4\} \in D\)
  3. \(\{2, 16\} \subseteq D\)
  4. \(6 \notin D\)
  5. \(\emptyset \subseteq D\)
  6. \(D \subset D\)
  1. True. \(4\) is one of the four listed elements of \(D\).
  2. False. The elements of \(D\) are numbers, not sets: \(\{4\}\) is a set containing the number \(4\), and no set appears among the elements of \(D\). (What is true: \(\{4\} \subseteq D\), since every element of \(\{4\}\), namely \(4\), is in \(D\).)
  3. True. \(\subseteq\) relates two sets: both elements of the left set, \(2\) and \(16\), are elements of \(D\).
  4. True. \(6\) does not appear in the list. The forwarder has no \(6\)-ton container.
  5. True. The empty set is a subset of every set: it has no element that could be missing from \(D\).
  6. False. \(D \subseteq D\) holds for every set, but the proper subset symbol \(\subset\) additionally requires \(D \neq D\), which is impossible. Remember: \(\subseteq\) works like \(\leq\), \(\subset\) like \(<\).
WarningCommon Mistake

When writing \(4 \subseteq D\) or \(\{4\} \in D\), always ask first: is the thing on the left an element or a set? \(\in\) is for elements, \(\subseteq\) for sets.

Problem 2: Set-Builder and Listing

Translate between the two ways of describing a set. Remember this tutorial’s convention: \(\mathbb{N} = \{1, 2, 3, \dots\}\) does not contain \(0\).

  1. List the elements of \(\{x \in \mathbb{N} : x \text{ is odd and } x < 10\}\).
  2. List the elements of \(\{x \in \mathbb{Z} : -2 \leq x < 3\}\).
  3. Write \(\{5, 10, 15, 20, 25\}\) in set-builder notation.
  4. List the elements of \(\{x \in \mathbb{N} : x^2 < 20\}\).

Read set-builder notation as a filter: start from the base set, keep exactly the elements passing the condition.

  1. Odd natural numbers below \(10\): \(\{1, 3, 5, 7, 9\}\).
  2. The base set is \(\mathbb{Z}\), so negative numbers and \(0\) are allowed. The left endpoint \(-2\) is included (\(\leq\)), the right endpoint \(3\) is excluded (\(<\)): \(\{-2, -1, 0, 1, 2\}\).
  3. The elements are the first five multiples of \(5\). One clean way to write this: \[\{5k : k \in \mathbb{N}, \, k \leq 5\}\] Equally correct: \(\{x \in \mathbb{N} : x \text{ is a multiple of } 5 \text{ and } x \leq 25\}\). Set-builder descriptions are not unique: any filter producing exactly these five elements is right.
  4. Test the natural numbers in order: \(1^2 = 1\), \(2^2 = 4\), \(3^2 = 9\), \(4^2 = 16\) are all below \(20\), but \(5^2 = 25 \geq 20\), and every larger \(n\) only gets worse. So the set is \(\{1, 2, 3, 4\}\). (Careful: \(0\) is not included; in this tutorial \(0 \notin \mathbb{N}\).)

Problem 3: Set Operations and De Morgan’s Laws

Work inside the universal set \(U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\). Let

\[A = \{1, 3, 5, 7, 9\} \quad \text{(the odd numbers)} \qquad B = \{6, 7, 8, 9, 10\} \quad \text{(the numbers above } 5\text{)}\]

  1. Compute \(A \cup B\) and \(A \cap B\).
  2. Compute \(A \setminus B\) and \(B \setminus A\). Are they equal?
  3. Compute the complements \(A^c\) and \(B^c\).
  4. Verify both De Morgan’s laws for these sets: compute \((A \cup B)^c\) and \(A^c \cap B^c\), then \((A \cap B)^c\) and \(A^c \cup B^c\).

  1. Union collects everything in at least one set, intersection keeps only shared elements: \[A \cup B = \{1, 3, 5, 6, 7, 8, 9, 10\} \qquad A \cap B = \{7, 9\}\] (\(7\) and \(9\) are the only numbers that are both odd and above \(5\).)

  2. \(A \setminus B\) removes from \(A\) everything that is in \(B\); \(B \setminus A\) works the other way around: \[A \setminus B = \{1, 3, 5\} \qquad B \setminus A = \{6, 8, 10\}\] They are not equal: set difference is not symmetric, order matters (just like subtraction of numbers).

  3. The complement is everything in \(U\) outside the set: \[A^c = \{2, 4, 6, 8, 10\} \quad \text{(the even numbers)} \qquad B^c = \{1, 2, 3, 4, 5\} \quad \text{(the numbers up to } 5\text{)}\]

  4. First law, \((A \cup B)^c = A^c \cap B^c\):

    Step 1 - Complement of the union. Remove \(A \cup B = \{1, 3, 5, 6, 7, 8, 9, 10\}\) from \(U\), leaving \[(A \cup B)^c = \{2, 4\}\]

    Step 2 - Intersect the complements: \[A^c \cap B^c = \{2, 4, 6, 8, 10\} \cap \{1, 2, 3, 4, 5\} = \{2, 4\} \checkmark\]

    Second law, \((A \cap B)^c = A^c \cup B^c\):

    Step 3 - Complement of the intersection. Remove \(A \cap B = \{7, 9\}\) from \(U\): \[(A \cap B)^c = \{1, 2, 3, 4, 5, 6, 8, 10\}\]

    Step 4 - Unite the complements: \[A^c \cup B^c = \{2, 4, 6, 8, 10\} \cup \{1, 2, 3, 4, 5\} = \{1, 2, 3, 4, 5, 6, 8, 10\} \checkmark\]

    Both pairs match: the complement flips \(\cup\) into \(\cap\) and vice versa. This is exactly Session 1’s law \(\neg(p \vee q) \Leftrightarrow \neg p \wedge \neg q\) in set notation.

Problem 4: Counting with Inclusion-Exclusion

A retailer audits its \(120\) suppliers. The audit finds that \(65\) suppliers hold a quality certification, \(48\) hold an environmental certification, and \(27\) hold both.

  1. How many suppliers hold at least one of the two certifications?
  2. How many suppliers hold no certification at all?
  3. How many suppliers hold the quality certification only (and not the environmental one)?
  4. A colleague simply adds \(65 + 48 = 113\) and reports “\(113\) certified suppliers”. Explain in one sentence what went wrong.

Let \(Q\) = suppliers with the quality certification and \(E\) = suppliers with the environmental one. We know \(|Q| = 65\), \(|E| = 48\), \(|Q \cap E| = 27\), and \(|U| = 120\).

  1. Inclusion-exclusion: adding \(|Q| + |E|\) counts the \(27\) double-holders twice, so subtract them once: \[|Q \cup E| = |Q| + |E| - |Q \cap E| = 65 + 48 - 27 = 86\] \(86\) suppliers hold at least one certification.

  2. “No certification” is the complement of the union: \[|(Q \cup E)^c| = |U| - |Q \cup E| = 120 - 86 = 34\]

  3. “Quality only” is the set difference \(Q \setminus E\). Of the \(65\) quality-certified suppliers, \(27\) also hold the environmental certificate: \[|Q \setminus E| = |Q| - |Q \cap E| = 65 - 27 = 38\]

    Sanity check: quality only (\(38\)) + environmental only (\(48 - 27 = 21\)) + both (\(27\)) gives \(38 + 21 + 27 = 86 = |Q \cup E|\), and \(86 + 34 = 120 = |U|\). Everything adds up.

  4. The \(27\) suppliers holding both certifications appear in both counts, so they were counted twice: the sum \(113\) overshoots the true value \(86\) by exactly \(|Q \cap E| = 27\). That double-count is precisely what the “\(-\,|Q \cap E|\)” in the inclusion-exclusion rule repairs.

Problem 5: Cartesian Products and Counting Routes

A carrier serves the hubs \(H = \{\text{Hamburg}, \text{Rotterdam}, \text{Antwerp}\}\) with departures on the days \(D = \{\text{Mon}, \text{Thu}\}\). Every combination of hub and day is one departure slot, an ordered pair \((\text{hub}, \text{day})\).

  1. Write down the set \(H \times D\) by listing all its elements.
  2. Compute \(|H \times D|\) using the counting rule. Does it match your list?
  3. Is \((\text{Mon}, \text{Hamburg}) \in H \times D\)? Justify your answer.
  4. The carrier expands to \(4\) hubs and \(5\) departure days. How many departure slots are there now? And conversely: a competitor’s schedule contains \(24\) slots using \(4\) hubs: on how many days does it operate?

  1. Pair every hub with every day, first entry from \(H\), second from \(D\): \[H \times D = \{(\text{Hamburg}, \text{Mon}), (\text{Hamburg}, \text{Thu}), (\text{Rotterdam}, \text{Mon}),\] \[(\text{Rotterdam}, \text{Thu}), (\text{Antwerp}, \text{Mon}), (\text{Antwerp}, \text{Thu})\}\]

  2. Each of the \(3\) hubs combines with each of the \(2\) days: \[|H \times D| = |H| \cdot |D| = 3 \cdot 2 = 6\] The list in a) has exactly \(6\) pairs. ✓

  3. No. The elements of \(H \times D\) are ordered pairs with the first entry from \(H\) and the second from \(D\). In \((\text{Mon}, \text{Hamburg})\) the entries are swapped: this pair belongs to \(D \times H\), a different set. For ordered pairs, \((a, b) \neq (b, a)\) unless \(a = b\).

  4. Expansion: \(4 \cdot 5 = 20\) departure slots.

    Competitor: the counting rule in reverse: from \(24 = 4 \cdot |D'|\) we get \(|D'| = 24 / 4 = 6\) days.

Problem 6: Grouping Matters, Three Sets

Let \(A = \{1, 2, 3, 4\}\), \(B = \{3, 4, 5\}\) and \(C = \{4, 5, 6\}\). A colleague claims: “\(A \cap B \cup C\) is unambiguous: parentheses are just decoration.” Test that claim.

  1. Compute \(A \cap (B \cup C)\): first the union, then the intersection.
  2. Compute \((A \cap B) \cup C\): first the intersection, then the union.
  3. Compare the two results. What does this tell you about the colleague’s claim?
  4. Now compute \((A \cap B) \cup (A \cap C)\) and compare with a). Which general law does this illustrate?

  1. Step 1 - Inner operation first: \(B \cup C = \{3, 4, 5, 6\}\).

    Step 2 - Then intersect with \(A\). Keep the elements of \(A\) that also lie in \(\{3, 4, 5, 6\}\): \[A \cap (B \cup C) = \{3, 4\}\]

  2. Step 1 - Inner operation first: \(A \cap B = \{3, 4\}\).

    Step 2 - Then unite with \(C\). The union dumps in all of \(C\), whether or not its elements belong to \(A\): \[(A \cap B) \cup C = \{3, 4\} \cup \{4, 5, 6\} = \{3, 4, 5, 6\}\]

  3. The results differ: \(\{3, 4\} \neq \{3, 4, 5, 6\}\). The elements \(5\) and \(6\) are not in \(A\), yet they enter the second result through the final “\(\cup\, C\)”. So the claim is false: when \(\cup\) and \(\cap\) mix, the grouping changes the set: “\(A \cap B \cup C\)” without parentheses is ambiguous, and you must write the parentheses.

  4. \(A \cap C = \{4\}\), so \[(A \cap B) \cup (A \cap C) = \{3, 4\} \cup \{4\} = \{3, 4\}\] which is the same result as in a). This is the distributive law \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\): intersection distributes over union, just like \(a \cdot (b + c) = a \cdot b + a \cdot c\) for numbers. Regrouping is fine when a law licenses it: the error in b) was dropping the second “\(\cap\, A\)”, not regrouping as such.

Problem 7: Complements Reverse Inclusion

An online shop tracks its customer base \(U = \{1, 2, 3, 4, 5, 6, 7, 8\}\) (customer IDs). The express-delivery customers are \(A = \{2, 3\}\) and the premium customers are \(B = \{2, 3, 5, 7\}\): every express customer is premium, i.e. \(A \subseteq B\).

  1. Compute \(A^c\) and \(B^c\). Then check both directions: is \(B^c \subseteq A^c\)? Is \(A^c \subseteq B^c\)?
  2. Explain why \(A \subseteq B \Rightarrow B^c \subseteq A^c\) holds for all sets \(A, B\), not just this example. (Hint: take an arbitrary \(x \in B^c\) and argue that \(x \in A^c\).)
  3. A colleague claims the direction is preserved instead: “\(A \subseteq B \Rightarrow A^c \subseteq B^c\).” Disprove this with a concrete counterexample.

  1. Complements with respect to \(U = \{1, \dots, 8\}\): \[A^c = \{1, 4, 5, 6, 7, 8\} \quad \text{(non-express)} \qquad B^c = \{1, 4, 6, 8\} \quad \text{(non-premium)}\]

    • Is \(B^c \subseteq A^c\)? Check every element of \(B^c\): \(1, 4, 6, 8\) all appear in \(A^c\). Yes. ✓
    • Is \(A^c \subseteq B^c\)? No: \(5 \in A^c\) but \(5 \notin B^c\): customer \(5\) is not express, yet premium. The inclusion reverses under complement; it does not stay put.

  2. General argument. Assume \(A \subseteq B\) and take any \(x \in B^c\), i.e. \(x \notin B\). Could \(x\) be in \(A\)? No. If \(x \in A\), then \(x \in B\) because \(A \subseteq B\), contradicting \(x \notin B\). Hence \(x \notin A\), i.e. \(x \in A^c\). Since \(x\) was an arbitrary element of \(B^c\), we conclude \(B^c \subseteq A^c\).

    This is Session 1’s contrapositive in set clothing: “\(A \subseteq B\)” says \(x \in A \Rightarrow x \in B\), and its contrapositive is \(x \notin B \Rightarrow x \notin A\), which says exactly \(B^c \subseteq A^c\). Just as with implications, “flip and negate” preserves the meaning.

    In business terms: since every express customer is premium, everyone who is not premium is certainly not express.

  3. The sets from a) already do the job: \(A = \{2, 3\} \subseteq B = \{2, 3, 5, 7\}\), but \[A^c = \{1, 4, 5, 6, 7, 8\} \not\subseteq \{1, 4, 6, 8\} = B^c,\] witnessed by \(5 \in A^c\) with \(5 \notin B^c\) (customer \(7\) works as a witness too). One counterexample settles it: the claim is false.

WarningCommon Mistake

Keeping the direction, \(A \subseteq B \Rightarrow A^c \subseteq B^c\), is the set version of the inverse error from Session 1 (\(p \Rightarrow q\) does not give \(\neg p \Rightarrow \neg q\)). Complement means negation, so the inclusion must flip: the smaller set has the bigger complement.

Problem 8: Power Sets and Product Bundles

A category manager can bundle any selection of the products \(S = \{P, Q, R\}\) into a promotion.

  1. List all elements of the power set \(\mathcal{P}(S)\) and confirm that their number matches the formula \(|\mathcal{P}(S)| = 2^{|S|}\).
  2. How many of these subsets contain the flagship product \(P\)? List them. Can you find the count without listing?
  3. How many bundles contain at least one product?
  4. Next quarter the assortment grows to \(5\) products, and marketing requires every promotion to bundle at least two of them. How many admissible bundles are there?

  1. Go through the subsets by size. This systematic order guarantees you miss none: \[\mathcal{P}(S) = \bigl\{\, \emptyset, \; \{P\}, \{Q\}, \{R\}, \; \{P, Q\}, \{P, R\}, \{Q, R\}, \; \{P, Q, R\} \,\bigr\}\] That is \(1 + 3 + 3 + 1 = 8\) subsets, and indeed \(2^{|S|} = 2^3 = 8\). ✓ Note that the elements of \(\mathcal{P}(S)\) are themselves sets: \(\{P\} \in \mathcal{P}(S)\), but \(P \notin \mathcal{P}(S)\).

  2. The subsets containing \(P\) are \[\{P\}, \quad \{P, Q\}, \quad \{P, R\}, \quad \{P, Q, R\}\] There are \(4\) of them. Without listing: fix \(P\) as “in”; the remaining elements \(Q\) and \(R\) are still free (in or out), giving \(2^2 = 4\) subsets. In general, exactly half of all subsets contain any fixed element.

  3. “At least one product” excludes only the empty bundle: \[|\mathcal{P}(S)| - 1 = 8 - 1 = 7\]

  4. Step 1 - Count all selections. With \(5\) products there are \(2^5 = 32\) subsets.

    Step 2 - Remove the too-small ones. Not admissible are the empty set (\(1\) subset) and the single-product bundles (\(5\) subsets, one per product): \[2^5 - 1 - 5 = 32 - 6 = 26\]

    There are \(26\) admissible bundles. Counting “all minus the forbidden few” is usually far easier than listing the admissible selections directly. With \(32\) subsets, listing would already be painful.