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$.

Comments

@Deepak Poonia sir please elaborate in easy way.

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.

Answer 2

For better understanding let start the question by taking set X = {1,2} and P(X) denotes the power set of X. So,

P(X) = { $\phi$, {1}, {2}, {1,2} }.

 

A binary operation $\Delta$ is defined on P(X) such that :

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

Simply saying $\Delta$ is symmetric difference.

 

And, H = ({ $\phi$, {1}, {2}, {1,2} }, $\Delta$).

 

---

 

Let's take a look of on the closure property, Associativity, Identity & Inverse for H.

 

Closure Property : H is said to be satisfying closure property iff we take any two element from 

{ $\phi$, {1}, {2}, {1,2} } the result will always belongs to this itself.

Example : Let A = {1} and B = $\phi$

Then, (A-B) $\cup$ (B-A) = ({1}-$\phi$) $\cup$ ($\phi$ - {1}) = {1} $\cup$ $\phi$ = {1} $\epsilon$ P(X).

 

If we try to take any two elements from P(X) then we will observe that result will belongs to P(X).

So, H satisfies Closure Property.

 

Associativity :  (A $\Delta$ B) $\Delta$ C = A $\Delta$ (B $\Delta$ C).

Let's take A = {1}, B = $\phi$ & C = {2}

LHS : (A $\Delta$ B) $\Delta$ C

= {1} $\Delta$ C = {1} $\Delta$ {2} 

= ({1} -{2}) $\cup$ ({2}-{1}) = {1,2}

 

RHS : A $\Delta$ (B $\Delta$ C)

= A  $\Delta$ ( $\phi$ $\Delta$ {2}) = A $\Delta$ ( ($\phi$ - {2}) $\cup$ ({2} - $\phi$) )

= A $\Delta$ {2} = {1} $\Delta$ {2}

= {1,2}

Hence, LHS = RHS.

So, H satisfies Associativity.

 

Identity Property : An element 'e' is said to be identity element iff 

A $\Delta$ E = E $\Delta$ A = A.

 

It can easily be observed that for this binary operation $\Delta$, $\phi$ is the identity element. E = $\phi$

Let's have a look How?

A $\Delta$ E = (A - $\phi$) $\cup$ ($\phi$ - A) = A $\cup$ $\phi$ = A

E $\Delta$ A = ($\phi$ - A) $\cup$ (A - $\phi$) = $\phi$ $\cup$ A = A

Hence, E = $\phi$ is the identity element.

So, H have Identity Element.

 

Inverse : Let, $A^{-1}$ be the inverse of A. An element is said to be inverse if 

A $\Delta$ $A^{-1}$ = $A^{-1}$ $\Delta$ A = E

 

Let's 'T' be any element from P(X) and try to find out it's inverse

T $\Delta$ $T^{-1}$ = $\phi$

(T - $T^{-1}$) $\cup$ ($T^{-1}$ - T) = $\phi$

This equation will only holds good when $T^{-1}$ = T, means every element should be it's own inverse.

So, H have Inverse Element.

 

As, H satisfies Closure Property, Associativity, Indetity Element & Inverse. Then H is a group.

With this conclusion Option A is accepted and Option B is Rejected.

From conclusion on inverse property we can conclude that Option C is Rejected and

Option D is accepted.

 

So, correct comination of Answer : A, D.