Proofs by contradiction and set theory I'm having trouble understanding proofs by contradiction. I'm running things by memory and not by understanding what a contradiction is. I'd like to know what we're assuming and how to start. My understanding is that if we have $p \rightarrow q$ it suffices to show $p \land \lnot q$ and we starting with $\lnot q$.
Here are two examples I found:
$$(A-B) \cap (B-A)=\emptyset \\ \text and \\ |A \cup B| = |A| +|B| \rightarrow A\cap B =\emptyset   $$
Well, for this first one, I don't have an if/then statement so do I just assume that $(A-B) \cap (B-A)  \neq \emptyset$ ? I know that this set is the empty by simple logic rules.
For the second one, do I assume $p \land \lnot q$ for  $ \lnot (A\cap B =\emptyset)  $ 
 A: Yes, to prove that $(A\setminus B)\cap(B\setminus A)=\varnothing$ for all $A$ and $B$, you can begin by assuming that $(A\setminus B)\cap(B\setminus A)\ne\varnothing$. Then let $x\in(A\setminus B)\cap(B\setminus A)$; clearly $x\in A\setminus B$, so $x\in A$. But also $x\in B\setminus A$, so $x\notin A$. This is a contradiction, so the original assumption that $(A\setminus B)\cap(B\setminus A)\ne\varnothing$ must be false. If $p$ is this assumption, and $q$ is $x\in A$, then the argument shows that $p\to(q\land\neg q)$. However
$$\Big(p\to(q\land\neg q)\Big)\to\neg p$$
is a tautology, so we infer $\neg p$, i.e., that $(A\setminus B)\cap(B\setminus A)=\varnothing$.
I would prove the second one by showing that
$$|A\cup B|=|A|+|B|-|A\cap B|\;;$$
it follows immediately that if $|A\cup B|=|A|+|B|$, then $|A\cap B|=0$ and hence that $A\cap B=\varnothing$.
A: To prove $p \rightarrow q$ by contradiction, one assumes to the contrary that $p \wedge \neg q$ holds and then tries to prove a contradiction, which is a statement of the form $r \wedge \neg r$, where $r$ is any formula you like.
Remark. We can compute the negation of $p \rightarrow q$ as follows:
$$\neg(p \rightarrow q) = \neg (\neg p \vee q) = \neg \neg p \wedge \neg q = p \wedge \neg q$$
So its negation really is $p \wedge \neg q$.
