Is there any commonality between Math induction and Logic induction?

1.4k Views Asked by At

Logic induction is reasoning by probability.

Math induction seems to be related to just Natural numbers and used to prove a statement for every natural number.

From these definitions there is no relationship between the two concepts or are there details within each of these concepts that are common ?

Update :

Ref : https://www.youtube.com/watch?v=0F8IDj6I-tM&list=PLS8vfA_ckeuZ9UjAHhA1q-ROZGuE_h21V&index=3 at time 4:42

screenshot :

enter image description here

3

There are 3 best solutions below

7
On BEST ANSWER

From the viewpoint of modern logic, no, they are just different things. There is an historical connection though. Historically, for some logicians, "induction" was inference from special cases to a general rule. This is related to the definition you found, in that some logicians would say that special cases can make the general rule probable though they can not prove it deductively.

On the other hand, mathematical induction was so-called by Augustus de Morgan because he saw it as getting a general rule from successive cases. See Gerald Edgar's answer to https://mathoverflow.net/questions/24102/historically-first-uses-of-mathematical-induction

Contrary to what a lot of people think, mathematical induction is not an inference made from infinitely many cases. It is not the idea that given $P(0)$ and $P(1)$ and $P(2)$ and so on through $P(n)$ for every specific natural number $n$, you can infer "for all natural numbers $n$, $P(n)$.'' In fact that principle is called Hilbert's Omega rule, and it does not hold in Peano Arithmetic, or in ZFC, or indeed in any consistent recursively axiomatized theory.

But mathematical induction does hold in those theories. It is a principle about what you can infer given two things: $P(0)$ and a proof for an indeterminate $n$ that "If $P(n)$ then $P(n+1)$.'' Not infinitely many different concrete numbers $n$, but a single indeterminate $n$, logically speaking a variable. Peano Arithmetic and ZFC both let you infer "for all natural numbers $n$, $P(n)$'' from those.

To see this intuitively think of G\"odel's second incompleteness theorem. If PA is consistent, then for every concretely given natural number $n$ it has to prove "$n$ does not code a proof in PA of $0=1$.'' That is because each concrete case can be checked concretely (given enough time). But the different cases have little to do with each other. The assumption that $n$ does not code such a proof gives you no leg up on showing that $n+1$ does not. You cannot organize the reasoning to work for an actually indeterminate $n$. And so PA does not prove "for all $n$, $n$ does not code a proof of $0=1$.

To clarify the usage: "mathematical induction" is normally understood the way the OP uses it. It is reasoning on the natural numbers, by proving a base case of $n=0$ and then an induction step where you assume the conclusion for an indeterminate $n$ and prove it for $n+1$. It is taken as an axiom scheme in formalized arithmetic, and (in one form or another, depending on details) is a part of the definition of the set of natural numbers in set theory.

This is far from the only kind of induction used in mathematics. Other prominent notions of induction are transfinite induction used on transfinite ordinals in set theory, epsilon-induction used in Zermelo-Fraenkel set theory, and Noetherian induction used on ideals of Noetherian rings (or on open subsets of Noetherian spaces). There is even a general theory of "well-founded relations," which in brief means relations that support a generalized concept of inductive proof. These are well explained many places on line.

None of those senses of induction involve any notion of probability. Nor can standard uses of "inductive reasoning" in probability be justified by somehow reducing them to these. But there is the historical link described above.

0
On

In a sense, you could regard the two kinds of induction as complementary. Keep in mind that the human brain works by pattern recognition. It's a big pattern recognition machine. When you do induction from observations in nature, you are inferring a pattern from what you see in the real world. In this case, the neural network (i.e. brain) sees many examples and forms a pattern which seems to fit what it seen.

By contrast, in mathematical induction, you have a pattern which is a formula or rule which applies to an infinite sequence of cases. Then your task is to prove logically that the pattern is in fact valid.

Thus in the first case, you are inferring the pattern from repeated observations. In the second case, you are verifying absolutely that the formula is always correct.

Trivial example. You might notice that when you multiply an integer by 5, it ends in 5 if the number was odd or 0 when the number was even. This hunch could then be verified by mathematical induction.

Perhaps I could add that the same issue occurs with the word "inference". It is sometimes used in the sense of statistical inference, making a probabilistic guess that something is true with some confidence level. The word "inference" is also often used in mathematical logic books to mean logical deduction which is water-tight with total certainty.

0
On

I'll first indicate that mathematical induction does appear outside the natural numbers. For instance, common proofs of the deduction meta-theorem use mathematical induction.

Both mathematical induction and logic induction start with at least one thing satisfying a property.

To use the example of the video, if I reason using logic induction one might argue as follows:

Base cases: The Sun rose the day before yesterday, yesterday, and today.

Therefore, the Sun will rise tommorow.

If I use mathematical induction I might write a proof like the following:

Base Cases: 0 is a natural number. And 0 = 0. 1 = 0, and 2 = 0.

Induction case: The induction step involves us proving that for a natural number called "num", if num = 0, then (num + 1) = 0. So, let's assume that num = 0. Since num = 0, (num + 1) = (0 + 1). And (0 + 1) = 1. Thus, (num + 1) = 1. By the second base case above, that is 1 = 0, it follows that (num + 1) = 0. Consequently, we've proved that the inductive schema holds.

Therefore, the successor of any natural number equals 0. Since every natural number equals the successor of some other natural number, all natural numbers equal 0.

Of course that isn't correct, because it isn't the case that 1 = 0 or 2 = 0. But I'll also point out that the Sun doesn't rise.. the Earth turns inward towards the Sun!