GATE CSE 2014 Set 2 | Question: 50

Question

Consider the following relation on subsets of the set $S$ of integers between $1$ and $2014$. For two distinct subsets $U$ and $V$ of $S$ we say $U\:<\:V$ if the minimum element in the symmetric difference of the two sets is in $U$.

Consider the following two statements:

• $S1$: There is a subset of $S$ that is larger than every other subset.
• $S2$: There is a subset of $S$ that is smaller than every other subset.

Which one of the following is $\text{CORRECT}$?

• A. Both $S1$ and $S2$ are true
• B. $S1$ is true and $S2$ is false
• C. $S2$ is true and $S1$ is false
• D. Neither $S1$ nor $S2$ is true

Comments

First take U={1,2,3,4} and V={1,2} (we can take any set other than ∅ and S)

why we cannot take  ∅ and s both are subset of s

---

For two distinct subsets U and V of S we say U<V if the minimum element in the symmetric difference of the two sets is in U :)

 

 

---

Very good question

Answer 1

Symmetric difference (SD) - suppose $A$ and $B$ are $2$ sets then symmetric difference of A and B is $(A-B)\cup(B-A) = (A\cup B)-(A\cap B).$

In question : U < V if the minimum element in the symmetric difference of the two sets is in U . Example: $\{1,2,3\} <\{2,3,4,5,6\}$ 

Symmetric difference is $\{1\} \cup \{4,5,6\}$.

Now Consider a smaller set. Suppose $S= \{1,2,3,4\}$

Now the given $2$ statements are about smallest and largest subset. So, considering set $S$ and $\emptyset$ (empty set) will be helpful.

First take $U = \{1,2,3,4\}$ and $V = \{1,2\}$ (we can take any set other than ∅ and S)

$SD = \{3,4\}$ $($just exclude the elements which are common in the $2$ sets$)$

Minimum element of $SD$ is $3$ which is in $U$  and if we observe carefully minimum element will always be in $U.$ Whatever the $V$ is.

So, according to the question $\{1,2,3,4\}$ is smaller than any other subset of $S.$ S2 is true.

Now consider 

$U=\emptyset$ and $V= \{1,2\}$ (we can take any subset of S)

$SD = \{1,2\}$

The symmetric difference will always be equal to $V.$ So minimum element of $SD$ will always exist in $V$ when $U$ is $\emptyset.$

So, according to the que, $\emptyset$ is greater than any other subset of $S.$ S1 is also true.

This is true even when  $S= \{1,2,3,\ldots,2014\}.$

So, answer is A. Both S1 and S2 are true

Comments

You can take V as $\phi$, but not S because U and V are distinct.

U $\Delta \space \phi$  = U. So the minimum of U and V will be in U.

@Akshara Nair

The answer has taken S(the universal set) as {1, 2, 3, 4}. So V = {1,2..,6} is invalid. 

 

---

The set S={1,2,3,…..,2014} is the smallest element as per the given relation and Null set is the largest set. 

---

Great explanation @Soumya29.

Answer 2

S1 seems satisfied by {L} where L is largest element in S, only until we compare it to {}, where symm. diff. is {L}. Now consider {}. Any other subset of S is smaller than {} as the minimum element in their symmetric difference will be in that set. So, {}, satisfies S1, any other subset should be less than it.

S2 on the other hand, will be satisfied by S, as any other subset will be like S-{some other elements}. So symm. diff. will be {some other elems}, which will belong in S, so min. elem. will belong in S. So, that's it - (A)

Comments

Distinct subset means at least one element must be different from all other subsets.

For eg. u ={2014} and v={1,2014} here both u and v are distinct subset .

---

Of course empty set {} is a distinct set/subset.

---

Thanks :)  mysticPrince for nice explanation.

Answer 3

According to the given information :

S1 is true because NULL set is smaller than every other set.

S2 is true because the UNIVERSAL set {1, 2, …, 2014} is larger than every other set.

 
Thus, both S1 and S2 are true.

Comments

Please see the definition of Larger and smaller given in the question.

In qs given that For two distinct subsets U and V of S we say U<V if the minimum element in the symmetric difference of the two sets is in U.

It is not based on the cardinality of the subset.

---

This answer is misleading

please remove it 

@Warrior right

 

Answer 4

Statement-1) is TRUE because { } > another subset because

           Let S1 denote any other subset of S other than { } 

           S1 - { } = S1 ... Now smallest element in set difference is nothing but smallest element in S1 .. So S1 < { } whatever subset you take for S1 apart from { }...

Statement-2) is TRUE because S > anyother subset of S other than S

           Let S2 be any other subset of S other than S

           S - S2 = some subset S3 of S ... Now Smallest element is nothing but element in S but not in S2 .. Since smallest element is from S ,  S < S2 whatever values you substitute for S2..

So Option A) is TRUE...

Comments

I think you should extend your answer to include symmetric difference. As of now it looks like set difference

---

Symmetric difference of x and y = all elements that's in x but not in y UNION all elements that's in y but not in x.