[PDF] prf1 Proof by Contradiction - Open Logic Project Builds

41264_1proof_by_contradiction.pdf prf.1 Proof by Contradiction mth:prf:con: secIn the ifirst instance, proof by contradiction is an inference pattern that is used to prove negative claims. Suppose you want to show that some claimpisfalse, i.e., you want to show¬p. The most promising strategy is to (a) suppose that pis 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 conlflicts with - contradicts - pitself, or some other hypothesis of the overall claim you are considering. For instance, a proof of "ifqthen¬p" involves assuming that qis true and proving¬pfrom it. If you prove¬pby contradiction, that means assumingpin addition toq. If you can prove¬qfromp, you have shown that the assumptionpleads to something that contradicts your other assumptionq, sinceqand¬qcannot both be true. Of course, you have to use other inference patterns in your proof of the contradiction, as well as unpacking deifinitions.

Let's consider an example.

Proposition prf.1.IfA⊆BandB=∅, thenAhas noelements . Proof.SupposeA⊆BandB=∅. We want to show thatAhas noelemen ts. Since this is a conditional claim, we assume the antecedent and want to prove the consequent. The consequent is:Ahas noelemen ts. We can make that a bit more explicit: it's not the case that there is anx∈A. Ahas noelemen tsifff it's not the case that there is an xsuch thatx∈A. So we've determined that what we want to prove is really a negative claim¬p, namely: it's not the case that there is anx∈A. To use proof by contradiction, we have to assume the corresponding positive claimp, i.e., there is anx∈A, and prove a contradiction from it. We indicate that we're doing a proof by contradiction by writing "by way of contradiction, assume" or even just "suppose not," and then state the assumptionp.

Suppose not: there is anx∈A.

This is now the new assumption we'll use to obtain a contradiction. We have two more assumptions: thatA⊆Band thatB=∅. The ifirst gives us thatx∈B:

SinceA⊆B,x∈B.

But sinceB=∅, everyelemen tof B(e.g.,x) must also bean ele- ment of ∅. SinceB=∅,x∈ ∅. This is a contradiction, since by deifinition∅has no elements . proof-by-contradictionrev:5df41c7 (2023-06-07) b yOLP / CC-BY 1 This already completes the proof: we've arrived at what we need (a contradiction) from the assumptions we've set up, and this means that the assumptions can't all be true. Since the ifirst two assump- tions (A⊆BandB=∅) are not contested, it must be the last assumption introduced (there is anx∈A) that must be false. But if we want to be thorough, we can spell this out. Thus, our assumption that there is anx∈Amust be false, hence,Ahas no elements

b ypro ofb ycon tradiction.Every positive claim is trivially equivalent to a negative claim:pifff¬¬p.

So proofs by contradiction can also be used to establish positive claims "indi- rectly," as follows: To provep, read it as the negative claim¬¬p. If we can prove a contradiction from¬p, we've established¬¬pby proof by contradiction, and hencep. In the last example, we aimed to prove a negative claim, namely thatA has no elemen ts , and so the assumption we made for the purpose of proof by contradiction (i.e., that there is anx∈A) was a positive claim. It gave us something to work with, namely the hypotheticalx∈Aabout which we continued to reason until we got tox∈ ∅. 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=∅" instead of the negative consequent "Ahas no elements ." (By deifinition of =, "A=∅" is a general claim, since it unpacks to "every elemen t of Ais anelemen tof ∅and vice versa".) But it is easily seen to be equivalent to the negative claim "not: there is anx∈A." So it is sometimes easier to work with¬pas an assumption than it is to provepdirectly. 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 theoppositeclaim. So, a proof by contradiction of¬p is a proof of a contradiction from the assumptionp; and proof by contradiction ofpis a proof of a contradiction from¬p.

Proposition prf.2.A⊆A∪B.

Proof.We want to show thatA⊆A∪B.

On the face of it, this is a positive claim: everyx∈Ais also in A∪B. The negation of that is: somex∈Ais/∈A∪B. So we can prove the claim indirectly by assuming this negated claim, and showing that it leads to a contradiction.

Suppose not, i.e.,A⊈A∪B.

2proof-by-contradictionrev:5df41c7 (2023-06-07) b yOLP / CC-BY

We have a deifinition ofA⊆A∪B: everyx∈Ais also∈A∪B. To understand whatA⊈A∪Bmeans, we have to use some elementary logical manipulation on the unpacked deifinition: it's false that every x∈Ais also∈A∪Bifff there issomex∈Athat is/∈C. (This is a place where you want to be very careful: many students' attempted proofs by contradiction fail because they analyze the negation of a claim like "allAs areBs" incorrectly.) In other words,A⊈A∪B ifff there is anxsuch thatx∈Aandx /∈A∪B. From then on, it's easy. So, there is anx∈Asuch thatx /∈A∪B. By deifinition of∪,x∈A∪B ifffx∈Aorx∈B. Sincex∈A, we havex∈A∪B. This contradicts the assumption thatx /∈A∪B.Problem prf.1.ProveindirectlythatA∩B⊆A. Proposition prf.3.IfA⊆BandB⊆CthenA⊆C. Proof.SupposeA⊆BandB⊆C. We want to showA⊆C. Let's proceed indirectly: we assume the negation of what we want to etablish.

Suppose not, i.e.,A⊈C.

As before, we reason thatA⊈Cifff not everyx∈Ais also∈C, i.e., somex∈Ais/∈C. Don't worry, with practice you won't have to think hard anymore to unpack negations like this. In other words, there is anxsuch thatx∈Aandx /∈C. Now we can use this to get to our contradiction. Of course, we'll have to use the other two assumptions to do it.

SinceA⊆B,x∈B. SinceB⊆C,x∈C. But this contradictsx /∈C.Proposition prf.4.IfA∪B=A∩BthenA=B.

Proof.SupposeA∪B=A∩B. We want to show thatA=B.

The beginning is now routine:

Assume, by way of contradiction, thatA̸=B.

Our assumption for the proof by contradiction is thatA̸=B. Since A=BifffA⊆BanB⊆A, we get thatA̸=BifffA⊈Bor B⊈A. (Note how important it is to be careful when manipulating negations!) To prove a contradiction from this disjunction, we use a proof by cases and show that in each case, a contradiction follows. proof-by-contradictionrev:5df41c7 (2023-06-07) b yOLP / CC-BY 3 A̸=BifffA⊈BorB⊈A. We distinguish cases. In the ifirst case, we assumeA⊈B, i.e., for somex,x∈Abut/∈B. A∩Bis deifined as thoseelemen tsthat AandBhave in common, so if something isn't in one of them, it's not in the intersection. A∪BisAtogether withB, so anything in either is also in the union. This tells us thatx∈A∪Bbutx /∈A∩B, and hence that

A∩B̸=A∪B.

Case 1:A⊈B. Then for somex,x∈Abutx /∈B. Sincex /∈B, then x /∈A∩B. Sincex∈A,x∈A∪B. So,A∩B̸=A∪B, contradicting the assumption thatA∩B=A∪B. Case 2:B⊈A. Then for somey,y∈Bbuty /∈A. As before, we havey∈A∪Bbuty /∈A∩B, and soA∩B̸=A∪B, again contradicting

A∩B=A∪B.Photo Credits

Bibliography

4