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

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

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,

$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 Loyal (3.5k 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 Boss (8.5k 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

32,619 questions
39,267 answers
109,738 comments
36,654 users