Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2008-10-28 16:57:47

fusilli_jerry89
Member
Registered: 2006-06-23
Posts: 86

Power Sets

Prove or disprove each of the following statements for all subsets A and B of a universal set
U :
a. P (A ∩ B) = P (A) ∩ P (B).


Yeah I was just wondering where to start with this problem..

Offline

#2 2008-10-28 23:41:40

LuisRodg
Real Member
Registered: 2007-10-23
Posts: 322

Re: Power Sets

Remember that the power set is a set itself and anytime you want to prove that a set is equal to another set you have to show two things, that is you need to prove that one set is a subset of the other and vice versa. If you have, for example, sets A and B, and you want to show that A = B then you need to show that A is a subset of B and B is a subset of A. That proves that A = B.

So we want to prove:

P (A ∩ B) = P (A) ∩ P (B)

So we take arbitrary x in P(A ∩ B). Since x is in P(A ∩ B) then we know that x is a subset of A ∩ B by definition of the power set. Since x is in A ∩ B then we know that x is in A and x is in B. Since x is in A and in B then it follows that x is in P(A) and x is in P(B). Hence x is in P (A) ∩ P (B). So we have showed that P (A ∩ B) is a subset of P (A) ∩ P (B).

So now we take arbitrary x in P (A) ∩ P (B). So it follows that x is in P(A) and x is in P(B). By the definition of the power set, it follows that x is a subset of A and x is a subset of B. Since x is a subset of A and B, then it follows that x is in A ∩ B. Since x is in A ∩ B, then it follows that x is in the power set of A ∩ B, that is x is in P(A ∩ B). So we have showed that P (A) ∩ P (B) is a subset of P(A ∩ B).

This completes the proof that P (A ∩ B) = P (A) ∩ P (B).

Last edited by LuisRodg (2008-10-28 23:48:47)

Offline

#3 2008-10-29 01:46:22

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: Power Sets

The arrows in the above proof can all be reversed to prove the reverse inclusion.

Hence

Offline

#4 2008-10-29 02:41:57

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: Power Sets

In the case of unions, however, the same method will only work in one direction but not the other. We only have

Obviously any subset of A or any subset of B is a subset of AB, so this is true intuitively. It is also fairly clear that, on the other hand, there are subsets of AB that are not subsets of A or subsets of B. Foir example, if

then

but
and

Offline

#5 2008-10-29 04:19:31

LuisRodg
Real Member
Registered: 2007-10-23
Posts: 322

Re: Power Sets

Hello Jane,

Was there anything wrong in my written proof?

Thanks.

Offline

#6 2008-10-29 13:25:27

fusilli_jerry89
Member
Registered: 2006-06-23
Posts: 86

Re: Power Sets

ooooooooooooh I get it now. Thanks!

But as another example, say we are given an equation for an arbitrary element in a set X say x = 5a + 3 (where a is an int) and a set Y with an arbitrary element y = 5b - 2. So I have to prove that the element x is in the set Y and the element y is in the set X right?

Offline

Board footer

Powered by FluxBB