Proofs

Source file content/methods/proofs/proofs.tex

Source file content/methods/proofs/introduction.tex

Introduction

Based on your experiences in introductory logic, you might be comfortable with a derivation system---probably a natural deduction or Fitch style derivation system, or perhaps a proof-tree system. You probably remember doing proofs in these systems, either proving a formula or show that a given argument is valid. In order to do this, you applied the rules of the system until you got the desired end result. In reasoning about logic, we also prove things, but in most cases we are not using a derivation system. In fact, most of the proofs we consider are done in English (perhaps, with some symbolic language thrown in) rather than entirely in the language of first-order logic. When constructing such proofs, you might at first be at a loss---how do I prove something without a derivation system? How do I start? How do I know if my proof is correct?

Before attempting a proof, it's important to know what a proof is and how to construct one. As implied by the name, a proof is meant to show that something is true. You might think of this in terms of a dialogue---someone asks you if something is true, say, if every prime other than two is an odd number. To answer “yes” is not enough; they might want to know why. In this case, you'd give them a proof.

In everyday discourse, it might be enough to gesture at an answer, or give an incomplete answer. In logic and mathematics, however, we want rigorous proof---we want to show that something is true beyond any doubt. This means that every step in our proof must be justified, and the justification must be cogent (i.e., the assumption you're using is actually assumed in the statement of the theorem you're proving, the definitions you apply must be correctly applied, the justifications appealed to must be correct inferences, etc.).

Usually, we're proving some statement. We call the statements we're proving by various names: propositions, theorems, lemmas, or corollaries. A proposition is a basic proof-worthy statement: important enough to record, but perhaps not particularly deep nor applied often. A theorem is a significant, important proposition. Its proof often is broken into several steps, and sometimes it is named after the person who first proved it (e.g., Cantor's Theorem, the Löwenheim--Skolem theorem) or after the fact it concerns (e.g., the completeness theorem). A lemma is a proposition or theorem that is used in the proof of a more important result. Confusingly, sometimes lemmas are important results in themselves, and also named after the person who introduced them (e.g., Zorn's Lemma). A corollary is a result that easily follows from another one.

A statement to be proved often contains assumptions that clarify which kinds of things we're proving something about. It might begin with “Let $!A$source be a formula of the form $!B \lif !C$source” or “Suppose $\Gamma \Proves !A$source” or something of the sort. These are hypotheses of the proposition, theorem, or lemma, and you may assume these to be true in your proof. They restrict what we're proving, and also introduce some names for the objects we're talking about. For instance, if your proposition begins with “Let $!A$source be a formula of the form $!B \lif !C$source,” you're proving something about all formulas of a certain sort only (namely, conditionals), and it's understood that $!B \lif !C$source is an arbitrary conditional that your proof will talk about.

Source file content/methods/proofs/starting-proofs.tex

Starting a Proof

But where do you even start?

You've been given something to prove, so this should be the last thing that is mentioned in the proof (you can, obviously, announce that you're going to prove it at the beginning, but you don't want to use it as an assumption). Write what you are trying to prove at the bottom of a fresh sheet of paper---this way you don't lose sight of your goal.

Next, you may have some assumptions that you are able to use (this will be made clearer when we talk about the type of proof you are doing in the next section). Write these at the top of the page and make sure to flag that they are assumptions (i.e., if you are assuming $p$source, write “assume that $p$source,” or “suppose that $p$source”). Finally, there might be some definitions in the question that you need to know. You might be told to use a specific definition, or there might be various definitions in the assumptions or conclusion that you are working towards. Write these down and ensure that you understand what they mean.

How you set up your proof will also be dependent upon the form of the question. The next section provides details on how to set up your proof based on the type of sentence.

Source file content/methods/proofs/using-definitions.tex

Using Definitions

We mentioned that you must be familiar with all definitions that may be used in the proof, and that you can properly apply them. This is a really important point, and it is worth looking at in a bit more detail. Definitions are used to abbreviate properties and relations so we can talk about them more succinctly. The introduced abbreviation is called the definiendum, and what it abbreviates is the definiens. In proofs, we often have to go back to how the definiendum was introduced, because we have to exploit the logical structure of the definiens (the long version of which the defined term is the abbreviation) to get through our proof. By unpacking definitions, you're ensuring that you're getting to the heart of where the logical action is.

We'll start with an example. Suppose you want to prove the following:

In order to even start the proof, we need to know what it means for two sets to be identical; i.e., we need to know what the “$=$source” in that equation means for sets. Sets are defined to be identical whenever they have the same elements. So the definition we have to unpack is:

This definition uses $A$source and $B$source as placeholders for arbitrary sets. What it defines---the definiendum---is the expression “$A = B$source” by giving the condition under which $A = B$source is true. This condition---“every element of $A$source is an element of $B$source, and vice versa”---is the definiens.Footnote: In this particular case---and very confusingly!---when $A = B$source, the sets $A$source and $B$source are just one and the same set, even though we use different letters for it on the left and the right side. But the ways in which that set is picked out may be different, and that makes the definition non-trivial. The definition specifies that $A = B$source is true if, and only if (we abbreviate this to “iff”) the condition holds.

When you apply the definition, you have to match the $A$source and $B$source in the definition to the case you're dealing with. In our case, it means that in order for $A \cup B = B \cup A$source to be true, each $z \in A \cup B$source must also be in $B \cup A$source, and vice versa. The expression $A \cup B$source in the proposition plays the role of $A$source in the definition, and $B \cup A$source that of $B$source. Since $A$source and $B$source are used both in the definition and in the statement of the proposition we're proving, but in different uses, you have to be careful to make sure you don't mix up the two. For instance, it would be a mistake to think that you could prove the proposition by showing that every element of $A$source is an element of $B$source, and vice versa---that would show that $A = B$source, not that $A \cup B = B \cup A$source. (Also, since $A$source and $B$source may be any two sets, you won't get very far, because if nothing is assumed about $A$source and $B$source they may well be different sets.)

Within the proof we are dealing with set-theoretic notions such as union, and so we must also know the meanings of the symbol $\cup$source in order to understand how the proof should proceed. And sometimes, unpacking the definition gives rise to further definitions to unpack. For instance, $A \cup B$source is defined as $\Setabs{z}{z \in A \text{ or } z \in B}$source. So if you want to prove that $x \in A \cup B$source, unpacking the definition of $\cup$source tells you that you have to prove $x \in \Setabs{z}{z \in A \text{ or } z \in B}$source. Now you also have to remember that $x \in \Setabs{z}{\dots z\dots}$source iff $\dots x\dots$source. So, further unpacking the definition of the $\Setabs{z}{\dots z \dots}$source notation, what you have to show is: $x \in A$source or $x \in B$source. So, “every element of $A \cup B$source is also an element of $B \cup A$source” really means: “for every $x$source, if $x \in A$source or $x \in B$source, then $x \in B$source or $x \in A$source.” If we fully unpack the definitions in the proposition, we see that what we have to show is this:

What's important is that unpacking definitions is a necessary part of constructing a proof. Properly doing it is sometimes difficult: you must be careful to distinguish and match the variables in the definition and the terms in the claim you're proving. In order to be successful, you must know what the question is asking and what all the terms used in the question mean---you will often need to unpack more than one definition. In simple proofs such as the ones below, the solution follows almost immediately from the definitions themselves. Of course, it won't always be this simple.

Source file content/methods/proofs/inference-patterns.tex

Inference Patterns

Proofs are composed of individual inferences. When we make an inference, we typically indicate that by using a word like “so,” “thus,” or “therefore.” The inference often relies on one or two facts we already have available in our proof---it may be something we have assumed, or something that we've concluded by an inference already. To be clear, we may label these things, and in the inference we indicate what other statements we're using in the inference. An inference will often also contain an explanation of why our new conclusion follows from the things that come before it. There are some common patterns of inference that are used very often in proofs; we'll go through some below. Some patterns of inference, like proofs by induction, are more involved (and will be discussed later).

We've already discussed one pattern of inference: unpacking, or applying, a definition. When we unpack a definition, we just restate something that involves the definiendum by using the definiens. For instance, suppose that we have already established in the course of a proof that $D = E$source (a). Then we may apply the definition of $=$source for sets and infer: “Thus, by definition from (a), every element of $D$source is an element of $E$source and vice versa.”

Somewhat confusingly, we often do not write the justification of an inference when we actually make it, but before. Suppose we haven't already proved that $D = E$source, but we want to. If $D = E$source is the conclusion we aim for, then we can restate this aim also by applying the definition: to prove $D = E$source we have to prove that every element of $D$source is an element of $E$source and vice versa. So our proof will have the form: (a) prove that every element of $D$source is an element of $E$source; (b) every element of $E$source is an element of $D$source; (c) therefore, from (a) and (b) by definition of $=$source, $D = E$source. But we would usually not write it this way. Instead we might write something like,

subsectionUsing a Conjunction

Perhaps the simplest inference pattern is that of drawing as conclusion one of the conjuncts of a conjunction. In other words: if we have assumed or already proved that $p$source and $q$source, then we're entitled to infer that $p$source (and also that $q$source). This is such a basic inference that it is often not mentioned. For instance, once we've unpacked the definition of $D = E$source we've established that every element of $D$source is an element of $E$source and vice versa. From this we can conclude that every element of $E$source is an element of $D$source (that's the “vice versa” part).

subsectionProving a Conjunction

Sometimes what you'll be asked to prove will have the form of a conjunction; you will be asked to “prove $p$source and $q$source.” In this case, you simply have to do two things: prove $p$source, and then prove $q$source. You could divide your proof into two sections, and for clarity, label them. When you're making your first notes, you might write “(1) Prove $p$source” at the top of the page, and “(2) Prove $q$source” in the middle of the page. (Of course, you might not be explicitly asked to prove a conjunction but find that your proof requires that you prove a conjunction. For instance, if you're asked to prove that $D = E$source you will find that, after unpacking the definition of $=$source, you have to prove: every element of $D$source is an element of $E$source and every element of $E$source is an element of $D$source).

subsectionProving a Disjunction

When what you are proving takes the form of a disjunction (i.e., it is an statement of the form “$p$source or $q$source”), it is enough to show that one of the disjuncts is true. However, it basically never happens that either disjunct just follows from the assumptions of your theorem. More often, the assumptions of your theorem are themselves disjunctive, or you're showing that all things of a certain kind have one of two properties, but some of the things have the one and others have the other property. This is where proof by cases is useful (see below).

subsectionConditional Proof

Many theorems you will encounter are in conditional form (i.e., show that if $p$source holds, then $q$source is also true). These cases are nice and easy to set up---simply assume the antecedent of the conditional (in this case, $p$source) and prove the conclusion $q$source from it. So if your theorem reads, “If $p$source then $q$source,” you start your proof with “assume $p$source” and at the end you should have proved $q$source.

Conditionals may be stated in different ways. So instead of “If $p$source then $q$source,” a theorem may state that “$p$source only if $q$source,” “$q$source if $p$source,” or “$q$source, provided $p$source.” These all mean the same and require assuming $p$source and proving $q$source from that assumption. Recall that a biconditional (“$p$source if and only if (iff) $q$source”) is really two conditionals put together: if $p$source then $q$source, and if $q$source then $p$source. All you have to do, then, is two instances of conditional proof: one for the first conditional and another one for the second. Sometimes, however, it is possible to prove an “iff” statement by chaining together a bunch of other “iff” statements so that you start with “$p$source” an end with “$q$source”---but in that case you have to make sure that each step really is an “iff.”

subsectionUniversal Claims

Using a universal claim is simple: if something is true for anything, it's true for each particular thing. So if, say, the hypothesis of your proof is $A \subseteq B$source, that means (unpacking the definition of $\subseteq$source), that, for every $x \in A$source, $x \in B$source. Thus, if you already know that $z \in A$source, you can conclude $z \in B$source.

Proving a universal claim may seem a little bit tricky. Usually these statements take the following form: “If $x$source has $P$source, then it has $Q$source” or “All $P$sources are $Q$sources.” Of course, it might not fit this form perfectly, and it takes a bit of practice to figure out what you're asked to prove exactly. But: we often have to prove that all objects with some property have a certain other property.

The way to prove a universal claim is to introduce names or variables, for the things that have the one property and then show that they also have the other property. We might put this by saying that to prove something for all $P$sources you have to prove it for an arbitrary $P$source. And the name introduced is a name for an arbitrary $P$source. We typically use single letters as these names for arbitrary things, and the letters usually follow conventions: e.g., we use $n$source for natural numbers, $!A$source for formulas, $A$source for sets, $f$source for functions, etc.

The trick is to maintain generality throughout the proof. You start by assuming that an arbitrary object (“$x$source”) has the property $P$source, and show (based only on definitions or what you are allowed to assume) that $x$source has the property $Q$source. Because you have not stipulated what $x$source is specifically, other that it has the property $P$source, then you can assert that everything with $P$source has the property $Q$source. In short, $x$source is a stand-in for all things with property $P$source.

subsectionProof by Cases

Suppose you have a disjunction as an assumption or as an already established conclusion---you have assumed or proved that $p$source or $q$source is true. You want to prove $r$source. You do this in two steps: first you assume that $p$source is true, and prove $r$source, then you assume that $q$source is true and prove $r$source again. This works because we assume or know that one of the two alternatives holds. The two steps establish that either one is sufficient for the truth of $r$source. (If both are true, we have not one but two reasons for why $r$source is true. It is not necessary to separately prove that $r$source is true assuming both $p$source and $q$source.) To indicate what we're doing, we announce that we “distinguish cases.” For instance, suppose we know that $x \in B \cup C$source. $B \cup C$source is defined as $\Setabs{x}{x \in B \text{ or } x \in C}$source. In other words, by definition, $x \in B$source or $x \in C$source. We would prove that $x \in A$source from this by first assuming that $x \in B$source, and proving $x \in A$source from this assumption, and then assume $x \in C$source, and again prove $x \in A$source from this. You would write “We distinguish cases” under the assumption, then “Case (1): $x \in B$source” underneath, and “Case (2): $x \in C$source halfway down the page. Then you'd proceed to fill in the top half and the bottom half of the page.

Proof by cases is especially useful if what you're proving is itself disjunctive. Here's a simple example:

subsectionProving an Existence Claim

When asked to prove an existence claim, the question will usually be of the form “prove that there is an $x$source such that $\dots x \dots$source”, i.e., that some object that has the property described by “$\dots x \dots$source”. In this case you'll have to identify a suitable object and show that it has the required property. This sounds straightforward, but a proof of this kind can be tricky. Typically it involves constructing or defining an object and proving that the object so defined has the required property. Finding the right object may be hard, proving that it has the required property may be hard, and sometimes it's even tricky to show that you've succeeded in defining an object at all!

Generally, you'd write this out by specifying the object, e.g., “let $x$source be dots” (where dots specifies which object you have in mind), possibly proving that $\dots$source in fact describes an object that exists, and then go on to show that $x$source has the property $Q$source. Here's a simple example.

subsectionUsing Existence Claims

Suppose you know that some existence claim is true (you've proved it, or it's a hypothesis you can use), say, “for some $x$source, $x \in A$source” or “there is an $x \in A$source.” If you want to use it in your proof, you can just pretend that you have a name for one of the things which your hypothesis says exist. Since $A$source contains at least one thing, there are things to which that name might refer. You might of course not be able to pick one out or describe it further (other than that it is $\in A$source). But for the purpose of the proof, you can pretend that you have picked it out and give a name to it. It's important to pick a name that you haven't already used (or that appears in your hypotheses), otherwise things can go wrong. In your proof, you indicate this by going from “for some $x$source, $x \in A$source” to “Let $a \in A$source.” Now you can reason about $a$source, use some other hypotheses, etc., until you come to a conclusion, $p$source. If $p$source no longer mentions $a$source, $p$source is independent of the asusmption that $a \in A$source, and you've shown that it follows just from the assumption “for some $x$source, $x \in A$source.”

It's maybe good practice to keep bound variables like “$x$source” separate from hypothetical names like $a$source, like we did. In practice, however, we often don't and just use $x$source, like so:

However, when you do this, you have to be extra careful that you use different $x$source's and $y$source's for different existential claims. For instance, the following is not a correct proof of “If $A \neq \emptyset$source and $B \neq \emptyset$source then $A \cap B \neq \emptyset$source” (which is not true).

Can you spot where the incorrect step occurs and explain why the result does not hold?

Source file content/methods/proofs/example-1.tex

An Example

Our first example is the following simple fact about unions and intersections of sets. It will illustrate unpacking definitions, proofs of conjunctions, of universal claims, and proof by cases.

Let's prove it!

Source file content/methods/proofs/example-2.tex

Another Example

Source file content/methods/proofs/proof-by-contradiction.tex

Proof by Contradiction

In the first instance, proof by contradiction is an inference pattern that is used to prove negative claims. Suppose you want to show that some claim $p$source is false, i.e., you want to show $\lnot p$source. The most promising strategy is to (a) suppose that $p$source is true, and (b) show that this assumption leads to something you know to be false. “Something known to be false” may be a result that conflicts with---contradicts---$p$source itself, or some other hypothesis of the overall claim you are considering. For instance, a proof of “if $q$source then $\lnot p$source” involves assuming that $q$source is true and proving $\lnot p$source from it. If you prove $\lnot p$source by contradiction, that means assuming $p$source in addition to $q$source. If you can prove $\lnot q$source from $p$source, you have shown that the assumption $p$source leads to something that contradicts your other assumption $q$source, since $q$source and $\lnot q$source cannot both be true. Of course, you have to use other inference patterns in your proof of the contradiction, as well as unpacking definitions. Let's consider an example.

Every positive claim is trivially equivalent to a negative claim: $p$source iff $\lnot\lnot p$source. So proofs by contradiction can also be used to establish positive claims “indirectly,” as follows: To prove $p$source, read it as the negative claim $\lnot\lnot p$source. If we can prove a contradiction from $\lnot p$source, we've established $\lnot\lnot p$source by proof by contradiction, and hence $p$source.

In the last example, we aimed to prove a negative claim, namely that $A$source has no elements, and so the assumption we made for the purpose of proof by contradiction (i.e., that there is an $x \in A$source) was a positive claim. It gave us something to work with, namely the hypothetical $x \in A$source about which we continued to reason until we got to $x \in \emptyset$source.

When proving a positive claim indirectly, the assumption you'd make for the purpose of proof by contradiction would be negative. But very often you can easily reformulate a positive claim as a negative claim, and a negative claim as a positive claim. Our previous proof would have been essentially the same had we proved “$A = \emptyset$source” instead of the negative consequent “$A$source has no elements.” (By definition of $=$source, “$A = \emptyset$source” is a general claim, since it unpacks to “every element of $A$source is an element of $\emptyset$source and vice versa”.) But it is easily seen to be equivalent to the negative claim “not: there is an $x \in A$source.”

So it is sometimes easier to work with $\lnot p$source as an assumption than it is to prove $p$source directly. Even when a direct proof is just as simple or even simpler (as in the next examples), some people prefer to proceed indirectly. If the double negation confuses you, think of a proof by contradiction of some claim as a proof of a contradiction from the opposite claim. So, a proof by contradiction of $\lnot p$source is a proof of a contradiction from the assumption $p$source; and proof by contradiction of $p$source is a proof of a contradiction from $\lnot p$source.