SET 05 · Power Set & Cardinality
Cardinality |A|
The number of distinct elements of A.
- {1, 3, 5, 7, 9} (odd positive integers < 10) →
- ,
- A nested set counts as one element:
Power set P(A) or 2ᴬ
The set of all subsets of A:
| A | P(A) | |P(A)| |
|---|---|---|
| ϕ | {ϕ} | 1 |
| {a} | {ϕ, {a}} | 2 |
| {a, b} | {ϕ, {a}, {b}, {a,b}} | 4 |
| {a, b, c} | {ϕ, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}} | 8 |
That’s why P(A) is written . (Each element is either in or out of a subset: 2 choices, n times.)
Always true for any A
- — ϕ is a subset of A, so it’s an element of P(A).
- — ϕ is a subset of everything.
Recipe for power sets of nested sets
- Count the top-level elements: that’s n.
- Treat each top-level element as an opaque item (even if it’s a set).
- List subsets by size: 0, 1, 2, …, n. Wrapping an element x gives the subset {x}.
Solved problems (slides) — try first
Problem 1. Give the power set of:
a)
👁 Show answer
— 4 elements. Note , not .
b)
👁 Show answer
— the element ϕ becomes the subset {ϕ}.
c)
👁 Show answer
Problem 2. Power set of: a) {a} b) {a, b} c) {ϕ, {ϕ}}
👁 Show answer
a) {ϕ, {a}} b) {ϕ, {a}, {b}, {a, b}} c) {ϕ, {ϕ}, {{ϕ}}, {ϕ, {ϕ}}}
Problem 3. How many elements?
a)
👁 Show answer
3 top-level elements (a, b, {a,b}) ⇒ .
b)
👁 Show answer
4 top-level elements ⇒ .
c)
👁 Show answer
has 1 element ⇒ has : .
Iterated power sets of ϕ
. Each step: .
GATE versions (1995, 2015, 2015) → SET 11 GATE PYQs
Prev ← SET 04 Universal Null Singleton · Next → SET 06 Cartesian Product