+2 votes
411 views
1. Prove that powerset $(A \cap B) = \text{powerset}(A) \cap \text{powerset}(B)$
2. Let $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$:

$sum(m+n) = sum(m) + sum(n) + mn$

asked
edited | 411 views
+3

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

2 Answers

+3 votes

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:

let 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)$..................(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)$ ..............(2)

From result (1) and (2),

$P(A)\cap P(B)= P(A\cap B)$

For question (b):

as obvious $sum(n)=\frac{n(n+1)}{2}$

so for n=1 $sum(1)=\frac{1(1+1)}{2}=1,$ which is true.

let assume that for n=n+m,

$sum(m+n)=sum(m)+sum(n)+mn$

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

$=\frac{(m+n)(m+n+1)}{2}$  is true.

then for n=m+n+1,

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

from above results,

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

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

is proved by mathematical induction.

answered by Active (3.2k points)
+1 vote
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.
answered by Loyal (8.1k points)
+1
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.

+31 votes
4 answers
1
+1 vote
1 answer
2
+25 votes
3 answers
3
+13 votes
4 answers
4
+13 votes
3 answers
5
+27 votes
4 answers
6
+2 votes
1 answer
7