Verify if $A * B = (A \cup B) - (A \cap B)$ forms a group, on sets from $G =\mathcal{P}(S)$.

This is a question ($Q. 6$) from the book by Louis W. Shapiro, titled: Introduction to Abstract Algebra, from sec. $1.2$.

Let $S$ be a set, and let $G$ be the set of subsets of $S$.
If $A$ and $B$ are subsets of $S$, then define $A * B = (A \cup B) - (A \cap B)$, that is, the subset of all elements in $A$ or in $B$, but not in both.

(a) Show, using Venn diagrams if you wish, that $(A * B) * C = A * (B * C)$.
(b) Show that $(G,*)$ is a group.
(c) Show that $(G,*)$ is an abelian group.
(d) If $S$ has two or three elements, how many elements will be in $G$?
(e) If $S$ has $n$ elements, how many elements will be in $G$?

If $S$ has $n$ elements, then: (e) $|G|=2^n$. So, (d) is $4, 8$ respectively for set $S$ with $2,3$ elements.

(a) If $A * B = (A \cup B) - (A \cap B)$,
so, taking l.h.s. of $(A * B) * C = A * (B * C)$, get:
$(A * B) * C = ((A \cup B) - (A \cap B))*C$
$= ((A \cup B) - (A \cap B))\cup C - ((A \cup B) - (A \cap B))\cap C$
$= (A \cup B)\cup C - (A \cap B)\cup C - (A \cup B)\cap C + (A \cap B)\cap C$
$= A \cup B\cup C - (A \cap B)\cup C - (A \cup B)\cap C + (A \cap B)\cap C$

taking r.h.s. of $(A * B) * C = A * (B * C)$, get:
$A * (B * C) = A*(B \cup C) - A*(B \cap C))$
$= A\cup(B \cup C) - A\cap(B \cup C) - A\cup(B \cap C) + A\cap(B \cap C)$
$= A \cup B\cup C - (A \cap B)\cup C - (A \cup B)\cap C + (A \cap B)\cap C$

(b) Show that $(G,*)$ is a group, so need show that $(G,*)$ satisfies the four properties:
(i) Identity $(e)$ exists, s.t. for any set $A, A*e = e*A= A\cup e - A\cap e = A$.
As there is a set $\emptyset$ as subset of any set that satisfies this property, so $e= \emptyset$.
(ii) Inverse ($C$) exists for any element (set, $A$), s.t. $A*C = A\cup C - A\cap C = e\implies A\cup C = A\cap C\implies C = A$
(iii) Closure exists, as all sets are from the $2^n$ sets, and any union or intersection will still be in the superset. Say, there are $3$ elements in $S$, so the subsets are $8$, labelled as :
x_1. $\lbrace 1,2,3\rbrace$,
x_2. $\lbrace 1,2\rbrace$,
x_3. $\lbrace 1,3\rbrace$,
x_4. $\lbrace 2,3\rbrace$,
x_5. $\lbrace 1\rbrace$,
x_6. $\lbrace 2\rbrace$,
x_7. $\lbrace 3\rbrace$,
x_8. $\emptyset$

$x_1 \cap x_2 = x_2, x_2\cap x_7 = x_8$, and so on.
But, request a more formal way to prove it.
(iv) Associativity property exists, as both commutativity (proved below in part (c)) and closure exist $\forall$ sets $A, B, C \in G \mid A*(B*C)= (A*B)*C$.
Request approach to prove (iv) by a better approach, as not possible to show failure by contradiction.

(c) To prove that $(G, *)$ is an abelian group means that $A*B$ yields the same results under swap ($B*A$).
$A*B = (A\cup B)-(A\cap B)$, while $B*A = (B\cup A)-(B\cap A)$
Due to the set union, set intersection & set difference being commutative operations; the result is the same under swap of sets for the operation.

Solution 1:

There is still another way of proving that the symmetric difference of sets (and write $A \Delta B= (A \cup B)-(A \cap B)$) induces an abelian group structure on the power set of $S$, and that is making use of characteristic functions mod $2$.

For every subset $A \subseteq S$, $x \in S$, define the function $1_A$ as follows. $$1_A(x)=\{^{1 \text{ if } x \in A}_{0 \text{ if } x \notin A}$$ so in particular $1_{\emptyset} \equiv 0$ and $1_S \equiv 1$. It is easy to see that $1_A=1_B$ if and only if $A=B$. Also, $1_{A \Delta B}=1_A + 1_B$ mod $2$. So, to prove associativity for example: $$1_{(A \Delta B)\Delta C}=(1_A + 1_B)+1_C=1_A + (1_B+1_C)=1_{A \Delta (B\Delta C)}$$ since addition mod $2$ is associative! Hence $(A \Delta B)\Delta C=A \Delta (B\Delta C)$.

I leave the rest to you. With this you can actually easily establish an isomorphism between ($\mathcal{P}(S)$,$\Delta$) and $C_2\times \cdots \times C_2$.

Solution 2:

• In part $(a)$, what does addition of sets means?

Let $S=\{1,2,3,4,5,6,7,8\}, A=\{1,2,3,4\}, B=\{2,3,5,6\}, C=\{3,4,6,7\}$.

$A*B=\{1,4,5,6\}$

$(A*B)*C=\{1,3,5,7\}.$

Now let's check your claim that $(A*B)*C=A \cup B \cup C -(A \cap B) \cup C-(A\cup B) \cap C +(A \cap B) \cap C$, whatever $+$ means, also assuming that $\cap$ and $\cup$ has a higher precedence than $-$.

$A\cup B\cup C = \{1,2,3,4,5,6,7\}$

$(A \cap B) \cup C = \{2,3,4,6,7\}$ and $(A \cup B) \cap C=\{3,4,6\}$ and $(A \cap B) \cap C=\{3\}$

$A \cup B \cup C - (A \cap B) \cup C = \{1,5\}$

$A \cup B \cup C - (A \cap B) \cup C - (A \cup B) \cap C = \{1,5\}$

$A \cup B \cup C - (A \cap B) \cup C - (A \cup B) \cap C + (A\cap B) \cap C = \{1,5\}+\{3\}$

which is unlikely to be correct.

• Also, in your working, you assume that you have $(A-B) \cup C = (A \cup C)-B \cup C$, the assumption is flawed.

• Closure: For any $A, B \subset S$, we have $A \cup B \subset S$, $A \cap B \subset S, A^c \subset S$, hence $A*B =(A \cup B) - (A \cap B)=(A \cup B) \cap (A \cap B)^c \subset S$

• The goal of part (a) is to prove associativity.

• Associativity: We know that $A*B = (A \cap B^c) \cup (A^c \cap B)$

Hence \begin{align}(A*B)*C &= ((A \cap B^c) \cup (A^c \cap B))*C\\ &=(((A \cap B^c) \cup (A^c \cap B)) \cap C^c ) \cup (((A \cap B^c) \cup (A^c \cap B))^c \cap C)\\ &=(A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c) \cup (((A^c \cup B) \cap (A \cup B^c)) \cap C)\\ &= (A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c) \cup ((A^c \cap B^c) \cup (A \cap B)) \cap C)\\ &= (A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c) \cup (A^c \cap B^c \cap C) \cup (A \cap B \cap C) \\\end{align}

Also, by commutivity that you have shown, \begin{align}A*(B*C)&=(B*C) *A \\ &=(C * B) *A \\ &= (C \cap B^c \cap A^c) \cup (C^c \cap B \cap A^c) \cup (C^c \cap B^c \cap A) \cup (A \cap B \cap C)\end{align}

the two expressions are equal, hence it is associative.

Edit: An alternative:

\begin{align}(A * B) * C &= ((A \cup B) - (A \cap B))*C \\&= ((A \cup B) - (A \cap B))\cup C - ((A \cup B) - (A \cap B))\cap C \\&= (((A\cup B) \cap (A \cap B)^c ) \cup C ) \cap (((A\cup B) \cap (A \cap B)^c )\cap C)^c \\&= (((A\cup B) \cap (A \cap B)^c ) \cup C ) \cap (((A \cap B^c) \cup (A^c \cap B) )\cap C)^c\\ &=(((A\cup B) \cap (A \cap B)^c ) \cup C ) \cap (((A^c \cup B) \cap (A \cup B^c) )\cup C^c)\\ &=(A\cup B \cup C) \cap (A^c \cup B^c \cup C ) \cap (A^c \cup B \cup C^c) \cap (A \cup B^c \cup C^c) \\ \\\end{align}

Again, by commutative,

\begin{align} (A*B)*C &= C*(B*A) \\ &=(A\cup B \cup C) \cap (C^c \cup B^c \cup A ) \cap (C^c \cup B \cup A^c) \cap (C \cup B^c \cup A^c) \end{align}