How Do De Morgan's Laws Apply to Set Theory Proofs?

[Potatochip911]

Homework Statement

Prove $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$

Homework Equations

3. The Attempt at a Solution [/B]
We will show that every element in $A\setminus(B\cap C)$ is contained in $(A\setminus B)$ or $(A\setminus C)$. If $x\in A\setminus (B\cup C)$ then $x\in A$, $x\notin B$ and $x\notin C$, thus $x\in(A\setminus B)$ and $x\in(A\setminus C)$ now I'm assuming the next step is to say that this shows that $x\in(A\setminus B)\cup(A\setminus C)$ but I'm confused as to why we this is a union instead of an intersection. If $x$ is not in B and C then why do we use and/or instead of just and? I am obviously interpreting this incorrectly so hopefully someone can clarify.

 

[Potatochip911]

Because it doesn't follow that $x\in A\setminus (B\cup C)$ that $x\notin B$. Think about it.

Okay so since it's possible that x is in either B or C we have $x\in A$, $x\in (B\cup C)$?

 

[verty]

It might be helpful to "de morgan" each side. For example, the left side becomes $\overline{A} \cup (B \cap C)$.

 

[Potatochip911]

It might be helpful to "de morgan" each side. For example, the left side becomes $\overline{A} \cup (B \cap C)$.

So I should also try to show that $(A\setminus B)\cup(A\setminus C)=A\setminus(B\cap C)$? Also I haven't yet learned what $\overline{A}$ represents.

 

[verty]

So I should also try to show that $(A\setminus B)\cup(A\setminus C)=A\setminus(B\cap C)$? Also I haven't yet learned what $\overline{A}$ represents.

Oh right, in that case do it the way you were doing it but be careful not to get the symbols wrong. I thought you had to apply De Morgan's laws somehow, so the obvious thing was to take the complement of each side.

 

[Ray Vickson]

Homework Statement

Prove $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$

Homework Equations

3. The Attempt at a Solution [/B]
We will show that every element in $A\setminus(B\cap C)$ is contained in $(A\setminus B)$ or $(A\setminus C)$. If $x\in A\setminus (B\cup C)$ then $x\in A$, $x\notin B$ and $x\notin C$, thus $x\in(A\setminus B)$ and $x\in(A\setminus C)$ now I'm assuming the next step is to say that this shows that $x\in(A\setminus B)\cup(A\setminus C)$ but I'm confused as to why we this is a union instead of an intersection. If $x$ is not in B and C then why do we use and/or instead of just and? I am obviously interpreting this incorrectly so hopefully someone can clarify.

If $E^c$ denotes the complement ("not-$E$) of a set $E$, then $D \backslash E = D \cap E^c$, essentially by definition. Do you know how one of the DeMorgan laws relates $(B \cap C)^c$ to $B^c$ and $C^c$?

 

[Potatochip911]

Oh right, in that case do it the way you were doing it but be careful not to get the symbols wrong. I thought you had to apply De Morgan's laws somehow, so the obvious thing was to take the complement of each side.

So for the other side: If $x\in (A\setminus B)\cup (A\setminus C)$ then $x\in A$ and $x\in (B\cup C)$

If $E^c$ denotes the complement ("not-$E$) of a set $E$, then $D \ E = D \cap E^c$, essentially by definition. Do you know how one of the DeMorgan laws relates $(B \cap C)^c$ to $B^c$ and $C^c$?

In my statistics class we had $P(B\cap C)^c=P(B^c)+P(C^c)-P(B\cup C)$

 

[Ray Vickson]

So for the other side: If $x\in (A\setminus B)\cup (A\setminus C)$ then $x\in A$ and $x\in (B\cup C)$

In my statistics class we had $P(B\cap C)^c=P(B^c)+P(C^c)-P(B\cup C)$

This is irrelevant: the question has nothing to do with statistics or probability. It is just a question about set manipulation.

 

[Potatochip911]

This is irrelevant: the question has nothing to do with statistics or probability. It is just a question about set manipulation.

Hmm I think I have solved this question, if $x\in A\setminus(B\cap C)$ then $x\in A$ and $x\notin (B\cap C)$, it follows that $x\notin B$ or $x\notin C$ which leads to $x\in (A\setminus B)\cup (A\setminus C)$

 

[Dick]

Hmm I think I have solved this question, if $x\in A\setminus(B\cap C)$ then $x\in A$ and $x\notin (B\cap C)$, it follows that $x\notin B$ or $x\notin C$ which leads to $x\in (A\setminus B)\cup (A\setminus C)$

I think you have solved it as well.

 

[Potatochip911]

I think you have solved it as well.

I would really appreciate it if someone could look over this one as well, I'm supposed to prove that $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$, In order to prove this I must show that that x can go from an element of the LHS to the RHS (Not really sure how to word this suggestions would be appreciated) $x\in (A\cup B)\cap (A\cup C)$, Starting from the LHS I have that if $x\in A\cup (B\cap C)$ then $x\in A$ and $x\in (B\cap C)$, this leads to two cases, the first case is when $x\in A$, this implies that $x\in (A\cup B)\cap (A\cup C)$ since if $x\in A$ this statement holds true. The second case is when $x\in (B\cap C)$, this also implies the RHS since if $x\in (B\cap C)$ then the statement $(A\cup B)\cap (A\cup C)$ also holds, therefore $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$. I'm curious as to whether or not this is sufficient or if I have to manipulate the expressions more.

 

[Ray Vickson]

Hmm I think I have solved this question, if $x\in A\setminus(B\cap C)$ then $x\in A$ and $x\notin (B\cap C)$, it follows that $x\notin B$ or $x\notin C$ which leads to $x\in (A\setminus B)\cup (A\setminus C)$

You have gone one way (proving that $A\setminus(B \cap C) \subset (A\setminus B) \cup (A\setminus C)$. You also need to establish the reverse.

 

[Potatochip911]

You have gone one way (proving that $A\setminus(B \cap C) \subset (A\setminus B) \cup (A\setminus C)$. You also need to establish the reverse.

Is it possible that the proof changes when going the other way around or is it always the same steps just proving them in reverse?

 

[Ray Vickson]

Is it possible that the proof changes when going the other way around or is it always the same steps just proving them in reverse?

You tell me.