Discrete Mathematics — Sets

Contents

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.

2Union, intersection, difference easy

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

• $A \cup B$, $A \cap B$, $A \setminus B$, $B \setminus A$.
• Verify that $|A \cup B| = |A| + |B| - |A \cap B|$.

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.

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$?

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|}$.

6Partition medium

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

• Disjoint partition → union equals the original set, intersection of any two parts is $\varnothing$.
• Cover → union still equals the set, but parts overlap.

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$.

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)$.

9Inclusion–Exclusion (3 sets) hard

In a class of 100 students:

• 60 study Math, 50 study Physics, 40 study CS.
• 30 study Math & Physics, 20 study Math & CS, 15 study Physics & CS.
• 10 study all three.

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|$$

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]$.

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.

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$?

Going further

• Re-do exercises 2, 5, 7 with sympy.FiniteSet instead of set.
• Implement a generator that lists subsets of $\mathbb{N}$ of cardinality $k$ in lexicographic order.
• Visualize Venn diagrams from exercise 9 with matplotlib_venn.venn3.
• Prove (in code, by exhaustive check) De Morgan's laws on small sets: $(A \cup B)^c = A^c \cap B^c$.

Open the main lesson for the matching theory.