1
$\begingroup$

Let A and B be two sets. Then

$A \setminus B = \{x: x\in A \wedge x\notin B\}$

$A \setminus B = \{x: x\in A \wedge x\notin A \cap B\}$

How can one prove that two logical statements are equal?

Suppose $x \in A \setminus B$.

Then,

$x \in A \wedge x \notin A \cap B$

$x \in A \wedge x \notin A \wedge x\notin B$

How do I move forward?

$\endgroup$
  • $\begingroup$ Why are you trying to show that something is equal to itself? Also, where did you encounter the silly definition $A\setminus B=\{x:x\in A\land x\not\in A\cap B\}$? $\endgroup$ – Daniel W. Farlow Mar 27 '15 at 3:36
  • $\begingroup$ I am a newbie in Mathematics, made it myself. However I want to use this in proving a statement about symmetric difference of two sets A and B. Symmetric difference is defined as a set D of all elements that belong to A or B, but not in both. With this verbal definition, $D = \{ x : x \in A \vee x \in B \wedge x \notin A \cap B\}$. If we apply distributive law, we get $ (x \in A \wedge x\notin A \cap B) \vee (x \in B \wedge x \notin A \cap B)$ and so on ... $\endgroup$ – Azfar Hussain Mar 27 '15 at 3:48
  • $\begingroup$ Nothing wrong with being a newbie. :) We all were at one point. You said that you wanted to "use this" in proving a statement about the symmetric difference. It would probably be better, in that case, to actually ask about the symmetric difference statement you are trying to prove. $\endgroup$ – Daniel W. Farlow Mar 27 '15 at 3:59
  • $\begingroup$ $x\notin A\cap B$ if and only if $x\notin A\vee x\notin B$ (not $x\notin A\wedge x\notin B$ as you suggest). $\endgroup$ – drhab Mar 27 '15 at 15:46
  • $\begingroup$ @Azfar Hussain you can accept one answer and exclude question from non-accepted list $\endgroup$ – user 1 Mar 4 '16 at 8:07
2
$\begingroup$

Since you're using two definitions of the same object, it's best not to start off with $x\in A\setminus B$ since it's ambiguous which definition of $A\setminus B$ you mean. So start with $a\in \{x:x\in A \land x\not\in B\}$. Then $a\in A$ and $a\not\in B$ so $a\not\in A\cap B$ so $a\in \{x:x \in A\land x\not\in A\cap B\}$.

Now let $a\in \{x:x\in A \land x\not\in A\cap B\}$. Then $a\in A$ and $a \not \in A\cap B$ so either $a\not \in A$ or $a\not\in B$. Since the first cannot be true, we have $a\not\in B$. Therefore $a\in \{x:x\in A\land x\not\in B\}$. So the sets are equal, and we denote it by $A\setminus B$.

$\endgroup$
  • $\begingroup$ I'm not going to downvote but any proof that $A\setminus B = A\setminus B$ is simply a waste of time. You can let $C=A\setminus B$ and then just show, trivially, that $C=C$ by mutual subset inclusion. This is a case, I think, where OP could possibly use some help with logic. $\endgroup$ – Daniel W. Farlow Mar 27 '15 at 3:46
  • $\begingroup$ @crash waste of time or not, it's asked because the person wants guidance on proof-writing. So I did basically as you said--showed mutual subset inclusion. The renaming as $C$ is unnecessary. $\endgroup$ – Addem Mar 27 '15 at 3:47
  • $\begingroup$ The entire thing is unnecessay. But assigning the set $A\setminus B$ one letter may be clearer when giving an element-chasing proof. Regardless, I think OP may be better off seeing why such a proof is unnecessary in the first place. Anyway, something to think about. $\endgroup$ – Daniel W. Farlow Mar 27 '15 at 3:51
  • 1
    $\begingroup$ @crash you think it's unnecessary because you understand what's going on. Obviously, the person who asked thought it was necessary to ask. It's not as though the equality of these sets is an axiom, so a proof is possible, and he is trying to figure out how that works. I helped. Not really that big of a deal. $\endgroup$ – Addem Mar 27 '15 at 3:53
  • $\begingroup$ Thanks Addem for the help. I am learning to write proofs. $\endgroup$ – Azfar Hussain Mar 27 '15 at 3:56
0
$\begingroup$

$x\notin A\cap B \equiv x\in (A \cap B)^C \equiv x\in A^C \,or\,x\in B^C $. If $x\in A$, then $x\notin B \equiv x\in A \,\,\,and \,\,\,x\notin B \equiv x\in A-B$,

$\endgroup$
0
$\begingroup$

Your implication $\{x \in A \wedge x \notin A \cap B\}\Rightarrow \{x \in A \wedge x \notin A \wedge x\notin B\}$ is not true; By De Morgan's laws it should be$$\{x \in A \wedge x \notin A \cap B\}\Rightarrow \{x \in A \wedge (x \notin A \lor x\notin B)\}$$


Now proof.

You want to prove: $$\{x: x\in A \wedge x\notin B\}=\{x: x\in A \wedge x\notin A \cap B\}$$ or equivalently: $$A \setminus B=A \setminus (A\cap B).$$


proof.1.

$$A \setminus (A\cap B)= A\cap (A\cap B)^c = A\cap (A^c\cup B^c)=(A\cap A^c)\cup (A\cap B^c)=(A\cap B^c)= A \setminus B$$


proof.2.

Since $A\cap B \subset B$ we have $A \setminus B\subset A \setminus (A\cap B)$.
on the other hand:
Now let $x\in A \setminus (A\cap B)$. So $\underline{x\in A}$ and $x\notin A\cap B$; which means $\underline {x\notin B} $. Therefore $x\in A \setminus B$. (this direction is just Addem's proof).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.