## Friday, 6 September 2013

### Further thoughts on reductio proofs

(Cross-posted at NewAPPS)

Some months ago I wrote two posts on the concept of indirect proofs: one presenting a dialogical conception of these proofs, and the other analyzing the concept of ‘proofs through the impossible’ in the Prior Analytics. Since then I gave a few talks on this material, receiving useful feedback from audiences in Groningen and Paris. Moreover, this week we hosted the conference ‘Dialectic andAristotle’s Logic’ in Groningen, and after various talks and discussions I have come to formulate some new ideas on the topic of reductio proofs and their dialectical/dialogical underpinnings. So for those of you who enjoyed the previous posts, here are some further thoughts and tentative answers to lingering questions.

Recall that the dialogical conception I presented in previous posts was meant to address the awkwardness of the first speech act in a reductio proof, namely that of supposing precisely that which you intend to refute by showing that it entails an absurdity. From studies in the literature on math education, it is known that this first step can be very confusing to students learning the technique of reductio proofs. On the dialogical conception, however, no such awkwardness arises, as there is a division of roles between the agent who supposes the initial thesis to be refuted, and the agent who in fact derives an absurdity from the thesis.

However, at that point I did not have a satisfactory answer to the contentious last step in a reductio proof, namely to conclude A from the fact that ~A entails an absurdity, or to conclude ~A from the fact that A entails an absurdity. (It is important to distinguish these two cases, as intuitionists are more than happy to accept the latter but vehemently deny the former.) In more pragmatic terms, the issue with this last step is the contentious move from showing that maintaining thesis A is a bad idea to concluding that maintaining thesis ~A is a good idea. For all we know, maintaining thesis ~A is also a bad idea.

Another philosophical problem with reductio proofs (which was mentioned during the conference by Mathieu Marion, and if my memory does not fail me a point that was raised by Mic Detlefsen when I presented the material in Paris) is that there is no way of knowing who exactly is the 'culprit' that led to absurdity. In a reductio proof, typically a given statement is isolated from the start as the one to be refuted (“Suppose for reductio that…”). But as the proof proceeds, along the way typically use is made of other premises, which may themselves be the source of trouble leading to absurdity. Why single out one particular thesis as the one to be refuted? Why conclude ~A rather than ~B in a reductio proof that starts with an assumption of A, but which uses B as a premise along the way?

Finally, a frequent charge against reductio proofs is that they have lower explanatory value than direct proofs: they show that something is the case, but not why something is the case. This is the gist of Aristotle’s own statement of the superiority of ‘ostensive’ (direct) demonstration over demonstration through the impossible in the Posterior Analytics A 26 (thanks to Marko Malink for the reference).

At the conference earlier this week, I came to realize that these issues arise from the fact that reductio proofs are expected to do a job that their genealogical antecedent, namely dialectical refutations, were not expected to perform. The typical structure of a dialectical exchange (as exemplified in Plato’s dialogues but also in Aristotle’s Topics) is for the questioner to show that the theses jointly maintained by the answerer lead to absurdity; in other words, the goal is to show that the answerer’s epistemic and discursive commitments are jointly incoherent. Indeed, this is the quintessential, and perhaps even the only way to ‘win’ such debates: to force your opponent into an incoherent position.

Now, as argued by L. Castagnoli (one of the conference’s participants) in his work on the notion of self-refutation (book, paper), the goal of reaching absurdity in such dialectical exchanges is not to establish the truth-value of a given thesis (either the falsity of one of answerer’s claims or the truth of the opposite claim), but simply to serve as a dialectical ‘silencer’:
Although ancient self-refutation arguments cannot ‘falsify’ our most radical adversaries’ views (and defuse our own most hyperbolical doubts) by proving that what they envisage is ‘logically impossible’, they can silence them, by delimiting the area of constructive philosophical inquiry and debate. (Castagnoli 2007, 69)
This is exactly what happens, for example, in Zeno’s paradoxical arguments: they show that rejecting Parmenides’ thesis that there is no such thing as movement or change leads to absurd conclusions. The argument is not meant to establish the truth of Parmenides’ position, but simply to discredit the position of his opponents. [UPDATE: this is precisely the position that Plato attributes to Zeno in Parmenides 128 a-e -- thanks to Matthew Duncombe for the reference.]

What this all means for the issue of reductio proofs is that, in a sense, and at least historically, indirect argumentation of this kind – refutation – had pride of place in ancient dialectic, rather than being a derivative concept vis-à-vis direct argumentation. However, these refutations were not expected to establish the truth-value (either truth or falsity) of a given statement: they were only meant to show the incoherence of the answerer’s overall position. In other words, the last contentious step in a reductio proof is conceptually extraneous to the original dialectical framework – no wonder it looks suspicious! Similarly, given that a refutation is intended to discredit the answerer’s overall position, the issue of the actual culprit leading to absurdity does not arise: there is no need to locate the exact source of trouble. Finally, such refutations were not expected to perform an explanatory role; instead, if they were intended as dialectical silencers, they were purely adversarial tools, whereas explanation is essentially a cooperative notion.

The core idea in my current research project is that every proof is and is not a dialogue: it is a dialogue because it retains crucial dialogical/dialectical features, but it is not a dialogue properly speaking because one of the participants has been internalized (the built-in opponent hypothesis). In the case of reductio proofs, their dialogical/dialectical origins are even more acutely perceived, but a key transformation was from the concept of purely negative refutations as ‘dialectical silencers’ to the concept of indirect proofs, capable of establishing positive conclusions. Moreover, as purely eristic (adversarial) dialectic then gave rise to more cooperative, didactic contexts where explanation of causes became the key notion (as in Aristotle’s notion of episteme), direct arguments came to be preferred over indirect ones.

In sum, I submit that reductio proofs are rightly seen as philosophically problematic. Even if the dialogical conception alleviates worries concerning the awkwardness of the first speech-act in a reductio proof, the contentious last step from absurdity to the final conclusion is extraneous to the dialectical framework of refutations. It requires (potentially unfairly) singling out a particular assumption as the culprit, and is based on a pragmatically questionable move (bad idea to maintain A/~A => good idea to maintain ~A/A).

However, while perhaps philosophically suspicious, I think it is fair to say that most of us are not prepared to live without this argumentative strategy in our tool boxes; it is just too damn convenient!

(Caveat: this analysis is based only on elements from the history of logic and philosophy; it would be interesting to see if similar considerations apply to the development of reductio proofs in mathematics.)

1. I'm not sure how much I'm worried by the "other culprits" objection. It seems to me to be a bit like objecting to a proof that A implies B on the grounds that "other facts" were brought in. In both reductio proofs and straightforward proofs one can use other facts if they have already been established. In both cases, one could consider objecting that they weren't truly established. I don't understand what separates reductio proofs from other proofs here.

There might of course be a situation where you make three assumptions and derive a contradiction. Then it is indeed wrong to single out one of them. But nobody does: the result of such an argument will be that the three assumptions cannot all be true.

1. This is very interesting. But as regards the history, I don't think that the structure of the relevant ('Socratic') dialogues is 'for [Socrates] to show that the theses jointly maintained by the answerer lead to absurdity; in other words, the goal is to show that the answerer’s epistemic and discursive commitments are jointly incoherent'. I think that way of seeing the elenchus was made into conventional wisdom by Vlastos, but that's not the goal, or not under that description. What gets identified as the conclusion of a typical elenchus is that a particular proposition, earlier maintained by the interlocutor, is *false*, not that a set of propositions is inconsistent. (This is what Vlastos found so mysterious, since he thought that only the inconsistency, if anything, had been demonstrated.) The point is that Socrates usually maintains a clear distinction between the proposition under examination (earlier maintained by the interlocutor, but now being 'tested' to see whether it's true) and the other propositions in play, usually as premises (and which Soc himself *may* not believe, eg Euthyphro's beliefs about the gods being in conflict). Since the whole discussion is framed by the condition 'as far as the interlocutor is concerned', the premises are being thought of not as propositions the interlocutor is committed to (although of course they are), but as *true propositions*, so that the point of their inconsistency with the 'target' proposition is that it shows the latter is *false*. It's true that Soc sometimes says, after an elenchus, 'Maybe there's some premise you want to take back?', and that does give the impression that the real issue is the (in)consistency of the set; but I think that question should really be understood as: 'Perhaps we [sc, really, 'you', the interlocutor] were mistaken as regards the truth about those other matters [sc expressed in the premises], and perhaps on a more adequate conception about how those matters stand, we won't after all be able to show that the target proposition is false, in the way that we did just now on our earlier conception.'

2. When I first heard this objection from Mic Detlefsen, I didn't quite see the problem either, as it seemed to me that part of the technique of formulating an indirect proof consists in isolating the relevant thesis from the start. However, now I'm starting to think that there is a genuine philosophical, even if not mathematical, 'culprit' problem. But I think I'm not articulating it in a sufficiently clear way yet; I'll think about it some more.

2. Sorry, obviously I didn't mean that to be a reply to gowers

1. I'm in no position to discuss subtleties of the textual evidence, not being trained as a classicist myself. But I take it that the idea of driving the answerer into a contradictory position is very much in the spirit of what one sees e.g. in Aristotle's Topics. One example would be: questioner asks: 'Is knowledge the same as perception?' If answerer says 'yes', questioner then goes on to get him to say yes to other statements which in turn will entail that knowledge is not the same as perception. If he had started with a 'no', then he would do the opposite thing. (Using 'he' everywhere here simply because 'back in the day' only men engaged in these disputations.)

However, the point you raise is a deep one, and has to do with the old question of whether dialectic is a suitable method to investigate the truth, or whether it is merely about 'beating the opponent'.

3. Catarina,
"In sum, I submit that reductio proofs are rightly seen as philosophically problematic."

Here are some examples of proofs which use reductio.

Suppose, for a contradiction, there is some arithmetic formula $\phi(x)$, which defines truth in $\mathbb{N}$. So, for any sentence $A$, we have $\phi(\ulcorner A \urcorner)$ is true in $\mathbb{N}$ iff $A$ is true in $\mathbb{N}$. So, $\phi(\ulcorner A \urcorner) \leftrightarrow A$ is true in $\mathbb{N}$. But, by the diagonal lemma, there is some $B$ such that $\neg \phi(\ulcorner B \urcorner) \leftrightarrow B$ is true in $\mathbb{N}$. So, $B \leftrightarrow \neg B$ is true in $\mathbb{N}$. So, $B$ is true in $\mathbb{N}$ and $B$ is not true in $\mathbb{N}$. Contradiction.
So, there is no arithmetic formula $\phi(x)$ defining arithmetic truth. (Tarski's theorem)

The ancient proof that there are no $p,q \in \mathbb{N}$ with $p^2 = 2 q^2$. I.e., suppose there is. ... blah ... contradiction. So, there isn't.

A version of Cantor's theorem. Let $L = (X_0, X_1, \dots, X_i, \dots)$ be a countable sequence of subsets of $\mathbb{N}$. Define a diagonal set $D(L)$ by: $n \in D(L)$ iff $n \notin X_n$, for any $n$. Suppose, for a contradiction, that $D(L) = X_k$, for some $k$. Then, $k \in D(L)$ iff $k \in X_k$. So, $k \in D(L)$ iff $k \notin D(L)$. Contradiction. It follows that $D(L) \neq X_k$, for any $k$. So, $D(L)$ is not on the list $L$. (I.e., every countable list of subsets of $\mathbb{N}$ omits at least one subset.)

Cheers,

Jeff

1. Sure, there are lots and lots of such examples! That's why I say at the end of the post that few of us would be prepared to live without reductio proofs. But more and more I'm coming to think that there is something philosophically fishy with these proofs, in particular because of the contentious last step from the absurdity to the final conclusion.

2. I'm not sure, because in these cases, $\neg A$ is proved by showing (background stuff +) $A$ implies $\bot$. I.e., by showing background stuff implies $A \to \bot$. But for some authors (e.g., intuitionists), this is exactly what $\neg A$ actually means!

Otherwise, it's pretty clear then how we might prove Tarski's theorem, irrationality of 2, etc.?

Jeff

3. Hi Jeff, I'm not sure I'm getting your point, sorry :)

As for intuitionists, the irony is precisely that they vehemently reject one form of reductio, but then have lots of love for the other form! (I think I mention it in the post.) I'd say that they are accepting much too easily the contentious step from maintaining A is a bad idea to maintaining ~A is a good idea.

4. Catarina, my fault - I'm not explaining well. :)
I guess your "maintaining $A$ is a bad idea" means "proving $A \to \bot$"? The thing is, this is the intuitionist's definition of $\neg A$.

(In 3-valued logic, $A$ could be bad and $\neg A$ could be bad too. E.g., in $K_3$, both could have the truth degree $u$.)

But, stepping back a bit, two kinds of things sometimes get called "reductio". In Machover's terminology, as metatheorems, we get

(RAA) If $\Delta, A \vdash \bot$, then $\Delta \vdash \neg A$.

(PIP) If $\Delta, \neg A \vdash \bot$, then $\Delta \vdash A$.

The first, (RAA), is accepted by classicists and intuitionists; but intuitionists reject (PIP) (equivalently, they reject double negation elimination).

I guess your worry is that (RAA), as above, is fishy?

Jeff

4. Too early in the morning ... I mean *unclear*! ...

5. As a distraction, I recommend my post on New Binary Theories of Physics: http://www.hypercubics.blogspot.com/2013/09/i-have-hints-of-new-physics-principles.html

Hopefully that could be interesting for those that are ambitious in the area, but have been reluctant to indulge. The best of philosopher's positions I think.

6. You asked at the end of the post if there were any differences when it came to mathematical proofs. Purely mathematical examples I can't offer, but I can offer a few from geometry.

Both Euclidean geometry and Appolonius' geometry of the conic sections will resort to reductio's in order to make a claim, and they'll do so in the same way as you describe above: show ¬A to be absurd, and then move to say "therefore A."

For example: given a parabola, any diameter drawn (any such lines which bisect a complete other set of parallels) will cut the parabola at exactly one point.

If not, let it be so. And then Appolonius shows that for this to be the case, it would be absurd, for the diamater will not continue bisecting each of these other parallels (the ordinates).

Or when Euclid does similar things when establishing areas of particular sizes, he'll say its a certain size, but then let it be either greater than or lesser than and then show that that will be absurd.

For geometry, the reason you go from ¬A to A is because you've established a certain number of possible categories. If you've shown that a given magnitude is neither greater than nor less than a particular magnitude AND you assume it must be of SOME size, proving ¬A is absurd exactly entails A.

In the end, its the assumption that your interlocutor shares your assumptions about the available alternatives. If you show all alternatives - or rather a case of each will apply to any instance of it - then you've got a demonstrations sans philosophical fishiness.

1. Thanks, that's very useful. And I agree with your final conclusion too, namely that if you share the assumption about the exhaustiveness of the available alternatives, then having shown that none of the others apply (it doesn't have to be only 2, it could also be a proof by cases with more than 2 alternatives), then there is no fishiness left. But now of course the tricky bit will be to ensure this agreement on alternatives.

2. Kevin,

For geometry, the reason you go from ¬A to A is because you've established a certain number of possible categories. If you've shown that a given magnitude is neither greater than nor less than a particular magnitude AND you assume it must be of SOME size, proving ¬A is absurd exactly entails A.

This isn't reductio. It's indirect proof.
Reductio is from $A$ to $\neg A$.
Indirect proof is from $\neg A$ to $A$.

Cheers,

Jeff

3. A reductio ad absurdum just requires you to show that an absurdity whose truth is denied results from the argument. This makes no distinction as to whether a positive or negative claim is being made.

Or rather, this is what we say when doing geometry when using Euclid's and Appolonius's language in the Elements or the Conics respectively. Perhaps a distinction has been made in other mathematical circles that what Euclid considered "reduced to the absurd" is not in fact a reductio ad absurdum. Perhaps the wanting distinction is between reductios and arguments ad absurdum?

I could make an argument that A is absurd - and therefore ¬A - like this: "I say that triangles having angles equal to four right angles is absurd. For if so, the angles about the base are right angles, and on that account the lines subtending those should not meet at a point. Therefore, if this polygon has its interior angles equal to four right angles, it is not a triangle for triangles the legs of a triangle meet at the point. From A is absurd to ¬A is true."

From what I can understand, - and at least insofar as geometry is concerned - anything which can be posited as ¬A to A can be reformulated as A to ¬A without any extra information being required. You just do the proposition backwards.

4. I'm with Kevin here: as I use it, both a proof from A to absurdity, to conclude ~A; and a proof from~A to absurdity, to conclude A, are reductio proofs. (I say this much in one of the blog posts, I suppose.) It's a terminological matter on which possibly not that much hinges, but I think it makes sense to call both these things 'reductio proofs'. Also, the fact that intuitionists accept one and not the other should not necessarily be taken as a sign that they are really different: to me, it is a sign that the intuitionist position on this is a bit incoherent. If they have trouble with one, they should have trouble with the other too!

5. Kevin,

"From what I can understand, - and at least insofar as geometry is concerned - anything which can be posited as ¬A to A can be reformulated as A to ¬A without any extra information being required. You just do the proposition backwards."

Do you mean to say that the following principles are equivalent

(RAA) If $\Delta, A \vdash \bot$ then $\Delta \vdash \neg A$.

(PIP) If $\Delta, \neg A \vdash \bot$ then $\Delta \vdash A$.

But they're distinct. For example, intuitionistic logic has (RAA), but rejects (PIP). According to "proof-theoretic inferentialism", (RAA) is just what $\neg$ means. It corresponds to $\neg$-Intro in a natural deduction system.

Catarina - yes, the terminology ("indirect proof", "reductio", "proof by contradiction", etc.) varies a bit, indeed. Evidence that Humpty-Dumptyism is true. :)

But (RAA) and (PIP) are quite different. For intuitionists, (RAA) expresses what $\neg$ means (i.e., $\neg$-Intro). But intuitionists reject (PIP), because it's equivalent to (DNE), i.e., from $\neg \neg A$ infer $A$. But (RAA) does't give us (DNE).

So, in this case, is it (RAA) that you think is problematic?

Cheers,

Jeff

6. (bleedin' latex! ..)

Hi Catarina,

On the "culprit" issue you raise, logic doesn't answer this, because consistency/inconsistency are global properties. If the set $\{A, B, C\}$ is inconsistent, (RAA) only tells us that $\{A, B\} \vdash \neg C$, and $\{A, C\} \vdash \neg B$ and $\{C, A\} \vdash \neg B$). Or, pretty much equivalently, if $\{A, B, C\}$ is inconsistent, logic tells us that

$\vdash \neg A \vee \neg B \vee \neg C$

But the question of which of $A,B,C$ is the "culprit" isn't settled by (RAA).

This is because consistency (unlike truth) is a global property -- a property of a set, and not a single sentence. If a theory $T$ is inconsistent, then the inconsistency is not "local". E.g., when $A$ and $\neg A$ are both consistent, then the inconsistency of $A$ and $\neg A$ is not automatically blameable on either $A$ and $\neg A$. Rather, it's a global property of the set $\{A, \neg A\}$.

(Another way to put this is that truth is compositional, but consistency is not compositional.)

On the other hand, the notion of a culprit does apply for the case of truth. If a set $\Delta$ of sentences is false, then at least one sentence $A \in \Delta$ must be false. This leads to the so-called Duhem-Quine problem/thesis in epistemology of science.

Let a theory $T = \{H,A\}$, where $H$ is a hypothesis and $A$ is an auxiliary statement. Suppose $T \vdash O$, where $O$ is an observation. Suppose $O$ is observed to be false.

From this alone, we cannot identify whether $H$ is false or $A$ is false. So, this is connected to the whole issue of theory choice in science. Often we can be reasonably sure that the auxiliaries are right, and then this allows us to conclude that the hypothesis is false. In other cases, we have good background reasons for thinking the hypothesis is right, and then, that a failed prediction is caused by a false auxiliary.

Cheers,

Jeff

7. Many peoples want to earn money on internet without any investment but there is many online jobs which have many investments. Now you can earn without any investment with Just clicking and Earn daily upto 10 Dollars.
Join this Best opportunity to make money online without any investment or Charges.
HotProClicks.com