Induction Oversights — Fundamental Oversights — Mathematics

INDUCTION... OVERSIGHTS
IN MATHEMATICS

One of the most unbelievable situations in mathematics is that mathematicians, logicians, and others — who should all be completely familiar with mathematical induction — in fact do NOT know what mathematical induction is and what it does and does not do.

Induction, specifically finite induction (transfinite induction is somewhat more arcane), is about as fundamental as one can get in mathematics, not just set theory but number theory. It is used everywhere, though to some extent invisibly because it has been used to prove theorems that are so fundamental that their proofs are no longer questioned.

Finite induction and the definition of the natural numbers {1,2,3...} are minor variants of each other. (Some might say that they are actually the same since Peano’s postulates, which seem to have originated with Dedekind, are used to define the natural number system and include the sometimes so-called “axiom of mathematical induction”, variously numbered 4th or 5th depending on the source. The question of whether this postulate/axiom is independent of the others will not be addressed here.) In any case, the natural numbers are defined inductively. This is done in 2 stages, as follows:

1 is a natural number (modernly, some have chosen to start with 0);
if n is a natural number, then n + 1 is a natural number.

Finite induction is used to prove (an infinite/transfinite number of) propositions over the set or class of natural numbers. I.e., we (want to) prove that P(1) is true, P(2) is true, etc. Finite induction is defined in 2 stages, as follows:

Prove that P is true for 1, i.e. that P(1) is true; (the BASE clause)
prove that if P is true for n, then P is true for n + 1. (the INDUCTIVE clause)

It is trivially obvious that if the 2 stages of finite induction are completed successfully, then we can say unequivocally that P(n) is true for any natural number n.

Finite induction is actually ambiguously named. Using finite induction one uses a finite proof to prove an infinite (transfinite) number of propositions (sometimes referred to as a transfinite schema). And this is where some mathematicians and logicians fail to know their own craft. (See Fundamental... Oversights.) We will look at the psychology of this failure, but first we will look at some extremely simple uses of finite induction, and their consequences.

SECTIONS

SIMPLE USE of FINITE INDUCTION

SIMPLE USE of FINITE INDUCTION
PERMUTATIONS of BIJECTIONS

Assume we have an arbitrary bijection B from the set of natural numbers onto itself, i.e. a bijection from Á 4 {1,2,3...} onto Á. The identity bijection from Á onto Á would have 1 mapped onto 1, 2 mapped onto 2, etc. But an arbitrary bijection allows any natural number i to be mapped onto any other natural number j.

It seems obvious that there should exist a valid bijection from any set onto itself. So we will not question that at this point. We will look at the possibility of permuting the bijection from Á onto Á into another bijection from Á onto Á.

We will start by asking a very simple question: under B, is 1 mapped onto itself, 1? If it is, then that much of B is the identity bijection. If it is not, then 1 is mapped onto some j, and some i is mapped onto 1. This mapping from 1 onto j and from i onto 1 is itself a bijection, a subbijection of B. We can permute this subbijection (and thus also permute B) by switching the mappings (we can call them “links”) so that 1 is mapped onto 1 and i is mapped onto j.

In terms of finite induction, we have proved the base clause, P(1), of the proposition (or theorem) that if B is a bijection from Á onto Á, then either 1 is initially mapped onto 1, or there exists a permutation of B that consists of switching the links between 2 numbers and their bijective counterparts such that 1 is mapped onto 1.

All we need to do is to note that we could have chosen any n instead of 1, and we have proven P(n), i.e. that if B is a bijection from Á onto Á, then either any n is initially mapped onto itself, n, or there exists a permutation of B such that n is mapped onto itself, n.

This last makes it trivial to prove the inductive clause since we have already proved that our P(n) for any n, and therefore we have already proved P(n + 1), i.e. that either any n + 1 is initially mapped onto itself, n + 1, or there exists a permutation of B such that n + 1 is mapped onto itself, n + 1.

What have we proved? Using finite induction we have proved that if we have an arbitrary bijection B from Á onto Á, then we can permute B by switching 2 links at a time so that we eventually get the identity bijection. It may take 1 simple permutation or link switch for each natural number, i.e. an infinite number of simple permutations or link switches, but such infinite numbers of operations is irrevocably a part of mathematics. (We can make it even more obvious if we subtract out the numbers that have been mapped onto themselves as we go along.) We have an infinite number of operations to create or construct Á, we have an infinite number of operations every time we use finite induction, so there is no problem with infinite numbers of operations.

(Incredible as it may seem, some mathematicians, obviously desperate, have raised objections to infinite numbers of operations, even though they are doing so in the context of the natural numbers which require an infinite number of operations for their construction. The psychology of this situation is essential to analyze in detail in the near future.)

This all sounds trivially obvious, and in a sense it is. But mathematics is notorious for starting with such simple beginnings and generating fascinating results.

SECTIONS

SIMPLE USE of FINITE INDUCTION

ANOTHER SIMPLE USE of FINITE INDUCTION

ANOTHER SIMPLE USE of FINITE INDUCTION
MORE PERMUTATIONS of BIJECTIONS

A mathematician who is interested in generalizing results such as that above would note that we have a situation involving bijections between sets that have a subset of elements in common. (In the result above, this subset was the improper subset of Á itself.) That is, if the 2 sets involved in the initial bijection have a set of elements in common, then we can permute the initial bijection until each and every element in the set of common elements is bijectively mapped onto itself in an identity subbijection of the cumulatively permuted bijection.

This sounds trivial to prove, especially if we are dealing with natural numbers, and it is. In fact, it is trivial enough that we can consider it proven here. Making it as rigorous as needed is completely straightforward. But...

There is a huge “but”...

Set theory has in its fundamentals that there exist bijections between sets (transfinite sets) and proper subsets of themselves. These are the basis for transfinite arithmetic, e.g. the standard bijection between {0,1,2,3...} and {1,2,3...} gives us the fundamental theorem that a₀ + 1 = a₀.

The huge “but” is that we proved above that we can permute an arbitrary bijection from a transfinite set such as {0,1,2,3...} onto a proper subset of itself such as {1,2,3...} so that the cumulatively permuted bijection has an identity subbijection from {1,2,3...} onto itself. This means that every element of {0,1,2,3...} is bijected onto itself except for 0, which is not one of the common elements. The huge “but” is that 0 both must be bijected onto an element of {1,2,3...} and CANNOT with even the remotest possibility be bijected onto an element of {1,2,3...}. I.e. if we allow bijections from sets onto proper subsets of themselves, there must exist bijections from non-empty sets such as {0} and the empty set, @ 4 { }. This will eventually be considered a fatal flaw in set theory.

It is at this point that some mathematicians will say that finite induction does not actually do what mathematics says it will do. Some have actually said that finite induction only proves the above results for finite sets of common elements, and not for e.g. a set of common elements equal to Á. This stance is completely out of accord with the essential mathematical meaning of finite induction. Psychologically this allows them to avoid admitting the essential failure of set theory... for a while longer.

SECTIONS

SIMPLE USE of FINITE INDUCTION

“TRANSFINITE CASE” FINITE INDUCTION THEOREM

“TRANSFINITE CASE” FINITE INDUCTION THEOREM

To help make the above point clear, we will prove a theorem about finite induction that generalizes it slightly to propositions concerning sets of numbers instead of just the numbers themselves. (See comment on general/second kind induction, below.) Because so many PhD mathematicians fail in their understanding of what finite induction is and does, it will be emphasized here that the following theorem is merely another way of stating the standard mathematical concept that the set of all finite natural numbers is a transfinite set, trivially the set Á 4 {1,2,3...}. It is logically equivalent to standard finite induction, i.e. either one can be used to prove the other. It is another way of saying that the set S of natural numbers n for which standard finite induction proves the propositions P(n) is precisely the set Á = {1,2,3...} of all natural numbers, a trivially transfinite set; i.e. S 4 Á. If the following theorem — which is logically equivalent to standard finite induction — is false, set theory is fatally flawed on that basis alone.

“TRANSFINITE CASE” FINITE INDUCTION THEOREM:
If (we can prove that):

P´({1}) is true; and

if P´({1...n}) then P´({1...n + 1})

then (we have proven) P´(Á) as well as P´({1...n}) for every natural number n.
I.e. IF P´({1…n}) is true “for all finite n”
THEN it is true in the “transfinite case”, P´(Á)
Further, “Transfinite Case” Finite Induction is logically equivalent to standard finite induction.
PROOF:
There are two obvious approaches, either one of which should suffice.
The first approach is to apply standard finite induction as follows: let P(n) = P´({1…n}), which we can also write as P(n) = P´({i| 1 £ i £ n}). (NOTE that this is different from some statements of general induction which refer only to strictly proper subsets, i.e. i < n.) By condition 1) we trivially have P(1) = P´({1}) and by condition 2) we trivially have P(n) ® P(n + 1); therefore, by standard finite induction, P(n) holds for all n Î Á, and therefore P´({n | n Î Á}) holds in addition to P´({1…n}) for all n Î Á; but {n | n Î Á} 4 Á, therefore P´(Á). NOTE that this first approach demonstrates that standard finite induction implies “Transfinite Case” Finite Induction.

Logical equivalency follows trivially by showing that “Transfinite Case” Finite Induction implies standard finite induction, as follows: let P´(S) be interpreted as meaning that for all elements n of the set S (of natural numbers), P(n) holds. If P´({1}) is true, this implies the truth of P(1). And if P´({1...n}) is true, this implies the truth of P(1), P(2),... and P(n), and therefore implies the truth of P(n), which is merely one of those propositions whose truth is implied by P´({1...n}). Similarly for P´({1...n + 1}). So if we have P´({1}) being true, and if we have that if P´({1...n}) then P´({1...n + 1}), then we also have that P(1), and that if P is true for n, then P is true for n + 1. Thus “Transfinite Case” Finite Induction implies standard finite induction, and they are logically equivalent.

A second, corroborative approach is to notice that, if we are constructing a set S, 1 Î S and 1…n Î S ® 1…n + 1 Î S (and no other elements in this set S) is logically equivalent to the standard definition of Á, i.e. S 4 Á. If that isn’t sufficient, consider the following: Conditions 1) and 2) construct such a set S with property P´. Condition 2) guarantees the property P´ is inherited by all thus constructed supersets of {1} Í S, which latter is condition 1); thus P´ is inherited by S 4 Á, therefore P´(Á). The argument that S ¹ Á fails, since in that case S must differ from Á by some least element m; m cannot be 1 by condition 1; therefore m – 1 Î S; by condition 2, m – 1 + 1 Î S, i.e. m Î S, which contradicts the assumption of non-equality, thus standardly accepted mathematical reasoning gives us S = Á.

A third approach, the use of general/second kind induction, is avoided here. Some might even say that the above is equivalent to general/second kind induction, which gives mathematicians even less excuse for the mistake that will be detailed in the next section.)

SECTIONS

SIMPLE USE of FINITE INDUCTION