GATE Overflow Test Series | Discrete Mathematics | Test 1 | Question: 16

Question

Let $P(X)$ be the collection of all the subset of a set $X$ with at least three elements. Consider the following two relations on $P(X):$

• $R:A \subseteq B$
• $S: A \cap B = \phi$.

Which of the following is true about relations $R$ and $S?$

• A. $R$ is anti-symmetric but $S$ is not anti-symmetric.
• B. $R$ is not anti-symmetric but $S$ is anti-symmetric.
• C. Both $R$ and $S$ are anti-symmetric
• D. None of these

Comments

The question fails to mention what A and B are. Kindly clarify.

---

R and S being relations on P(X), implies that A and B are elements of P(X).

Answer 1

Condition for an anti-symmetric relation $R$ is $aRb$ and $bRa \implies a = b.$
$A \subseteq B$ and $B \supseteq A\implies A = B$
So, $R$ is anti-symmetric.

$A$ disjoint from $B$ and $B$ disjoint from $A,$ does not imply that $A = B.$
So $S$ is not anti-symmetric. $A$ disjoint from $B$ implies that $B$ disjoint from $A.$ So, this relation is symmetric.

Comments

OK got it. Thnks

---

@Himanshu_Devrani

condition of three elements is on original set X and not P(X).

"P(X) be the collection of all the subset of a set X  with at least three elements"

condition is on X.

Logically also we cant have condition directly on P(X), it would be more appropriate to say Subset S of P(X) which have elements with cardinality more than 3.

---

@Godlike

ohh my bad thankss ….

Answer 2

$P(X)$ be the collection of all the subset of a set $X$ with at least three elements.

Lets take $X=\{1,2,3\},\;P(X) = \{\phi,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

$R:A\subseteq B\;\text{(Satisfied)}$

Lets take $A = \{a,b,c\}, B=\{a,b,c\}$

Now, Reflexive relation$:A$ relation $\sim\;\text{on}\; A $ is reflexive if $\forall a \in A \quad a \sim a.$

$A \subseteq A\;\text{(always true)}$

Equality is a reflexive relation. Everything is equal to itself.

Symmetric relatrion$:A$ relation $\sim\;\text{on}\; A$ is said to be symmetric, if $\forall a,b \in A \quad a\sim b \implies b \sim a.$

Here, $A \subseteq B \implies B\subseteq A \;\text{(Symmetric)}$

and, $(A\subseteq B) \wedge (B\subseteq A) \implies A = B\;\text{(Anti-symmetric)}$

So, for above instance both are symmetric and anti-symmetric.

Again, lets take $A = \{a,b\}, B=\{a,b,c\}$

Symmetric relatrion$:A$ relation $\sim\;\text{on}\; A$ is said to be symmetric, if $\forall a,b \in A \quad a\sim b \implies b \sim a.$

Here, $A \subseteq B \implies B\nsubseteq A \;\text{(Not symmetric, but it is anti-symmetirc)}$

So, $R$ is antisymmetric.

Now, consider $S:A \cap B = \phi$

Only one case is possible, $A = \{a,b\},\;B=\{1,2\}$

For anti-symmetric relation$:(A\cap B) \wedge (B\cap A) \implies A = B\;\text{(Not anti-symmetric)}$

$\text{(OR)}$

$A \cap B \implies B \cap A$

$\phi \implies \phi\;\text{(Symmetric)}$

So, the correct answer is $(A).$