Power Set Unions and inclusion

6 replies · 3K views · last reply
Kolmin
Messages
66
Reaction score
0
I am studying Velleman's "How to prove it: a structured approach" and I have to say that it is one of the best decision I have taken. Right now I am working on the exercises that are on Velleman's page along with the java applet "Proof Designer" and I have the feeling I start to get a bit how proofs work. But still...

This proof is really making me think and I don't see how I can get out of it.

Assume [itex]\wp[/itex](A)[itex]\cup[/itex][itex]\wp[/itex](B)=[itex]\wp[/itex](A[itex]\cup[/itex]B)
Prove that A[itex]\subseteq[/itex]B or B[itex]\subseteq[/itex]A.
[Suggested Exercise no.20]

I have to admit I tried basically everything (i.e. contradiction, cases) but I don't really go anywhere close to the solution.

For example, proof designer asks you to define a bounded variable if it is in the "given" section. I rephrase [itex]\wp[/itex](A)[itex]\cup[/itex][itex]\wp[/itex](B)=[itex]\wp[/itex](A[itex]\cup[/itex]B) and I don't know how to define the subset X of A and B (out of desperation I put X=A but doesn't look a great idea).

Still I am not sure if it is a matter of not knowing how to properly use the software (which is actually quite easy) or I simply don't know how to work out the proof.
 
Tried to use Venn Diagram?? It really helps in visualizing the sets, their union, intersections, etc.
 
Kolmin said:
I am studying Velleman's "How to prove it: a structured approach" and I have to say that it is one of the best decision I have taken. Right now I am working on the exercises that are on Velleman's page along with the java applet "Proof Designer" and I have the feeling I start to get a bit how proofs work. But still...

This proof is really making me think and I don't see how I can get out of it.

Assume [itex]\wp[/itex](A)[itex]\cup[/itex][itex]\wp[/itex](B)=[itex]\wp[/itex](A[itex]\cup[/itex]B)
Prove that A[itex]\subseteq[/itex]B or B[itex]\subseteq[/itex]A.
[Suggested Exercise no.20]

I have to admit I tried basically everything (i.e. contradiction, cases) but I don't really go anywhere close to the solution.

For example, proof designer asks you to define a bounded variable if it is in the "given" section. I rephrase [itex]\wp[/itex](A)[itex]\cup[/itex][itex]\wp[/itex](B)=[itex]\wp[/itex](A[itex]\cup[/itex]B) and I don't know how to define the subset X of A and B (out of desperation I put X=A but doesn't look a great idea).

Still I am not sure if it is a matter of not knowing how to properly use the software (which is actually quite easy) or I simply don't know how to work out the proof.
How about proving the contra positive?
Assume [itex]\displaystyle \text{ A} \not\subseteq \text{B and B} \not\subseteq \text{ A }.[/itex]

Prove [itex]\displaystyle \ \ <br /> \wp\text{(A)}\cup\wp\text{(B)}\neq\wp\text{(A}\cup\text{B)}\,.[/itex]​
 
Last edited:
Well, my contradiction didn't look that great...

About the Venn diagrams, it's not a matter of understanding the result (at least this one...): the only problem is really to prove it.

Right now I am trying with the contrapositive (thanks for the suggestion...:smile: ) but it's a bit problematic. I don't know if you ever used "Proof Designer": I find it amazing, because it really forces you to not fly around.
The fact is that I guess I should build up a subset with certain properties but I am not really sure I can do it. [...or maybe I am completely wrong]
 
Btw, a question that should look silly but that I facing yesterday.

Let's imagine we have the following goal:

A not-[itex]\subseteq[/itex]B [itex]\vee[/itex] A[itex]\subseteq[/itex]B

Instead of using the disjunction or the cases approach to prove the goal, can we consider it an implication?

I mean, basically it is the same of

[itex]\neg[/itex](A[itex]\subseteq[/itex]B) [itex]\vee[/itex] A[itex]\subseteq[/itex]B

which is the same as

A[itex]\subseteq[/itex]B[itex]\rightarrow[/itex]A[itex]\subseteq[/itex]B

I was wondering cause (if the trick is not wrong) you cannot use it in Proof Designer
 
Anyway, I finally got it.
Being a bit in a hurry for a travel, I will post the proof when I'll have time (hopefully before coming from the trip).