GATE 2023 CS Q.51: solution and answer

GATE 2023 · CSQ.51 · 2 marks · MSQ

Let $X$ be a set and $2^{X}$ denote the powerset of $X$ . Define a binary operation $Δ$ on $2^{X}$ as follows:

A Δ B = (A - B) \cup (B - A) .

Let $H = (2^{X}, Δ)$ . 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$ .

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Options (A) and (D) are correct: $H$ is a group, and every element is its own inverse.

Official answer: A, DSource: Official answer key, GATE 2023 CS (IIT Kanpur)

Closure: $A Δ B = (A - B) \cup (B - A)$ is built from elements of $X$ , so it is a subset of $X$ and lies in $2^{X}$ .
Associativity: an element $x$ lies in $A Δ B$ exactly when it belongs to exactly one of $A, B$ , that is, to an odd number of them. For three sets, $x \in (A Δ B) Δ C$ exactly when the number of sets among $A Δ B$ and $C$ containing $x$ is odd. This happens exactly when $x$ lies in an odd number of $A, B, C$ : if $x$ is in $C$ , it must lie in an even number of $A, B$ ; if not, in an odd number. The same count describes $A Δ (B Δ C)$ . Both sides contain exactly the elements that belong to an odd number of $A, B, C$ , so $Δ$ is associative.
Identity: $A Δ \emptyset = (A - \emptyset) \cup (\emptyset - A) = A \cup \emptyset = A$ , and $\emptyset Δ A = A$ by symmetry. So $\emptyset$ is the identity.
Inverse: $A Δ A = (A - A) \cup (A - A) = \emptyset$ . Every element is its own inverse, so (D) is true.
Closure, associativity, identity and inverses all hold, so $H$ is a group (an abelian group, since the definition is symmetric in $A$ and $B$ ). (A) is true and (B) is false.
Check (C): the complement $\overline{A} = X - A$ gives $A Δ \overline{A} = A \cup \overline{A} = X$ . This equals the identity $\emptyset$ only when $X = \emptyset$ . For example, with $X = {1}$ and $A = {1}$ , the complement is $\emptyset$ and $A Δ \emptyset = A \neq = \emptyset$ . So (C) is false in general.
Correct options: (A) and (D).

KEY IDEA

Symmetric difference is addition mod 2 on indicator vectors: $(2^{X}, Δ)$ is a group with identity $\emptyset$ , and every element is its own inverse because $A Δ A = \emptyset$ .

WATCH OUT FOR

Confusing the inverse with the complement. $A Δ \overline{A} = X$ , not $\emptyset$ , so the complement is not the inverse. Also, doubting associativity because the operation looks unusual.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 7 Groups questions, with notes

GATE 2023 CS Q.51: solution and answer

Answer and solution

More Groups questions