GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
125 views

Let $A$ and $B$ be finite sets such that $A \subseteq B$. Then, what is the value of the expression:

$$\Sigma_{C:A \subseteq C \subseteq B} (-1)^{\mid C \setminus A \mid,}$$

Where $C \setminus A=\{x \in C : x \notin A \}$?

  1. Always 0
  2. Always 1
  3. 0 if $A=B$ and 1 otherwise
  4. 1 if $A=B$ and 0 otherwise
  5. Depends on the soze of the universe
asked in Set Theory & Algebra by Veteran (87.4k points)   | 125 views

3 Answers

+3 votes

Let set B be of cardinality n. 

Total subsets(A) possible are : nC0 + nC1 + nC2 + ... + nCn. i.e nCr number of subsets exist with r cardinality.

Note that for each r, summation has $2^{n-r}$ terms to sum. 

Case 1: r= 0. Which is $\Phi$ .

Total terms = $2^{n}$. 

Total terms when |C\A| even = nC0 + nC2 + nC4 + ... + nC(n-1) { if n is odd, nCn otherwise } 

Similarly for odd = 2ⁿ - |C\A| 

Even contributes to 1 whereas odd contributes to -1.

Therefore Summation = 0 as 2ⁿ terms are present with half as 1 & half as -1. 

Case 2: r = 1 , total terms = $2^{n-1}$

Total terms when |C\A| even = nCr + nC(r+2) + ... + nCn  { if n is odd n-1 otherwise } 

Total terms when |C\A| odd = nC(r+1) + nC(r+3) + ... 

Again we are end up with total even terms with half contributing to 1 & half -1. 

same situation will arise for every r ≠ n.(as for such r, $2^{r}$ is always even) i.e summation = 0 for all r, r ≠ n. 

Case n: r = n , total terms = $2^{n-n}$ = 1. This is the case when B = A. 

THEREFORE |C\A| = 0 as both are equal. 

Summation = 1. 

therefore answer is : 1 if A = B, 0 otherwise.  

Lemme know if I'm wrong. 

answered by Loyal (4.6k points)  
perfect ! rohit (y)
Thank you. :)
+3 votes

Very good QS.

answered by Veteran (51.4k points)  

Nice explanation.Thanks,  Debashish Deka.

0 votes

Correct option is (D) 1 if A=B and 0 otherwise

answered by Boss (5.8k points)  


Top Users Sep 2017
  1. Habibkhan

    7828 Points

  2. Warrior

    2746 Points

  3. rishu_darkshadow

    2692 Points

  4. Arjun

    2672 Points

  5. A_i_$_h

    2426 Points

  6. nikunj

    1980 Points

  7. manu00x

    1920 Points

  8. Bikram

    1854 Points

  9. makhdoom ghaya

    1770 Points

  10. SiddharthMahapatra

    1718 Points


26,239 questions
33,805 answers
80,214 comments
31,159 users