55 votes

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 CORRECT?

- Both $S1$ and $S2$ are true
- $S1$ is true and $S2$ is false
- $S2$ is true and $S1$ is false
- Neither $S1$ nor $S2$ is true

0

"if the minimum element in the symmetric difference of the two sets is in *U" *

Can someone explain what does this sentence mean ?

4

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.

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.

13

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 ....

1

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.

74 votes

Best answer

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 acc. 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 acc. 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**

0

@ Soumya29

" if we observe carefully minimum element will always be in U .Whatever the V is. "

what do u mean by this? but I think this not correct.

Say U={3,4} and V={1,2,3,4}

then minimum element 1 is in V

So, it the line " the minimum element in the symmetric difference of the two sets is in U" is not given in question, we can assume minimum element in V too.

Correct me if anything wrong

2

"Minimum element of **Symmetric Difference** will always be in U"

here i am taking U= S( given set) .

So suppose S= {1,2,3,4,5}

U= {1,2,3,4,5} , V= {1,2}

minimum element of S.D = 3 .

3 is in U.

You can take V=S. In that case , minimum element of S.D will always exist in V

0

then this statement " if we observe carefully minimum element will always be in U .Whatever the V is. " is incorrect

Say U={1,2,4,5} and V={1,2,3,7,8} then min element is in V

So, V cannot be take what ever we want.rt?

4

In this question it is asked about largest and smallest set.

so taking extreme cases are beneficial here..so I consider S(i.e the given set itself) and ∅ for proving the 2 statements.

Now for proving Statement 2 to be true-

I consider **U=S**.

and with respect to **this condition(i.e when U=S)** only this statement - "if we observe carefully minimum element will always be in U .Whatever the V is." is true.

U and V can be any subset of S but there is no point in taking other sets as ultimately we want to find where given statements are true or not.

hope you get it now :)

0

yes good :)

then we can say in question " if the minimum element in the symmetric difference of the two sets is in U" is at all not required.

Without this line we can get same solution. rt?

then we can say in question " if the minimum element in the symmetric difference of the two sets is in U" is at all not required.

Without this line we can get same solution. rt?

0

I could not understand that how ∅ is greater than all subsets.. It looks to me that the set S itself is smaller as well as greater than all the subsets as per definition given because both the smaller as well as larger element will be present in U itself when U=S. Please clarify,

2

For the sake of clarification,i think in the explanation of S1. the answer says:-

U= {∅} And V= {1,2} (we can take any subset of S)

But i think ,the terminology of U and V is swapped in question,it should be:

V= {∅} And U= {1,2} (we can take any subset of S)

0

I think symmetric difference of sets is just given for no reason (V and U definitions). This can be solved without it.

Just take a normal set S and solve it as the statements suggest.

Just take a normal set S and solve it as the statements suggest.

0

@soumya

U = $\phi$ ( $\phi$ is the subset of S)

or

U = {$\phi$} ?? ( $\phi$ is not the element of S)

U = $\phi$ ( $\phi$ is the subset of S)

or

U = {$\phi$} ?? ( $\phi$ is not the element of S)

0

@soumya

take a set

$U=\left \{ 1,2,7 \right \}$ and $V=\left \{ 1,2,3,9 \right \}$

then minimum element in the symmetric difference will be in V na?

0

Yes.. In your example, the smallest element of symmetric difference is 3 which is in V. So V is smaller than U.

Similarly in V= {∅} And U= {1,2} . 1 is smallest element of SD which is U so U<V.

Similarly in V= {∅} And U= {1,2} . 1 is smallest element of SD which is U so U<V.

2

how {1,2,3,4} is smaller than any other subset of *S*, it should be greater r8 ?

we are talking greater, smaller wrt set size or something else ? please clarify.

if we are talking about set size,

then **{1,2,3,4}** should be greater and** ∅ **ahould be smaller ?

how am i wrong !!

0

@Soumya29

I think for proving S1 to be true you should take V=ϕ and U={1,2}(It can be any subset Of S other than ϕ and S), then ur point of proving ϕ will be larger than any other element will be correct.

0

Sir, please anyone explain this

how {1,2,3,4} is smaller than any other subset of

S, it should be greater rt?, ∅ is greater than any other subset of S. isn't smaller ?

0

When U=S AND V=S

then SD will be empty set and minimum of empty set is nothing. Then how can we say that this is present in both.

then SD will be empty set and minimum of empty set is nothing. Then how can we say that this is present in both.

31 votes

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)

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)

0

Can someone explain how are we comparing { } Null set with anything?

Example:- U={} V={1,2,3...2014}

Is Symmetric difference={ {} union 1,2,3...2014} in which minimum element is {} ie, i U set

Example:- U={} V={1,2,3...2014}

Is Symmetric difference={ {} union 1,2,3...2014} in which minimum element is {} ie, i U set

0

The union of *A* with the empty set is *A*:

now here the minimum element belongs to v set thats why v subset would be larger than every other subset of s and if take any other subset rather than empty set for example U = {1,2} and V = {2,3,4}

then their symmetric difference will come out to be {1,3,4} where min belongs to U which would be smaller than any other subset correct if i am wrong is it every other subset or any other ?

10 votes

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.

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.

4 votes

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...