1.4: A.4- Inference Patterns

Using 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\) and \(q\), then we’re entitled to infer that \(p\) (and also that \(q\)). This is such a basic inference that it is often not mentioned. For instance, once we’ve unpacked the definition of \(D = E\) we’ve established that every element of \(D\) is an element of \(E\) and vice versa. From this we can conclude that every element of \(E\) is an element of \(D\) (that’s the “vice versa” part).

Proving a Conjunction

Sometimes what you’ll be asked to prove will have the form of a conjunction; you will be asked to “prove \(p\) and \(q\).” In this case, you simply have to do two things: prove \(p\), and then prove \(q\). 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\)” at the top of the page, and “(2) Prove \(q\)” 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\) you will find that, after unpacking the definition of \(=\), you have to prove: every element of \(D\) is an element of \(E\) and every element of \(E\) is an element of \(D\)).

Proving a Disjunction

When what you are proving takes the form of a disjunction (i.e., it is an statement of the form “\(p\) or \(q\)”), 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).

Conditional Proof

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

Conditionals may be stated in different ways. So instead of “If \(p\) then \(q\),” a theorem may state that “\(p\) only if \(q\),” “\(q\) if \(p\),” or “\(q\), provided \(p\).” These all mean the same and require assuming \(p\) and proving \(q\) from that assumption. Recall that a biconditional (“\(p\) if and only if (iff) \(q\)”) is really two conditionals put together: if \(p\) then \(q\), and if \(q\) then \(p\). 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\)” and end with “\(q\)”—but in that case you have to make sure that each step really is an “iff.”

Universal 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\), that means (unpacking the definition of \(\subseteq\)), that, for every \(x \in A\), \(x \in B\). Thus, if you already know that \(z \in A\), you can conclude \(z \in B\).

Proving a universal claim may seem a little bit tricky. Usually these statements take the following form: “If \(x\) has \(P\), then it has \(Q\)” or “All \(P\)s are \(Q\)s.” 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\)s you have to prove it for an arbitrary \(P\). And the name introduced is a name for an arbitrary \(P\). We typically use single letters as these names for arbitrary things, and the letters usually follow conventions: e.g., we use \(n\) for natural numbers, \(A\) for formulas, \(A\) for sets, \(f\) for functions, etc.

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

Proof by Cases

Suppose you have a disjunction as an assumption or as an already established conclusion—you have assumed or proved that \(p\) or \(q\) is true. You want to prove \(r\). You do this in two steps: first you assume that \(p\) is true, and prove \(r\), then you assume that \(q\) is true and prove \(r\) 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\). (If both are true, we have not one but two reasons for why \(r\) is true. It is not necessary to separately prove that \(r\) is true assuming both \(p\) and \(q\).) To indicate what we’re doing, we announce that we “distinguish cases.” For instance, suppose we know that \(x \in B \cup C\). \(B \cup C\) is defined as \(\Setabs{x}{x \in B \text{ or } x \in C}\). In other words, by definition, \(x \in B\) or \(x \in C\). We would prove that \(x \in A\) from this by first assuming that \(x \in B\), and proving \(x \in A\) from this assumption, and then assume \(x \in C\), and again prove \(x \in A\) from this. You would write “We distinguish cases” under the assumption, then “Case (1): \(x \in B\)” underneath, and “Case (2): \(x \in C\) 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:

Proving an Existence Claim

When asked to prove an existence claim, the question will usually be of the form “prove that there is an \(x\) such that \(\dots x \dots\)”, i.e., that some object that has the property described by “\(\dots x \dots\)”. In this case you’ll have to identify a suitable object 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\) be …” (where … specifies which object you have in mind), possibly proving that \(\dots\) in fact describes an object that exists, and then go on to show that \(x\) has the property \(Q\). Here’s a simple example.

Using 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\), \(x \in A\)” or “there is an \(x \in A\).” 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\) 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\)). 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\), \(x \in A\)” to “Let \(a \in A\).” Now you can reason about \(a\), use some other hypotheses, etc., until you come to a conclusion, \(p\). If \(p\) no longer mentions \(a\), \(p\) is independent of the asusmption that \(a \in A\), and you’ve shown that it follows just from the assumption “for some \(x\), \(x \in A\).”

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

Suppose \(A \neq \emptyset\), i.e., there is an \(x \in A\). By definition of \(\cup\), \(x \in A \cup B\). So \(A \cup B \neq \emptyset\).

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

Suppose \(A \neq \emptyset\) and \(B \neq \emptyset\). So for some \(x\), \(x \in A\) and also for some \(x\), \(x \in B\). Since \(x \in A\) and \(x \in B\), \(x \in A \cap B\), by definition of \(\cap\). So \(A \cap B \neq \emptyset\).

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