FA18:Lecture 4 proofs

From CS2800 wiki

In this lecture, we will examine several forms of proposition; for each we will discuss how to prove it, how to disprove it, and how to use it in a proof (if it is already known to be true).



You may find it useful to look at the list of all proofs in the course. Although you don't have the definitions yet, you should be able to understand the structure of the proofs using the techniques from this lecture.


Propositions

Definition: Proposition
A proposition is a statement that is either true or false.

For example, [math]3 \gt 5 [/math] is a proposition, as is [math]3 \lt 5 [/math]. "Professor George is taller than 5'" is a proposition. If [math]x [/math] is known to be 5, then "[math]x \gt 5 [/math]" is a proposition.

If a fact depends on a variable, we will not consider it to be a proposition. For example, "[math]x \gt 5 [/math]" by itself is not a proposition. Neither is "[math]x \gt x-1 [/math]". These statements are called properties of [math]x [/math], or predicates on [math]x [/math]. Similarly, we can have properties of two variables (e.g. [math]x \gt y [/math]).

Predicates can be turned into propositions by quantifying them; stating that they must be true either for all [math]x [/math] or for some [math]x [/math].

For example, "for any sets [math]A [/math] and [math]B [/math], [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]" is a proposition, as is "there exists some [math]x [/math] with [math]x \gt 0 [/math]".

This process can be repeated: "for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]x \geq y [/math]" is a predicate, because it depends on [math]y [/math] (but not [math]x [/math]!). But "there exists [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] such that for every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]x ≥ y [/math]" is a proposition.

We are often lazy and leave off the quantification of a variable in a statement. When we have an undefined variable [math]x [/math] in a claim, we implicitly mean "for all [math]x [/math]". For example, if I ask you to prove or disprove that [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math], I implicitly mean to prove or disprove that, for all sets [math]A [/math] and [math]B [/math], [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math].

Combining propositions

If you have propositions [math]P [/math], [math]Q [/math], and [math]R [/math], you can combine them in natural ways to form new propositions. The structure of these combined propositions can help you determine how to prove them, or how to use them if you know they are true. We will examine several of these combined propositions today; we will summarize them in the next lecture in a table of proof techniques.

You can view this overview as a guide to doing what it says, and using what you know. At any point in a proof, there is a current set of facts that you've already proven (or assumed), and there is a particular proposition that you are trying to show. You can apply these strategies to those propositions to make progress.

Note on notation

We are introducing symbols for words like "and", "or", and "not". These symbols are helpful when talking about logic itself, but I find they make proofs much harder to read, so I avoid them when writing proofs. This is a matter of style.

P and Q

If [math]P [/math] and [math]Q [/math] are propositions, then "[math]P [/math] and [math]Q [/math]" is a proposition (written [math]P \href{/cs2800/wiki/index.php/%E2%88%A7}{∧} Q [/math]); it is true if both [math]P [/math] is true and [math]Q [/math] is true.

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

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

To disprove "[math]P [/math] and [math]Q [/math]", you must either disprove [math]P [/math] or disprove [math]Q [/math]. Put another way, the logical negation of "[math]P [/math] and [math]Q [/math]" is "not [math]P [/math] or not [math]Q [/math]".

P or Q

If [math]P [/math] and [math]Q [/math] are propositions, then "[math]P [/math] or [math]Q [/math]" is a proposition (written [math]P \href{/cs2800/wiki/index.php/%E2%88%A8}{∨} Q [/math]); it is true if [math]P [/math] is true, or if [math]Q [/math] is true (or both).

Note that this is somewhat different from the use of "or" in colloquial English; if both [math]P [/math] and [math]Q [/math] are true, we still consider [math]P [/math] or [math]Q [/math] to be true. This saves us work: we can prove [math]P [/math] or [math]Q [/math] by just proving [math]P [/math]; we don't have to also disprove [math]Q [/math].

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!)

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.

To disprove "[math]P [/math] or [math]Q [/math]", you must both disprove [math]P [/math] and disprove [math]Q [/math]. Put another way, the logical negation of "[math]P [/math] or [math]Q [/math]" is "not [math]P [/math] and not [math]Q [/math]".

P is false

If [math]P [/math] is a proposition, then "[math]P [/math] is false" (or more succinctly, "not [math]P [/math]", written [math]\href{/cs2800/wiki/index.php?title=%C2%ACP&action=edit&redlink=1}{¬P} [/math]) is also a proposition; it is true if [math]P [/math] is false, and false if [math]P [/math] is true.

  • To prove [math]P [/math] is false: disprove [math]P [/math]; To disprove "[math]P [/math] is false": prove [math]P [/math]. Put another way, the logical negation of "not [math]P [/math]" is [math]P [/math].
  • You can think of "proof by contradiction" as a way of using "not [math]P [/math]". If you are able to prove both [math]P [/math] and "not [math]P [/math]", then you must have made contradictory assumptions at some point; this means you can go back to your most recent assumption and conclude that it was invalid. This is useful to rule out cases when doing case analysis.

It is often a good way to start a proof: assume that what you are trying to prove is false, and then find a contradiction. At that point, you know your assumption was incorrect, so the original claim must be true.

This style of proof usually starts "Assume for the sake of contradiction, that [math]P [/math] is false..." and usually ends "...this is a contradiction, and [math]P [/math] must have been true in the first place." It is a useful approach when the claim you are trying to prove already has a logical negation in it, for example if you are trying to prove that something is not injective or not countable. You assume that it is injective or countable, and then you have a fact that you can work with.

For all x, P

If [math]P [/math] is a predicate that depends on [math]x [/math], then "for all [math]x [/math], [math]P [/math]" is a proposition. It is true if every possible value of [math]x [/math] makes [math]P [/math] evaluate to true.

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

  • If you know [math]P [/math] holds for all [math]x [/math], then you can conclude [math]P [/math] holds for any specific [math]x [/math]. For example, if you know for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} ℝ [/math], [math]x^2 ≥ 0 [/math], then you can conclude [math]7^2 ≥ 0 [/math] (since [math]7 ∈ ℝ [/math]).

There exists x such that P

If [math]P [/math] is a predicate depending only on [math]x [/math], then "there exists [math]x [/math] such that P" (written [math]\exists x, P [/math] or [math]\exists x~\href{/cs2800/wiki/index.php?title=S.t.&action=edit&redlink=1}{s.t.}~P [/math]) is a proposition. It is true if there is some value [math]x [/math] that makes [math]P [/math] evaluate to true.

[math]\href{/cs2800/wiki/index.php/%5Cexists}{\exists} [/math] is sometimes called the existential quantifier.

  • To prove that there exists an [math]x [/math] such that [math]P(x) [/math] holds, it suffices to give a specific [math]x [/math] and then prove that [math]P [/math] is true for that [math]x [/math]. Such a proof usually starts "let [math]x:= \cdots [/math]", and then goes on to prove that [math]P(x) [/math] holds for the given [math]x [/math]. [math]x [/math] is sometimes referred to as a witness for [math]P(x) [/math].
  • If you know there exists some [math]x [/math] satisfying [math]P [/math], you can use it in a proof by treating [math]x [/math] as an arbitrary value. [math]x [/math] is arbitrary because the only thing you know about [math]x [/math] is that it exists, not what its value is.
  • To disprove that there exists an [math]x [/math] satisfying [math]P [/math], you must disprove [math]P [/math] for an arbitrary [math]x [/math]. Put another way, the logical negation of "there exists an [math]x [/math] such that [math]P [/math]" is "for all x, not P".


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.

If P then Q

If [math]P [/math] and [math]Q [/math] are propositions, then "if [math]P [/math] then [math]Q [/math]" (written [math]P \href{/cs2800/wiki/index.php?title=%5Cimplies&action=edit&redlink=1}{\implies} Q [/math] or "[math]P [/math] implies [math]Q [/math]") is a proposition. It is true if either [math]P [/math] is false, or if [math]Q [/math] is true.

  • To prove "if [math]P [/math] then [math]Q [/math]", assume [math]P [/math] and then prove [math]Q [/math].
  • If you know "if [math]P [/math] then [math]Q [/math]", and you also know [math]P [/math], you can conclude [math]Q [/math]. This technique is sometimes referred to as "modus ponens".
  • To disprove "if [math]P [/math] then [math]Q [/math]", you must show that [math]P [/math] is true and that [math]Q [/math] is false ("[math]P [/math] implies [math]Q [/math]" only makes a claim about the world where [math]P [/math] is true; an example where [math]P [/math] is false doesn't contradict the claim).

Logical negation

If [math]P [/math] is a proposition, the logical negation of [math]P [/math] is the proposition that is equivalent to "not [math]P [/math]".

For example, to disprove "[math]P [/math] and [math]Q [/math]", it suffices to either disprove [math]P [/math] or to disprove [math]Q [/math]. This is the same thing as proving "not [math]P [/math] or not [math]Q [/math]," so the logical negation of "[math]P [/math] and [math]Q [/math]" is "not [math]P [/math] or not [math]Q [/math]."

For further examples, see the table of proof techniques.

Table of proof techniques

Here is a table of proof techniques summarizing proof techniques for the basic logical connectives. These techniques will get you most of the way through most of the proofs in this course. There is also a convenient one-page pdf

Proposition Symbol To prove it To use it Logical negation
P and Q (P Q) prove both P and Q you may use either P or Q (¬P) (¬Q)
P or Q (P Q) You may either prove P or prove Q case analysis (¬P) (¬Q)
P is false (or "not P") ¬ P disprove P contradiction P
if P then Q (or "P implies Q") P Q assume P, then prove Q if you know P, conclude Q P ¬ Q
for all x, P ∀x, P choose an arbitrary value x apply to a specific x x, ¬ P
there exists x such that [math]P [/math] ∃x, P give a specific x use an arbitrary x satisfying P x, ¬ P

You can think of these as the valid outlines of a valid proof. When writing a 5-paragraph essay, the structure consists of an introductory paragraph, three supporting paragraphs, and a conclusion. Supporting paragraphs have their own structure (made up of sentences, which themselves have a structure...).

Similarly, a proof of a statement like "for all x, P" has an introduction of an arbitrary variable, followed by another proof (this time of P(x)). This proof in turn will have one of the structures in the table above, and so on.

Note that this process is recursive: most of these techniques say "to prove ..., do ... and then prove ...". In most cases, you must repeatedly apply these techniques to build a complete proof.