Posted in theory

Mathematica Induction is Also a Kind of Deduction

Peter Suber, here, makes it clear that mathematical induction is also a kind of deduction. In a typical case of induction, the conclusion has some information that does not follow from the premises. While in deduction, the conclusion has some information that logically follows from the premises. In his own words, deductions tautologously restates its premises.

In the same way, in mathematical induction, the conclusion has some information that follows from what is latent in the premises.

Peter: Mathematical induction is deductive, however, because the sample plus a rule about the unexamined cases actually gives us information about every member of the class. Hence the conclusion of a mathematical induction does not contain more information than was latent in the premises. Mathematical inductions therefore conclude with deductive certainty.

We can prove that smallest number (2) is divisible by 2. We can also prove that every next even number after the even number that is divisible by 2 is also divisible by 2. This is the rule of induction. And the sample case together with the rule is enough to say that all even numbers are divisible by 2.

The induction consists of three steps:

  1. Prove that P (some assertion/principle) holds for the minimal case.
  2. In the induction case, we introduce an hypothesis that it is true for some case (our assumption) and prove that it is true for the successor case.
  3. Then we discharge the hypothesis and make a conditional statement out of the hypothesis and conclusion.
  4. 1,2,3 taken together shows us that P is true for all cases. If we don’t use the minimal case in 1, then P is true for the case we started with and all the successors and not for all possible cases. Thus it is necessary to start with the minimal case.

The induction step is basically a conditional statement, where the condition is the antecedent and we derive the consequent.

There are other subtleties too. Peter again: Perhaps it does not go without saying that if we are to use mathematical induction to prove that some theorem applies to “all possible cases”, then those cases must somehow be enumerable and tightly linked to successive integers. We have to be able to speak about the minimal case, the nth case, and the successor of a given case. So it is perfect for proving theorems about integers themselves. The theorem that all even numbers are divisible by 2 clearly has a minimal case, namely 2, and each case (even number) clearly has a successor (the next even number). We could not use mathematical induction to prove that all hackers smell like pizza.

So, the sample set should be totally ordered set?

It takes ingenuity to decide whether to use mathematical induction or not to prove something. It necessitates one parameter upon which we can build our proof and that parameter should indeed be representative of the desired property of the thing in hand.

Posted in ramblings

Algorithms by Udi Manber

I have recently taken the book Algorithms, a creative approach by Udi Manber up for reading. The very first chapter kinda sets the stage for what is to follow. There Udi says something. He says that the intuitive solution to a problem (i.e. the one that first comes to our mind) may be inefficient, as it gets applied to larger and more complex instances of it.

So, efficient solutions get counter-intuitive and also complex. What does one learn from this simple, yet powerful statement? It kind of properly sets our expectations, once we start to read and understand things. For example, upon encountering a complex algorithm, we may not understand. But the knowledge that algorithms can indeed get counter-intuitive and complex, gives us patience to put more time and energy into it in an attempt to understand it. And once, you understand it, it further increases the confidence levels.

ThisĀ  applies not just to the algorithms, but to all complex phenomena out there. Be it a complex I/O subsystem, a complex planning system for a city etc.