GATE CS 2023 Q.51: Monoids and Groups

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

Let $H = (2^X, \Delta)$ . Which of the following statements about $H$ is/are correct?

$H$ is a group.

Every element in $H$ has an inverse, but $H$ is NOT a group.

For every $A \in 2^X$ , the inverse of $A$ is the complement of $A$ .

For every $A \in 2^X$ , the inverse of $A$ is $A$ .

Official answer and solution

Official answer: A and D
From: Official GATE 2023 answer key

Solution

Verify group axioms for the symmetric difference operation $\Delta$ on powerset $2^X$ .

Let $H = (2^X, \Delta)$ where $A \Delta B = (A - B) \cup (B - A)$ :

Closure: For any $A, B \subseteq X$ , $A \Delta B \subseteq X$ , so $A \Delta B \in 2^X$ .
Associativity: Symmetric difference is associative: $(A \Delta B) \Delta C = A \Delta (B \Delta C)$ holds for all subsets.
Identity Element: The empty set $\emptyset$ serves as the identity element because $A \Delta \emptyset = (A - \emptyset) \cup (\emptyset - A) = A$ .
Inverses: For every $A \in 2^X$ , $A \Delta A = (A - A) \cup (A - A) = \emptyset$ . Thus, the inverse of $A$ is $A$ itself (every element is self-inverse).

Since closure, associativity, identity, and inverses all exist, $H$ is a group (an abelian group of exponent 2). Therefore, statements (A) and (D) are correct.

Final answer

Options (A, D)

Common trap

Thinking the inverse is the set complement $X - A$ , whereas $A \Delta (X - A) = X \neq \emptyset$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 51 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source