1
$\begingroup$

I am trying to study for a proofs final, and I'm really struggling with writing proofs. Does anyone have any suggestions that might help me to write proofs when given a theorem? I know there are different strategies that can help you like if your goal is of the form $P\implies Q, P \vee Q, \forall xP(x)$, ect. But I've having a hard time understanding how to apply these strategies to more complex proofs like...

Theorem: For all sets $A$ and $B$, $A \subseteq B$ if and only if $A \setminus B = \emptyset$.

Also can someone show me how I would prove this theorem? I know you need to prove it both ways, but after that I stuck on where to go from there.

$\endgroup$
3
  • $\begingroup$ en.m.wikipedia.org/wiki/Proof_by_contradiction $\endgroup$ – shai horowitz May 22 '16 at 20:14
  • 2
    $\begingroup$ Most proofs in these "proof classes" basically come down to expanding the definitions out and then making a small number of steps from there. One of the subtle things is knowing when to use contradiction/contraposition. (For instance, it can be convenient to negate the statement that some set is empty, because that allows you to instantiate some element of that set to use to derive a contradiction.) $\endgroup$ – Ian May 22 '16 at 20:15
  • $\begingroup$ for instance elaborate what does $ a \subset eq b$ mean? what does a\b mean? $\endgroup$ – shai horowitz May 22 '16 at 20:34
1
$\begingroup$

For me at least, the first thing to do, especially for problems of this level, is to convince yourself that the theorem is true. One way to do that here would be to draw a picture. If you draw a Venn Diagram with a set $A$ and a set $B$ such that $A\subseteq B$, this theorem should make sense.

Once you have convinced yourself it is true and are kinda starting to see why, you can proceed with the proof. I should say, though, that sometimes the problems are too abstract to really convince yourself. For more advanced math, it can sometimes even be hard to see what is going on, at which point it might be prudent to think about whatever theorem you know that might apply, and blindly follow. But here this sort of thinking should be fine. Hopefully you know that this is an iff statement; that is, you need to prove that the first part implies the second part, and the second implies the first. To do that, you must assume that one holds and show the other must hold.

So here is one direction. Let's try and show that $A\subseteq B$ implies $A\setminus B=\emptyset$. As others have mentioned, let's assume $A\subseteq B$ and then show that the opposite cannot hold--that is, it cannot be that $A\setminus B\neq \emptyset$. So we assume that, and show there is a problem. If $A\setminus B\neq \emptyset$, by definition, there exists some element $x\in A$ such that $x\notin B$. But by definition, $A \subseteq B$ if and only if for all $x \in A$, $x \in B$. But we have shown there is such an element without this property, so it cannot be that $A\subseteq B$, which contradicts our original assumption that this held. Also note that this can also be formulated as a proof of the contrapositive instead of a proof by contradiction. Try to do the other direction in a similar way.

$\endgroup$
0
$\begingroup$

See this question. The most important part in my opinion is the reflection on a meta level what you are doing and how good proofs are written (which properties do they have)?

$\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.