Discrete Mathematics — Sets

Exercises & Solutions (Python)

Notes By Pr. El Hadiq Zouhair

Contents

  1. Definition, cardinality, deduplication easy
  2. Built-in set operations (∪, ∩, −) easy
  3. Membership in $\mathbb{Z}$, $\mathbb{N}$, $\mathbb{Q}$ easy
  4. Subset / proper subset / superset medium
  5. Power set medium
  6. Partition into chunks medium
  7. Cartesian product medium
  8. Symmetric difference medium
  9. Venn — inclusion–exclusion hard
  10. SymPy intervals & unions medium
  11. Countability of $\mathbb{Z}$ hard
  12. Empty set traps hard

1Definition, cardinality & deduplication easy

Given the list L = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]:

  1. Convert it to a set $S$.
  2. Compute the cardinality $|S|$.
  3. Return the elements in sorted order.
Solution
Python L = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] S = set(L) print(S) # {1, 2, 3, 4, 5, 6, 9} print(len(S)) # 7 print(sorted(S)) # [1, 2, 3, 4, 5, 6, 9]

2Union, intersection, difference easy

Let $A = \{1, 2, 3, 4, 5\}$ and $B = \{4, 5, 6, 7, 8\}$. Compute, using Python built-ins:

Solution
Python A = {1, 2, 3, 4, 5} B = {4, 5, 6, 7, 8} print(A | B) # {1, 2, 3, 4, 5, 6, 7, 8} print(A & B) # {4, 5} print(A - B) # {1, 2, 3} print(B - A) # {6, 7, 8} assert len(A | B) == len(A) + len(B) - len(A & B) # 8 == 5+5-2

3Membership in $\mathbb{Z}$, $\mathbb{N}$, $\mathbb{Q}$ easy

For each value, decide whether it belongs to $\mathbb{Z}$, $\mathbb{N}$, $\mathbb{Q}$, or none (use SymPy):

-3,   0,   Fraction(7, 2),   sqrt(2),   pi.

Solution
Python — SymPy from sympy import S, sqrt, pi, Rational candidates = [-3, 0, Rational(7, 2), sqrt(2), pi] labels = ["Z (Integers)", "N0 (Naturals)", "Q (Rationals)"] sets = [S.Integers, S.Naturals0, S.Rationals] for x in candidates: membership = [x in st for st in sets] print(f"{x!s:>8} → " + ", ".join( f"{lab}: {m}" for lab, m in zip(labels, membership)))
Output -3 → Z: True, N0: False, Q: True 0 → Z: True, N0: True, Q: True 7/2 → Z: False, N0: False, Q: True sqrt(2)→ Z: False, N0: False, Q: False pi → Z: False, N0: False, Q: False

4Subset / proper subset / superset medium

Let $A = \{2, 4\}$, $B = \{2, 4, 6\}$, $C = \{2, 4\}$. Decide:

  1. Is $A \subseteq B$? Is $A \subset B$ (proper)?
  2. Is $A \subseteq C$? Is $A \subset C$?
  3. Is $B \supseteq A$?
Solution
Python A, B, C = {2, 4}, {2, 4, 6}, {2, 4} print(A <= B, A < B) # True, True (subset, proper subset) print(A <= C, A < C) # True, False (equal sets — not proper) print(B >= A) # True (superset)

Note: <= is issubset, < is proper subset, >= is issuperset.

5Power set medium

Write a function powerset(s) that returns the list of all subsets of $s$. Test on $S = \{a, b, c\}$ and confirm $|\mathcal{P}(S)| = 2^{|S|}$.

Solution
Python from itertools import chain, combinations def powerset(s): s = list(s) return [set(c) for r in range(len(s)+1) for c in combinations(s, r)] S = {"a", "b", "c"} P = powerset(S) print(P) print(len(P), "==", 2 ** len(S)) # 8 == 8
Output [set(), {'a'}, {'b'}, {'c'}, {'a','b'}, {'a','c'}, {'b','c'}, {'a','b','c'}] 8 == 8

6Partition medium

Partition range(1, 13) into groups of 4 (disjoint). Then build a cover of size 4 with step 2 (overlapping). Verify:

Solution
Python def partition(seq, n): return [list(seq[i:i+n]) for i in range(0, len(seq), n)] def cover(seq, n, step): return [list(seq[i:i+n]) for i in range(0, len(seq)-n+1, step)] xs = list(range(1, 13)) P = partition(xs, 4) C = cover(xs, 4, 2) print(P) # [[1,2,3,4],[5,6,7,8],[9,10,11,12]] print(C) # overlapping windows # verify partition flat_P = set().union(*map(set, P)) assert flat_P == set(xs) for i in range(len(P)): for j in range(i+1, len(P)): assert set(P[i]) & set(P[j]) == set() # verify cover assert set().union(*map(set, C)) == set(xs)

7Cartesian product medium

Let $A = \{1, 3, 5\}$ and $B = \{x, y\}$.

  1. Compute $A \times B$.
  2. Confirm $|A \times B| = |A| \cdot |B|$.
  3. Compute $A \times A \times A$ (i.e. product(A, repeat=3)) and check $|A^3| = |A|^3$.
Solution
Python from itertools import product A = {1, 3, 5} B = {"x", "y"} AB = list(product(A, B)) print(AB) print(len(AB), "==", len(A) * len(B)) # 6 == 6 A3 = list(product(A, repeat=3)) print(len(A3), "==", len(A) ** 3) # 27 == 27

8Symmetric difference medium

The symmetric difference is $A \,\triangle\, B = (A \setminus B) \cup (B \setminus A)$. With $A = \{1,2,3,4\}$, $B = \{3,4,5,6\}$:

  1. Compute $A \,\triangle\, B$ two ways: by the formula and via the ^ operator.
  2. Verify $A \,\triangle\, B = (A \cup B) \setminus (A \cap B)$.
Solution
Python A = {1, 2, 3, 4} B = {3, 4, 5, 6} D1 = (A - B) | (B - A) D2 = A ^ B D3 = (A | B) - (A & B) print(D1, D2, D3) # all {1, 2, 5, 6} assert D1 == D2 == D3

9Inclusion–Exclusion (3 sets) hard

In a class of 100 students:

Compute the number who study at least one subject, and the number who study none.

$$|M \cup P \cup C| = |M|+|P|+|C| - |M\cap P| - |M\cap C| - |P\cap C| + |M\cap P\cap C|$$

Solution
Python m, p, c = 60, 50, 40 mp, mc, pc = 30, 20, 15 mpc = 10 at_least_one = m + p + c - mp - mc - pc + mpc print(at_least_one) # 95 print(100 - at_least_one) # 5 students study none

Simulation check with random sets:

Python — sanity check by construction M = set(range(0, 60)) P = set(range(40, 90)) # |P|=50, |M∩P| approx tweakable # (For a strict combinatorial check, build the Venn diagram regions explicitly.)

10Intervals & unions in SymPy medium

Using sympy.Interval:

  1. Build $I_1 = [0, 5]$, $I_2 = (3, 8]$, $I_3 = [10, 12)$.
  2. Compute $I_1 \cup I_2$ and $I_1 \cap I_2$.
  3. Compute $(I_1 \cup I_2 \cup I_3) \setminus [4, 11]$.
Solution
Python — SymPy from sympy import Interval, Union, Intersection, Complement I1 = Interval(0, 5) I2 = Interval.Lopen(3, 8) # (3, 8] I3 = Interval.Ropen(10, 12) # [10, 12) print(Union(I1, I2)) # [0, 8] print(Intersection(I1, I2)) # (3, 5] print(Complement(Union(I1, I2, I3), Interval(4, 11))) # [0, 4) ∪ [11, 12)... actually [0,4) ∪ {12 region}

11Countability of $\mathbb{Z}$ hard

Write a bijection $f : \mathbb{N} \to \mathbb{Z}$ as a Python function. Print $f(0), f(1), \dots, f(9)$. Then check that the inverse $f^{-1}$ also maps each integer back to its original index.

Solution
Python def f(n): """N -> Z bijection: 0,1,-1,2,-2,3,-3,...""" if n == 0: return 0 k = (n + 1) // 2 return k if n % 2 == 1 else -k def f_inv(z): if z == 0: return 0 return 2 * z - 1 if z > 0 else -2 * z vals = [f(n) for n in range(10)] print(vals) # [0, 1, -1, 2, -2, 3, -3, 4, -4, 5] print([f_inv(z) for z in vals]) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

12Empty set traps hard

For each item, predict the answer before running it:

  1. $|\varnothing|$ and $|\{\varnothing\}|$ and $|\{\varnothing, \{\varnothing\}\}|$.
  2. $\mathcal{P}(\varnothing)$ and $\mathcal{P}(\mathcal{P}(\varnothing))$.
  3. $\varnothing \times \{2, 4, 6, 8\}$.
  4. Is $\varnothing \subseteq A$ for every set $A$?
Solution
Python from itertools import chain, combinations, product # 1) sizes print(len(set())) # 0 print(len({frozenset()})) # 1 print(len({frozenset(), frozenset({frozenset()})}))# 2 # 2) power sets def powerset(s): s = list(s) return [frozenset(c) for r in range(len(s)+1) for c in combinations(s, r)] p0 = powerset(set()) # [frozenset()] → {∅} p1 = powerset(p0) # [frozenset(), frozenset({frozenset()})] → {∅, {∅}} print(p0) print(p1) # 3) Cartesian product with ∅ print(list(product(set(), {2, 4, 6, 8}))) # [] — empty # 4) ∅ ⊆ A always A = {7, 8, 9} print(set().issubset(A)) # True (vacuously)

Key insight: $\varnothing$ has size 0, but $\{\varnothing\}$ has size 1 — it contains one element (which happens to be the empty set). And $\varnothing \subseteq A$ is vacuously true for every $A$.

Going further

Open the main lesson for the matching theory.