Power Set

Context: FIT1058_MOC · the set of all subsets of a set · size $2^n$ · refined by size via the Binomial Coefficient

Quick Revision

• 🎯 Objective: $\mathcal{P}(B)$ = all subsets of $B$ ➔ including $\varnothing$ and $B$.
• 📦 Core Components: $|\mathcal{P}(B)|=2^{|B|}$ ➔ binary-choice argument ➔ ${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$.
• ⚡ Key Constraint: exponential blow-up — $|B|=20$ gives over a million subsets.

📝 Core

1. The Power Set (All Subsets)

• Definition ➔ $\mathcal{P}(B)=\{A:A\subseteq B\}$ — its elements are themselves sets.
• Cardinality ➔ $|\mathcal{P}(B)|=2^{|B|}$ (exponential).
• Edge case ➔ $\mathcal{P}(\varnothing )=\{\varnothing \}$, size $2^0=1$.

2. Why $2^n$ (Binary Choice)

• Per element ➔ include or exclude, $2$ independent options.
• Product rule ➔ $\underset{n}{\underbrace{2\times \cdots \times 2}}=2^n$ subsets.

3. Maximum vs Maximal

• Maximum ➔ largest size of any qualifying subset (global).
• Maximal ➔ cannot be enlarged while keeping the property (local).
• Relation ➔ maximum ⟹ maximal, not conversely (dually minimum/minimal).

Key identities:

$|\mathcal{P}(B)|=2^n,{\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$ $\mathcal{P}(\{a,b\})=\{\varnothing ,\{a\},\{b\},\{a,b\}\}$

⚖️ Core Decision Matrix

Notion	Meaning	Example
maximum	largest size anywhere	maximum clique
maximal	can’t be extended	maximal clique
minimum	smallest size	—
minimal	can’t be shrunk	—

When It Flips: subsets split by size — $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ per layer, summing to $2^n$ (Binomial Coefficient). Contrast the Cartesian Product: its size $|A||B|$ multiplies, whereas the power set's $2^{|B|}$ is exponential.

📊 Exam Execution Trace

Manual Execution Trace

$\mathcal{P}(\{a,b,c\})$ by size:

Step / State	Size $k$	Subsets	$\left(\genfrac{}{}{0ex}{}{3}{k}\right)$
0 (Init)	—	—	—
1	0	$\varnothing$	1
2	1	$\{a\},\{b\},\{c\}$	3
3	2	$\{a,b\},\{a,c\},\{b,c\}$	3
4	3	$\{a,b,c\}$	1

⚠️ Common Mistakes

• 💡 Elements of $\mathcal{P}(B)$ are sets ➔ $\varnothing$ and $B$ are members; and enumerating $\mathcal{P}(B)$ is infeasible for large $B$ (over $10^6$ subsets at $|B|=20$).

🧠 Active Recall

Prove that a set with $n$ elements has exactly $2^n$ subsets.

• Hint: Independent binary choice.

Answer

• Short answer: Each element is independently “in” or “out” ⟹ $2^n$ subsets by the product rule.
• Why: Edge check ➔ $\varnothing$ gives $2^0=1$, $\mathcal{P}(\varnothing )=\{\varnothing \}$.

Distinguish a maximal subset from a maximum subset (clique example).

• Hint: Local vs global.

Answer

• Short answer: Maximal = can’t be enlarged; maximum = largest anywhere.
• Why: Maximum ⟹ maximal ➔ a maximal clique may be far smaller than the maximum clique.

How do the binomial coefficients relate to the power-set size?

• Hint: Layer by size.

Answer

• Short answer: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ subsets of each size $k$; disjoint layers cover $\mathcal{P}(B)$.
• Why: Sum ➔ ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$.