SP19:Lecture 10 Quantifier review

From CS2800 wiki

We spent most of this lecture reviewing one of the questions from homework 2.

The reason for reviewing it was to show that the entire question could be done with a combination of applying the standard proof techniques and plugging in definitions. We particularly emphasized "doing what it says and using what you know" and "making a wish".

See the solutions to homework 2 for a written version of the proof we did in lecture today. When reading any proof (yours or mine), make a habit of pausing after each statement and asking "what proof techniques, known facts, and definitions were used to get to this statement?"

At the end of lecture, we spent some time introducing the notion of a relation, including the definition, and several examples (Tables are relations, Family relationships are relations, Inequalities are relations, Equations are relations). We also defined binary relation.

The notes on relations are included in the lecture 11 notes.

Do what it says, use what you know

A good way to approach proofs is to "Do what it says, use what you know". In other words, look at the structure of what you've already proved (or assumed) and what you are trying to prove.

Often, this can help you make progress. We will present a table of proof techniques in a future lecture, but we list some of the techniques here.

Case analysis

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.

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].

Make a wish

When trying to prove an existential statement [math]\href{/cs2800/wiki/index.php/%E2%88%83}{∃x}, \href{/cs2800/wiki/index.php/Predicate}{P}(x) [/math], you need to give a specific value of [math]x [/math] (a witness).

Often, in a proof, it is not immediately obvious what the witness should be. Finding one often involves solving some equations or combining some known values.

One nice technique for finding a witness is to simply leave a blank space for the value of [math]x [/math] and continue on with your proof of [math]P(x) [/math]. As you go, you may need [math]x [/math] to satisfy certain properties (for example, maybe you need [math]x \gt 17 [/math] at one point, and later you need [math]x \lt 85 [/math]). You can make a "wishlist" on the side of your proof, reminding you of all the properties you want [math]x [/math] to satisfy. Once you've completed your proof, you can go back and find a specific value of [math]x [/math] (say, [math]50 [/math]) that satisfies all of your wishes.