# Set and it's Subset Operation

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 \}$$

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