The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
  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 in Set Theory & Algebra by Veteran (59.5k points)
edited by | 317 views


2) it's quite basic 


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


2 Answers

+2 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,



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

then for n=m+n+1,


from above results,



is proved by mathematical induction.

answered by Active (3k points)
+1 vote
proof by contradiction:

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




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.2k points)
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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,110 questions
44,694 answers
43,753 users