in Set Theory & Algebra edited by
1,239 views
8 votes
  1. Prove that powerset $(A \cap B) = \text{powerset}(A) \cap \text{powerset}(B)$
  2. 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$

in Set Theory & Algebra edited by
1.2k views

1 comment

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

11

2 Answers

12 votes
 
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.
edited by
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.

1 comment

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.
2

Related questions

Ask
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