SP20:Lecture 4 Proof techniques

From CS2800 wiki

We finished our proof that [math]\href{/cs2800/wiki/index.php/Claim:A_%E2%88%AA_(B_%E2%88%A9_C)_%3D_(A_%E2%88%AA_B)_%E2%88%A9_(A_%E2%88%AA_C)}{A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)} [/math] and used this as a way to demonstrate several proof techniques.


Note: We did not finish the proof in lecture; I have finished it below, but it's also a good exercise to work through on your own.

A direct proof

[math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) \href{/cs2800/wiki/index.php/Equality_(sets)}{=} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]
Proof: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Choose arbitrary sets [math]A [/math], [math]B [/math], and [math]C [/math]. We want to show that the LHS is a subset of the RHS and vice-versa.

To see that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} LHS [/math]. Then we know that either [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] or [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) [/math].

In the case that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], we see that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%5Ccup}{\cup} B) [/math] by definition; similarly [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]. Therefore [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) = \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] as desired.

In the other case, we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C [/math]. We want to show that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} = (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]. Thus we must show both that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]. Well, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) [/math] because [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math] (since we know [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} C [/math]); [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math] similarly. This completes this case and the fact that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math].

We must now show that [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math]. Choose an arbitrary [math]x ∈ \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]; note that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]. We know that either [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] or [math]x \notin A [/math]. If [math]x ∈ A [/math] then [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math] by definition of .

On the other hand, if [math]x \notin A [/math] then [math]x [/math] must be in [math]B [/math]; otherwise [math]x [/math] could not be in [math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]. Similarly, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} C [/math]; thus [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} (B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) [/math] so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math] as required.

We have now shown that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] and [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math], which completes the proof that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math].

This is a good (although perhaps slightly wordy) proof of the claim: each statement is clear, and follows from the previous statements using standard proof techniques.

There are a variety of different styles demonstrated in this proof. For example, the first case in the [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] works fortward from what is known, while the second case works backwards from what we want to show. Both styles are useful, but you must clearly distinguish what you have already proved from what you want to show. Otherwise, you will end up giving an invalid backwards proof.

Proof techniques

The above proof demonstrated the following proof techniques; In the coming lectures, we will systematically develop a table of proof techniques for the course.

Proving for all statements

If your goal is to prove "for all [math]x\href{/cs2800/wiki/index.php/%E2%88%88}{∈}A [/math], P", you can proceed by choosing an arbitrary value [math]x∈A [/math] and then proving that P holds for that [math]x [/math].

The fact that [math]x [/math] is arbitrary does not mean you get to pick [math]x [/math]; on the contrary, your proof should work no matter what [math]x [/math] you choose. This means you can't use any property of [math]x [/math] other than that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math].

Proving and statements

To prove "[math]P [/math] and [math]Q [/math]", you can separately prove [math]P [/math] and then prove [math]Q [/math].

Using and statements

If you have already proved (or assumed) [math]P [/math] and [math]Q [/math], you can conclude [math]P [/math]. You can also conclude [math]Q [/math].

Proving or statements

To prove "[math]P [/math] or [math]Q [/math]", you can either prove [math]P [/math], or you can prove [math]Q [/math] (your choice!)

Using or statements

If you know that "P or Q" is true for some statements P and Q, and you wish to show a third statement R, you can do so by separately considering the cases where P is true and where Q is true. If you are able to prove R in either case, then you know that R is necessarily true.

This technique is often referred to as case analysis.