Listening to Markopoulos & Xulouris – O Digenis
Abstraction has been defined in the preceding discussion. A convenient sequel concerns what is commonly called ‘mathematical induction’. This is an instance of abstraction.
Mathematical induction has a wrong name
Mathematical induction has a wrong name. It is a boy called Sue. It is czar Putin called president. There is no induction in ‘mathematical induction’. The term is used to indicate that each natural number n has a next one, n+1. Thus for number 665 the mathematician induces 666: big surprise. And then 667 again, even a bigger surprise after 666 should be the end of the world. The second confusion is that the full name of ‘proof by mathematical induction’ is often shortened to only ‘mathematical induction’: which obscures that it concerns a method of proof only.
This method applies to the natural numbers. It actually is a deduction based upon the definition of the natural numbers. Since the natural numbers are created by numerical succession, a proper name for the method is proof by numerical succession.
Let us define the natural numbers and then establish this particular method of proof. It is assumed that you are familiar with the decimal system so that we don’t have to develop such definitions. It is also assumed that zero is a cardinal number.
Definition of the natural numbers
A finite sequence of natural numbers is N[5] = {0, 1, 2, 3, 4, 5}. Since we can imagine such sequences for any number, there arises the following distinction given by Aristotle. He called it the difference between potential and actual infinity.
(1) Potential infinity: N[n] = {0, 1, 2, 3, …., n}. This reflects the human ability to count. (1a) It uses the successor function (“+1”): s[n] = n + 1. For each n there is a n+1. The successor function is a primitive notion that cannot be defined. You get it or you don’t get it. As a formula we can ‘define’ it by writing ‘For each n there is a n+1′, but this is not really a definition but rather the establishment of a convention how to denote it. (1b) Numerical succession might actually be limited to a finite number, say for a window of a small calculator that allows for 6 digits: 0 ≤ n ≤ 999,999. The crux of N[n] however is that n can be chosen and re-chosen at will. For each N[n] we can choose a N[n+1].
(2) Actual infinity: N = {0, 1, 2, 3, …}. This reflects the human ability to give a name to some totality. Here the name is ‘the natural numbers’.
Another formulation uses recursion: N = {n | n = 0, or n-1 ∈ N}. Thus 1 ∈ N because 0 is. 2 ∈ N because 1 is. And so on. Thus, we now have defined the natural numbers.
The potential infinite deals with finite lists. Each list has a finite length. The distinctive property of these lists is that for each such number one can find a longer list. But they are all finite. It is an entirely different situation to shift to the actual infinite, in which there is a single list that contains all natural numbers.
There need be no doubt about the ‘existence’ of the natural numbers. The notion in our minds suffices. However, our mental image may also be a model for reality. If the universe is finite, then it will not contain an infinite line, and there cannot be a calculator with a window of infinite length. But, on every yardstick in the range [0, 1] we have all 1H, 2H, 3H, ….. PM. We denote nH = 1 / n, to be pronounced as per-n, see the earlier discussion on nH.
The relation between potential and actual infinity
The shift from N[n] to N is an instance of abstraction. N[n] is a completed whole but with a need to build it, with a process of repetition. N ‘leaves out’ that one is caught in some process of repetition, while there still is a completed whole. Let us use a separate symbol @ for the particular kind or instance of abstraction that occurs in the shift from (1) to (2).
(3) N[n] @ N. This records that (1) and (2) are related in their concepts and notations. In the potential form for each n there is a n+1. In the actual form there is a conceptual switch to some totality, caught in the label N.
Since we already defined (1) and (2) to our satisfaction, (3) is entirely derivative and does not require an additional definition. It merely puts (1) and (2) next to each other, while the symbol ‘@’ indicates the change in perspective from the potential to the actual infinite.
(There might be a link to the notion of ‘taking a limit’ but it is better to leave the word ‘limit’ to its well-defined uses and take ‘@’ as capturing above instance of abstraction.)
Proof by numerical succession
The method of proof by numerical succession follows the definition of the natural numbers.
Definition: Let there be a property P[n] that depends upon natural number n. The property can be established – or become a theorem – for all natural numbers n ≥ m, by the following method of proof, called the method by numerical succession: (i) show that P[m] holds, (ii) show that P[n-1] ⇒ P[n]. (The validity of the proof depends upon whether these two steps have been taken well of course.)
When m = 0 then the property might hold for all natural numbers. The second step copies the definition of N: If n-1 ∈ N and P[n-1], then n ∈ N and then it must be shown that P[n]: if it is to hold that P[n] for all n ∈ N.
PM 1 below contains an example that uses a more conventional notation of going from n to n+1.
The definition of the method of proof doesn’t state this explictly: In the background there always is (N[n] @ N) w.r.t. the fundamental distinction between the finite N[n] and the infinite N. Conceivably we could formulate a method for N[n] separately that emphasizes the finitary view but there is no need for that here.
Conclusions
(1) A prime instance of abstraction is the relation N[n] @ N, i.e. the shift from the potential to the actual infinity of natural numbers.
(2) The method of ‘proof by numerical succession’ is a deductive method based upon the definition of the natural numbers.
(3) ‘Proof by numerical succession’ is a proper name, for what confusingly is called ‘proof by mathematical induction’.
(4) Without further discussion: There is no ‘unreasonable effectiveness’ in the creation of the infinity of the natural numbers and the method of proof by numerical succession, and thus neither in the application to the natural sciences, even when the natural sciences would only know about a finite number (say number of atoms in the universe).
PM 1. An example of a proof by numerical succession
We denote nH = 1 / n, see the earlier discussion on nH.
Theorem: For all n ∈ N:
1 + 2 + 3 + … + n = n (n + 1) 2H
Proof: By numerical succession:
(i) It is trivially true for n = 0. For n = 1: 1 = 1 * (1 + 1) 2H . Use that 2 2H = 1.
(ii) Assume that it is true for n. In this case the expression above holds, and we must prove that it holds for n+1. Substitution gives what must be proven:
1 + 2 + 3 + … + n + (n + 1) =?= (n + 1)(n + 2) 2H
On the LHS we use the assumption that the theorem holds for n and we substitute:
n (n + 1) 2H + (n + 1) =?= (n + 1)(n + 2) 2H
Multiply by 2:
n (n + 1) + 2 (n + 1) =?= (n + 1)(n + 2)
The latter equality can be established by either do all multiplications or by separation of (n+1) on the left. Q.E.D.
PM 2. Background theory
See CCPO-PCWA (2102, 2013) section 4, p16, for more on @.
PM 3. Rejection of alternative names
The name ‘mathematical succession’ can be rejected since we are dealing with numbers while mathematics is wider. The name ‘natural succession’ can be rejected since it doesn’t refer to mathematics – consider for example the natural succession to Putin. The name ‘succession for the natural numbers’ might also be considered but ‘numerical succession’ is shorter and on the mark too.
PM 4. Wikipedia acrobatics
Earlier we diagnosed that wikipedia is being terrorized by students from MIT who copy their math books without considering didactics. The wiki team seems to grow aware of the challenge and is developing a ‘simple wiki’ now. Check the standard article on mathematical induction and the simple article. The next steps for the wiki team are: to establish the distinction between easy and their notion of simplicity, then reduce the standard wiki into an easy one, and subsequently ask the MIT students to do both their copying and their experiments on simplicity at this ‘simple wiki’.