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:

AP(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

  1. Count the top-level elements: that’s n.
  2. Treat each top-level element as an opaque item (even if it’s a set).
  3. 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)

b)

c)

Problem 2. Power set of: a) {a} b) {a, b} c) {ϕ, {ϕ}}

Problem 3. How many elements?

a)

b)

c)

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