GATE1993-8.3

Question

Let $S$ be an infinite set and $S_1 \dots , S_n$ be sets such that $S_1 \cup S_2 \cup \dots \cup S_n = S$. Then

• A. at least one of the set $S_i$ is a finite set
• B. not more than one of the set $S_i$ can be finite
• C. at least one of the sets $S_i$ is an infinite
• D. not more than one of the sets $S_i$ can be infinite
• E. None of the above

Comments

Is it to be always assumed that the number of subsets is finite?

---

given that "n" is finite

---

Counter Example for

S = Whole Numbers , S1= Even Natural Number , S2 = Odd Natural Number

(A) So no requirement of any of the Sn to be finite.

(B) S1, S2 with S3 = { 1,2} , S4 = { 3,4}

Two finite sets still it will be satisfied.

(C) This is must as the union of finite sets will always be finite.

(D) S1 and S2 both are infinite.

So (C) is correct.

---

@vaibhav101 No such assumption taken. @Niraj Singh 2  Yes n is finite.

Answer 1

A) at least one of the set $S_{i}$ is Finite Set. Well it is not said that$S_{1},S_{2}\ldots S_{n}$ whether they are finite or infinite. It is possible to break down infinite set into few sets (Some of which can be finite). This seems True, but I'm not able to prove it. Please Give suitable counterexample here, if you think this is false.

Ex-$: a^{*},\text{this is infinite set. I can write it as} \{\}\cup \{a^{*}\},$ where $\{a^{*}\}$ is infinite.
 

B) Not more than one of set can be finite -> This is false.

ex $: a^{*}b^{*}\Rightarrow \{ab\} \cup  \{\} \cup \{{aa}^{+}{bb}^{+}\}.$

C) at least one of the sets is Infinite -> This must be True. As this is finite union of sets, one of set must be infinite to make whole thing infinite.  True.

D) not more than one of the sets $S_i$ can be infinite. This is false. 

Ex $: a^{*}b^{*} = \{a^{p}b^{q}|p=q\}\cup \{a^{m}b^{n}|m\neq n\}$ such that $p,q,m,n \geq 0.$

Answer ->  C is surely true.

ESi

Comments

i think option (b) & (a) in a way both are not necessary and sufficient conditions. and you mean a+ in your example but this is a example ratther than counter one

counter example : (edit) a* = a* U a*

it is not necessary that one of the sets definitely needs to be finite.

option (c) is more stronger because without it infinite enumeration is not possible so both necessary and sufficient

---

yes, we can take Si = S for a choice- union of same sets give the same set. And "n" should make it finite union.

---

sir please check if i m correct?

---

nopes because LHS != RHS. RHS for example does not generate "ba". We can simply give

a* = a* U a*

---

yes u re correct  (corrected)

---

Consider the Set S of Integers

Now S= S1 U S2 U S3

where S1=Set of all negative integers

S2=Set of all positive integers

S3={0},

Note that S3(zero) which does not belong to set of positive and negative integers, may be included in S1 or S2 thereby making it false to say that at least one of the set S_i must be finite.

Since, we know that set of integers is an infinite set, one of the Set S_i must be infinite.

---

Option A is FALSE because:

suppose S = N (set of natural numbers)

Then S1 can be set of odd numbers and s2 can be set of even numbers. Then union of both will give N. But neither of S1 nor S2 is finite. Is this reasoning correct?

---

@Rishabh Gupta 2
S1 should be set of odd natural number and s2 should be set of even natural numbers.

Answer 2

atleast one of set should  b infinite..

Answer 3

If an infinite set is partitioned into finitely many subsets, then at least one of them must be infinite.

https://en.wikipedia.org/wiki/Infinite_set#Properties