The Abelian Group of the Power Set of a Finite Set

Recall from the Abelian Groups page that an Abelian group is a group with the extra property of commutativity on its operation $\cdot$. That is, an Abelian group is a set $G$ paired with a binary operation $\cdot : G \times G \to G$ where:

• 1) For all $a, b, c \in G$ we have that $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ (Associativity of $\cdot$).

• 2) There exists an element $e \in G$ such that $a \cdot e = a$ and $e \cdot a = a$ (The existence of an identity for $\cdot$).

• 3) For all $a \in G$ there exists a $a^{-1} \in G$ such that $a \cdot a^{-1} = e$ and $a^{-1} \cdot a = e$ (The existence of inverses for each element in $G$).

• 4) For all $a, b \in G$ we have that $a \cdot b = b \cdot a$ (Commutativity of $\cdot$).

We will now look at the Abelian group of the power set of a finite set.

Let $S$ be any finite set. Then the power set of $S$ denoted $\mathcal P (S)$ is the set of all subsets of $S$, namely:

(1)

\begin{align} \quad \mathcal P (S) = \{ B : B \subseteq S \} \end{align}

Furthermore, let $\oplus : \mathcal P (S) \times \mathcal P(S) \to \mathcal P(S)$ be the operation of the symmetric difference of two sets, that is, for $A, B \in \mathcal P(S)$ we have that:

(2)

\begin{align} \quad A \oplus B = (A \setminus B) \cup (B \setminus A) \end{align}

In other words, $A \oplus B$ is the set of elements $x$ such that $x \in A$ or $x \in B$ and such that $x \not \in A \cup B$. We will now show that $(\mathcal P(S), \oplus)$ is a group.

Let $A, B \in \mathcal P (S)$. Then $A, B \subseteq S$. Furthermore, $(A \setminus B) \subseteq S$ and $(B \setminus A) \subseteq S$ so $A \oplus B = (A \setminus B) \cup (B \setminus A) \subseteq S$. Therefore $A \oplus B \in \mathcal P (S)$ so $\mathcal P (S)$ is closed under $\oplus$.

Now let $A, B, C \in \mathcal P (S)$. Then we have that:

(3)

\begin{align} \quad A \oplus (B \oplus C) = A \oplus ((B \setminus C) \cup (C \setminus B)) = A \setminus [(B \setminus C) \cup (C \setminus B)] \cup [(B \setminus C) \cup (C \setminus B)] \setminus A \end{align}

Similarly we have that:

(4)

\begin{align} \quad (A \oplus B) \oplus C = ((A \setminus B) \cup (B \setminus A)) \oplus C = [(A \setminus B) \cup (B \setminus A)] \setminus C \cup C \setminus [(A \setminus B) \cup (B \setminus A)] \end{align}

Proving that $A \oplus (B \oplus C) = (A \oplus B) \oplus C$ is not algebraic difficult, just a bit tedious. We can instead see that the two equations above are indeed equal if we look at the Venn diagram produced by both:

So indeed $A \oplus (B \oplus C) = (A \oplus B) \oplus C$, and hence $\oplus$ is associative.

The identity element with respect to $\oplus$ is the empty set $\emptyset \in \mathcal P (S)$ since for all subsets $A \in \mathcal P(S)$ we have that:

(5)

\begin{align} \quad A \oplus \emptyset = (A \setminus \emptyset) \cup (\emptyset \setminus A) = A \cup \emptyset = A \end{align}

And similarly:

(6)

\begin{align} \quad \emptyset \oplus A = (\emptyset \setminus A) \cup (A \setminus \emptyset) = \emptyset \cup A = A \end{align}

For each element $A \in \mathcal P(S)$ we have that the inverse of $A$ with respect to $\oplus$ is $A$ itself since:

(7)

\begin{align} \quad A \oplus A = (A \setminus A) \cup (A \setminus A) = \emptyset \cup \emptyset = \emptyset \end{align}

Lastly, for $A, B \in \mathcal P (S)$ we have that:

(8)

\begin{align} \quad A \oplus B = (A \setminus B) \cup (B \setminus A) = (B \setminus A) \cup (A \setminus B) = B \oplus A \end{align}

Hence $\oplus$ is commutative. Therefore $(\mathcal P(S), \oplus)$ is an Abelian group