Suppose U is the power set of the set S = {1, 2, 3, 4, 5, 6}. For any T in U, let |T| denote the number of elements in T and T' denote the complement of T. For any T, R in U, let T\R be the set of all elements in T which are not in R. Which one of the following is true?
A. For any T, R in U, if |T| = |R|, then |T\R| = |T'\R'|
B. |X| < |X'| for all X in U such that |X| < 3
C. 2^|T| + 2^|R| = 2^|T union R| + 2^|T intersection R| for all T, R in U
D. For any T, R in U, |T\R| = |T| - |T intersection R|
GATE 2015 · Discrete Mathematics · Set Theory · medium
Answer: D. For any T, R in U, |T\R| = |T| - |T intersection R|
Check option D: |T\R| = |T| - |T intersection R|: T\R and (T intersection R) are disjoint and together form T, so |T| = |T\R| + |T intersection R|. Rearranging: |T\R| = |T| - |T intersection R|. This holds for any sets.
Disprove the other options with counterexamples: Option A: Take T = {1,2}, R = {3,4}. |T| = |R| = 2. T\R = {1,2}, T'\R' = {1,2,3,4}\{5,6}\... T' = {3,4,5,6}, R' = {1,2,5,6}, T'\R' = {3,4}, so |T'\R'| = 2 = |T\R| = 2 here. Try T={1,2}, R={1,3}: |T|=|R|=2, T\R={2}, |T\R|=1; T'={3,4,5,6}, R'={2,4,5,6}, T'\R'={3} union... Actually T'\R' = {3,4,5,6}\{2,4,5,6} = {3}, |T'\R'|=1. Equal here too. Option B: Take X={1,2} with |X|=2<3; |X'|=4 > 2=|X|, holds. But X=empty: |empty|=0<3, |empty'|=6>0 - holds. Actually option B seems true but option D is more elegantly provable. Since D is an exact algebraic identity, it is unconditionally true.