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

can we take U as ∅ (empty set)?

---

"if the minimum element in the symmetric difference of the two sets is in U"
Can someone explain what does this sentence mean ?

---

It means for example-

U={1,2,3,4 }

V={2,6,9,100}

Symmetric Difference of U and V is (1,9,100).

The minimum element in the above symmetric diff is 1 which belongs to U.

---

The symmetric difference of two sets A and B is the set(A – B) ∪ (B – A) and is denoted by A △ B ... i think its nt the right result of ur assumption ....

---

How to approach?

Meaning of symmetric difference: We will have elements not common in U or V.

Source: https://www.math-only-math.com/symmetric-difference-using-Venn-diagram.html

we say U<V if the minimum element in the symmetric difference of the two sets is in U.
So V can have smallest element among U and V only if they are common to both V and U. 

S1: There is a subset of S that is larger than every other subset.

Suppose we start with V ={some number between 1-2014 say 10}

There will be U for which  U < V will violate like U having no elements smaller than 10.

Suppose we try with V = { } ( empty set).

U < V will always hold as symmetric difference will be U. 

See this: https://cs.stackexchange.com/questions/93228/symmetric-difference-of-a-set-with-an-empty-set

S2: There is a subset of S that is smaller than every other subset.

$S Δ$ any set => minimum will always come from S. Why? Δ cancels out common element and whatever is left will be coming from S only as other set will always be subset of S and hence will disappear after Δ.

How to know that we have to try with edge cases like S and empty set? You can know with practice and in these kind of question you should start with such cases as many statements which otherwise appear to be true may fail for such cases or statements like "this is never satisfied" will be satisfied for such cases.

 

---

Symmetric difference is like XOR.

---

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.