1.2 Subsets, Power Sets & Set Membership Algebra

Back to Discrete Mathematics Notes

📚Module 01: Set Theory & CardinalityTopic 1.2: Subsets, Power Sets & Set Membership Algebra⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Operating System Directory Tree

Imagine inspecting a directory tree on a modern operating system:

1. The Direct Item (Element $\in$): A file report.pdf sitting inside folder Project/ is an element of that folder (report.pdf $\in$ Project/).
2. The Archive / Sub-Collection (Subset $\subseteq$): If you create a zip archive containing a subset of the files from Project/, that archive is a subset of Project/. Every file inside the archive is also inside Project/.
3. The Subdirectory Trap (Nested Sets): If Project/ contains a subdirectory named backup/, that subdirectory itself is an element of Project/. But the files inside backup/ are not loose in Project/! They cannot be referenced as direct files of Project/ without traversing the inner container first.
4. The Power Set: The power set is the collection of all possible zip archives you could ever create by picking any combination of files from Project/—from the empty archive containing nothing, up to the full archive containing everything!

💻 Bridging to Computer Science: Bitmask State Spaces & Access Control Matrices

In hardware design and software engineering, the power set represents the state space of an $n$-bit configuration register or the space of all possible cache line configurations. In database access control, permissions are evaluated over power sets: if an application defines $n$ user privileges (read, write, execute, admin), the security engine evaluates access across all $2^n$ possible permission combinations.

📑Table of Contents

• ⚖️ Equivalent Sets vs Equal Sets
  • 1. Equivalent Sets
  • 2. Equal Sets
• 📦 Subset Inclusion & Proper Subsets
  • Subsets Cardinality Formulas
  • Foundational Properties of Subsets
• 🔍 The Element vs Subset Disambiguation Matrix
  • The Diagnostic Test Case
  • The Classic Nested Trap: Sets with Nested Empty Elements
• ⚡ The Power Set & Combinatorial Cardinality
  • Concrete Expansion of the Power Set
• 🏗️ Iterated Power Sets & Recursive Towers
  • Iteration Trace and Cardinality Growth
• 🏛️ Fundamental Power Set Algebraic Theorems
• 🌍 Real-World Engineering Context
• 📝 Step-by-Step Worked Examples
  • Example 1: Disambiguating Nested Set Membership and Inclusion
  • Example 2: Cardinality of Iterated Power Sets
  • Example 3: Proof of Power Set Intersection Distributivity
• 🎯 Exam & Interview Pitfall Check

---

⚖️ Equivalent Sets vs Equal Sets

Before examining subsets, we must distinguish between sets that share the same magnitude and sets that share the same identity.

1. Equivalent Sets

Two sets $A$ and $B$ are equivalent (denoted $A \sim B$ or $A \approx B$) if and only if they possess identical cardinality:

📖Definition 1.5: Set Equivalencedefinition

$$A \sim B \iff |A| = |B|$$

For finite sets, equivalence means they have the exact same count of elements. For infinite sets, equivalence requires a 1-to-1 bijective mapping between them (e.g., $|\mathbb{N}| = |\mathbb{Z}| = \aleph_0$).

2. Equal Sets

Two sets $A$ and $B$ are equal if and only if every element of $A$ belongs to $B$, and every element of $B$ belongs to $A$:

📖Definition 1.6: Set Equalitydefinition

$$A = B \iff \forall x (x \in A \leftrightarrow x \in B) \iff (A \subseteq B \land B \subseteq A)$$

Equal Sets (A = B)          ==>  Always Equivalent (|A| = |B|)
Equivalent Sets (|A| = |B|)  ==>  NOT Necessarily Equal (Elements may differ)

Concrete Example:

• Let $A = \{1, 2, 3\}$ and $B = \{x, y, z\}$. Here $|A| = 3$ and $|B| = 3$. Hence, $A \sim B$ (equivalent), but $A \neq B$.
• Now let $C = \{3, 1, 2\}$. Here $A = C$ and $|A| = |C| = 3$. Equal sets are always equivalent.

---

📦 Subset Inclusion & Proper Subsets

A set $A$ is a subset of set $B$ (denoted $A \subseteq B$) if every element belonging to $A$ also belongs to $B$.

📖Definition 1.7: Subset Inclusion & Proper Subsetdefinition

$$A \subseteq B \iff \forall x (x \in A \implies x \in B)$$$$A \subset B \iff (A \subseteq B \land A \neq B)$$

Conversely, to prove that $A$ is not a subset of $B$ ($A \not\subseteq B$), we must find at least one witness element $x$ such that:

$$\exists x (x \in A \land x \notin B)$$

When $A \subseteq B$, we also say that $B$ is a superset of $A$ (denoted $B \supseteq A$).

Subsets Cardinality Formulas

📐Formula 1.1: Combinatorial Subset Counting Formulasformula

For any finite set $A$ with $|A| = n$ elements:

1. Total Number of Subsets: $$N_{\text{subsets}} = 2^n$$
2. Total Number of Proper Subsets: $$N_{\text{proper}} = 2^n - 1 \quad \text{(excluding the improper subset } A \text{ itself)}$$
3. Total Number of Non-Empty Proper Subsets: $$N_{\text{non-empty proper}} = 2^n - 2 \quad \text{(excluding } \emptyset \text{ and } A\text{)}$$

Foundational Properties of Subsets

• The Empty Set Invariant: $\emptyset \subseteq A$ for every set $A$.
  • Formal Proof via Vacuous Truth: The condition requires $\forall x (x \in \emptyset \implies x \in A)$. Because the empty set has no elements, the premise $x \in \emptyset$ is identically False for all $x$. Under formal logic, a conditional statement with a False antecedent is always True ($\mathbf{F} \to P \equiv \mathbf{T}$). Therefore, $\emptyset \subseteq A$ holds universally.
• Reflexivity: $A \subseteq A$ for every set $A$.
• Transitivity: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.
• Antisymmetry: If $A \subseteq B$ and $B \subseteq A$, then $A = B$.

---

🔍 The Element vs Subset Disambiguation Matrix

The boundary between element membership ($\in$) and subset containment ($\subseteq$) is one of the most vital distinctions in discrete mathematics.

Element Membership (∈) vs Subset Inclusion (⊆)

The fundamental syntactic and structural boundary in set theory

Membership

Element Membership (x ∈ A)

🎯

Dominant Architecture / DomainDirect Container Association

• •Relates an individual element x directly to a container set A.
• •x must appear explicitly as a top-level item inside the braces of A.
• •Strip away the outer braces of A: if x is directly listed, then x ∈ A.
• •Example: If A = {1, {2}}, then 1 ∈ A and {2} ∈ A, but 2 ∉ A.

"x ∈ A asks: 'Is x directly sitting on the shelf inside container A?'"

Inclusion

Subset Inclusion (X ⊆ A)

📦

Dominant Architecture / DomainSub-Collection Relationship

• •Relates one container set X to another container set A.
• •Every single element belonging to X must independently belong to A.
• •Take every item inside X: each item must satisfy item ∈ A.
• •Example: If A = {1, {2}}, then {1} ⊆ A and {{2}} ⊆ A, but {2} ⊈ A.

"X ⊆ A asks: 'Is every single item inside box X also sitting on the shelf inside A?'"

The Diagnostic Test Case

Consider the test set:

$$A = \{1, \; 2, \; \{3\}, \; \emptyset\}$$

Let us evaluate the exact truth value of 10 classic membership and inclusion statements:

Statement	Truth Value	Justification & Verification Rule
$1 \in A$	True	$1$ is an explicitly enumerated top-level member of $A$.
$\{1\} \in A$	False	The singleton $\{1\}$ is not an element of $A$; only the naked integer $1$ is.
$\{1\} \subseteq A$	True	The element inside $\{1\}$ is $1$, which satisfies $1 \in A$.
$3 \in A$	False	$3$ is encapsulated inside an inner set $\{3\}$; not a direct element of $A$.
$\{3\} \in A$	True	The object $\{3\}$ is explicitly listed as a member of $A$.
$\{3\} \subseteq A$	False	For $\{3\} \subseteq A$, $3$ must belong to $A$, but $3 \notin A$.
$\{\{3\}\} \subseteq A$	True	The element inside $\{\{3\}\}$ is $\{3\}$, and $\{3\} \in A$.
$\emptyset \in A$	True	$\emptyset$ is explicitly written as a member of $A$.
$\emptyset \subseteq A$	True	Universally true for every set (vacuous truth).
$\{\emptyset\} \subseteq A$	True	The element inside $\{\emptyset\}$ is $\emptyset$, and $\emptyset \in A$.

The Classic Nested Trap: Sets with Nested Empty Elements

Consider the classic trap set $A = \{\emptyset, \{\emptyset\}\}$:

• Cardinality: $|A| = 2$ (the two top-level elements are $\emptyset$ and $\{\emptyset\}$).
• Power Set: Contains $2^2 = 4$ subsets: $$\mathcal{P}(A) = \big\{ \emptyset, \; \{\emptyset\}, \; \{\{\emptyset\}\}, \; \{\emptyset, \{\emptyset\}\} \big\}$$

Proposition	Evaluation	Mental Model Rule
$\emptyset \in A$	True	$\emptyset$ is the first top-level element.
$\emptyset \subseteq A$	True	$\emptyset$ is a subset of every set.
$\{\emptyset\} \in A$	True	$\{\emptyset\}$ is the second top-level element.
$\{\emptyset\} \subseteq A$	True	Its member $\emptyset \in A$.
$\{\{\emptyset\}\} \in A$	False	$\{\{\emptyset\}\}$ is not listed as a top-level element.
$\{\{\emptyset\}\} \subseteq A$	True	Its member $\{\emptyset\} \in A$.
$A \in \mathcal{P}(A)$	True	Every set is an element of its own power set.
$A \subseteq \mathcal{P}(A)$	False	$\emptyset \in A$ and $\emptyset \in \mathcal{P}(A)$, but $\{\emptyset\} \in A$ while $\{\emptyset\} \subseteq A$ (an element vs set mismatch).

---

⚡ The Power Set & Combinatorial Cardinality

The power set of a set $A$, denoted by $\mathcal{P}(A)$ or $2^A$, is the set of all possible subsets of $A$.

📖Definition 1.8: The Power Setdefinition

$$\mathcal{P}(A) = 2^A = \{S \mid S \subseteq A\}$$$$S \in \mathcal{P}(A) \iff S \subseteq A$$

🔍Proof 1.2: Combinatorial Proof of Power Set Cardinalityproof

Theorem: If a set $A$ has cardinality $|A| = n$, then $|\mathcal{P}(A)| = 2^n$.

Proof: Let $A = \{a_1, a_2, \dots, a_n\}$. To construct any arbitrary subset $S \subseteq A$, we examine each element $a_i$ sequentially and make a binary choice:

• Choice 1: Include $a_i$ in $S$ ($1$).
• Choice 2: Exclude $a_i$ from $S$ ($0$).

Because the decision for each of the $n$ elements is mutually independent:

$$|\mathcal{P}(A)| = \underbrace{2 \times 2 \times 2 \times \dots \times 2}_{n \text{ decisions}} = 2^n$$

Equivalently, summing the binomial coefficients over all subset sizes $k \in \{0, 1, \dots, n\}$:

$$|\mathcal{P}(A)| = \sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$$

Concrete Expansion of the Power Set

For $A = \{a, b, c\}$ where $|A| = 3$, the power set contains $2^3 = 8$ subsets:

$$\mathcal{P}(A) = \big\{ \emptyset, \; \{a\}, \; \{b\}, \; \{c\}, \; \{a, b\}, \; \{b, c\}, \; \{a, c\}, \; \{a, b, c\} \big\}$$

---

🏗️ Iterated Power Sets & Recursive Towers

What happens when we recursively apply the power set operation to the empty set? This generates the foundational set-theoretic hierarchy of numbers.

Recursive Iterated Power Set Construction from the Empty Set

Step-by-step expansion trace of iterated power set operations starting from the null set

Base State (P⁰)

Level 1 (P¹)

Level 2 (P²)

Level 3 (P³)

1

Base State (P⁰)→Level 1 (P¹)

Power Set of Empty Set: P(∅)

2

Level 1 (P¹)→Level 2 (P²)

Power Set of P(∅): P({∅})

3

Level 2 (P²)→Level 3 (P³)

Power Set of P(P(∅)): P({∅, {∅}})

Iteration Trace and Cardinality Growth

Let $\mathcal{P}^k(S)$ denote $k$ repeated applications of the power set operation:

1. Iteration 0: $$S_0 = \emptyset \implies |S_0| = 0$$
2. Iteration 1: $$S_1 = \mathcal{P}(\emptyset) = \{\emptyset\} \implies |S_1| = 2^0 = 1$$
3. Iteration 2: $$S_2 = \mathcal{P}(\mathcal{P}(\emptyset)) = \{\emptyset, \; \{\emptyset\}\} \implies |S_2| = 2^1 = 2$$
4. Iteration 3: $$S_3 = \mathcal{P}(\mathcal{P}(\mathcal{P}(\emptyset))) = \big\{ \emptyset, \; \{\emptyset\}, \; \{\{\emptyset\}\}, \; \{\emptyset, \{\emptyset\}\} \big\} \implies |S_3| = 2^2 = 4$$
5. Iteration 4: $$|S_4| = |\mathcal{P}^4(\emptyset)| = 2^4 = 16$$
6. Iteration 5: $$|S_5| = |\mathcal{P}^5(\emptyset)| = 2^{16} = 65{,}536$$

📐Formula 1.2: Iterated Power Set Tower Cardinalityformula

$$|\mathcal{P}^k(\emptyset)| = 2^{2^{2^{\dots^0}}} \quad (k \text{ levels of exponentiation})$$

---

🏛️ Fundamental Power Set Algebraic Theorems

Core Invariants of Power Set Algebra

Universal algebraic rules governing power set inclusion, intersection, and union

🎯

Universal Membership Invariant

Membership Identity

• For any arbitrary set A, the empty set ∅ is ALWAYS an element: ∅ ∈ P(A).
• For any arbitrary set A, the set A itself is ALWAYS an element: A ∈ P(A).
• These hold because ∅ ⊆ A and A ⊆ A are universal subset truths.

Key Abstractions / Calls

∅ ∈ P(A)A ∈ P(A)∅ ⊆ P(A)

🔗

Intersection Distributivity

Exact Equality

• The power set distributes perfectly over set intersection.
• P(A ∩ B) = P(A) ∩ P(B) holds with strict equality for all sets A and B.
• A subset S ⊆ (A ∩ B) if and only if S ⊆ A and S ⊆ B simultaneously.

Key Abstractions / Calls

P(A ∩ B) = P(A) ∩ P(B)Bidirectional Proof

⚠️

Union Non-Distributivity Trap

Strict Subset Only

• The power set does NOT distribute equally over set union!
• P(A) ∪ P(B) ⊆ P(A ∪ B) holds, but equality FAILS in general.
• Subsets containing mixed elements from both A and B belong to P(A ∪ B) but not P(A) ∪ P(B).

Key Abstractions / Calls

P(A) ∪ P(B) ⊆ P(A ∪ B)P(A) ∪ P(B) ≠ P(A ∪ B)

♾️

Cantor's Theorem

Cardinality Growth

• For any set A (whether finite or infinite), |A| < |P(A)| strictly.
• There can never exist a surjective mapping from A onto its power set P(A).
• Guarantees an infinite hierarchy of strictly larger infinities: ℵ₀ < 2^(ℵ₀) < 2^(2^(ℵ₀)).

Key Abstractions / Calls

|A| < |P(A)|No Surjection A → P(A)

📐Theorem 1.1: Power Set Intersection Distributivitytheorem

$$\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$$

A subset $X$ satisfies $X \subseteq (A \cap B)$ if and only if $X \subseteq A$ and $X \subseteq B$.

⚡Law 1.2: Power Set Union Non-Distributivity Invariantlaw

$$\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)$$$$\mathcal{P}(A) \cup \mathcal{P}(B) = \mathcal{P}(A \cup B) \iff (A \subseteq B \lor B \subseteq A)$$

In general, strict equality fails because mixed subsets containing elements from both $A$ and $B$ belong to $\mathcal{P}(A \cup B)$ but are absent from $\mathcal{P}(A) \cup \mathcal{P}(B)$.

---

🌍 Real-World Engineering Context

1. Bitmasking & Dynamic Programming: In competitive programming and optimization algorithms (such as the Travelling Salesperson Problem via the Bellman-Held-Karp algorithm), subsets of a set of $n$ vertices are represented as integers from $0$ to $2^n - 1$. The $i$-th bit being 1 represents $x_i \in S$, and bitwise operations (S | (1 << i), S & ~(1 << i)) perform $O(1)$ set insertion and removal.
2. Access Control Matrices (RBAC): In cloud platforms like AWS IAM or GCP Cloud IAM, roles are sets of permission strings. When evaluating whether a role assignment $R_1$ is subsumed by role $R_2$, the policy engine executes a formal subset check: $R_1 \subseteq R_2$.
3. Model Checking & State Space Exploration: In formal verification of hardware circuits and concurrent protocols, the power set represents the reachable state configurations. State explosion arises precisely because an $n$-variable boolean system possesses $|\mathcal{P}(V)| = 2^n$ distinct global states.

---

📝 Step-by-Step Worked Examples

Example 1: Disambiguating Nested Set Membership and Inclusion

Problem Statement:
Given the set $S = \{a, \{a\}, \{b\}, \{\emptyset\}\}$, evaluate the truth value of the following 6 statements:

1. $a \in S$
2. $\{a\} \in S$
3. $\{a\} \subseteq S$
4. $\{\{b\}\} \subseteq S$
5. $\emptyset \in S$
6. $\emptyset \subseteq S$

Step-by-Step Solution:

1. $a \in S$: Inspecting $S$, the element $a$ appears as the first top-level element. True.
2. $\{a\} \in S$: The set $\{a\}$ appears as the second top-level element. True.
3. $\{a\} \subseteq S$: The only element inside $\{a\}$ is $a$. Because $a \in S$ (from Step 1), the subset condition holds. True.
4. $\{\{b\}\} \subseteq S$: The only element inside $\{\{b\}\}$ is $\{b\}$. Inspecting $S$, $\{b\}$ is indeed a top-level element ($\{b\} \in S$). Therefore, the subset relation holds. True.
5. $\emptyset \in S$: Inspecting $S$, the elements are $a$, $\{a\}$, $\{b\}$, and $\{\emptyset\}$. The symbol $\emptyset$ does not appear directly on its own (only wrapped inside braces as $\{\emptyset\}$). Therefore, $\emptyset \notin S$. False.
6. $\emptyset \subseteq S$: The empty set is a subset of every set without exception. True.

Key Takeaway:
An element inside nested braces cannot be directly referenced as a subset of the outer container without preserving its exact container depth.

---

Example 2: Cardinality of Iterated Power Sets

Problem Statement:
Let $A = \{x \in \mathbb{R} \mid x^2 + 1 = 0\}$. Determine the exact numerical value of:

$$|\mathcal{P}(\mathcal{P}(\mathcal{P}(A)))|$$

Step-by-Step Solution:

1. Determine Set $A$:
   • The equation is $x^2 + 1 = 0 \implies x^2 = -1 \implies x = \pm i$.
   • But the domain is restricted to real numbers: $x \in \mathbb{R}$.
   • Since there are no real roots, $A$ contains zero elements: $A = \emptyset$.
   • Therefore, $|A| = 0$.
2. First Power Set $\mathcal{P}(A)$: $$|\mathcal{P}(A)| = 2^{|A|} = 2^0 = 1$$
3. Second Power Set $\mathcal{P}(\mathcal{P}(A))$: $$|\mathcal{P}(\mathcal{P}(A))| = 2^{|\mathcal{P}(A)|} = 2^1 = 2$$
4. Third Power Set $\mathcal{P}(\mathcal{P}(\mathcal{P}(A)))$: $$|\mathcal{P}(\mathcal{P}(\mathcal{P}(A)))| = 2^{|\mathcal{P}(\mathcal{P}(A))|} = 2^2 = 4$$

Key Takeaway:
The base case for iterated power sets over the empty set is $|\mathcal{P}(\emptyset)| = 1$, not $0$.

---

Example 3: Proof of Power Set Intersection Distributivity

Problem Statement:
Prove that for any two arbitrary sets $A$ and $B$:

$$\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$$

Step-by-Step Solution:

To prove set equality, we must prove mutual inclusion: (i) $\mathcal{P}(A \cap B) \subseteq \mathcal{P}(A) \cap \mathcal{P}(B)$ and (ii) $\mathcal{P}(A) \cap \mathcal{P}(B) \subseteq \mathcal{P}(A \cap B)$.

• Part (i): Forward Direction:

  1. Let $X \in \mathcal{P}(A \cap B)$.
  2. By definition of power set, this means $X \subseteq (A \cap B)$.
  3. By definition of intersection, every element $x \in X$ satisfies $x \in A$ and $x \in B$.
  4. Hence, $X \subseteq A$ and $X \subseteq B$.
  5. By definition of power set, $X \in \mathcal{P}(A)$ and $X \in \mathcal{P}(B)$.
  6. Therefore, $X \in \mathcal{P}(A) \cap \mathcal{P}(B)$.
  7. This establishes $\mathcal{P}(A \cap B) \subseteq \mathcal{P}(A) \cap \mathcal{P}(B)$.

• Part (ii): Reverse Direction:

  1. Let $Y \in \mathcal{P}(A) \cap \mathcal{P}(B)$.
  2. By definition of intersection, $Y \in \mathcal{P}(A)$ and $Y \in \mathcal{P}(B)$.
  3. This implies $Y \subseteq A$ and $Y \subseteq B$.
  4. If an element $y \in Y$, then $y \in A$ and $y \in B \implies y \in (A \cap B)$.
  5. Therefore, $Y \subseteq (A \cap B)$.
  6. By definition of power set, $Y \in \mathcal{P}(A \cap B)$.
  7. This establishes $\mathcal{P}(A) \cap \mathcal{P}(B) \subseteq \mathcal{P}(A \cap B)$.

Combining Parts (i) and (ii) completes the proof: $\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$.

Key Takeaway:
Power set distributes over intersection with strict equality, but only forms a subset relationship under union.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why is A ∈ P(A) always true, but A ⊆ P(A) almost always false?"
Key Focus Points:

• Element vs Subset of P(A): $\mathcal{P}(A)$ is the set of all subsets of $A$. Because $A \subseteq A$ (reflexivity), $A$ is one of the listed subsets inside $\mathcal{P}(A)$, making $A \in \mathcal{P}(A)$ always true.
• Type Incompatibility: For $A \subseteq \mathcal{P}(A)$ to hold, every element of $A$ must itself be a subset of $A$. If $A = \{1, 2\}$, the elements of $A$ are numbers ($1, 2$), but the elements of $\mathcal{P}(A)$ are sets ($\emptyset, \{1\}, \{2\}, \{1, 2\}$). Since $1 \notin \mathcal{P}(A)$, $A \not\subseteq \mathcal{P}(A)$.

Question 2: "Why does P(A) ∪ P(B) ≠ P(A ∪ B) in general? Give a concrete minimal counterexample."
Key Focus Points:

• Mixed Subsets: $\mathcal{P}(A \cup B)$ contains subsets that combine elements from both $A$ and $B$.
• Minimal Counterexample: Let $A = \{1\}$ and $B = \{2\}$.
  • $\mathcal{P}(A) = \{\emptyset, \{1\}\}$ and $\mathcal{P}(B) = \{\emptyset, \{2\}\}$.
  • $\mathcal{P}(A) \cup \mathcal{P}(B) = \{\emptyset, \{1\}, \{2\}\}$ (size 3).
  • $A \cup B = \{1, 2\} \implies \mathcal{P}(A \cup B) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$ (size 4).
  • $\{1, 2\} \in \mathcal{P}(A \cup B)$, but $\{1, 2\} \notin \mathcal{P}(A) \cup \mathcal{P}(B)$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: How many proper subsets does an n-element set have? Is the empty set counted as proper?
Answer: $2^n - 1$. Yes, the empty set $\emptyset$ is counted as a valid proper subset for any non-empty set! The only subset excluded is the improper subset $A$ itself. If a question asks for non-empty proper subsets, the answer is $2^n - 2$.

Trap 2: If A has n elements, what is the cardinality of P(P(A))?
Answer: $2^{2^n}$, not $4^n$. The first power set has cardinality $|\mathcal{P}(A)| = 2^n$. The second power set exponentiates that cardinality: $|\mathcal{P}(\mathcal{P}(A))| = 2^{|\mathcal{P}(A)|} = 2^{2^n}$.

---

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic1.1 Set Definitions, Representations & the Number System HierarchyNext Topic →1.3 Set Operations, Venn Diagrams, Algebraic Laws & Cardinality Theorems