Google
 

Reduction to Absurdity in Differential Equations

  1. How to straighten an argument using reduction to absurdity.
    1. Searching for a direct and exact relationship. [Pet, p.48, l.10-l.15] →[Sne, p.107, (10)].
    2. Replacing (not B Þ not A) by (A if and only if B). [Po3, p.17, l.17-l.24] →[Ja1, p.239, l.2-l.5].
    3. By using the general property of a Hausdorff space [Dug, p.138, 1.2(4)] rather than the special property of a covering space [Mas, p.152, l.−12-l.−6], we may easily prove that {yÎY: f0(y) = f1(y)} is closed. The method reduces the complexity of the setting and avoids a logical detour.
    4. Choosing the right feature for contradiction [War, p.50, Exercise 6]. In [War, p.50, l.−18-l.−15], Warner chooses "being nowhere dense" as the feature of a slice to obtain a contradiction. In [War, p.50, l.−15-l.−2], he chooses the feature of measure 0 to obtain a contradiction. The former choice uses the Baire category theorem whose proof also requires reduction to absurdity.
    5. Converting to a simpler structure [Mas, p.170, Theorem 9.1] so that the target for contradiction (the order of a fundamental group [Mas, p.172, l.6]) emerges.
    6. We may reduce the number of reductions to absurdity in cyclic proofs by negating the statements.
          In [Dug, p.229, Theorem 3.2], if we prove the theorem according to the order (1)Þ(2)Þ(3)Þ(1), we have to use the method of reduction to absurdity twice. If we negate all the three statements and reverse the above order to (not (1))Þ(not (3))Þ(not (2))Þ(not (1)), we will use reduction to absurdity only once.

  2. Reduction to absurdity focuses on a single aspect for contradiction, so it is less informative and constructive.
        [Ru1, p.34, Theorem 2.40] uses math induction and reduction to absurdity. In [Ru1, p.34, l.−5], In+1 is indefinite and selected from In. Therefore, {In} is actually a sequence of variables and each variable depends on the previous one. The reduction to absurdity used in [Buc, p.65, Theorem 24] is trivial and Buck's method is more constructive in practice.

  3. Using reduction to absurdity to prove AÞB, we first assume B is false. This assumption will contradict some fact S. We would like to make the target S for contradiction as basic as possible. If S is an advanced result whose proof goes through many logical steps, it will be difficult to determine which step is the main factor that causes the contradiction.
    Example. Compare the proof of [Ru1, p.208, Theorem 9.34] with that in [Cou2, pp.36-37, §1.4.d].
    Remark. A stronger target requires more conditions to characterize its features. In contrast, a weaker target requires fewer conditions to characterize its features. If we are able to go to the extreme and choose a target with no conditions, then we will have a proof without using reduction to absurdity.

  4. The reduction to absurdity used in [Akh, p.68, Theorem 2] is nontrivial and [Akh, p.70, l.-10, Statement A] is a special case of [Akh, p.68, Theorem 2] (n=1). We may prove [Akh, p.70, l.-10, Statement A] in a more intuitive and straightforward [Wan3, pp.107-108] manner by using [Akh, p.70, l.-1, Statement B*]. Indeed, the proof of [Akh, p.70, l.-1, Statement B*] does not use the method of reduction to absurdity at all and the reduction of absurdity used in [Akh, p.71, l.-8-l.-1] can be considered trivial.

  5. [Dug, p.349, Corollary 6.2] uses a cyclic argument to prove that (1), (2), and (3) are equivalent. The proof that (2)Þ(3) essentially does not use reduction to absurdity. However, both the proof (3)Þ(1) and the proof that (1)Þ(2) use tricky reduction to absurdity. If statements (1), (2), and (3) are equivalent and the proof that (2)Þ(3) is long and straightforward (without using reduction to absurdity), then perhaps there is no short and straightforward proof for the converse (3)Þ(2).

  6. 2-level reduction to absurdity: a reduction to absurdity embedded in another reduction to absurdity
    (The Jordan separation theorem: Every homeomorphic image of Sn in En+1 separates En+1) By examining the number of times reduction to absurdity is used, we can see that the proof of [Mun00, p.379, Theorem 61.3] is more effective than the proof of [Dug, p.358, Theorem 2.4]. The proof of [Mun00, p.379, Theorem 61.3] uses reduction to absurdity once [Mun00, p.379, l.-14-l.-3]. In contrast, the proof of [Dug, p.358, Theorem 2.4] uses 2-level reduction to absurdity. This is because if we negate the conclusion of Borsuk's separation theorem [Dug, p.357, Theorem 2.1(1)], we will reach a conclusion contradictory to Brouwer's theorem [Dug, p.341, Corollary 2.2(1)]. The proof of Brouwer's theorem [Dug, p.340, Theorem 2.1] uses [Dug, p.339, Theorem 1.1] to reach a contradiction. Thus, the proof of [Dug, p.340, Theorem 2.1] also uses nontrivial reduction to absurdity.

  7. 3-level reduction to absurdity: a reduction to absurdity embedded in the second reduction to absurdity which is embedded in the third reduction to absurdity
    (Invariance of domain: if U is open in Rn and f: U ® Rn is continuous and injective, then f(U) is open in Rn)
        The proof of [Mun00, p.383, Theorem 62.3] uses reduction to absurdity [Mun00, p.384, l.7-l.11]. The reduction to absurdity uses [Mun00, p.383, Step 1] in [Mun00, p.384, l.8]. However, the proof of [Mun00, p.383, Step 1] uses Borsuk's lemma [Mun00, p.382, Lemma 62.2]. The proof of [Mun00, p.382, Lemma 62.2] also uses reduction to absurdity [Mun00, p.382, l.-2-p.383, l.14]. The last statement of the proof comes from [Mun00, p.348, Theorem 55.2] the proof of which also uses non-trivial [Mun00, p.345, Theorem 54.5] reduction to absurdity. Thus, the proof of [Mun00, p.383, Theorem 62.3] uses 3-level reduction to absurdity.
        In contrast, the proof of [Dug, p.359, Corollary 3.2] uses [Dug, p.358, Theorem 3.1]. The proof of [Dug, p.358, Theorem 3.1] uses [Dug, p.357, Corollary 2.3] in [Dug, p.359, l.3]. [Dug, p.357, Corollary 2.3] is a corollary of Borsuk's separation theorem [Dug, p.357, Theorem 2.1]. From the discussion in 6, we see that the proof of [Dug, p.357, Theorem 2.1] uses 2-level reduction to absurdity.

  8. n-level reduction to absurdity: Assume that (n-1)-level reduction to absurdity is defined. The proof of Theorem A begins with the assumption that Theorem A is false, and ends with a contradiction. Suppose during the proof we use Theorem B whose proof requires the use of (n-1)-level reduction to absurdity. Then we say that the proof of Theorem A uses n-level reduction to absurdity.
        Let Sn be the statement given in [Zyg, vol.1, p.62, (9.4)]. According to the scheme of its proof, we use reduction to absurdity to prove the validity of Sn+1. We first assume that Sn+1 is false. The assumption will lead to a statement contradictory to Sn [Zyg, vol.1, p.62, l.11]. Therefore, Sn+1 is true. Using the same method, we can prove the validity of Sn. In total, we use n embedded levels of reduction to absurdity to prove the validity of Sn.

  9. (The Jordan curve theorem: E2-J has no more than two components)
    1. (Real length) Both the proof given in [Dug, p.362, l.-2-p.363, l.15] and the proof given in [Mun00, p.391, l.7-l.17] use reduction to absurdity and have about the same length. Does this mean that they are equally effective? The answer is no because the length considered above is a part of the real length. The real length of a proof of the Jordan curve theorem is the proof's length plus the sum of the proof lengths of all the theorems used to prove the Jordan curve theorem. Thus, [Dug, p.361, l.6-p.363, l.15] gives the former proof's real length, while [Mun00, p.385, l.12-p.391, l.17] gives the latter proof's real length. By comparing the two proofs' real lengths, we conclude that the former proof is more effective than the latter one. {1}
    2. (Relationships) If we assume that the Jordan curve separates E2 into more than two components, the assumption will lead to a conclusion which contradicts [Dug, p.362, Theorem 5.2] if we follow the argument of [Dug, p.362, Theorem 5.4], and will lead to another conclusion which contradicts [Mun00, p.385, Theorem 63.1(c)] if we follow the argument of [Mun00, p.390, Theorem 63.4]. [Dug, p.362, Theorem 5.2] involves the simple concept "x, y lie in distinct component of CJ" [Dug, p.361, l.-1], while [Mun00, p.385, Theorem 63.1(c)] involves the complicated concept of the subgroups of a fundamental group. The former concept has a close relationship with the Jordan curve J, while the latter concept has a indirect relationship with the Jordan curve. Thus, in terms of relationships, Munkres' proof also takes a greater length to reach the contradiction than Dugundji's.
    3. (Embedding structures ® À0-level reduction to absurdity) The proof of [Dug, p.362, Theorem 5.4] uses reduction to absurdity once [Dug, p.362, l.-2-p.363, l.14]. Although the proof of "the Ü part" of [Dug, p.359, Proposition 4.1.(1)] uses reduction to absurdity, [Dug, p.362, l.7] only uses "the Þ part" of [Dug, p.359, Proposition 4.1.(1)].
          In contrast, reduction to absurdity used in the proof of [Mun00, p.390, Theorem 63.4] starts from [Mun00, p.391, l.7] and ends in [Mun00, p.391, l.17]. In [Mun00, p.391, l.10] Munkres uses [Mun00, p.389, Theorem 63.2] twice (one for C1 and one for C2). The first proof of [Mun00, p.389, Theorem 63.2] uses Borsuk's lemma [Mun00, p.382, Lemma 62.2]. The proof of [Mun00, p.382, Lemma 62.2] involves 2-level reduction to absurdity as discussed in 7. The second proof of [Mun00, p.389, Theorem 63.2] is divided into two parts: [Mun00, p.389, l.15-p.390, l.6] and [Mun00, p.390, l.7-l.26]. Both parts use reduction to absurdity. The induction step in part 2 uses part 1, so the reduction to absurdity for case n is embedded in the reduction to absurdity for case n+1. Thus, part 2 of the second proof of [Mun00, p.389, Theorem 63.2] uses À0-level reduction to absurdity. À0-level reduction to absurdity is the most twisted argument against intuition in logic, we should avoid using this type of argument whenever possible. Because the proof of [Dug, p.362, Theorem 5.4] uses reduction to absurdity fewer times than does the proof of [Mun00, p.390, Theorem 63.4], the former proof is more straightforward than the latter one.
    Remark. The proof of the second part of [Mun00, p.390, Theorem 63.4] uses [Mun00, p.389, Theorem 63.2].  The first proof of [Mun00, p.389, Theorem 63.2] uses [Mun00, p.382, Lemma 62.2]. The proof of [Mun00, p.382, Lemma 62.2] involves 2-level reduction to absurdity as discussed in 7. In contrast, the second part [Dug, p.358, l.3-l.5] of [Dug, p.358, Theorem 2.4] uses [Dug, p.357, Corollary 2.3], a corollary of [Dug, p.357, Theorem 2.1]. From the discussion in 6, we see that the proof of [Dug, p.357, Theorem 2.1] also uses 2-level reduction to absurdity.

  10. [Guo, p.479, l.-16-l.-2] proves special cases using the method of reduction to absurdity. The approach that uses the following fact is simpler and more straightforward and leads to the general case: The Laurent series of an even analytic function contain only even powers; the Laurent series of an odd analytic function contain only odd powers.

  11. The statement we target for contradiction must be clearly stated. In order to shorten the length of the argument used for reduction to absurdity, the statement targeted for contradiction should be as weak as possible.
        Between [Gon1, p.370, l.-8] and [Gon1, p.370, l.-7] González should have inserted the following three sentences: "Assume the pair {2w1, 2w2} is not reduced. Note that (|t|³1 Þ (w1 is a nonzero period with smallest absolute value)). Therefore, (a) there exists a reduced pair of fundamental periods {2w1, 2w} such that
    |w| < |w2|. Then (b) Im (w/w1) > 0 and |w| < |w2| (by (a) and [Gon1, p.369, Definition 5.4])." The assumption given in [Gon1, p.370, l.-7] alone will not lead to the conclusion that {2w1, 2w2} is reduced [Gon1, p.371, l.5] if we do not assume that {2w1, 2w} is reduced. The statement (b) is weaker than the statement (a). González aims to contradict statement (a), so he writes "and the pair {2w1, 2w} is not reduced" four times [Gon1, p.370, l.-6-l.-5; p.371, l.6, l.15 & l.22]. Had he aimed to contradict statement (b), all four phrases "and the pair {2w1, 2w} is not reduced" could have been eliminated. In fact, all he has to do is to use [Gon1, p.369, Definition 5.4] once to prove the statement (b) rather than use [Gon1, p.369, Definition 5.4] four times to contradict the statement (a).

  12. Hardy's convergence theorem
        The proof of [Wat1, pp.156-158, Theorem 8.5] uses reduction to absurdity twice, while the proof of [Zyg, p.78, Theorem 1.26] does not use reduction to absurdity [Zyg, p.79, l.-2-p.80, l.5; p.80, l.13-l.19].
    Remark. In [Wat1, p.158, l.4], Watson uses n/k ³ e to obtain a contradiction. By contrast, in [Zyg, vol. 1, p.80, l.16] Zygmund uses n/k £ M to obtain the convergence. These two approaches seem to proceed in opposite directions. This observation provides us a clue about how to eliminate the use of reduction to absurdity.

  13. Orthogonal polynomials
        Usually, the argument of reduction to absurdity is not oriented directly and effectively toward the goal, but is a side effect of other purposes.
    (1). The proof in [Inc, p.163, l.10-l.16] is simpler than the proof of [Bir, p.305, Theorem 6].
    (2). The proof of [Bir, p.305, Theorem 6] seems simpler than that of [Nat, p.78, Lemma 3.1]. However, if we add the proof of [Nat, p.79, Lemma 3.2] to the former proof, then the latter proof becomes simpler than the former one. Furthermore, [Nat, p.78, Lemma 3.1] reveals the intertwining relation between the zeros of Hn+1 and the zeros of Hn.

  14. We can simplify the argument of reduction to absurdity by choosing a closely related target for contradiction.
        The proof of [Ru1, p.36, Theorem 2.43] uses the concept of compactness. The proof of [Roy, p.56, Corollary 4] uses the concept of infimum. In contrast, the proof of [Per, p.20, Theorem 2.1.4] uses a more directly related concept: countability. Consequently, the third proof is the simplest. [1]

  15. The reason we are obliged to use the method of reduction to absurdity is that our resources are limited. Once our resources are amply supplied, we may avoid using the method of reduction to absurdity in our proof. Thus, the method of reduction to absurdity can be considered a detour approach when a direct access is not available. If we use a more elementary method in proving a theorem, the proof becomes more straightforward and effective.
    Example. (The Jordan curve theorem: the complement of a Jordan curve has at least two components)
        The proof of [Ahl, p.118, Exercise 3] does not use the method of reduction to absurdity. In contrast, the proof given in [Mun00, p.391, l.1-l.6] uses the Jordan separation theorem [Mun00, p.379, Theorem 61.3] whose proof uses a nontrivial [Mun00, p.379, l.-4] reduction to absurdity. If the Jordan curve is a closed polygon, we can even use elementary geometry to prove this theorem [Sak, chap. IV, §11]. Ahlfors' proof is the best because it shows that the concept of winding number is the key to proving the theorem.


  16. Adopting a powerful tool that leads to a quick contradiction
        Suppose we try to use the method of reduction to absurdity to prove AÞB. First, we assume B is false. Then we have statements A1, A2, …, Am in succession. Suppose we obtain a contradiction once we have Am. Then we should go back to check if any Ai can be derived without assuming that B is false. If the answer is yes, we remove it from our list. Finally, we acquire a sublist B1, B2, …, Bn  which are true only if B is false. We call n the reduced length of the argument using reduction to absurdity. A shorter length gives a more straightforward argument. For example, the argument using reduction to absurdity given in the proof of [Ahl, p.129, Theorem 9] could have included all the statements given in [Ahl, p.128, l.21-p.129, l.10]. Since all these statements are true without assuming that the conclusion of [Ahl, p.129, Theorem 9] is false, we should not put them into the argument for reduction to absurdity even though they are specifically designed for proving [Ahl, p.129, Theorem 9]. Obviously, the reduced length of the proof of [Ahl, p.129, Theorem 9] is shorter than that of the proof of [Sak, p.144, Theorem 6.1]. This is because Ahlfors adopts a powerful tool [Ahl, p.128, l.-11-l.-9] to reach a contradiction. After he uses the tool for the first time, he concludes that a is not an essential singularity of f (z) - A. After he uses the tool for the second time, he almost reaches a contradiction.

  17. Another example: Proof of [Mun00, p.350, Theorem 55.5]
        In order to facilitate the calculation of the reduced length, we should put all the statements contained in [Mun00, p.350, l.-12-l.-7] outside the argument of reduction to absurdity.

  18. We should state our argument using reduction to absurdity as positively as possible. That is, we should try to make our argument as straightforward as possible and remove our argument outside the process of reduction to absurdity the best we can.
    Example
        In the proof of [Nar, p.27, Theorem 6], we use reduction to absurdity to show r0 = r [Nar, p.27, l.20]. The proof seems long [Nar, p.27, l.-15-l.-1]. However, we may summarize most of the argument in a positive manner as the following lemma:
    Lemma. Let D = D(a, r) and fÎH(D). If f has a primitive on D(a, q), where q < r, then there exists an e > 0 such that f has a primitive on D(a, q+e).
    We may prove this lemma without using reduction to absurdity and without assuming r0 < r. Then we assume r0 < r. Using the lemma, we prove that f has a primitive on D(a, q+e). This contradicts the definition of r0 [Nar, p.27, l.14]. Thus, the reduced length of the argument using reduction to absurdity is 2.


  19. Both the proof of Schmidt's theorem [Wat1, p.223, l.15] and that of  [Boc, p.47, Theorem 2]
  20. consider the series given in [Wat1, p.223, l.-3]. However, the former proof reduces the scope of reduction to absurdity to almost nothing [Wat1, p.234, l.1-l.2].

  21. Prove that G(z)-1 has an essential singularity at z = ¥.
    Proof using reduction to absurdity.
    If G(z)-1 is analytic or has a pole of order m at z = ¥, then
    F(t) = tm G(t-1)-1 is analytic at t = 0.
    F(1/n) = F(0) = 0 Þ tm G(t-1)-1 º 0. We have a contradiction.
    Proof without using reduction to absurdity.
    Let y > 0.
    G(yi) = (2p)1/2 e-yi e(yi - 1/2)(log |y| + ip/2) [1 + O(|y|-1)]
  22.  [Wat1, p.249, l.-8]
    = O(e(log |y|)/2 - py/2) ® 0 as y®+¥.
    G(n) ® ¥ as n®+¥.

  23. For the example given in [Perr, p.276, l.-12-l.-7], the proof given in [Perr, p.276, l.-8-l.-7] uses reduction to absurdity, while the proof given in [Perr, p.274, l.3-p.275, l.7] does not.


  24. (The Sturm comparison theorem)[Bir, pp.267-268, §10.6]
        The reduction to absurdity used in the proof given in [Inc1, §10.31] is contained in [Inc1, p.226, l.12-l.15]. All it does is compare a positive number with 0, so the reduction to absurdity used here is trivial. Now we count the number of times that reduction to absurdity used in the proof of [Bir, p.268, Theorem 3].
    I. Prerequisites
    1. The proof of [Bir, p.26, Theorem 7] uses a nontrivial reduction to absurdity given in [Bir, p.26, l.-12-l.-3]. The reduction to absurdity is nontrivial because [Bir, p.24, Lemma 2] is used in [Bir, p.26, l.-6].
    2. The proof of [Bir, pp.26-27, Theorem 8] uses [Bir, p.26, Theorem 7] twice.
    3. [Bir, p.27, Corollary 1] follows from [Bir, pp.26-27, Theorem 8].
    4. The proof of [Bir, p.27, Corollary 2] uses another nontrivial reduction to absurdity given in [Bir, p.27, l.-11-l.-5]. The reduction to absurdity is nontrivial because [Bir, pp.26-27, Theorem 8] is used in [Bir, p.27, l.-7].
    II.
    1. [Bir, pp.26-27, Theorem 8] is used in [Bir, p.268, l.9].
    2. In order to prove q(x)ºq1(x) given in [Bir, p.268, l.12], we must use [Bir, p.27, Corollary 2].
    3. In order to prove the statement given in [Bir, p.268, l.16-l.17], we must use [Bir, pp.26-27, Theorem 8, Corollary 1 & Corollary 2].
    Remark. The reduction to absurdity used in [Inc1, §10.31] is trivial because the Picone formula reaches deeply into the essence of the problem. In contrast, the proof of [Bir, p.268, Theorem 3] uses reduction to absurdity so many times because the proof remains at a shallow level from beginning to end. [Bir, pp.266-267, §10.5] is nothing but a complication. Thus, Birkhoff and Rota's proof of the Sturm comparison theorem is far less straightforward than Picone's proof. Consequently, it is important to teach students in mathematics that more straightforward proofs are better. Authors of textbooks in mathematics should choose better proofs to put into their books.


  25. Links {1}.