Relation – GATE CSE Engineering MathematicsPractice Questions & PYQs

For a binary relation $R$ on $A=\{1, 2, 3, 4\}$ to be reflexive, $(x, x) \in R$ must hold for all $x \in A$. Since $(4, 4) \notin R$, the relation is not reflexive.
For a relation to be irreflexive, $(x, x) \notin R$ must hold for all $x \in A$. Since $(1, 1), (2, 2), (3, 3) \in R$, the relation is not irreflexive.
A relation is transitive if $(x, y) \in R$ and $(y, z) \in R$ implies $(x, z) \in R$ for all $x, y, z \in A$.
Checking compositions, such as $(2, 3) \in R$ and $(3, 4) \in R$ implies $(2, 4) \in R$, or $(3, 2) \in R$ and $(2, 1) \in R$ implies $(3, 1) \in R$, all resulting pairs exist within $R$.
Thus, the relation is transitive.
Therefore, the relation is neither reflexive nor irreflexive, but it is transitive.

An equivalence relation $R$ on a set $A$ is defined as a subset of the Cartesian product $A \times A$.
Given that $|A| = n$, the total number of elements in the Cartesian product $A \times A$ is $n \cdot n = n^2$.
The largest possible relation on $A$ is the universal relation $R = A \times A$, which contains all possible ordered pairs $(a, b)$ where $a, b \in A$.
This universal relation is reflexive, symmetric, and transitive, satisfying all requirements to be an equivalence relation.
Since this relation comprises all possible pairs in $A \times A$, the number of elements in the largest equivalence relation is $n^2$.

The number of equivalence relations on a set with $n$ elements is equal to the Bell number $B_n$, which represents the total number of ways to partition the set.
For $n=4$, we determine $B_4$ using the recurrence formula $B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$, starting with $B_0 = 1$.
We calculate the sequence $B_1 = 1$, $B_2 = 2$, and $B_3 = 5$.
Substituting these values to calculate $B_4$ yields:
$B_4 = \binom{3}{0}B_0 + \binom{3}{1}B_1 + \binom{3}{2}B_2 + \binom{3}{3}B_3 = 1(1) + 3(1) + 3(2) + 1(5) = 15$
Thus, there are $15$ distinct equivalence relations for the set $\{1, 2, 3, 4\}$.

The relation is defined as $A R B \iff A \cap B = \phi$.

1. Symmetry: Because the intersection of sets is commutative, $A \cap B = B \cap A$. Therefore, $A \cap B = \phi \iff B \cap A = \phi$, which implies $A R B \iff B R A$, so $R$ is symmetric.
2. Reflexivity: $A R A \iff A \cap A = \phi$, which only holds if $A = \phi$. Since the collection contains non-empty sets, $R$ is not reflexive.
3. Transitivity: Consider sets $A=\{1\}, B=\{2\}, C=\{1\}$. We have $A \cap B = \phi$ and $B \cap C = \phi$, meaning $A R B$ and $B R C$ are true. However, $A \cap C = \{1\} \neq \phi$, so $A R C$ is false. Thus, $R$ is not transitive.
4. Consequently, $R$ is symmetric and not transitive.

A relation $R$ on a set $A$ is symmetric if $aRb \implies bRa$ and transitive if $aRb \land bRc \implies aRc$.
For $R$ to be reflexive, we must have $aRa$ for all $a \in A$.
Consider the empty relation $R = \emptyset$ on a non-empty set $A = \{1, 2\}$.
This relation is vacuously symmetric and transitive, but it is not reflexive because $(1, 1) \notin R$.
Since symmetry and transitivity do not guarantee reflexivity, $R$ is not necessarily an equivalence relation or a partial order.
Consequently, options A, B, and C are incorrect as they require $R$ to be reflexive.

A partial ordering is defined as a relation that is reflexive, antisymmetric, and transitive. The relation $\lt$ on the set of real numbers is irreflexive because $x \lt x$ is false for all $x \in \mathbb{R}$. While the relation $\lt$ is transitive and (vacuously) antisymmetric, it fails the reflexivity requirement necessary for a partial ordering. Options A and B are incorrect because they label the relation as a partial ordering. Option C incorrectly claims it is not asymmetric, and option D incorrectly claims it is not antisymmetric. Thus, none of the provided reasons accurately describe the classification, making the target answer E.