Unit 9: Conditional Proof and Indirect Proof

Using CP and IP

Make an assumption. Write anything on a line! (again, like addition, you’ll only do this with very specific forward-looking goals in mind, so don’t use this randomly)

Justify that line by way of “Assp. C.P.” or “Assp. I.P.”

This line is typically indented a bit.

Start drawing a line at this assumption down the left side of the proof lines (just right of the numbers).

Make justified steps as usual until you get to the thing you wanted to prove from the assumption and then close off the line by underlining the last line of the C.P. or I.P.

You must discharge all assumptions before you finish the overall proof!

conditional Proof (CP)

For conditional proof, our assumption will always be the antecedent of the conditional we wish to prove.

We then try to derive the conclusion of the conditional we wish to prove within that scope of that assumption.

Once we have it, we close of the scope and are justified in writing the conditional on a line outside the scope line with the right-side justification being “C.P. n1-n2”

Indirect Proof (IP)

For I.P. (aka, Reductio ad Absurdum), we assume the opposite of what we want to prove (i.e. the unnegated conclusion).

We then show that that assumption leads to absurdity (i.e. any contradiction).

We are then justified in closing the scope of the assumption and writing the negation of the assumption. (justified with “I.P. n1-n2”)

Theorem: a statement form that can be proven from no premises (Pr.).

Use C.P. or I.P. to introduce and discharge assumptions to construct theorems.

As we have seen, the truth-table method (sometimes called the semantic method) is theoretically independent from the proof method (which I sometimes call a syntactic method, though that isn’t common).

For sentential logic these two methods give exactly the same results in every case.

Sentential logic is (unsurprisingly) complete and consistent.

However, (very surprisingly), even basic arithmetic is incomplete. That is, there are true arithmetical claims which cannot be proven.