A technical question about logic

Here is a thoroughly standard definition of 'sound deductive argument':

A deductive argument is sound if and only if it is both valid, and all of its premises are actually true. Otherwise, a deductive argument is unsound.

But a reductio ad absurdum is a deductive argument that proceeds from premises that are false. But a reductio can be sound, can't it? How is this possible? I mean: how is it officially possible, in light of the standard definition of deductive soundness? Is there some standard, textbook definition of 'sound reductio'? It seems that there should be. On the other hand, it is quite clear that what makes something a reductio is that it is a valid deductive structure with a certain pragmatic use as a proof, in light of the fact that the culprit responsible for generating the contradiction should be obvious. So perhaps there are technically no sound reductiones ad absurdum? (That seems absurd.)

Comments

[Juan]

Assumptions for reductio (and any other assumptions) are not premises, so a reductio can still be officially sound.

[Jim]

1. The hypothesis being reduced to an absurdity is not a premise of the argument. It's introduced as a supposition. That's different. E.g., if I want to prove that P&Q -> P, I'd begin by introducing P&Q as a supposition for conditional proof. That wouldn't make P&Q a premise of my argument. Same goes for hypotheses introduced for reductio.

2. There's certainly _a_ use of "reductio ad absurdum" to pick out a species of deductive argument, as you say. But in practice, I think lots of philosophers will call an argument a reductio even if it's not deductive, and even if the "absurdum" in question isn't a contradiction but just grossly implausible. That makes "reductios" look more like a species of informal argument. Point 1 would still apply about their premises, though.

[jholbo]

Thanks, Juan and Jim. I was sort of going to say myself that it's an assumption not a premise. Vague memories from intro logic years ago haven't quite faded. But isn't the difference between 'assumption' and 'premise' rather a peculiar one to introduce into formal logic, come to think of it?

Really what you are allowed to do is introduce any premise you like, for proof purposes. Calling it an 'assumption' is more or less just a way of announcing that you intend to make a particular use of it - probably making it the antecedent of a true conditional and then making use of that for some purpose. (And you still write 'P', not 'A' off to the right, giving that as your reason. Don't you?)

There isn't really a formal distinction between a premise and an assumption (is there?). Furthermore, it doesn't seem quite right to say that a reductio is sound, i.e. meets the letter of the definition of soundness, because it contains no false premises, only one (or more) false assumptions. Because why not take any other valid but unsound proof and turn it sound by declaring one of its premises to be an 'assumption'? That doesn't sound right.

Obviously this isn't really terribly momentous. Just a terminological detail. (My old logic textbooks are all boxed up for the summer, too, or I would have consulted their wisdom.)

I just happen to be writing a paper in which I had occasion to talk in passing about what a reductio is - just giving the standard definition - and I started talking about what a sound reductio is, and how you are able to introduce anything as a premise, for conditional proof purposes; and I realized I was in flagrant violation of the definition of 'sound'. And then I thought about distinguishing premises from assumptions, but suddenly it seemed a bit weak.

But I'm sure you are right that my logic textbooks, when I see them again, will say just what you said.

And Jim is right that the argument form may be regarded as informal, not deductive. Which does seem rather important.

[bza]

There's not really anything odd about a distinction between assumptions and premises. It might make the matter more intuitive if we note that an assumption can be made only for some sub-portion of the argument. That is, for some stretch of the proof, one reasons under the assumption, and so for that portion of the proof the assumption is just like a premise. But for the proof as a whole, one takes for granted only that the premises are true. The truth or fasity of the assumptions is neither here nor there.

So, for instance, in a natural deduction system one can prove A-->B by assuming that A is true, then deriving B, and therefrom conclude that A->B. After assuming A is true, A functions just like a premise. But when we conclude, from the derivability of B on the assumption A, that A->B is true, we're no longer reasoning under the assumption that A. We know A->B, and this doesn't depend on taking A to be true. So even though A functioned as a "premise"-like fashion at some points in the proof, the conclusion of the argument is independent of the truth or falsity of A. This is a useful distinction to mark, and it's marked by the distinction between assumption and premise.

[jholbo]

Let me add: if anyone wants to save me a trip to the library to check out a logic text by refreshing my 15 year old memories of first-order predicate calculus, I would be much obliged. What is the formal difference between an 'assumption' and a 'premise'? Presumably an obligation, in the former case, to conditionalize it away at some point. Is this distinction formally marked in basic logic texts by the introduction of a specific inference rule governing assumptions but not premises? Or is it just the case that you are allowed to look at the conclusion, notice that it didn't really depend on the suspect assumption that got conditionalized away, and call it a job well done. Obviously it really doesn't matter, but I'm just trying to remember the mechanical details of how I actually did my homework long ago, so my incidental asides about standard intro logic don't make me sound like I've forgotten intro logic the way I sort of actually have. (I mean, I still think logically and all. Try to.)

[jholbo]

Thanks for your response, bza, which come while I was posting my follow-up bleg to my own comment. Let me clarify that I perfectly well see the difference between a premise and an assumption. And I very much appreciate the utility of being able to assume things for purposes of conditional proof. But I don't remember the distinction being formally marked in my intro logic text. When I said 'weak' I really only mean 'not formal', because the difference is really a matter of intended purpose, and authorial intentions are not usually marked in formal proofs like that. But maybe I'm forgetting that once upon a time I knew about different formal rules for dealing with premises and assumptions. It's just been too long since I did my homework.

[Juan]

John, the difference between assumptions and premises is that assumptions have to be cancelled. That is a formal difference--rules governing assumptions always have a cancellation step, rules governing premises don't. In some textbooks, you even put a little sign to the left of any assumption, and then draw a line marking the scope of the assumption. Of course, whether you use a proposition as an assumption or a premise depends on you, but what doesn't depend on you is what you can infer from that, and you can infer different things from the same proposition depending on whether you use it as a premise or as an assumption. This doesn't mean, I don't think, that the difference is not formal. Or, at least, it is as formal as the difference between premises and conclusion. Which of "If A then B" and "If not-B then not-A" you use as premise and which as conclusion is also up to you.

[Juan]

Let me just add that, in many systems, the difference between premises and assumptions is crucial when dealing with quantifiers. In many systems you need assumptions both to introduce the universal and to eliminate the existential, and it is absolutely crucial that those assumptions be cancelled in the right way.

[jholbo]

Okey, thanks Juan. That really does bring it all back. It's obviously necessary to cancel, and to do it in the right way. Somehow I've just blotted out the experience. It must have been somehow traumatic for me to see those implausible little assumptions just go away like that.

In short, I've been blathering and wasting everyone's time with this post. Cheers, and thanks for reviving the memories.

[Jonathan Lundell]

Suppose we're proving some supposition S to be false because it leads to a false conclusion F. The reductio argument is:

1. Assume S.
2. Premise: F is false.
3. Premise: S implies F.
4. S must be false because it implies a false conclusion.

But that argument can be recast as a simple deduction:

1. Premise: F is false
2. Premise: S implies F
3. From (1) we argue that ~F is true (excluded middle and non-contradiction).
4. from (2) we argue that ~F implies ~S (modus tollens).
5. from (3) and (4) we argue that ~S (modus ponens). QED.

No assumptions, no cancellations, just true premises and a valid deduction. The two forms are isomorphic.

[jholbo]

This is right, Jonathan. But a potential difference might concern step 3 in your first proof. Plausibly, 3 needn't be a premise but can be deduced from premise 1. (You assume S, then prove F from S, from which S -> F follows, at which point you've conditionalized away your S.) What this shows is a potentially important difference between the first proof and the second. Namely, the first contains a kind of subproof of premise 2 of the second proof (P2 needn't be obviously true, after all.)

[jam]

The premise of a reductio is that the conclusion of a valid implication is false:

Premise: -F;
S => F;
Therefore -S.

This is a sound deductive argument.

But people are sloppy. All the hard work in the proof is showing that S => F. So they regard that step as actually constituting the argument. It doesn't. That's why Banach-Tarski is a paradox: S => F and F doesn't look very appetizing but I'm not willing to say right out that it's false so I can't really say that S is false so I'll label the whole thing a paradox and let other people worry about it.

[Jonathan Lundell]

John, call it a meta-premise if you like, but for reductio to succeed, S must imply F.

My premise was S -> F; your that "F can be proved from S" (if it can't, you don't have a proof, after all). Isn't that a distinction without a difference?

[jholbo]

Well, one way to see the difference is to see that the assumption of S is unnecessary in your first proof. If you are ALSO going to assume S-> F you can get by just with the latter, since the latter is sufficient to prove -S, on the assumption of -F. This shows why people actually assume S, in cases like this. They want to use it to demonstrate the self-evidence of S -> F before taking it as premise.

[Des von Bladet]

I've only studied logic in maths ("math") departments, but it seems to me you can skip all the assumption/premise malarkey by rewriting the whole argument as a giant "if" clause:

If P then (argument goes here) we obtain a contradiction. Therefore ¬P.

[Des von Bladet]

I've only studied logic in maths ("math") departments, but it seems to me you can skip all the assumption/premise malarkey by rewriting the whole argument as a giant "if" clause:

If P then (argument goes here) we obtain a contradiction. Therefore ¬P.

[jholbo]

You can rewrite it as a conditional, but only after you've got it. On the assumption that the conditional isn't obvious, you need to construct it, and you need rules for construction. I do agree that this discussion is pointless to the extent that it truly is a completely verbal question. There isn't any question whether reductio ad absurdum works, or how it works. It's just a matter of how to label its bits so that the definition of 'sound' potentially covers some reductiones. Making the premise/assumption distinction, and marking the difference with formal rules, makes that possible. For what it's worth.

[Neel Krishnaswami]

It looks like you're getting slightly confused by the fact that the schema for proof by contradiction is higher-order. If you look at it, it looks like this, where ~ means not and -> is implication.

(~A -> false) -> A

So this schema, together with a proof that not-A implies false, will let you conclude A using the ordinary implication elimination rule. And to prove that not-A implies false, you are allowed to assume not-A using the ordinary implication introduction rule.

With a Gentzen-style proof tree:

   ----[x]
    ~A
     .
     .
     .
   false
-----------[x]        
~A -> false     (~A -> false) -> A 
----------------------------------
               A

The [x] shows that the assumption of ~A is introduced because you are proving an implication. It's not a premise of the whole proof, but only of a subtree of it.

[Jonathan Lundell]

If I follow Neel, his "higher-order schema" is what I was trying to get at with "meta-premise". And if we haven't beaten this to death by now, and if I follow John's drift, I'd like to see a specific reductio argument that can't be recast as straight deduction. I've been asserting that there is no such argument, so I'm easily refuted by a counterexample. (Well, if I'm right, then not so easily.)

[Juan]

Jonathan, I'm not really sure what you are looking for, but how about this proof that 'p->p'?

1. p assumption for -> intro
2. -p assumption for reductio
3. p.-p conjunction, 1 and 2
4. --p reductio 2-3
5. p double neg., 4
6. p->p -> intro, 1-5

[Jonathan Lundell]

Juan, let me recap. John adduced a definition for a "sound deductive argument", and pointed out that it includes a requirement that all the argument's premises be valid, and that since a reduction ad absurdum proceeds from false premises, it isn't (per the definition) a sound deductive argument.

John concludes by wondering whether reduction arguments are techinically sound (or perhaps whether the definition of a technically sound argument needs a rewrite).

I conjecture that none of this is necessary, because any reductio argument can be transformed into a simple deduction with true premises, fitting the definition as given. That is, a valid reduction argument is always a simple deductive argument in another form.

If my conjecture is true, then John's worry is unnecessary. If it's false, then there should be a reduction argument that cannot be so transformed, and I'm asking for an example merely.

[Neel Krishnaswami]

Hi Jonathan, my officemate pointed out that your conjecture isn't true. You have to introduce a hypothetical to prove negation -- the rule for introducing negations is of the form:

    [x]
     A
     .
     .
     .
   false
  -------[x]
    ~A

That is, to prove not-A, you must assume A is true and then show that assumption lets you derive false.

[Juan]

Jonathan, didn't I provide what you were looking for? Granted, the main proof is not a reductio, but (a) it contains one, and (b) John's point applies to all proofs with assumptions, not just reductiones.

Also, suppose you are right, and a reductio can be transformed into an argument from true premises. (I'm still not sure I understand what you are after with this, and I waver between thinking that is obviously true but irrelevant and obviously false. Perhaps if you tell me whether my proof above is a counterexample I can decide.) So what? It's going to be a different argument, and so John's question still applies to the original argument.

[William S]

I think the more interesting question is whether a reductio can be unsound.

[The 16]

Firstly, know the exact meaning of 'reductio ad absurdum'. i'm just 16. Interested in whatever argumentative it is... :)