FA18:Lecture 4 proofs

([itex]1) [/itex]2 | [itex]3 ([/itex]4) | [itex]5 ([/itex]6)

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, is a proposition, as is . "Professor George is taller than 5'" is a proposition. If is known to be 5, then "" is a proposition.

If a fact depends on a variable, we will not consider it to be a proposition. For example, "" by itself is not a proposition. Neither is "". These statements are called properties of , or predicates on . Similarly, we can have properties of two variables (e.g. ).

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

For example, "for any sets and , " is a proposition, as is "there exists some with ".

This process can be repeated: "for all , " is a predicate, because it depends on (but not !). But "there exists such that for every , " is a proposition.

We are often lazy and leave off the quantification of a variable in a statement. When we have an undefined variable in a claim, we implicitly mean "for all ". For example, if I ask you to prove or disprove that , I implicitly mean to prove or disprove that, for all sets and , .

Combining propositions

If you have propositions , , and , 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 and are propositions, then " and " is a proposition (written ); it is true if both is true and is true.

To prove " and ", you can separately prove and then prove .

If you have already proved (or assumed) and , you can conclude . You can also conclude .

To disprove " and ", you must either disprove or disprove . Put another way, the logical negation of " and " is "not or not ".

P or Q

If and are propositions, then " or " is a proposition (written ); it is true if is true, or if is true (or both).

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

To prove " or ", you can either prove , or you can prove (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 " or ", you must both disprove and disprove . Put another way, the logical negation of " or " is "not and not ".

P is false

If is a proposition, then " is false" (or more succinctly, "not ", written ) is also a proposition; it is true if is false, and false if is true.

• You can think of "proof by contradiction" as a way of using "not ". If you are able to prove both and "not ", 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 is false..." and usually ends "...this is a contradiction, and 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 is a predicate that depends on , then "for all , " is a proposition. It is true if every possible value of makes evaluate to true.

The fact that is arbitrary does not mean you get to pick ; on the contrary, your proof should work no matter what you choose. This means you can't use any property of other than that .

• If you know holds for all , then you can conclude holds for any specific . For example, if you know for all , , then you can conclude (since ).

There exists x such that P

If is a predicate depending only on , then "there exists such that P" (written or ) is a proposition. It is true if there is some value that makes evaluate to true.

is sometimes called the existential quantifier.

• To prove that there exists an such that holds, it suffices to give a specific and then prove that is true for that . Such a proof usually starts "let ", and then goes on to prove that holds for the given . is sometimes referred to as a witness for .
• If you know there exists some satisfying , you can use it in a proof by treating as an arbitrary value. is arbitrary because the only thing you know about is that it exists, not what its value is.

When trying to prove an existential statement , you need to give a specific value of (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 and continue on with your proof of . As you go, you may need to satisfy certain properties (for example, maybe you need at one point, and later you need ). You can make a "wishlist" on the side of your proof, reminding you of all the properties you want to satisfy. Once you've completed your proof, you can go back and find a specific value of (say, ) that satisfies all of your wishes.

If P then Q

If and are propositions, then "if then " (written or " implies ") is a proposition. It is true if either is false, or if is true.

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

Logical negation

If is a proposition, the logical negation of is the proposition that is equivalent to "not ".

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

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