The Gateway to Computer Science Excellence
+50 votes
4.9k views

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?

  1. Both $S1$ and $S2$ are true
  2. $S1$ is true and $S2$ is false
  3. $S2$ is true and $S1$ is false
  4. Neither $S1$ nor $S2$ is true
in Set Theory & Algebra by Veteran (105k points)
edited by | 4.9k views
+2
can we take U as ∅ (empty set)?
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.
+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.

Image result for symmetric difference

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.

 

5 Answers

+60 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

by Boss (16.3k points)
edited by
0
Nicely explained.
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
ok , but if we take U=S and also V=S

then smaller element lies in which set? :)
+1
Then there will be no smallest element. S.D wil be  ∅ .. which is present in both the sets. :)
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?
+1
ryt :)
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.
0
@soumya

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

or

U = {$\phi$}   ??     ( $\phi$ is not the element of S)
+1
@Hemant
It should be-
U = ϕ      ( ϕ is the subset of S)
I'll edit it. Thanks :)
0
@rahul

if V= {∅} And U= {1,2} then for the question U<V doesnot work
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.
0
So can we conclude that the smallest element that can satisfy both the statements is  ∅ ?
+1

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 andahould be smaller ?

how am i wrong !!

0
i got it :)
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

@Shaik Masthan 

@abhishekmehta4u 

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 ?

 

+30 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)
by Junior (675 points)
+1
can we say an empty set is a distinct set .?
0
what is the meaning of symetric difference of the two sets
+4
If P and Q are sets then symetric difference of P and Q is
(P union Q)  minus (P intersection U)
0
Can someone exlain it taking an example ?
0
what if both the subsets contain the largest element 2014??
0
For two distinct subsets U and V, can distinct subsets have some elements in common?
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
0

The union of A with the empty set is A:

\forall A:A\cup \emptyset =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 ?

0
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 .
0
Of course empty set {} is a distinct set/subset.
0

Thanks :)  mysticPrince for nice explanation.

+8 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.
by Loyal (5.7k points)
+6
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.
+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...

by Loyal (8k points)
+1
I think you should extend your answer to include symmetric difference. As of now it looks like set difference
0
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.
–2 votes

  The correct option is ,(A)Both S1 and S2are true

by Loyal (8k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
198,265 comments
104,979 users