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) $
Best Answer
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$.