Ethical Realism

February 20, 2013

Logic Part 6: Conditional & Indirect Proof

Filed under: philosophy — JW Gray @ 9:27 am
Tags: ,

Part 1 | Part 2 | Part 3 | Part 4 | Part 5

This is part 6 of a series. Links to the other parts of the series are above.

The straightforward way to construct proofs using natural deduction is called the “direct method.” Every line of that type of proof is validly deduced from the premises and rules of inference. Every line of such a proof could be considered to be true as long as we consider the premises to be true. However, there are two other strategies: The conditional proof and the indirect proof. Both of these types of proofs introduce an additional premise that is assumed to be true “for the sake of argument.”

Conditional proof

If a proof contains a conditional statement as a premise, conclusion, or as a proven statement based on the premises, then we can add an additional premise afterward—the first part of the conditional. For example, “A” is the first part of the conditional “A → B.” Let’s assume “A” is added as an “assumption for conditional proof.” In that case the letters “ACP” are put on the right-hand side of the line it’s added on. This line can be added to the proof at any time, but it is often added right after the other premises are stated. The assumed premise is then used to derive a conditional statement.

Then once a conditional is derived using the assumed premise, we have a conditional proof and the final line of the proof has “CP” on the right-hand side. All lines using the assumption are also cited. However, the conditional proof is not necessarily the entirety of the proof—more might have to be proven to deduce the conclusion of the original argument that we want to prove to be valid.

The lines of conditional proofs that are used to derive the conditional conclusion can’t be used by any other part of the proof. These lines require a tentative assumption and are not validly deduced by the premises of the original argument. The assumption itself is not validly deduced from the original argument, and the rest of the proof requires that assumption, other than the conclusion of the conditional proof.

Example

Consider the following argument:

  1. If all humans are mortal, then no humans are gods and no humans are angels.

  2. If no humans are gods, then no human is omnipotent and no human is omniscient.

  3. Therefore, either all humans are mortal or it’s not the case that no human is omnipotent.

This argument has the following form in propositional logic:

  1. A → (B ∧ C)

  2. B → (D ∧ E)

  3. ∴¬A ∨ D

A: All humans are mortal.

B: No humans are gods.

C: No humans are angels.

D: No human is omnipotent.

E: No human is omniscient.

The following is the proof that this argument is valid (using conditional proofs):

  1. A → (B ∧ C)

  1. B → (D ∧ E)

/ ¬A ∨ D

  1. A

ACP

  1. B ∧ C

1, 3, MP

  1. B

4, Simp

  1. A → B

3, 4, 5, CP

  1. B

ACP

  1. D ∧ E

2, 7, MP

  1. D

8, Simp

  1. B → D
7, 8, 9 CP
  1. A → D
7, 10, HS
  1. ¬A ∨ D
11, Impl

Lines 3, 4, and 5 contain a single conditional proof. The assumption for conditional proof (A) is allowed because line 1 contains a conditional, and the first part of the conditional is “A.”

Lines 7, 8, and 9 contain another conditional proof. The assumption for conditional proof (B) is allowed because line 2 contains a conditional, and the first part of the conditional is “B.”

Because lines 3-5 and 7-9 contain conditional proofs, those lines are not actually validly deduced from the original premises. If they were, line 5 would have already proven “B,” so the second conditional proof would have been unnecessary. These lines are merely tentatively assumed to be validly deduced for the sake of argument.

The conclusions of each conditional proof are proven, and they are used with a hypothetical syllogism to prove “A → D.” We know “A → B; B → D; ∴ A → D” is a valid argument because it has the same form as the hypothetical syllogism (p → q; q → r; ∴p → r”).

Finally, keep in mind that the conclusion of our argument can also justify the use of an assumption for a conditional proof as long as it’s a conditional statement. For example, if an argument concludes “A → (B ∧ C),” then we can have “A” as an assumption for a conditional proof.

Indirect proof

Indirect proofs are also known as a “reductio ad absurdum” (i.e. “reduction to the absurd”). Indirect proofs can be used to prove any argument is valid. Indirect proofs have three additional steps:

  1. There’s an additional premise—a statement that is tentatively assumed to be true. This is the “assumption for indirect proof” and “AIP” is written on the right-hand side of the line of the assumption. This statement is one we will actually hope to prove to be false.

  2. The assumption is used to derive a contradiction (p ∧ ¬p). The contradiction must appear on a line, and it is often explicitly derived on a single line using the rule of conjunction.

  3. Once the contradiction is derived, the negation of the assumption is proven. “IP” is written on the right-hand side of that line along with the numbers of all lines that use the assumed premise.

Once again, the lines of an indirect proof require tentative assumptions, and they are not proven to be validly deduced from the original premises. They can’t be used by other parts of the proof for that reason. Only the final line of an indirect proof is actually proven (and it is validly deduced from the original premises).

Note that indirect proofs often assume the negation of the conclusion. Once it is proven that assuming the negation of the conclusion leads to a contradiction, the conclusion is actually proven to be true. For example, we can assume that the conclusion of modus ponens is false. In that case we assume “p → q,” “p” and “¬q” to be true. But “p → q” and “¬q” proves “¬p” to be true via modus tollens. We now know that the argument is valid because assuming the conclusion is false leads to a contradiction (“p ∧ ¬p”).

Example

Consider the following argument:

  1. Either killing people is sometimes wrong or always wrong.

  2. If the killing people is always wrong, then killing people when necessary for self-defense is wrong, and killing people when necessary for self-defense is not wrong.

  3. If killing people is sometimes wrong, then not all homicide is murder.

  4. Therefore, sometimes homicide is not murder.

The logical form of this argument is the following:

  1. P ∨ Q

  2. P → (R ∧ ¬R)

  3. Q → S

  4. ∴S

P: Killing people is sometimes wrong.

Q: Killing people is always wrong.

R: Killing people when necessary for self-defense is wrong.

S: Sometimes homicide is not murder.

A proof that this argument is valid using an indirect proof is the following:

  1. P ∨ Q

  1. P → (R ∧ ¬R)

  1. Q → S

/ S

  1. Q ∨ P

1, Com

  1. ¬Q

AIP

  1. P

4, 5, DS

  1. R ∧ ¬R

2, 6, MP

  1. Q

5, 6, 7, IP

  1. S

3, 8, MP

The indirect proof occurs on lines 5, 6, and 7. It was necessary to show that “Q” is true in order to use line 3 (Q → S) with modus ponens to reach the conclusion (S).

Note that the lines of the indirect proof are not actually taken to be validly deduced in the long run. They are only tentatively assumed to be validly deduced. The assumption is actually the negation of what is proven.

Update: I said something about how lines of a proof are “proven true,” but they are only proven true if the premises are true. This point was clarified above. Other minor corrections were made.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: