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

1,239 views

- Prove that powerset $(A \cap B) = \text{powerset}(A) \cap \text{powerset}(B)$
- 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$

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

Best answer

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.

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.

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.

Search GATE Overflow