The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+37 votes
3.2k 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
asked in Set Theory & Algebra by Veteran (112k points)
edited by | 3.2k 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 ?

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

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

5 Answers

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

answered by Boss (14.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

0

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

+3

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,
+1

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  ∅ ?
0

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 :)
+27 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)
answered by Junior (617 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.
answered by Active (4.7k points)
+4
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...

answered by Loyal (7.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

answered by Loyal (7.2k 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

44,459 questions
49,916 answers
165,421 comments
65,897 users