Mathematical-Reasoning · Unit 15 · Video 5 · Interactive Practice

Power Sets Have 2ⁿ Elements: Cardinality and the Number Systems

IKey Formulas

Statement	Name	Status
$\mathcal{P}(A) = \{X \subseteq U \mid X \subseteq A\}$ , so $X \in \mathcal{P}(A) \iff X \subseteq A$	Power set	Definition
$\operatorname{card}(T) = n \implies \operatorname{card}(\mathcal{P}(T)) = 2^n$ for each integer $n \ge 0$	Subsets of a finite set	Theorem (induction on $n$ )
$\mathbb{Q} = \left\{ \frac{m}{n} \,\middle\|\, m, n \in \mathbb{Z} \text{ and } n \ne 0 \right\}$ , $\;\mathbb{Q}^c = \{x \in \mathbb{R} \mid x \notin \mathbb{Q}\}$	Rational and irrational numbers	Set builder notation
$(a + bi)(c + di) = (ac - bd) + (ad + bc)i$	Complex product	Uses $i^2 = -1$

Key Insight: $\in$ relates an element to a set and $\subseteq$ relates two sets: $5 \in \mathbb{Z}$ and $\{5\} \subseteq \mathbb{Z}$ , and with $B = \{a, b, c\}$ , $c \in B$ but $c \notin \mathcal{P}(B)$ , because every element of $\mathcal{P}(B)$ is a set.

IIEach New Element Doubles the Subsets

Every subset of $A$ either omits the newest element $t$ or equals $X \cup \{t\}$ for exactly one older subset $X$ .

card(A) = 3

IIIElement or Subset?

$X \in \mathcal{P}(B)$ exactly when $X \subseteq B$ , so every element of $\mathcal{P}(B)$ is a set, never a letter.

Statement

IVThe Number Systems

Each number system is contained in the next: $\mathbb{N} \subset \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$ , and $\mathbb{R} = \mathbb{Q} \cup \mathbb{Q}^c$ .

Number

VQuiz Questions

Problem 1 · Listing a Power Set

Given: $A = \{x, y\}$ — find $\mathcal{P}(A)$ .

✅ Correct! The four subsets of

A

(sizes

0

1

1

and

2

) are the four elements of

\mathcal{P}(A)

, and

2^2 = 4

❌ Not quite.

x

and

y

are elements of

A

, not subsets of

A

, so they cannot be elements of

\mathcal{P}(A)

; the subsets

\emptyset

\{x\}

and

\{y\}

are missing.

❌ Close, but one subset is missing.

\emptyset

is a subset of every set, so

\emptyset \in \mathcal{P}(A)

; this set has

3

elements, not

2^2 = 4

❌ Close, but check the braces. It has four elements, but

x

and

y

are not subsets of

A

; the one-element subsets are

\{x\}

and

\{y\}

Show solution

Sort the subsets of $A$ by size.

Size $0$ : $\emptyset$ .
Size $1$ : $\{x\}$ and $\{y\}$ .
Size $2$ : $\{x, y\} = A$ .

Collecting these four subsets as the elements of one set gives

\mathcal{P}(A) = \{\emptyset, \{x\}, \{y\}, \{x, y\}\}.

Each element of $\mathcal{P}(A)$ is itself a set, and $\operatorname{card}(\mathcal{P}(A)) = 4 = 2^2$ .

Problem 2 · Element or Subset

Given: $B = \{a, b, c\}$ — which statement is false?

✅ Correct!

b

is a letter, an element of

B

; every element of

\mathcal{P}(B)

is a set, so

b \notin \mathcal{P}(B)

, while

\{b\} \in \mathcal{P}(B)

❌ That one is true.

\{b\} \subseteq B

, so

\{b\}

is one of the eight elements of

\mathcal{P}(B)

❌ That one is true. The empty set is a subset of every set,

\mathcal{P}(B)

included.

❌ That one is true. Every set is a subset of itself, so

B \subseteq B

and therefore

B \in \mathcal{P}(B)

Show solution

Use $X \in \mathcal{P}(B) \iff X \subseteq B$ on each statement.

$\{b\} \subseteq B$ , so $\{b\} \in \mathcal{P}(B)$ : true.
$\emptyset$ is a subset of every set, so $\emptyset \subseteq \mathcal{P}(B)$ : true.
$B \subseteq B$ , so $B \in \mathcal{P}(B)$ : true.
$b$ is not a set, so it is not a subset of $B$ , and $b \notin \mathcal{P}(B)$ : false.

The false statement is $b \in \mathcal{P}(B)$ . The correct statements about $b$ are $b \in B$ and $\{b\} \in \mathcal{P}(B)$ .

Problem 3 · Counting with 2ⁿ

Given: $T = \{1, 2, 3, 4, 5\}$ — find (i) the number of subsets of $T$ that contain $5$ , and (ii) $\operatorname{card}\big(\mathcal{P}(\mathcal{P}(\{a\}))\big)$ .

Part (i)

Part (ii)

✅ Correct! The subsets containing

5

match the

2^4 = 16

subsets of

\{1, 2, 3, 4\}

, and

\mathcal{P}(\{a\})

has

2

elements, so its power set has

2^2 = 4

❌ Not quite.

2^5 = 32

counts every subset of

T

; the

16

subsets of

\{1, 2, 3, 4\}

do not contain

5

❌ Close, but one is missing. Each subset containing

5

X \cup \{5\}

for exactly one

X \subseteq \{1, 2, 3, 4\}

, and

X = \emptyset

gives

\{5\}

; that makes

2^4 = 16

❌ Not quite.

5 = \operatorname{card}(T)

counts elements; the question counts subsets.

❌ Not quite.

\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}

has

2

elements; the question asks for the power set of that set.

❌ Close, but one is missing. A set with

2

elements has

2^2 = 4

subsets:

\emptyset

\{\emptyset\}

\{\{a\}\}

and

\{\emptyset, \{a\}\}

❌ Not quite.

2^3 = 8

would need

\mathcal{P}(\{a\})

to have

3

elements; it has

2

, namely

\emptyset

and

\{a\}

Show solution

(i) Let $S = T - \{5\} = \{1, 2, 3, 4\}$ , so $\operatorname{card}(S) = 4$ . A subset $Y$ of $T$ that contains $5$ equals $X \cup \{5\}$ with $X = Y - \{5\} \subseteq S$ , and different subsets $X$ of $S$ give different sets $X \cup \{5\}$ because $5 \notin X$ . So the subsets containing $5$ correspond one-to-one with the subsets of $S$ :

2^4 = 16.

The other $16$ subsets of $T$ omit $5$ , and $16 + 16 = 32 = 2^5$ , as the theorem says.

(ii) First $\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$ , a set with $2$ elements. Its subsets are

\emptyset, \quad \{\emptyset\}, \quad \{\{a\}\}, \quad \{\emptyset, \{a\}\},

so $\operatorname{card}\big(\mathcal{P}(\mathcal{P}(\{a\}))\big) = 2^2 = 4$ .

Problem 4 · Where Does a Complex Product Live?

Given: the product $(2 + i)(2 - i)$ — find the smallest of the sets in $\mathbb{N} \subset \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$ that contains it.

✅ Correct! With

a = 2

b = 1

c = 2

d = -1

, the product is

(ac - bd) + (ad + bc)i = 5 + 0i = 5

, a natural number.

❌ Not quite. The factors lie in

\mathbb{C}

, but the

i

-part of the product is

ad + bc = 2(-1) + 1 \cdot 2 = 0

, so the product is the real number

5

❌ Close, but there is a smaller set. The product is

5

, which lies in

\mathbb{Z}

and also in the smaller set

\mathbb{N}

❌ Close, but there is a smaller set. The product is real, but

ac - bd = 4 - (1)(-1) = 5

, and

5 \in \mathbb{N}

Show solution

Expand term by term and use $i^2 = -1$ :

(2 + i)(2 - i) = 4 - 2i + 2i - i^2 = 4 - (-1) = 5.

The formula gives the same: with $a = 2$ , $b = 1$ , $c = 2$ , $d = -1$ ,

(ac - bd) + (ad + bc)i = (4 + 1) + (-2 + 2)i = 5 + 0i.

Taking $b = 0$ in $a + bi$ gives the real number $a$ , so the product is $5$ . Since $5 \in \mathbb{N}$ and $\mathbb{N}$ is contained in each of the other sets, the smallest set in the chain that contains the product is $\mathbb{N}$ .

Solved: 0 / 4