Powersets and Boolean Algebra

Powersets

Definition

The powerset of a set $A$, written $\mathcal{P}(A)$ or $2^A$, is the set of all subsets of $A$.

$\mathcal{P}(A) = \{S : S \subseteq A\}$

Examples

• $\mathcal{P}(\emptyset) = \{\emptyset\}$
• $\mathcal{P}(\{1\}) = \{\emptyset, \{1\}\}$
• $\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$

Cardinality

For finite sets:

$|\mathcal{P}(A)| = 2^{|A|}$

Proof: Each element of $A$ either is or is not in a subset. For $|A| = n$, there are $n$ independent binary choices, giving $2^n$ subsets.

Visualising Powersets

Hasse Diagrams

A Hasse diagram shows $\mathcal{P}(A)$ ordered by $\subseteq$:

• Elements are arranged with $\emptyset$ at the bottom
• Larger sets are drawn above subsets
• Edges connect sets that differ by exactly one element

Venn Diagrams

Venn diagrams visualise set relationships in the plane.

Universal set $U$ is shown as a rectangle. Sets $A$, $B$ are shown as overlapping circles within $U$.

The Powerset Boolean Algebra

Structure

$(\mathcal{P}(A), \cup, \cap, ^c, \emptyset, A)$ forms a Boolean algebra:

Operation	Symbol	Corresponds to
Join	$\cup$	OR
Meet	$\cap$	AND
Complement	$^c$	NOT
Bottom	$\emptyset$	False
Top	$A$	True

Boolean Algebra Laws

Commutativity: $A \cup B = B \cup A$ $A \cap B = B \cap A$

Associativity: $(A \cup B) \cup C = A \cup (B \cup C)$ $(A \cap B) \cap C = A \cap (B \cap C)$

Absorption: $A \cup (A \cap B) = A$ $A \cap (A \cup B) = A$

Identity: $A \cup \emptyset = A$ $A \cap U = A$

Complement: $A \cup A^c = U$ $A \cap A^c = \emptyset$

The Analog with Propositional Logic

Set Theory	Logic
$\cup$	$\lor$
$\cap$	$\land$
$^c$	$\neg$
$\subseteq$	$\Rightarrow$
$\emptyset$	False
$U$	True

This correspondence is not coincidental. The Boolean algebra of sets is a model of propositional logic, and vice versa.

Characteristic (Indicator) Functions

Definition

For $S \subseteq A$, the characteristic function (or indicator function) $\chi_S : A \to \{0, 1\}$ is:

$\chi_S(x) = \begin{cases} 1 & \text{if } x \in S \\ 0 & \text{if } x \notin S \end{cases}$

Correspondence

There is a bijection between $\mathcal{P}(A)$ and the set of functions $A \to \{0, 1\}$:

$\mathcal{P}(A) \cong \{f : A \to \{0, 1\}\}$

This gives an alternative proof that $|\mathcal{P}(A)| = 2^{|A|}$ for finite $A$.

---

Summary

• $\mathcal{P}(A)$ is the set of all subsets of $A$
• $|\mathcal{P}(A)| = 2^{|A|}$ for finite $A$
• $\mathcal{P}(A)$ forms a Boolean algebra with $\cup$, $\cap$, $^c$
• Hasse diagrams show inclusion structure; Venn diagrams show overlap relations
• Characteristic functions establish $\mathcal{P}(A) \cong (A \to \{0, 1\})$