Axion of Powerset

The next axiom we look at will be the Axiom of Powerset. We previously looked at what it means for a set to be a subset of another set. In this section we will examine the set containing all subsets of a given set. This is called the power set of a given set.

The power set gets it’s name from the fact that if the A has n elements, then the powerset \mathcal{P}(A) has 2^n elements. For example, if

A = \{1,2\}

then

\mathcal{P}(A) = \{\varnothing,\{1\},\{2\},\{1,2\}\}.

We will prove this fact later once we have developed tools to count the number of elements in a set. It is worth noting that the empty set and the given set are both a member of a given sets power set.

Definition

Given a set A, the Power set of A is the set of all subsets of A, denoted

\mathcal{P}(A) = \{B \mid B \subseteq A\}

We have the definition, but of course we need to prove that the power set of any given set exists. This is where the axiom of power set comes in.

Axiom of Power Set

For any set A, there is a set whose members are exactly the subsets of A:

(\forall A)(\exists B)(\forall C) (C \in B \iff C \subseteq A)

As a side note, it is possible to prove that the power set of finite sets exists without using the axiom of powerset. However, since the power set of a given set has exponentially more elements then the given set, it is necessary to prove that the power set of infinite sets exists. We will touch on this matter more when we discuss cardinality.

Properties

We can now discuss various properties of the power set. This list of theorems is given in Suppes. The following follows immediately from the definition, and is stated for use in future theorems.

Theorem [86]

Let A,B be sets. Then B \in \mathcal{P}(A) if and only if B \subseteq A.

Proof

This follows immediately from the definition.

Next we prove that given a set A, the set A itself and the empty set are elements of \mathcal{P}(A).

Theorem [87]

Let A be a set. Then A \in \mathcal{P}(A).

Proof

By Theorem 5, A \subseteq A. Then by Theorem 86 A \in \mathcal{P}(A).

Theorem [88]

Let A be a set. Then \varnothing \in \mathcal{P}(A).

Proof

By Theorem X, \varnothing \subseteq A. Then by Theorem 86 \varnothing \in \mathcal{P}(A).

The next two theorems are simply proving the results of repeatedly applying the powerset to the empty set.

Theorem [89]

\mathcal{P}(\varnothing) = \{\varnothing\}

Proof

By Theorem 87, \varnothing \in \mathcal{P}(\varnothing). We now must show no other element exist in \mathcal{P}(\varnothing). By Theorem 86 if A \in \mathcal{P}(\varnothing) then A \subseteq \varnothing. But then by Theorem X, A = \varnothing. Thus

Theorem [90]

Let A be a set. Then \varnothing \in \mathcal{P}(A).

Proof

By Theorem X, \varnothing \subseteq A. Then by Theorem 86 \varnothing \in \mathcal{P}(A).