The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
297 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 (59.4k points)
edited by | 297 views
0

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 Active (3k 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.3k 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.


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

34,770 questions
41,730 answers
118,876 comments
41,381 users