Questions: Power Set and Boolean Algebra Operations

Question 1

A set A has 10 elements. Someone estimates |P(A)| ≈ 20, reasoning: 'each element contributes two subsets — one containing it, one not.' What is the correct size of P(A) and what is wrong with this reasoning?

• A. P(A) has 20 elements — the reasoning is correct
• B. P(A) has 100 elements — there are n² possible pairs
• C. P(A) has 1,024 elements — the reasoning should count all combinations of n independent binary choices, giving 2^n
• D. P(A) has 10 elements — P(A) and A have the same cardinality

Answer: (C)

The error treats each element's contribution in isolation rather than in combination. For each of the 10 elements, you make one binary choice: include or exclude. With 10 independent binary choices, there are 2^10 = 1,024 possible combinations. The '20 elements' reasoning implicitly assumes subsets contain at most one element, ignoring all the subsets with 2, 3, ..., 10 members. The counting argument (n independent yes/no decisions → 2^n outcomes) is the cleanest proof of |P(A)| = 2^n.

Question 2

Cantor's theorem states that for any set A, |P(A)| > |A|. What does this imply for infinite sets?

• A. It does not apply to infinite sets — all infinite sets have the same size
• B. It implies there are infinitely many distinct infinite cardinalities, since each power-set operation creates a strictly larger infinity
• C. It implies P(A) is infinite for any infinite A, but all infinite sets are the same size
• D. It only means P(ℕ) is larger than ℕ; beyond that all infinite power sets collapse to the same size

Answer: (B)

Cantor's theorem has no exception for infinite sets — P(A) is strictly larger than A for any set whatsoever. Applying it repeatedly: ℕ < P(ℕ) < P(P(ℕ)) < ··· This generates a proper class of distinct infinite cardinalities. This was one of Cantor's most shocking results: not only are there different sizes of infinity, but there are infinitely many of them, with no largest one. Every infinite cardinal has a strictly larger power-set cardinal above it.

Question 3

For any set A, both ∅ and A itself are always elements of P(A).

• T. True
• F. False

Answer: True

P(A) is the set of all subsets of A. The empty set ∅ is a subset of every set (vacuously: there is no element of ∅ that fails to be in A), so ∅ ∈ P(A) always. Every set is a subset of itself (A ⊆ A trivially), so A ∈ P(A) always. These are structural features of the power set, not edge cases. A common error is constructing P(A) while forgetting one or both — always check that your count includes ∅ and A.

Question 4

For any infinite set A, P(A) and A have the same cardinality because both are infinite.

• T. True
• F. False

Answer: False

This is exactly what Cantor's theorem disproves. 'Both are infinite' is true but irrelevant — there are different sizes of infinity. Cantor showed that no function from A to P(A) can be surjective, regardless of how large A is. For example, ℕ is countably infinite, but P(ℕ) has the same cardinality as the real numbers ℝ (uncountably infinite), which is strictly larger. The intuition that 'all infinities are equal' is one of the most consequential misconceptions in mathematics.

Question 5

Explain Cantor's diagonal argument: why can no function f from A to P(A) be surjective, regardless of how large A is?

Model answer: Suppose for contradiction that f: A → P(A) is any function. Define D = {x ∈ A : x ∉ f(x)} — the set of elements that are not members of their own image. D is a subset of A, so D ∈ P(A). But D cannot be in the range of f: if some element a mapped to D (i.e., f(a) = D), then asking 'is a ∈ D?' leads to a contradiction — a ∈ D iff a ∉ f(a) = D. So no element of A maps to D, meaning f is not surjective. Since f was arbitrary, no surjection from A to P(A) can exist.

The diagonal construction is the key technique: D is built specifically to differ from f(x) at the position x for every x in A. This 'diagonal' element D is outside the range of f by construction. The same technique appears in Cantor's original diagonal argument about ℝ, in Gödel's incompleteness theorem, and in the proof that the halting problem is undecidable — it is one of the most powerful proof patterns in all of mathematics.