in Set Theory & Algebra edited by
2,053 views
11 votes
11 votes

Suppose $(S_{1}, S_{2},\ldots,S_{m})$ is a finite collection of non-empty subsets of a universe $U.$ Note that the sets in this collection need not be distinct. Consider the following basic step to be performed on this sequence. While there exist sets $S_{i}$ and $S_{j}$ in the sequence, neither of which is a subset of the other, delete them from the sequence, and 

  1. If $S_{i}\cap S_{j}\neq \emptyset $, then add the sets $S_{i}\cup S_{j}$ and $S_{i}\cap S_{j}$ to the sequence;
  2. If $S_{i}\cap S_{j} = \emptyset$, then add only the set $S_{i}\cup S_{j}$ to the sequence.

In each step we delete two sets from the sequence and add at most two sets to the sequence. Also, note that empty sets are never added to the sequence. Which of the following statements is TRUE?

  1. The size of the smallest set in the sequence decreases in every step
  2. The size of the largest set in the sequence increases in every step
  3. The process always terminates
  4. The process terminates if $U$ is finite but might not if $U$ is infinite
  5. There is a finite collection of subsets of a finite universe $U$ and a choice of $S_{i}$ and $S_{j}$ in each step such that the process does not terminate
in Set Theory & Algebra edited by
2.1k views

4 Comments

@Soumya29 

Actually when I tried some paperwork , I get to know that we are performing either Intersection Or Union so eventually we will end up forming sets which are same or mutually subsets so it will terminate.

0
0

Thnx @HeadShot for pointing it out :)

1
1
If someone knows the answer of this question, please provide answer with full explanation (I didn't able to understand the answer provided by Arjun sir). Thank you
0
0

3 Answers

3 votes
3 votes
Best answer

There are $m$ sets in the initial sequence. If we pick two sets $S_i$ and $S_j$ NEITHER of which are subsets of each other we add

  1. $S_i \cup S_j$
  2. $S_i \cap S_j$ if it is not NULL.

So, the two added sets are not eligible to be picked as a pair as INTERSECTION is always a subset of UNION. So, in each step we are removing a pair of eligible sets. But the addition of set(s) can cause more eligible pairs to be created. 

With $m$ sets we can only have ${}^mC_2$ pairs possible. So, if we repeat the procedure for ${}^mC_2$ times, and number of times $S_i \cap S_j = \phi$ is $k,$

  • Number of sets reduces by $k$
  • Number of ineligible pairs will be $\geq {}^mC_2 -k$
  • Number of possible eligible pairs $ \leq {}^{m-k}C_2 - \left({}^mC_2 -k\right)$
    $ \implies \frac{(m-k) (m-k-1)} {2}- \frac{m(m-1)}{2} + k$
    $= \frac{m^2-mk-m-mk+k^2+k-m^2+m}{2}+k$
    $ = \frac{k^2-2mk+k}{2} + k $
    $= k\left[ \frac{k-2m+1}{2}+1\right]$
    Maximum value of $k$ is $m$. If we put $k = m$ we get
    $m\left[ \frac{m-2m+1}{2}+1\right] = \frac{-m^2}{2}+\frac{3m}{2} \leq 0$ for $m \geq 3$
  • i.e., for all $m \geq 3$ after some finite moves we are left with $0$ eligible pairs to choose. 
  • For $m=1$ since there are no eligible pairs, process cannot start. For $m=2$ there can be maximum one eligible pair and after one step this must reduce to no eligible pairs.
  • So, the process always terminates.
  • PS: Even if each of the sets is infinite it won't affect the termination of the process.

Option C.

selected by
by

4 Comments

Suppose, there are two sets $S_{i}=\left \{ 1,2,3 \right \}$ and $S_{j}=\left \{ 1,2 \right \}$, then how will the process terminate??
0
0

@ Arjun sir, please explain below lines, it seems difficult to understand for me.

0
0
number of eligible pairs=tol-ineligible
0
0
0 votes
0 votes

The Answer should be $E$.

Let's say my Universe consist of only two elements $\{1,2\}$ and I define two subsets $s_1 = \{1\}, s_2 = \{1,2\}.$ And Sequence $S = s_1s_2 = \{1\}\{1,2\}$.

Initially - $\{1\}\{1,2\}$
$Step \ 1$ - $\{1,2\}\{1\}$

$S_1 \cap S_2$ is not null so we delete these two sets and add $S_1 \cup S_2$ which will be = $\{1,2\}$ and there intersection which will be = $\{1\}$. Now we got the same sets in the sequence again. If we again do the same procedure then again we get the same set. So only Option E matches.

$Step \ 2$ - $\{1\}\{1,2\}$
$Step \ 3$ - $\{1,2\}\{1\}$
$\vdots$

A is false likewise B because the size of smallest and largest set is constant in every step. Infact smallest set and largest set can change in any step.

Note that as soon as we find 2 consecutive sets in the sequence such that one is the subset of other, they will get repeated again and again and the process never terminates.
So C and D are false.

edited by
by

4 Comments

Oh yes typing mistake. Edited :)
0
0

@Soumya29

Say, sets are $U=\left \{ 1 \right \},\left \{ 1,2 \right \},\left \{ 1,2,3 \right \}$

then where will be infinite number of sets? Why will it be not terminate?

0
0

See these two lines of question: 

While there exist sets Si and Sj in the sequence, neither of which is a subset of the other, delete them from the sequence, 

 

ii)If Si∩Sj=∅, then add only the set Si∪Sj to the sequence.

Is not these two lines contradictory?

Say sets are $U=\left \{ 1 \right \},\left \{ 2 \right \},\left \{ 1,2 \right \},\left \{ 1,2,3 \right \}$

Now, here $\left\{ 1 \right \},\left \{ 2 \right \}$ not subset of each other. So, delete both,as a pair?

Remaining $U$ is $\left \{ 1,2 \right \},\left \{ 1,2,3 \right \}$

Now what to add?

I havenot got it.


Another example

Say $U$ is $U=\left \{ 1 \right \},\left \{ 1,2 \right \},\left \{ 1,2,3 \right \},\left \{ 1,2,3,4 \right \},...........\left \{ 1,2,3,4,5,..............\infty \right \}$, the also need to check infinite times. So, then this problem also goes upto infinite.

right??

0
0
0 votes
0 votes

Option D

While there exist sets Si and Sj in the sequence, "neither of which is a subset of the other," delete them from the sequence

read the bold part again, we delete sets iff neither of two is a subset of the other.

Hence the process must terminate if U is finite.

by

2 Comments

And why it does not terminate if $U$ is infinite?
0
0

See these two lines of question: 

While there exist sets Si and Sj in the sequence, neither of which is a subset of the other, delete them from the sequence, 

 

ii)If Si∩Sj=∅, then add only the set Si∪Sj to the sequence.

Is not these two lines contradictory?

Say sets are $U=\left \{ 1 \right \},\left \{ 2 \right \},\left \{ 1,2 \right \},\left \{ 1,2,3 \right \}$

Now, here $\left\{ 1 \right \},\left \{ 2 \right \}$ not subset of each other. So, delete both,as a pair?

Remaining $U$ is $\left \{ 1,2 \right \},\left \{ 1,2,3 \right \}$

Now what to add?

I havenot got it.


Another example

Say $U$ is $U=\left \{ 1 \right \},\left \{ 1,2 \right \},\left \{ 1,2,3 \right \},\left \{ 1,2,3,4 \right \},...........\left \{ 1,2,3,4,5,..............\infty \right \}$, the also need to check infinite times. So, then this problem also goes upto infinite.

right??

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