GATE CSE 2001 | Question: 3

Question

1. Prove that powerset $(A \cap B) = \text{powerset}(A) \cap \text{powerset}(B)$
2. Let $\text{sum} (n) = 0 + 1 + 2 + ..... + n$ for all natural numbers n. Give an induction proof to show that the following equation is true for all natural numbers $m$ and $n$:

$\text{sum}(m+n) = \text{sum}(m) + \text{sum}(n) + mn$

Comments

1) https://proofwiki.org/wiki/Intersection_of_Power_Sets

2) it's quite basic 

sum(m+n)=sum(m)+(m+1)+(m+2)+(m+3)+.....(m+n)

                 =sum(m)+(1+2+3+...n)+(m+m+m+....n times)

                 =sum(m)+sum(n)+m*n

---

https://math.stackexchange.com/questions/499746/intuition-power-set-of-intersection-union-velleman-p77-ex-2-3-10-11

---

The beauty of this question is that for statements involving “Power Set”, Venn Diagram method cannot be applied.

So, learning the “Formal Analytical Method” to prove Set Equality is also Very important.

$\color{red}{\text{Find Video Solution Below, with Variations:}}$

Detailed Video Solution with Variations

Watch the following playlist to master the “Formal Analytical Method” to prove Set Equality.

https://youtube.com/playlist?list=PLIPZ2_p3RNHjYd_k_L5k4Bs5y-QLl2h6L

Answer 1

For question (a):

To prove $P(A\cap B )= P(A)\cap P(B)$ we should show that $P(A\cap B )\subseteq P(A)\cap P(B)$ and $P(A)\cap P(B)\subseteq P(A\cap B )$.

For first part:

Lets take some subset $X\subseteq A\cap B$ then $X\in P(A\cap B )$. Also $X\subseteq A\wedge X\subseteq B$, means $X\in P(A)\wedge X\in P(B)$. Again this proves that $X\cap P(A)\cap P(B)$. This proves $P(A\cap B)\subseteq P(A)\cap P(B)\quad \to (1)$

For second part:

Take any $X$ such that $X\subseteq A$ and $X\subseteq B$. This is $X\in P(A)\wedge X\in P(B)$. That means $X\in P(A)\cap P(B)$. Now also $X\subseteq (A\cap B)$. This also means that $X\in P(A\cap B)$. This proves $P(A)\cap P(B)\subseteq P(A\cap B) \quad \to(2)$

From results (1) and (2),
$$P(A)\cap P(B)= P(A\cap B)$$
For question (b):

$\text{Sum}(n)=\frac{n(n+1)}{2}$

So, for $n=1\: \text{Sum}(1)=1$

For $n = 2, \text{Sum} (2) = 1 + 2 = 3$

$\text{Sum}(1+1) = \text{Sum}(1) + \text{Sum}(1) + 1\times 1 = 1+1+1=3$

So, base case of the formula holds true.
Lets assume the formula holds true for $n+m$

$\implies \text{Sum}(m+n)=\text{Sum}(m)+\text{Sum}(n)+mn$

$\qquad =\frac{m(m+1)}{2}+\frac{n(n+1)}{2}+mn$

$\qquad =\frac{(m+n)(m+n+1)}{2}$

Now, we get for
$\text{Sum}(m+n+1)= \frac{(m+n+1)(m+n+2)}{2}$
$\qquad =  \frac{(m+n)(m+n+2)}{2} +  \frac{(m+n+2)}{2}$
$\qquad  = \frac{(m+n)(m+n+1)}{2} +  \frac{(m+n+2)}{2} +\frac{m+n}{2}$
$\qquad = \frac{(m+n)(m+n+1)}{2} +  \frac{(m+n)}{2} + 1 +\frac{m+n}{2}$
$\qquad = \text{Sum}(m+n)+\text{Sum}(1) + (m+n) \times 1$

Hence, proved by mathematical induction.

Comments

A={1,2}

B={3,4}

p(A)= { phi, 1, 2, 12}

p(B)={ phi, 3, 4, 34}

p(A^B) = P(phi)= { phi, {phi} }

p(A)^p(B) = { phi, 1, 2, 12} ^ { phi, 3, 4, 34} = {phi}

“hence” both are not equal,

Answer 2

proof by contradiction:

assume : P(A int B) != P(A) int P(B)

now,

A={1,2}

B={2,3}

P(A)={ empty set, {1}, {2}, {1,2} }

P(B)={ empty set, {3}, {2}, {3,2} }

A intersection B = {2}

P(A int B)={ empty set, {2} } = P(A) int P(B), which is contradicting our assumption.

therefore our assumption is wrong. hence the statement is proved.

Comments

this is no way of proving. contradiction is used for disproving not for proving.

or if you have to prove using contradiction then prove for a generalised case not for a specific case. this is wrong purely.