The Abelian Group of the Power Set of a Finite Set

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 $*$. That is, an Abelian group is a set $G$ paired with a binary operation $* : G \times G \to G$ where:

  • For all $a, b \in G$ we have that $(a * b) \in G$ (Closure under $*$).
  • For all $a, b, c \in G$ we have that $(a * b) * c = a * (b * c)$ (Associativity of $*$).
  • There exists an element $e \in G$ such that $a * e = a$ and $e * a = a$ (The existence of an identity for $*$).
  • For all $a \in G$ there exists a $a^{-1} \in G$ such that $a * a^{-1} = e$ and $a^{-1} * a = e$ (The existence of inverses for each element in $G$).
  • For all $a, b \in G$ we have that $a * b = b * a$ (Commutativity of $*$).

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:

Screen%20Shot%202015-09-06%20at%206.53.33%20PM.png

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License