Day 36 — Set operations

Day 36 — Set operations

Stage IV · concept day
Goal: Master union, intersection, difference, symmetric difference, and complement; reason with Venn diagrams carefully; prove set identities; define the power set; prove \(|\mathcal{P}(S)|=2^{|S|}\) for finite \(S\) by induction or bitstring bijection.

Why this matters

Boolean combinations of sets are boolean combinations of membership predicates—the same algebra as Days 24–25 with \(\in\) as the atom. Power sets appear in configuration spaces, subset DP, and “all subsets of permissions.” Counting \(2^n\) subsets is a foundational counting fact.

Theory

Definitions (relative to elements)

Fix sets \(A,B\) (and universe \(U\) when complements appear).

\[ \begin{align*} A \cup B &= \{ x : x\in A \lor x\in B \},\\ A \cap B &= \{ x : x\in A \land x\in B \},\\ A \setminus B &= \{ x : x\in A \land x\notin B \},\\ A \triangle B &= (A\setminus B)\cup(B\setminus A) = (A\cup B)\setminus(A\cap B),\\ A^c &= U\setminus A = \{ x\in U : x\notin A \}. \end{align*} \]

\(A\) and \(B\) are disjoint when \(A\cap B = \emptyset\).

Venn reasoning

Diagrams guide intuition for \(2\)–\(3\) sets. They do not replace element-chase proofs for identities you must justify. For \(n\) sets, \(2^n\) regions—same explosion as truth tables.

Algebra of sets (selected identities)

\[ \begin{align*} A\cup B &= B\cup A, & A\cap B &= B\cap A,\\ (A\cup B)\cup C &= A\cup(B\cup C), & (A\cap B)\cap C &= A\cap(B\cap C),\\ A\cup(B\cap C) &= (A\cup B)\cap(A\cup C),\\ A\cap(B\cup C) &= (A\cap B)\cup(A\cap C),\\ A\cup\emptyset &= A, & A\cap\emptyset &= \emptyset,\\ A\cup U &= U, & A\cap U &= A,\\ A\cup A &= A, & A\cap A &= A,\\ A\cup A^c &= U, & A\cap A^c &= \emptyset,\\ (A^c)^c &= A,\\ (A\cup B)^c &= A^c \cap B^c, & (A\cap B)^c &= A^c \cup B^c && \text{(De Morgan)}. \end{align*} \]

Absorption: \(A\cup(A\cap B)=A\), \(A\cap(A\cup B)=A\).

These mirror Boolean algebra with \(\cup\leftrightarrow\vee\), \(\cap\leftrightarrow\wedge\), \(^c\leftrightarrow\neg\).

Proving identities

Element chase: \(x\in\) LHS iff (logic) iff \(x\in\) RHS.
Double inclusion: LHS \(\subseteq\) RHS and converse.
Algebraic rewrite using known identities (name them).
Characteristic vectors / indicator functions: \(1_{A\cup B} = \max(1_A,1_B)\) or boolean or, etc.

Power set

\[\mathcal{P}(S) = \{ A : A \subseteq S \}\]
the set of all subsets of \(S\). Always \(\emptyset \in \mathcal{P}(S)\) and \(S \in \mathcal{P}(S)\).

Cardinality of the power set (finite)

Theorem. If \(|S|=n < \infty\), then \(|\mathcal{P}(S)| = 2^n\).

Proof 1 (bitstrings). Fix enumeration \(S=\{s_1,\ldots,s_n\}\). Map \(A\subseteq S\) to \((b_1,\ldots,b_n)\in\{0,1\}^n\) with \(b_i=1\) iff \(s_i\in A\). This is a bijection. \(|\{0,1\}^n|=2^n\). \(\square\)

Proof 2 (induction on \(n\)).
\(n=0\): \(\mathcal{P}(\emptyset)=\{\emptyset\}\), size \(1=2^0\).
Assume true for \(|S|=k\). Let \(|T|=k+1\), pick \(a\in T\), \(S=T\setminus\{a\}\).
Subsets of \(T\) partition into those not containing \(a\) (\(\mathcal{P}(S)\)) and those containing \(a\) (\(\{ B\cup\{a\} : B\subseteq S \}\)).
Sizes \(2^k + 2^k = 2^{k+1}\). \(\square\)

Disjoint union (awareness)

Sometimes \(A \sqcup B\) means disjoint union (tagged): copy sets to force disjointness. Distinct from \(A\cup B\) when they overlap. Day 37 contrasts with products.

Inclusion indicators

\(x\in A\cap B\) iff both memberships; truth table of \(\wedge\). Set identities \(\leftrightarrow\) propositional tautologies about membership.

Worked examples

Example 1 — Compute

\(A=\{1,2,3\}\), \(B=\{3,4\}\):
\(A\cup B=\{1,2,3,4\}\), \(A\cap B=\{3\}\), \(A\setminus B=\{1,2\}\), \(A\triangle B=\{1,2,4\}\).

Example 2 — De Morgan proof sketch

\(x\in (A\cup B)^c \Leftrightarrow x\notin A\cup B \Leftrightarrow x\notin A \wedge x\notin B \Leftrightarrow x\in A^c \cap B^c\).

Example 3 — Distributivity element chase

\(x\in A\cap(B\cup C) \Leftrightarrow x\in A \wedge (x\in B\vee x\in C) \Leftrightarrow \cdots \Leftrightarrow x\in (A\cap B)\cup(A\cap C)\).

Example 4 — Symmetric difference

\(A\triangle A = \emptyset\), \(A\triangle\emptyset = A\), \(A\triangle B = B\triangle A\).

Example 5 — Power set small

\(S=\{1,2\}\): \(\mathcal{P}(S)=\{\emptyset,\{1\},\{2\},\{1,2\}\}\), size \(4=2^2\).

Example 6 — Bitstring

\(S=\{a,b,c\}\), subset \(\{a,c\}\) ↔︎ \(101\).

Example 7 — Complement depends on \(U\)

If \(U=\mathbb{Z}\) and \(A=\) evens, \(A^c=\) odds. If \(U=\) evens, \(A^c=\emptyset\) when \(A=U\).

Example 8 — Identity

\(A\setminus B = A \cap B^c\) (prove by element chase).

Example 9 — Counting

\(|A\cup B| = |A|+|B|-|A\cap B|\) for finite sets (inclusion-exclusion lite; Stage V deepens).

Example 10 — Partition via characteristic

For fixed \(A\), universe splits into \(A\) and \(A^c\).

Example 11 — Prove \(A\subseteq B \Leftrightarrow A\cup B = B\)

⇒: if \(A\subseteq B\), \(A\cup B\subseteq B\cup B=B\), and \(B\subseteq A\cup B\).
⇐: if \(A\cup B=B\) then \(A\subseteq A\cup B=B\).

Example 12 — \(\mathcal{P}\) monotonic

If \(A\subseteq B\) then \(\mathcal{P}(A)\subseteq\mathcal{P}(B)\).

Example 13 — Not true

\(\mathcal{P}(A\cup B) = \mathcal{P}(A)\cup\mathcal{P}(B)\) is false generally. Counterexample: \(A=\{1\},B=\{2\}\), \(\{1,2\}\) in left not in right.

Example 14 — Config space

\(n\) independent boolean flags: \(2^n\) configurations \(=|\mathcal{P}([n])|\) if each subset is “enabled set.”

Exercises

1. Compute all of \(\cup,\cap,\setminus,\triangle\) for \(A=\{0,1,2\}\), \(B=\{1,2,3\}\).
   
2. Prove \(A\setminus B = A \cap B^c\).
   
3. Prove De Morgan \((A\cap B)^c = A^c \cup B^c\).
   
4. Prove distributivity \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\).
   
5. Prove \(A\subseteq B \Leftrightarrow A\cap B = A\).
   
6. Prove \(A\triangle B = (A\cup B)\setminus(A\cap B)\).
   
7. List \(\mathcal{P}(\{1\})\) and \(\mathcal{P}(\{\emptyset\})\).
   
8. Prove by induction \(|\mathcal{P}(S)|=2^{|S|}\) for finite \(S\).
   
9. Give the bitstring bijection proof in your own words.
   
10. Counterexample: \(\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap\mathcal{P}(B)\)—is this true? Prove or disprove.
    
11. True or false: \(\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)\).
    
12. Prove \((A^c)^c=A\).
    
13. If \(A,B\) finite, prove \(|A\setminus B| = |A|-|A\cap B|\).
    
14. Show \(A\) and \(A^c\) disjoint and union \(U\).
    
15. Simplify \((A\cup B)\cap(A\cup B^c)\) .
    
16. Prove absorption \(A\cup(A\cap B)=A\).
    
17. Venn: shade \((A\cap B)\setminus C\); describe in words.
    
18. How many subsets of an \(n\)-set contain a fixed element \(a\)?
    
19. How many subsets have even cardinality? (Binomial; state \(\sum \binom{n}{2k}=2^{n-1}\) awareness.)
    
20. Prove \(A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)\).
    
21. CS: express active users as \(Registered \setminus Banned\).
    
22. Prove \(A\triangle B = \emptyset \Leftrightarrow A=B\).
    
23. If \(|\mathcal{P}(S)|=32\), what is \(|S|\)?
    
24. Show there is no bijection between \(S\) and \(\mathcal{P}(S)\) for any set \(S\) (Cantor; outline diagonal)—preview Day 43.
    
25. Prove \(A\cap(B\setminus A)=\emptyset\).

CS connection

• SQL UNION, INTERSECT, EXCEPT ≈ \(\cup,\cap,\setminus\) (bag semantics caveats).
  
• Permission sets: grant \(= A\cup B\), revoke difference.
  
• Feature flags power set of options.
  
• Bitsets implement subsets of a fixed universe; OR/AND/NOT = \(\cup/\cap/^c\).
  
• Subset sum / DP over \(\mathcal{P}([n])\) for small \(n\).
  
• De Morgan in firewall rules: deny all except…

Common pitfalls

Pitfall	What to do instead
Complement without universe	Fix \(U\)
Trusting Venn alone	Element chase for proofs
\(\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)\)	False; see counterexample
Counting \(\mathcal{P}\) as \(n\)	\(2^n\)
Confusing \(\setminus\) with \(-\) on numbers	Set difference
Symmetric difference as intersection	It is XOR of membership

Checkpoint

• Define \(\cup\cap\setminus\triangle\) and complement
  
• Prove one De Morgan and one distributive law
  
• Define \(\mathcal{P}(S)\) and list a small one
  
• Prove \(|\mathcal{P}(S)|=2^n\) two ways (sketch both)
  
• Give counterexample for a false power-set identity
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — indicator functions

For \(A\subseteq U\), the indicator \(1_A: U\to\{0,1\}\) has \(1_A(x)=1\) iff \(x\in A\). Then:

\[ \begin{align*} 1_{A\cap B} &= 1_A \cdot 1_B,\\ 1_{A\cup B} &= 1_A + 1_B - 1_A 1_B,\\ 1_{A^c} &= 1 - 1_A,\\ 1_{A\triangle B} &= 1_A + 1_B \bmod 2. \end{align*} \]

Set algebra ↔︎ arithmetic on indicators ↔︎ boolean algebra on membership bits. Bitsets in programming are indicators of subsets of a fixed universe.

Counting subsets with structure

• Subsets containing fixed \(a\): \(2^{n-1}\).
  
• Subsets of size \(k\): \(\binom{n}{k}\) (Stage V).
  
• Even-sized subsets: \(2^{n-1}\) for \(n\ge 1\).

Power set functoriality

If \(f: A\to B\), define \(\mathcal{P}(f): \mathcal{P}(A)\to\mathcal{P}(B)\) by \(S\mapsto f(S)=\{f(x):x\in S\}\) (direct image). Not to be confused with preimage \(f^{-1}(T)\).

More worked examples

Example 15 — Simplify
\((A\cup B)\cap(A\cup B^c)\cap(A^c\cup B)\) stepwise.

Example 16 — Symmetric difference associative
\(A\triangle(B\triangle C)=(A\triangle B)\triangle C\) (indicator mod 2).

Example 17 — Power set size
\(|\mathcal{P}(\mathcal{P}(\{1\}))|=|\mathcal{P}(\{\emptyset,\{1\}\})|=4\).

Example 18 — Disjointify
\(A\setminus B\) and \(A\cap B\) partition \(A\).

Additional exercises

26. Prove \(A\triangle B = A^c\triangle B^c\).
    
27. Prove by induction \(|\mathcal{P}(S)|=2^{|S|}\) writing the partition step carefully.
    
28. Show \(\mathcal{P}(A)\cap\mathcal{P}(B)=\mathcal{P}(A\cap B)\).
    
29. Disprove \(\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)\).
    
30. Bitset: express \(A\subseteq B\) as a bitwise condition on indicators.

Extended practice workshop

Compute on \(A=\{1,2,3\}\), \(B=\{2,3,4\}\), \(U=\{1,2,3,4,5\}\)

1. \(A\cup B\), \(A\cap B\), \(A\setminus B\), \(B\setminus A\), \(A\triangle B\)
   
2. \(A^c\), \(B^c\)
   
3. \((A\cup B)^c\) and \(A^c\cap B^c\)—match
   
4. \((A\cap B)^c\) and \(A^c\cup B^c\)—match

Identity proofs (element chase)

5. Distributivity \(A\cap(B\cup C)\)
   
6. De Morgan one form
   
7. \(A\setminus B=A\cap B^c\)
   
8. \(A\subseteq B\Leftrightarrow A\cup B=B\)
   
9. \(A\subseteq B\Leftrightarrow A\cap B=A\)
   
10. \(A\triangle B=\emptyset\Leftrightarrow A=B\)

Power set

11. List \(\mathcal{P}(\{a,b\})\)
    
12. List \(\mathcal{P}(\{\emptyset\})\)
    
13. Induction proof \(|\mathcal{P}|=2^n\)
    
14. Bitstring proof sketch
    
15. Counterexample \(\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)\)
    
16. Prove \(\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap\mathcal{P}(B)\)

Counting

17. Subsets of \(n\)-set containing a fixed element
    
18. \(|A\cup B|\) given sizes and intersection
    
19. \(|\mathcal{P}(\mathcal{P}(\emptyset))|\)

CS

20. Bitwise AND/OR/NOT as \(\cap/\cup/^c\) on bitsets.
    
21. Feature flags as elements of \(\mathcal{P}(F)\).
    
22. SQL EXCEPT as \(\setminus\).

Indicator cheat sheet

\(1_{A\cap B}=1_A 1_B\), \(1_{A^c}=1-1_A\), \(1_{A\triangle B}\equiv 1_A+1_B\pmod 2\).

Synthesis

Set operations are the boolean algebra of collections: \(\cup\) like \(\vee\), \(\cap\) like \(\wedge\), complement like \(\neg\). Element-chase proofs of identities are the same muscle as truth-table or algebraic boolean proofs, rephrased with \(\in\). Power sets shift attention from elements of \(S\) to subsets of \(S\)—critical for relations (\(\mathcal{P}(A\times B)\)) and state spaces.

Proof patterns for identities

1. Element chase both sides of \(X=Y\) via double inclusion.
   
2. Indicator algebra on a fixed universe: rewrite \(1_X\) and compare.
   
3. Known laws (De Morgan, distributivity) in a chain with names—like Day 24.

More worked examples

Example — Distributivity chase.
\(x\in A\cap(B\cup C)\) iff \(x\in A\) and (\(x\in B\) or \(x\in C\)) iff (\(x\in A\cap B\) or \(x\in A\cap C\)) iff \(x\in (A\cap B)\cup(A\cap C)\).

Example — Set difference as intersection.
\(A\setminus B = A\cap B^c\) by unfolding: \(x\in A\) and \(x\notin B\).

Example — Subset via union.
\(A\subseteq B \Leftrightarrow A\cup B=B\): if subset, union adds nothing; if union equals \(B\), every \(x\in A\) is in the union hence in \(B\).

Example — Power set size.
For \(S=\{1,2,3\}\), list \(8\) subsets. Inductive idea: subsets of \(S\cup\{a\}\) split into those without \(a\) (\(\mathcal{P}(S)\)) and those with \(a\) (same count).

Example — Counterexample \(\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)\).
\(A=\{1\}\), \(B=\{2\}\): \(\{1,2\}\in\mathcal{P}(A\cup B)\) but \(\{1,2\}\) is neither a subset of \(A\) nor of \(B\), so not in the union of power sets.

Extra exercises (synthesis)

31. Prove \((A\setminus B)\setminus C = A\setminus(B\cup C)\).
    
32. Prove \(A\triangle B = (A\cup B)\setminus(A\cap B)\).
    
33. Show \(A\subseteq B \Leftrightarrow B^c \subseteq A^c\).
    
34. Compute \(|\mathcal{P}(\mathcal{P}(\{1\}))|\).
    
35. If \(|A|=n\), how many subsets have even cardinality? (Binomials preview—or compute for \(n\le 4\) and conjecture.)
    
36. Bitset: explain \(A\cap B\) as bitwise AND of characteristic vectors of length \(|U|\).

Identity priority list (memorize proofs of)

Identity	Why first
De Morgan (both)	Complements in specs
\(A\setminus B=A\cap B^c\)	Rewrite tool
Distributivity one direction	Case reasoning
\(A\subseteq B\Leftrightarrow A\cap B=A\)	Spec refinement
\(|\mathcal{P}(S)|=2^{|S|}\)	Counting backbone

Venn diagrams are discovery tools; element chase is the proof. Indicators are a power-user shortcut once membership reasoning is solid.

Tomorrow

Day 37 — Products & tuples. \(A\times B\); \(n\)-tuples; \(|A\times B|=|A||B|\); relations as subsets of products (preview); disjoint union vs product.