Intuition, Logic, and Induction.

[Alexander Zenkin]

    First of all, I would like to thank Samuel S. Kutler, Michael
Deakin, and Boaz Tsaban for their kind and interesting responses to my
question on who was the formal author of the mathematical induction
method ([HM]: Wed, 03 Mar 1999 03:18:50).
      As is known, from the "naive" point of view, the DEDUCTION is the
AUTHENTIC inference of a LESS COMMON statement (say, a theorem) from a
MORE COMMON statement (say, an axiom system that can be considered as
one conjunction of all axioms of the system). From the same point of
view, the INDUCTION is any inference of a MORE COMMON statement  from a
LESS COMMON statement. There are some different forms of the induction.
   1) The J.S.Mill's induction is an inference of COMMON statement from
a set of PARTICULAR facts. Such the COMMON statement can always be only
a PLAUSIBLE statement  (i.e., a hypothesis). Therefore, all laws of,
say, physics are only plausible hypotheses which, according to the
recognized K.Popper's paradigm, can be, in principle, falsifyed by some
new facts (usually, in the sense "advance", e.g., Newton == > Einstein,
and much more rare in the sense "disproof", e.g., Ptolemei (?sorry) == >
Coppernicus). All modern natural science is based upon that J.S.Mill's
induction paradigm.
      However, there are three type of the AUTHENTIC INDUCTION.
   2) The so-called full listed (perechislitel'naja) induction. Let
M={a1,a2,┘,an} be a FINITE set. By direct testing P(ai) for all
i=1,2,┘,n, we prove (of course, if there are not counter-examples,
not-P) the authentic truth of the common inductive statement (i)P(ai).
It is not the most interesting induction from the point of Mathematics
view.
   3) The complete mathematical induction (CMI) method is formulated so
(see Michael Detlefsen's FOM-message, Date: Mon, 1 Mar 1999 12:03:54):
   [P(1) & (n)[P(n) == > P(n+1)]] == > (n)P(n)     (1)
   As to the CMI-method understanding, Stephen G Simpson (FOM-message,
Date: Thu, 25 Feb 1999 17:01:24) writes:
"Poincare and Detlefsen want to say that mathematical induction is
illogical." I think, it would be more correct to say: Poincare and
Detlefsen want to say that mathematical induction includes some
illogical (intuitive) stages which usually are called insights, and
which are not formalized even in modern meta-mathematics.
   The well-known B.Pascal's interpretation of the CMI-method allows to
understand well and to distinguish fine the intuitive (insightful),
logical, and mathematical stages of the CMI-method.
   Indeed, the stage P(1) is usually an almost arithmetical stage. The
"almost" is here because that an arithmetical calculation is completed
by a cheking of a trivial logic condition (=, >, <, and alike).
   But in reality, that stage P(1) is not so trivial: we never begin to
use the CMI-method because only that P(1) is true. In the beginning, any
mathematician checks out a series of values P(1), P(2), P(3), ┘ . Up to
what a limit? Nobody knows. The intuition of mathematician only can stop
such the testing.  Neither the mathematical logic, nor the
meta-mathematics can proves the theorem of such the kind: there exists
the number, say, n0 such that IF P(n) for all n=1,2,┘,n0, THEN the
CMI-method is applicable. To what value n0 is equal? 3,5,10,20? For such
the case, there is the well-known example: consider integer  expression
n^2 + n + 41 and the predicate P(n) = " n^2 + n + 41 is a prime number".
Here P(n) is true up to n0=39, but P(40) is false. Who now can guarantee
that an alike expression does not exsit where n0 is equal to either
1000, or w, or w^w, or w^w^w and so on? Nobody. So, they can state that
this intuitive stage (to find a stop point, = nahozhdenije tochki
ostanova, = in the testing process P(1), P(2), P(3) ┘) of the CMI-method
is not formalized even in ZFC. Of course, any not-P(n), n>1, is a stop
point, but also it always means the rejection from the CMI-method
application.
   So, if the first stage did not disprove the CMI-method applicability,
a mathematician starts the second stage - the proof of a MATHEMATICAL
THEOREMS of the beforehand defined, fixed (see below), well-known FORM:
(n)[P(n) == > P(n+1)]. Sometimes, there is a prepared mathematical
algorithm for proof of such a theorem (for example, the summing up of
the finite sequence 1+2+3+┘+n), but sometimes, the proof can occupy many
journal's pages and even include intuitive, insightful, i.e., (today!)
not formalized, steps. Here is one example.
    In 1770, English mathematician Waring formulated his famous
hypothesis on the representation of any natural number n>=1 by sums of s
r-th powers of non-negative (m=0) natural numbers by any s>=G(r), where
G(r) is a constant for any fixed r>=2. During about one and a half of
Century, such outstanding mathematicians as Euler, Lagrange, Gauss, and
others were investigating the problem. But as far back as 1909,
D.Hilbert gave the complete solution of the Classical (m=0) Waring's
Problem. As to the Hilbert's proof, Poincare said that "the analytical
Hilbert's proof, based upon a 25-multiple integration, is not only very
bulky in a formal relation┘, but it is quite obscure in the conceptual
sense; ... but if motive powers of the proof will ever be understood
well, then arithmetical results of a great importance will shower down
as from horn of plenty" (it is cited by Alexander Hinchin essay "Three
Pearls of Number Theory". - Moscow:"NAUKA", 1979). As we today well
know, it occured just so: the Hilbert's proof initiated the developement
of the power analytical methods in the modern Number Theory.
    Unfortunately, I do not know whether it is possible today to
formalize the "very bulky and quite obscure" Hilbert's poof in a
framework, say, ZFC, but I can certainly state that my generalization of
the Classical Waring's Problem (m=0) and the Hilbert's Theorem (m=0) to
any case m=1,2,3,┘, {see: A.A.Zenkin, Generalization of Hilbert-Waring's
Theorem. - Vestnik of Moscow University, Ser.1, Math., Mech., 1983, No.
2, 11-19.} could not be ever formalized in a framework of any future
formal systems. Remark, that my generalization of the Hilbert's proof is
a proof realized by means of the common CMI- method (about 7 journal
pages) with the Hilbert's proof as the first P(0)-stage. Why? - Because
in order to proof the MATHEMATICAL THEOREM (n)[P(n) == > P(n+1)] I was
forced to DISCOVER a new type of number-theoretical objects - so-called
invariant sets Z(m,r), m=0,1,2,┘, r=2,3,4,┘, of the Generalized (m>=1)
Waring's Problem which were not known in modern Number Theory. What
these sets are? They are finite sets of finite natural numbers, and the
first such set, Z(1,2)={1,2,4,5,7,10,13} was discovered by American
mathematician G.Pall as far back as 1933. I would like especially to
emphasize here the following very non-trivial fact: the invariant sets
Z(m,r) were discovered not in an unaccessible transfinite ordinals area,
but in the very beginning of the common series of common finite natural
numbers!
    As I suspect, none of modern formal system, even ZFC, can formalized
such the essential here stage of the CMI-method as the scientific
discovery process itself.
    All the more, that the Z(m,r)-sets Discovery was made by means of
the Cognitive (Semantic) Computer Visualization of number-theoretical
abstractions. What is the Cognitive (Semantic) Computer Visualization? -
We know well what is the SEMIOTICS OF SIGNS, symbols, names, words, and
their sets and formal consequences. The Cognitive (SEMANTIC) Computer
Visualization is a quite large step to a SEMIOTICS OF IMAGES that
represent an essense of a given abstract problem domain. Such the
(color-musical) images of scientific abstractions (of any high levels)
directly contact with our intuitive, visual, creative thinking, and,
under certain conditions, can generate a conceptually new scientific
knowledge in our mind. I believe that such the Cognitive (Semantic)
Computer Visualization of scientific abstractions (SEMIOTICS OF IMAGES)
is the most effective way for an experimental investigation,
comprehension, and, further, probably, formalization of high
meta-procedures of our intuitive, creative thinking. Unfortunately (or
maybe fortunately), today all that is not formalized, and the last means
that my CMI-generalization of Hilbert's Theorem contains intuitive,
insightful stages that can not be formalized in a framework of any
formal system of modern meta-mathematics.
   The third main stage of the CMI-proof is a PURE LOGICAL stage: if the
single statment P(0) and the mathematical theorem (n)[P(n) == > P(n+1)]
are proved, then further we have an infinite sequence of applications of
the Aristotle's modus ponens rule:
[P(0)&[P(0) == >P(1)]] == > P(1); [P(1)&[P(1) == >P(2)]] == > P(2);
[P(2)&[P(2) == >P(3)]] == > P(3); and so on.
   So, indeed, the Classical Complete Mathematical Induction Method
includes some different stages: logical stages as well as mathematical
and intuitive (insightful) ones.

   Now, some words as to Detlefsen's examples.
   Stephen G Simpson (Date:Thu, 25 Feb 1999 17:01:24) writes:
"Detlefsen in his posting doesn't give any REAL example, so it's hard to
know what he and Poincare are getting at. I of course disagree with
Poincare and Detlefsen, ┘".
   Unfortunately, I disagree with Stephen G Simpson because Detlefsen
(implying Poincare's ideas) gives a brilliant example for the real
understanding of the epistemological essense of the mathematical
induction and the universal quantifier. I am sure that the Detlefsen's
example will be included in ALL and ANY manuals of meta-mathematics-XXI.
: -)  Because that example allows to understand well the very important,
EPISTEMOLOGICAL difference between that two important, paradigmal
notions, ALL and ANY, of modern meta-mathematics.
    I will try to explain that.
Detlefsen's K1 says: P(1)&[ P(1) == > P(2) == > P(3) == > ┘] == (n)P(n),
i.e., for ANY (EVERY GIVEN) n P(n).
Detlefsen's K2 says: P(1)&[ P(1) & P(2) & P(3) & ┘] == (n)P(n) , i.e.,
for ALL  n P(n).
{of cousre, the K2 obtains his/her P(2), P(3), P(3), and so on, by the
same Aristitle's modus ponens rule}
    It must be emphasized here that in the both cases the statement
(n)P(n) is not an inference (implication, deduction) from the left part:
it is simply a short NOTATION of the (ideal) result which is logically
(algorithmically) produced by the left part. And nothing more.
    So,  the K1 states: I can prove P(n) for ANY GIVEN n.
    The K2 states: I have just tested that P(n) is true for ALL n.
What does it  mean? That means that K1 considers the set of all n as a
POTENTIALLY infinte set, but the K2 considers the same set of all n as
an ACTUAL infinite set.
    Moreover, since the right parts (n)P(n) in the both cases are the
same, it means that the most important, paradigmal notion of the modern
meta-mathematics, - the notion (conception) of the universal quantifier
(n), - does not distinguishes the potential and actual infinitities !

   I think it is a very non-trivial FACT for the modern
meta-mathematics. : -)

    Further, the Induction Problem has now the follwing new aspects.

I. A NEW KIND OF MATHEMATICAL REASONINGs.

     In 1949, German mathematician H.E.Richert proved one unusual
statement on the common finite natural numbers (the complete formulation
is enclosed below). Unfortunately, he (and nobody after him) did not
understand the EPISTEMOLOGICAL sense of his own theorem.
    In 1978-1979, I discovered two new different classes of the alike
statements. The last allowed me to formulate a new inductive method, -
the so-called Super-Induction (SI) method, - for proving common
mathematical statements of the form _An P(n) {here and further, it is
more convenient to denote the "Existence" and "for ALL" quantors by _E
and _A correspondingly} based upon the EA-Theorems of the following
unusual, or, one may say, "impossible" kind.

EA-THEOREM.    IF  there exists at least one natural number, say n*,
such that a predicate Q(n*) holds, THEN for all natural number n > n* a
predicate P(n) is true, or, in a short symbolic form:

_E n* Q(n*) == > _A n>n* P(n).        (1*)

Here, P and Q=f(P) are some number-theoretical properties (predicates) ,
and symbols "_E" and "_A" simply replace here the usual mathematical
words "there exists" and " for all", correspondingly.

   So, EA-Theorem states the following absolutely "impossible" thing:
the COMMON statement _An>n*P(n) is rigorously DEDUCED from a SINGLE
statement _En*Q(n*). In other words, the Theorem is the AUTHENTIC
DEDUCTION of the "from a SINGLE to a COMMON" INDUCTION.

     Such the statement might seem to be a nonsense, but it is proved by
the Classical Mathematics methods, i.e., absolutely rigorosly. In
particular, the logical and mathematical correctness of the
H.E.Richert's EA-Theorem is certifying not only by Richert's proof
itself, but also by the following historical fact.
    Original H.E.Richert's paper was published in 1949, and then it was
described almost word for word in the page 143 of famous W.Sierpinski's
monography "Elementary Theory of Numbers" (Warszaw, 1964).
    From that time, the book became a handbook and a manual for 99% of
mathematicians, and a lot of thausends, or even millions, of
mathematicians had been reading the page 143 with H.E.Richert's Theorem
from 1964 up to now. But none of them pays attention to that unusual
EA-Theorem just in the connection with the EPISTEMOLOGY of the inductive
inference.
    Using his EA-Theorem, H.E.Richert proved a lot of beautiful new
theorems in classical Number Theory on representations of natural
numbers by sums of different prime numbers.

CONCLUSION 1. The EA-Theorems are a totally new kind of INDUCTIVE
statements in Mathematics.

 Some important and unexpected consequences follow from such the
EA-Theorems.

II. GENERALIZATION OF THE J.S.MILL's INDUCTIVE LOGIC.
   As it already was said above, the most fundamental Paradigm of the
Classical Mill's Inductive Logic sounds so:  It is always possible to
formulate (not to deduce, but, rather, to invent ) a common statement
(and even not one) from a set of particular facts. But such the
statement will always be a plausible, hypotetical statement only, and
never an authentic one, i.e., any Induction of the kind "from a
particular statment to a common one" is always a plausible Induction,
and never a realiable one. The Paradigm is the corner-stone of all the
Natural Science.

CONCLUSION 2. The EA-Theorems prove mathematically, i.e., rigorously in
the calssical logic sense, the authentic Induction (1*) "from a SINGLE
fact to a COMMON statement".
REMARK. Of course, EA-Theorems refer (today) to some areas of discrete
mathematics (such as Number Theory, Combinatorics, Graph Theory) only,
and therefore it does not disprove the Mill's Paradigm in general. But
it brings to light some new and unexpected (including philosophical)
aspects of our cognition of the Inductive Logic.

III. GENERALIZATION OF THE MOST FAMOUS DEDUCTIVE RULE OF ARISTOTLE's
CLASSICAL LOGIC.
    The question is about the famous modus ponens rule of Aristotle's
Logic. As is well known, the rule is formulated as follows: IF a
statement A is true and IF the statement A == > B is true, THEN the
statement B is true too. From the Aristotle time, they have in mind that
the statement A == > B is a deductive inference of a less common
statement B from a more common statement A, for example, a deductive
inference of a theorem from axioms.

CONCLUSION 3. The EA-Theorems prove mathematically, i.e., by rigorously
deductive way, that famous Aristotel's modus ponens rule is valid when a
statement A is a single statement, but its consequence B is a common
one. So, the EA-Theorems generalize the modus ponens rule of Aristotle's
Logic.
REMARK. The Classical Logic, and even the modern meta-mathematics logic
do not forbid such the case explicitly. Simply, they were considering
such a case never.

VI. GENERALIZATION OF THE COMPLETE MATHEMATICAL INDUCTION METHOD.

     It is most fantastical that in general case there are no
restrictions to predicates P and Q. Indeed, you can take any P and any
dependence Q=f(P). - The most terrible what can occur is that you simply
will not prove the corresponding EA-Theorem, and nothing more.
     Let P be an arbitrary number-theoretical predicate. We define new
predicate Q=f(P), for example, as follows:

Q(n*) = P(n*) &  [ _A n>n* [P(n) == > P(n+1)]],         (2*)

where n* - is now a variable natural number. Since n in (2*) is a bound
variable, our predicate Q(n*) depends really from n* only.
     So, even by a pure formal way, substituting that Q(n*) in
EA-Theorem (1*), we obtain:

_E n* [P(n*) & [ _A n>n* [P(n) == > P(n+1)]]] == > _A n>n* P(n)
(3*)

    As it is easy to see, the expression (3*) is the famous Complete
Mathematical Induction Method (in its the more correct notation then the
usual notation (1)).

REMARK. In tasks that was solved by H.E.Richert, the threshold number n*
may take different values, for example, 9, 17, 29, and so on.  As is
well known, as to the Complete Mathematical Induction Method, the
corresponding "theshold" number n* is, usually, equal to either 0 or 1.

CONCLUSION 4. The EA-Theorems generalize the Classical Complete
Mathematical Induction Method which kids of all over the world study at
school from the XVII Century. For the very end of XX Century, it is not
trivial event : -).

    Today, I already know three absolutely different classes of such the
EA-Theorems, and the today's maximal threshold number n*=77 900 162. I
think the classical mathematical induction with an alike value for n* is
not known.

REMARK. The SI-method works fine for solving such problems of discrete
mathematics where the usual mathematical induction method simply does
not work.

   As to Stephen G Simpson's rejection of the mathematical induction
irrationality (informalizability of some its stages).
   Today, the choice of the predicate Q, and the formulation of the
mathematical connection Q=f(P) in the generalized mathematical induction
method (I mean the SI-method) do not have a theory, i.e, they are quite
irrational, i.e. pure intuitive, informal, actions which realize a
natural human-being's aspiration for an unrestricted freedom for the
mathematical creativity, in complete accordance with the famous slogan
by Georg Cantor. : -)

Sincerely yours,

A Z

> ############################################
> Prof. Alexander A. Zenkin,
> Doctor of Physical and Mathematical Sciences,
> Leading Research Scientist of the Computer Center
> of the Russian Academy of Sciences.
> e-mail: alexzen at com2com.ru
> WEB-Site   http://www.com2com.ru/alexzen
> ############################################
> "Infinitum Actu Non Datur" - Aristotel.
>

P.S.

THE ORIGINAL MATHEMATICAL FORMULATION OF THE H.E.RICHART's EA-THEOREM.
{see W.Sierpinski, Elementary Theory of Numbers. - Warszaw, 1964,
Chapter III. Prime numbers, pp. 143-144. Below, I give it in some
inessentially changed notation}.

 H.E.Richert▓s LEMMA (1949).    Let  { m1, m2, ┘} be an infinite
sequence of natural numbers
such that for a certain natural number k the inequality
(18)                                  m_(i+1) < = 2 m_i  for all i > k,
holds and let s0 >= m_(k+1) be a natural number.
 In such the case,
 IF there exists an integer n* > = 0 such that each of the numbers
(21)                                  n*+1, n*+2,  ┘, n*+s0
is the sum of different terms of the sequence { m1, m2, ┘, mk },
THEN every natural number  n > n* is the sum of different terms of the
sequence {m1, m2, ┘ }.

 Define the following two number-theoretical predicates:

P(n) = "n is the sum of different terms of the sequence { m1, m2, ┘ }",
and
Q(n) = Q1(n)&Q2,  where Q1(n) = " n+j is the sum of different terms of
the sequence { m1, m2,
┘, mk } for every j=1,2,..., s0 "  and  Q2 = "s0 >= m_(k+1)",

 Thus we can rewrite H.E.Richert's Lemma in the following form.

 H.E.Richert▓s LEMMA. Let  { m1, m2, ┘ } be an infinite sequence of
natural numbers such that
for a certain natural number k the inequality
(18)                       m_(i+1) <= 2 m_i  for  i > k
holds and let s0>= m_(k+1) be a natural number.
 In such the case,
    IF       there exists a number n* >= 0 such that Q(n*) is true,
 THEN  for any n > n*  P(n) is valid,
or, in the short symbolic notation,
                        _En*Q(n*) ==>
_An>n*P(n),                              (1)