What are common examiner traps in Sets, Relations, Lattices and Groups?

Confusing 'proper subgroup' with any subgroup (including G itself, leading to returning |G| instead of |G|/2). Assuming the converse of Lagrange's theorem holds generally without qualification. Incorrectly assuming non-abelian groups can have abelian subgroups or vice-versa (a subgroup of an abelian group must always be abelian). Failing to apply cancellation laws correctly when working with non-commutative group identities. Assuming generators do not commute and calculating an infinite or arbitrarily large number of words without simplifying (xy)2 = e. Double counting elements by failing to reduce alternating words (e.g., counting xyx as distinct from y). Forgetting the identity element e = x0 y0 when enumerating group elements. Assuming inverses exist without checking if the inverse mapping stays within the defined codomain (e.g., non-negative integers requiring negative inverses) Confusing the inverse of a set under symmetric difference (which is the set itself) with its complement Overlooking the proper subgroup condition (L G) when listing subgroup order divisors under Lagrange's theorem Assuming direct images distribute over intersections: f(A B) = f(A) f(B) is false in general unless f is injective. Assuming |f(A B)| = |f(A)| + |f(B)| while forgetting that f(A) and f(B) may overlap even if A and B are disjoint. Overlooking self-pair restrictions (e.g., 'distinct elements' automatically forces irreflexivity despite satisfying the algebraic condition). Testing reflexivity on pairs ((p,q),(p,q)) by assuming p=q holds universally instead of testing for arbitrary p q. Assuming distributivity is symmetric (i.e., assuming if distributes over , then distributes over ). Evaluating associativity without applying operator precedence correctly from innermost parentheses to outermost. Confusing the role of operands when an asymmetric operator like a b = a + 2b is nested.

Sets, Relations, Lattices and Groups

11 Qs · since 2014 · 17 marks · 0.7 marks/paperStandard yield

Take topic test

In GATE CS, questions on sets, relations, and functions test formal mathematical rigor through algebraic verification of binary relation properties (reflexivity, symmetry, transiti… Guide

Type

GATE CSE 2025 Set 1Q49MSQ2 marksMedium $A = \{0, 1, 2, 3, \dots\}$ is the set of non-negative integers. Let F be the set of functions from $A$ to itself. For any two functions, $f_1, f_2 \in \text{F}$ , we define $(f_1 \odot f_2)(n) = f_1(n) + f_2(n)$ for every number $n$ in $A$ . Which of the following is/are CORRECT about the mathematical…
GATE CSE 2024 Set 1Q52MSQ2 marksEasyConsider the operators $\Diamond$ and $\square$ defined by $a \Diamond b = a + 2b$ , $a \square b = ab$ , for positive integers. Which of the following statements is/are TRUE?
GATE CSE 2023Q51MSQ2 marksMediumLet $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?
GATE CSE 2022Q27MSQ1 markEasyWhich of the following statements is/are TRUE for a group $G$ ?
GATE CSE 2018Q19NAT1 markEasyLet $G$ be a finite group on 84 elements. The size of a largest possible proper subgroup of $G$ is ________.
GATE CSE 2016 Set 1Q28NAT2 marksHardA function $f : \text{N}^+ \to \text{N}^+$ , defined on the set of positive integers $\text{N}^+$ , satisfies the following properties: $f(n) = f(n/2) \quad \text{if } n \text{ is even}$ $f(n) = f(n+5) \quad \text{if } n \text{ is odd}$ Let $R = \{i \mid \exists j : f(j) = i\}$ be the set of distinct values…
GATE CSE 2015 Set 2Q16MCQ1 markEasyLet $R$ be the relation on the set of positive integers such that $aRb$ if and only if $a$ and $b$ are distinct and have a common divisor other than 1. Which one of the following statements about $R$ is true?
GATE CSE 2015 Set 3Q41MCQ2 marksMediumLet $R$ be a relation on the set of ordered pairs of positive integers such that $((p,q),(r,s)) \in R$ if and only if $p - s = q - r$ . Which one of the following is true about $R$ ?
GATE CSE 2014 Set 3Q2MCQ1 markMediumLet $X$ and $Y$ be finite sets and $f: X \rightarrow Y$ be a function. Which one of the following statements is $\textbf{TRUE}$ ?
GATE CSE 2014 Set 3Q3NAT1 markEasyLet $G$ be a group with 15 elements. Let $L$ be a subgroup of $G$ . It is known that $L \neq G$ and that the size of $L$ is at least 4. The size of $L$ is _______.
GATE CSE 2014 Set 3Q50NAT2 marksMediumThere are two elements $x, y$ in a group $(G, *)$ such that every element in the group can be written as a product of some number of x's and y's in some order. It is known that $x * x = y * y = x * y * x * y = y * x * y * x = e$ where $e$ is the identity element. The maximum number of elements in such a group…

Topic guide

What does GATE test in Sets, Relations, Lattices and Groups?

In GATE CS, questions on sets, relations, and functions test formal mathematical rigor through algebraic verification of binary relation properties (reflexivity, symmetry, transitivity), set-theoretic properties of direct and inverse images of functions, and state-reachability or partition analysis on integer domain functions. The questions range from conceptual 1-mark MCQs on standard definitions and counterexamples to 2-mark algebraic or NAT problem-solving items involving equivalence classes and modular cycles.

Core concepts

Lagrange's Theorem and orders of subgroups
Proper subgroups vs improper subgroups
Abelian (commutative) groups and algebraic criteria for commutativity
Cyclic groups and groups of prime order
Inheritance of commutativity to subgroups
Generators and relations (Group presentations)
Self-inverse elements (Involutions / elements of order 2)
Commutativity derivation in groups
Klein four-group structure (V4 Z2 Z2)
Canonical forms of generated words in groups
Monoid vs Group definitions (existence of inverse element)
Abelian vs Non-Abelian properties (commutativity)
Lagrange's Theorem on subgroup orders
Identity and Inverse elements in power set Boolean groups
Domain and codomain closure restrictions for function spaces
Equivalence relations and relational properties (reflexive, symmetric, transitive, irreflexive)
Relations over product sets (A B)
Preimage vs direct image under general functions
Connected components and equivalence classes on discrete state spaces
Number-theoretic properties (GCD, divisibility, modular arithmetic) in relation definitions
Binary Operations
Associative Property
Distributive Property of one binary operation over another
Algebraic structures on positive integers

Recurring question patterns

Subgroup Order Bounds via Lagrange's Theorem
occasional · NAT · 1 marks · 2018
Given the finite order of a group $|G|$ , determine the maximum possible size of a proper subgroup (or possible subgroup orders) using Lagrange's theorem.
Abelian / Group Property Verification
occasional · MSQ · 1 marks · 2022
A collection of algebraic identities, element orders, or subgroup inheritance statements where candidates verify whether each condition implies commutativity or holds true for all groups.
Group Presentation and Cardinality Bounding
rare · NAT · 2 marks · 2014
Given a set of generators and algebraic relation equations (e.g., $x^2 = y^2 = (xy)^2 = e$ ), algebraically derive the commutativity of generators and reduce any arbitrary word in the generators to a canonical form to find the maximum possible order of the group.
Algebraic Structure Classification
common · MSQ · 2 marks · 2025, 2023
Given a set (e.g., function sets, power sets) and an operation (e.g., pointwise addition, symmetric difference), verify closure, associativity, commutativity, identity existence, and inverse existence to classify the structure as a semigroup, monoid, Abelian monoid, group, or Abelian group.
Subgroup Order Divisibility via Lagrange's Theorem
occasional · NAT · 1 marks · 2014
Given the order of a finite group and bounds or conditions on a proper subgroup, determine the exact size/order of the subgroup using Lagrange's Theorem.
Relation Property Verification
common · MCQ · 1.5 marks · 2015
A relation is defined on integers or ordered pairs via an algebraic equation or number-theoretic condition (e.g., GCD, difference equations). Students must verify whether the relation satisfies reflexivity, symmetry, and/or transitivity.
Direct and Inverse Image Set Identities
occasional · MCQ · 1 marks · 2014
Questions evaluating true/false statements regarding how functions interact with set operations (unions, intersections, preimages, and cardinalities).
Equivalence Partitioning and Function Range Analysis
occasional · NAT · 2 marks · 2016
A function on positive integers is defined piecewise via recurrence-like equivalences. Students must analyze domain reachability or connected components modulo certain bases to determine the maximum size of the function's range.
Algebraic Properties of Custom Binary Operations
common · MSQ · 2 marks · 2024
Two binary operations are defined over a set (such as positive integers). Candidates must verify whether the operations satisfy associativity and whether one operation distributes over the other.

Formulas GATE uses

Lagrange's Theorem

|H| \text{ divides } |G|

Determining possible sizes of subgroups $H$ of a finite group $G$ .

Maximum Proper Subgroup Size

\max(|H|) = \frac{|G|}{p_{\min}}

Finding the largest proper subgroup size, where $p_{\min}$ is the smallest prime factor dividing $|G|$ .

Self-Inverse Commutativity Identity

\forall x \in G, x^2 = e \implies x = x^{-1} \implies xy = (xy)^{-1} = y^{-1}x^{-1} = yx

Proving that a group in which every non-identity element has order 2 is abelian.

Exponential Distribution Commutativity Identity

\forall x,y \in G, (xy)^2 = x^2 y^2 \iff xyxy = xxyy \iff yx = xy

Proving commutativity using left/right cancellation laws.

Canonical Word Form Reduction

g = x^a y^b \quad \text{where } a, b \in \{0, 1\}

Used when generators commute ( $xy = yx$ ) and have order 2 ( $x^2 = e, y^2 = e$ ) to enumerate all distinct group elements.

Commutativity Derivation from Involutions

(xy)^2 = e \implies xyxy = e \implies yx = x^{-1}y^{-1} = xy

Used to show generators commute when each generator is self-inverse ( $x = x^{-1}, y = y^{-1}$ ).

Symmetric Difference Definition

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

Used when defining operations on the power set $2^X$ to check group axioms (where $\emptyset$ is identity and $A^{-1} = A$ ).

Pointwise Operation on Function Spaces

(f_1 \odot f_2)(n) = f_1(n) + f_2(n)

Used to define binary operations on sets of functions $F = \{f : A \to A\}$ .

Preimage Intersection Preservation

f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)

Used when evaluating whether inverse image maps distribute over intersection without requiring injectivity.

Forward Image Intersection Inclusion

f(A \cap B) \subseteq f(A) \cap f(B)

Used when analyzing the failure of equality for direct images under non-injective functions.

Reflexive Relation Criterion

\forall x \in S, (x, x) \in R

Used to test if all elements in the base set are related to themselves.

Symmetric Relation Criterion

\forall x, y \in S, (x, y) \in R \implies (y, x) \in R

Used to determine whether relation order can be inverted universally.

Transitive Relation Criterion

\forall x, y, z \in S, ((x, y) \in R \land (y, z) \in R) \implies (x, z) \in R

Used to check chained relational reachability.

Associative Law

(a \ast b) \ast c = a \ast (b \ast c)

Used to check if an operator $\ast$ is associative over a given domain.

Distributive Law (Left Distributivity)

a \ast (b \circ c) = (a \ast b) \circ (a \ast c)

Used to verify whether operator $\ast$ distributes over operator $\circ$ .

Examiner traps in Sets, Relations, Lattices and Groups

Confusing 'proper subgroup' with any subgroup (including G itself, leading to returning |G| instead of |G|/2).
Assuming the converse of Lagrange's theorem holds generally without qualification.
Incorrectly assuming non-abelian groups can have abelian subgroups or vice-versa (a subgroup of an abelian group must always be abelian).
Failing to apply cancellation laws correctly when working with non-commutative group identities.
Assuming generators do not commute and calculating an infinite or arbitrarily large number of words without simplifying (xy)2 = e.
Double counting elements by failing to reduce alternating words (e.g., counting xyx as distinct from y).
Forgetting the identity element e = x0 y0 when enumerating group elements.
Assuming inverses exist without checking if the inverse mapping stays within the defined codomain (e.g., non-negative integers requiring negative inverses)
Confusing the inverse of a set under symmetric difference (which is the set itself) with its complement
Overlooking the proper subgroup condition (L G) when listing subgroup order divisors under Lagrange's theorem
Assuming direct images distribute over intersections: f(A B) = f(A) f(B) is false in general unless f is injective.
Assuming |f(A B)| = |f(A)| + |f(B)| while forgetting that f(A) and f(B) may overlap even if A and B are disjoint.
Overlooking self-pair restrictions (e.g., 'distinct elements' automatically forces irreflexivity despite satisfying the algebraic condition).
Testing reflexivity on pairs ((p,q),(p,q)) by assuming p=q holds universally instead of testing for arbitrary p q.
Assuming distributivity is symmetric (i.e., assuming if distributes over , then distributes over ).
Evaluating associativity without applying operator precedence correctly from innermost parentheses to outermost.
Confusing the role of operands when an asymmetric operator like a b = a + 2b is nested.

How questions are asked

Identify true/false theoretical statements about abelian groups and subgroup properties (MSQ)
Calculate the maximum/minimum possible order of a proper subgroup or cyclic subgroup (NAT)
Numerical calculation of maximum group order from generator relations
Classify mathematical structure (MSQ)
Identify inverse and group properties of set-theoretic operations (MSQ)
Determine subgroup size from given constraints and order (NAT)
Truth evaluation of set-theoretic function identities (MCQ)
Property identification of relations on integers or product sets (MCQ)
Finding the maximum size of a function's range via component reduction (NAT)
Multiple-choice / Multiple-select evaluation of algebraic properties for custom operations

Paper trends

Shift from single numerical bounds computed via standard divisor arithmetic (NAT) to multi-statement conceptual verification checking several group-theoretic lemmas in one question (MSQ).
2022, 2018
Appeared as a 2-mark NAT question testing abstract group relations and generation of the Klein four-group structure.
2014
Shift from direct 1-mark numerical questions on Lagrange's Theorem to 2-mark MSQs verifying multiple structural properties (identity, inverse validity, commutativity) on abstract algebraic sets.
2025, 2023, 2014
Relation verification questions evolved from simple 1D number-theoretic constraints on integers to relations defined over Cartesian pairs $\mathbb{N} \times \mathbb{N}$ with higher mark weight.
2015
Introduction of NAT format testing function equivalence classes and range cardinalities through Collatz-like state transitions.
2016
Introduction of 2-mark MSQ questions assessing multiple independent algebraic properties (associativity, distributivity) across custom-defined binary operators.
2024

Difficulty notes

Easy items test standard properties like $(xy)^2 = x^2 y^2 \implies xy = yx$ , basic prime order groups, or direct application of Lagrange's theorem. Medium items involve non-trivial element orders, cyclic generators, cosets, or modular arithmetic groups. Hard items require combining homomorphisms, kernel properties, or specific non-abelian group structures (like $D_n$ or $S_n$ ).