483 views
closed as a duplicate of: GATE CSE 2023 | Question: 41
Let $x$ be a set, $2^x=$ power $2 \mathrm{k}$ set of $\mathrm{X}$. define A binary operation $\Delta$ on $2^x$ as $A \Delta B=(A-B) \cup(B-A)$. Let $H=\left(2^x, \Delta\right)$, then
1. for every $A \in 2^x$; inverse of $A$ is $\operatorname{not} A$.
2. $\mathrm{H}$ is a group.
3. $\mathrm{H}$ satisfies inverse prop, but not a group
4. for every $A \in 2^x$; the inverse of $A$ is $A$.

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 (B), (D)

Edit:

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

Detailed Video Solution: Group Theory Question

$\color{\red}{\text{ALL Discrete Mathematics Questions:}}$

Question 1: First Order Logic question, P(x) --> Q(x,y)

Question 2: Greedy Graph Coloring Algorithm