0
$\begingroup$

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 

i)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;

ii)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?

A)The size of the smallest set in the sequence decreases in every step.

B)The size of the largest set in the sequence increases in every step.

C)The process always terminates.

D)The process terminates if $U$ is finite but might not if $U$ is infinite.

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


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?? So, Ans will be D) Am I right? Can someone can prove it with induction? So that C) also possible as per Problems on finite collection of non-empty subsets of a universe link

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Upon removing all the subsets that are not one a subset of the other, a possibility empty nest of some of the subsets remains.
A nest is a collection of subsets that is linearly ordered by the subset relation.
Thus property ii is vacuous.
In addition property i does nothing.
Finite or infinite, the result is a not unique nest of some of the original sets.

$\endgroup$
5
  • $\begingroup$ "Finite or infinite, the result is a not unique nest of some of the original sets. "-means? Any example? $\endgroup$
    – Srestha
    Commented Jun 19, 2019 at 11:03
  • $\begingroup$ ({0}, {0,1}, {0,2}) yields two nests. $\endgroup$ Commented Jun 19, 2019 at 12:15
  • $\begingroup$ Still I have not got, what nest mean? Any reference? And what is ur answer? C) or D)? $\endgroup$
    – Srestha
    Commented Jun 19, 2019 at 13:01
  • $\begingroup$ The correct spelling is "your". $\endgroup$ Commented Jun 19, 2019 at 22:17
  • $\begingroup$ yes, I know. Is answer C) or D)? $\endgroup$
    – Srestha
    Commented Jun 20, 2019 at 2:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .