GATE CSE 2023 | Question: 41

Question

Let $X$ be a set and $2^{X}$ denote the powerset of $X$.

Define a binary operation $\Delta$ on $2^{X}$ as follows:
\[
A \Delta B=(A-B) \cup(B-A) \text {. }
\]
Let $H=\left(2^{X}, \Delta\right)$. Which of the following statements about $H$ is/are correct?

• A. $H$ is a group.
• B. Every element in $H$ has an inverse, but $H$ is NOT a group.
• C. For every $A \in 2^{X},$ the inverse of $A$ is the complement of $A$.
• D. For every $A \in 2^{X},$ the inverse of $A$ is $A$.

Answer 1

This is proof regarding the given question.

Here Binary operation $\Delta$ is defined on the power set of set $X.$ i.e. $2^X.$

Now, say, there are two elements $A$ and $B$ of the set $2^X$ and 

$A \Delta B = (A-B)  \cup (B-A) = (A \cup B) \  – \ (A \cap B) $

$1) $ Closure:

Since, $2^X$ is a power set of set $X$, so it contains all the subsets of set $X$ and so, $(A \cup B) \in 2^X$ and $(A \cap B) \in 2^X$

and so,  $(A \cup B) \  – \ (A \cap B) \in 2^X $ and hence, $A \Delta B \in 2^X \ \ $ $\forall A,B \in 2^X $

$2) $ Associativity:

(i) $A \Delta(B\Delta C) = A \Delta ((B\cup C)  \ – \ (B \cap C)) = A \Delta ((B\cup C)  \ \cap \ (B \cap C)’)$

$= A \Delta ((B\cup C)  \ \cap \ (B’ \cup C’)) = A \cup ((B\cup C)  \ \cap \ (B’ \cup C’)) \ – \ A \cap ((B\cup C)  \ \cap \ (B’ \cup C’)) $

$= (A \cup B \cup C) \cap (A \cup B’ \cup C’) \cap (A \cap ((B\cup C)  \ \cap \ (B’ \cup C’))’$

$= (A \cup B \cup C) \cap (A \cup B’ \cup C’) \cap (A’ \cup (B’ \cap C’) \cup (B\cap C))$

$= (A \cup B \cup C) \cap (A \cup B’ \cup C’) \cap (((A’ \cup B’) \cap (A’ \cup C’))\cup (B \cap C))$

$= (A \cup B \cup C) \cap (A \cup B’ \cup C’) \cap ((A’ \cup B’) \cap (A’ \cup C’)\cup B) \cap ((A’ \cup B’) \cap (A’ \cup C’)\cup C)$

$= (A \cup B \cup C) \cap (A \cup B’ \cup C’) \cap (A’ \cup C’ \cup B) \cap (A’ \cup B’ \cup C)$

 

(ii) $(A \Delta B) \Delta C = ((A \cup B) \ – \ (A \cap B)) \Delta C =  ((A \cup B) \ \cap \ (A \cap B)’) \Delta C$

$=  (((A \cup B) \ \cap \ (A \cap B)’) \cup C) \ – \ (((A \cup B) \ \cap \ (A \cap B)’) \cap C)$

$= (A \cup B \cup C) \cap (A’ \cup B’ \cup C) \cap (C’ \cup (A \cup B)’ \cup (A’ \cup B’)’)$

$= (A \cup B \cup C) \cap (A’ \cup B’ \cup C) \cap (C’ \cup (A’ \cap B’) \cup (A \cup B))$

$= (A \cup B \cup C) \cap (A’ \cup B’ \cup C) \cap (C’ \cup B’ \cup A) \cap (C’ \cup A’ \cup B)$

Hence, Associativity satisfies. You can prove it using Venn diagram too.

$3)$ Identity:

Say $e \in 2^X$ is an identity element.

$A \Delta e = e \Delta A = A$ for $e \in 2^X$

$A \Delta e = A$ means $(A\cup e) \ –  \ (A \cap e) = A$

It is possible when $(A\cup e) = A$ and $ (A \cap e) = \phi$

$(A\cup e) = A$ is possible when $e=A$ or $e \subset A$ or $e = \phi$

But $e=A$ or $e \subset A$ then $(A \cap e) \neq \phi$ and so, identity element $e = \phi$  

$4)$ Inverse:

Say two elements $A,B \in 2^X$ and are inverse to each other.

$A\Delta B = B \Delta A = \phi$

So, $A\Delta B = \phi $ which means $(A \cup B) \  – \ (A \cap B) = \phi $

It is possible when $(A \cup B)  =  (A \cap B)$ because $(A \cup B)$ can’t be proper subset of $A\cap B$

And $(A \cup B)  =  (A \cap B)$ is possible when $A=B$

So, every element in $2^X$ is its own inverse.

Therefore (A), (D) 

 

One more way to prove associativity is by converting set theory operations to digital logic operations i.e. $\cup$ to $+$ and $\cap$ to $.$

So, $A \Delta B = (A \ – \ B) \cup (B \ – A) = (A \cap B’) \cup (B \cap A’ ) = AB’ + B A’  = A \oplus B$

So, symmetric difference operation in set theory is equivalent to exor operation in digital logic.

Now, $(A \oplus B) \oplus C = (AB’ + BA’) \oplus C = (AB’ + BA’)C’ + (AB’ + BA’)’C$

$= AB’C’ + BA’C’ + (A’+B)(B’+A)C = AB’C’ + BA’C’ + A'B’C + BAC$

$= A(BC + B'C’) + A’(BC’+B'C) = A (B \oplus C)’ + A' (B \oplus C) = = A \oplus (B \oplus C)$

Comments

Why option C is wrong?

---

Reason is already added. Let me know if you have any doubt.

Alternatively, you can also check with the help of software here 

It is also noted that Inverse should be unique and since, $A^{-1}=A$ for each A, so given group is also an Abelian group.

This Abelian group is for the name of the mathematician Abel and the story of Abel and Galois is quite interesting, specially the story of Galois. If you have interest then you can go through it.

Both were died at the very young age but before that they have made a remarkable contribution in the field of mathematics.

---

beautiful.