Dear Paolo! Diez, Sept. 19, 2007

Considering our pleasant meeting half a year ago in München and the privatissimum you gave me there, and after re-reading the relevant sections in (Bussotti, 2006), I am still not absolutely sure on what you exactly mean with indefinite descent and reduction-descent. The weakness of (Bussotti, 2006) in this point of differentiation is the following. You give only an extensional account of the two notions, but this account differs from page to page. Moreover, you state that you have a clear intuition of the difference in intensional terms, but you do not define the two notions intensionally. I cannot work with such notions. So I will try to find an intensional definition here.

To make sure that we mean exactly the same with the two notions, I will describe my view on induction here in very detail. I see no other way to become certain that the two names denote the same notions for both of us.

I hope that you agree with the following or even consider it all to be trivial. Then we could go on with our joint paper.

1 Logic

For me there is only one single general form of mathematical induction. I recognize its applications at any times in the known history of mathematics, from Hippasus over Euclid to Fermat.

Behind several lingual forms of presentation, there is a single logical basis to this, which is the Theorem of Nötherian Induction (N), based on the notion of well-foundedness Wellf(<). A relation < is well-founded if any non-empty set has a minimal element, i.e. an element m for which there is no other element w with w<m. Note that a total (i.e., linear) irreflexive ordering < (on A) is well-founded iff it is a well-ordering (on A).

(Wellf(<)) ∀Q. ( ∃x. Q(x) ⇒ ∃m. ( Q(m) ∧ ¬∃w<m. Q(w) ) )
(N)  ∀P. ( ∀x. P (x) ⇐ ∃<. \binom{∀v. ( P (v) ⇐ ∀u<v. P (u) )}{∧ Wellf(<)} )
(S)  ∀P. ( ∀x. P (x) ⇐ P (0) ∧ ∀y. ( P (s(y)) ⇐ P (y) ) )
(nat1)  ∀x. ( x = 0 ∨ ∃y. x = s(y) )
(nat2)  ∀x. s(x) ≠ 0
(nat3)  ∀x, y. ( s(x) = s(y) ⇒ x = y )

It is important to note that (N) is a theorem and not an axiom. This means that there is no reason at all to explain the justification for applying (N). This is different for the case of an axiom, such as the Axiom of Structural Induction (S). There is no need to discuss potential use of the actual infinite in this context. Assuming two-valued (i.e., classical) logic, there is also no need to discuss apagogic vs. positive reasoning, or whether a reductio ad absurdum may be useful in a proof.

I suggest that we restrict our discussion to two-valued logic because the topic is already sufficiently complicated without other logics, such as intuitionistic logic; cf. Heyting (1930). Moreover, for the relevant time until 1900, all logics in mathematics are two-valued.

For two-valued logic, the theorem (N) is indeed a trivial one, simply because Wellf(<) is equivalent to its contrapositive, which is equivalent to Wellf(<)′.

(Wellf(<)′) ∀P. ( ∀x. P (x) ⇐ ∀m. ( P (m) ⇐ ∀w<m. P (w) ) )

The natural numbers are specified up to isomorphism by the axioms (nat1) and Wellf(s), for the successor function s given by s(x) := x+1.

(Wellf(s)) ∀Q. ( ∃x. Q(x) ⇒ ∃m. ( Q(m) ∧ ¬∃w. (s(w) = m ∧ Q(w)) ) )
(Wellf(s)′) ∀P. ( ∀x. P (x) ⇐ ∀m. ( P (m) ⇐ ∀w. (s(w) = m ⇒ P (w)) ) )

Using (nat1), (nat2), and (nat3) this can be simplified to the following logically equivalent formulas, which are variants of the Axiom of Structural Induction (S).

(Wellf(s))′ ∀Q. ( ∃x. Q(x) ⇒ ( Q(0) ∨ ∃y. ( Q(s(y)) ∧ ¬Q(y) ) ) )
(Wellf(s)′)′ ∀P. ( ∀x. P (x) ⇐ ( P (0) ∧ ∀y. ( P (s(y)) ⇐ P (y) ) ) )

Note that Wellf(<) and (nat1) are similar to the axioms of Mario Pieri (1860–1913) (cf. Pieri (1907)), with the exception that Pieri avoids a name for the 0.^{1}

According to Lemma 2.1 of (Wirth, 2004), Wellf(s) implies Wellf( ≺) for the ordering of the natural numbers ≺, i.e., the transitive closure of s. Thus, the natural numbers are born with the following instance of Nötherian induction on ≺.

(N′) ∀P. ( ∀x. P (x) ⇐ ( ∀v. ( P (v) ⇐ ∀u ≺ v. P (u) ) ) )

Regarding logic and the justification and soundness of proofs, everything should be clear now.

2 Methods

So let us come to proof methods. The most simple lingual representation is Fermat’s descente infinie: For an assumed arbitrary counterexample, show the existence of another counterexample which is smaller in ≺!

This is all what a working mathematician has to do. What he thinks when he does this is irrelevant from a mathematical point of view. On the one hand, he might think about an actual infinity of smaller counterexamples (indefinite descent), and see the proof as a reductio ad absurdum. On the other hand, he might think about some small values for which the theorem is true and into which the reductive process starting from an assumed counterexample would have to crash, and see the proof as a form of apagogic reasoning. In any case, the reasoning is merely hypothetical. The infinite is not involved.

Compared to all other forms of induction, descente infinie is more useful or at least just as useful under practical methodological aspects.

1I was not able to understand the sentence “In order to infer the principle of complete induction from Pieri’s axioms, it is necessary not only that a minimum exists, but also that such a minimum is unique.”

[Bussotti (2006), p.466f.] I was not able to read (Di Leonardo and Marino, 2001), simply because I am too stupid to read any languages besides German, English, Latin, French, and Dutch.

Moreover, descente infinie typically offers some advantages for representation of proofs in natural language.

Finally, descente infinie may be also superior under the aspect of non-two-valued logics, but I am not interested in this topic here.

3 Foundations of Mathematics

From a foundational point of view, one should note that the infinitely descending sequences may not exist, even if we take an ordering that is not well-founded. I will discuss this here for the case of the natural numbers because it might have to do with the philosophical differences between indefinite descent and reduction-descent.

Well, if anything needs discussion, then it is the second-order axiom Wellf(s), which is equivalent to the second-order Axiom of Structural Induction (S).

We could say that every natural number has the form s^{n}(0) for a natural number n. Then it is clear that we have to get to 0 after n steps of taking the predecessor. This explanation, however, is of little epistemological value because it just applies the natural number n from the meta level for the explanation the natural numbers of the object level.

If we suppose a non-well-founded successor relation s, surprisingly this does not mean that we also have an infinitely descending s-chain, simply because we cannot name this chain in any (formal) language. If we have the Axiom of Choice to our disposal, then the infinitely descending s-chain must exist. Otherwise not.

So if you insist on the descending chains (for which there is no reason in mathematics, but maybe in philosophy or history), then I can see the following difference w.r.t. the foundations of mathematics between indefinite descent and reduction-descent. The origin of this view of mine is based more on the München privatissimum than on (Bussotti, 2006).

For the existence of the infinitely descending chain required for indefinite descent you need a weak form of the Axiom of Choice, namely the Principle of Dependent Choice, cf. § 2.1.2 of (Wirth, 2004).

For the existence of the arbitrarily long finite chain required for reduction-descent you do not need (any weak forms of) the Axiom of Choice, provided that you can explicitly describe the smaller counterexample in terms of the given one.

But then your classification lacks an important intermediate notion. Suppose that you can show that the smaller counterexample cannot be named explicitly, but that it is possible to show that there is a finite set of smaller counterexamples for any given one. This is typically the case because a proof, say the only one explicitly given by Fermat as discussed in (Wirth, 2006), exhibits a finite set of smaller counterexamples in a finite number of cases. Then you need only König’s Lemma to construct the infinitely descending <-chain. König’s Lemma is a strictly weaker form of the Axiom of Choice than the Principle of Dependent Choice, i.e. if there are models of set theory where König’s Lemma holds, then there are models of set theory where König’s Lemma holds but the Principle of Dependent Choice does not hold.

4 My München View

Let us assume that you are right that we have to differentiate between indefinite descent and reduction-descent, say for historiographical purposes.

The reduction-descent is a proper sub-method of the method of indefinite descent. This means that, in any case, if the applicability conditions of the method of reduction-descent are satisfied, then

1. the applicability conditions of the method of indefinite descent are satisfied, and

2. the sequence of proof steps of a proof by reduction-descent satisfies the requirements of a proof by indefinite descent.

Indeed:

ad 1. The method of reduction-descent is applicable to all irreflexive orderings < for which the set { a | a<b } has a finite cardinality for any b. By finitistic inspection of this set we immediately can conclude that such an ordering is a well-founded relation. Thus, the method of indefinite descent is applicable.

ad 2. If we name one unique smaller counterexample, then there exists a smaller counterexample.

Abstracting from the concrete situation of the natural numbers, talking in terms of an irreflexive ordering <, we thus get:

applicability condition

agenda

Reduction-descent { a | a<b } is finite for any b.

Give an algorithm to compute from an arbitrary counterexample another counterexample that is smaller in < w.r.t. a recursive weight function.

Indefinite descent < is well-founded. Or does this have the same restriction as reductiondescent here?

For an arbitrary counterexample, show the existence of another counterexample that is smaller in < w.r.t. a weight function. Do we need an algorithm (i.e., computability) here? Do we need recursiveness of the weight function?

Descente infinie < is well-founded For an arbitrary counterexample, show the existence of another counterexample that is smaller in < w.r.t. a weight function. Recursiveness and constructiveness are nowhere required in this process. The cardinality of the smaller counterexamples used in the argumentation is not required to be finite.

According to his letter for Huygens (cf. Fermat (1891ff.), Vol.1, p.431f.) I think that the name descente infinie is justified for the above method. The only difference of the method that I call descente infinie to Fermat’s description is that he speaks of a sequence descending to infinity instead of a non-well-founded set. But this difference, manifesting itself in the Principle of Dependent Choice, was clearly not perceivable before 1900.

5 The Question

Do you agree with all of my points?

Are there still some minor differences in our views? Which ones?

Please also do answer my open question in the above table!

Sincerely, CP

References

Berka, K., Kreiser, L. (Eds.), 1973. Logik-Texte – Kommentierte Auswahl zur Geschichte der modernen Logik. Akademie-Verlag, Berlin, 2^{nd} rev. ed. (1^{st} ed. 1971; 4^{th} rev. rev. ed. 1986).

Bussotti, P., 2006. From Fermat to Gauß: indefinite descent and methods of reduction in number theory. No. 55 in Algorismus. Dr. Erwin Rauner Verlag, Augsburg.

Di Leonardo, M. V., Marino, T., 2001. Il principio del minimo interio è equivalente al principio di induzione completa? Quaderni della riceria in didattica 10.

URL http://math.unipa.it/~grim/pieri3.pdf

Fermat, P., 1891ff.. Œuvres de Fermat. Gauthier-Villars, Paris, Ed. by Paul Tannery, Charles Henry.

URL http://fr.wikisource.org/wiki/%C5%92uvres_de_Fermat

Heyting, A., 1930. Die formalen Regeln der intuitionistischen Logik. Sitzungsberichte der Preußischen Akademie der Wissenschaften, Berlin, Physikalisch-mathematische Klasse II 1930, 42–56, short version also in: Berka and Kreiser (1973), pp. 173–178.

Pieri, M., 1907. Sopra gli assiomi aritmetici. Il Bollettino dell’Accademia Gioenia di Scienze Naturali, Catania ?, 26–30.

Wirth, C.-P., 2004. Descente Infinie + Deduction. Logic J. of the IGPL 12, 1–96.

URL http://www.ags.uni-sb.de/~cp/p/d

Wirth, C.-P., 2006. A Self-Contained and Easily Accessible Discussion of the Method of Descente Infinie and Fermat’s Only Explicitly Known Proof by Descente Infinie. SEKI-Working-Paper SWP–2006–02 (ISSN 1860–5931). SEKI Publications, Saarland Univ.

URL http://www.ags.uni-sb.de/~cp/p/fermatsproof