There were weak induction and strong induction.

Question (1) When can we use weak induction or strong induction?

Weak induction seemed to use the nature number as it was assuming $n$ to $n+1$, but we can say all the cases before $\alpha$ was true in strong induction. Does that mean we can only use strong induction when the definition/axiom of nature number doesn't exist?

Question (2) How do we prove weak induction or strong induction?

I've seen induction principles in Algebra, logic, although their statement was a little different, they seemed to be the same thing. I saw some post say weak induction could be proven by recursion, but in some classes they explained induction differently, say because of the usage of natural number. What's the general proof for weak induction and strong induction?


1 Answer 1


While induction is classically taught using the natural numbers, it is possible to extend it to any inductive data type; that is, any type that can have its objects built up from 'smaller' objects.

One of the easiest examples of an inductive data type is the natural numbers; defined by the rules $0$ is a natural number, and if $n$ is a natural number, $n+1$ is a natural number.

Here's another inductive data type (call it $\Gamma$) of strings over the alphabet $\{a,b\}$, with more constructors. I'll use capital letters to indicate elements of $\Gamma$, and $a,b$ for the letters of the alphabet itself.

$$a \in \Gamma$$ $$S \in \Gamma \implies aSb \in \Gamma$$ $$S \in \Gamma \implies Sbb \in \Gamma$$

Induction is a method by which we can prove a statement over all objects of some inductive type. As an example, we could prove $$\forall n \in \mathbb{N}, n+1 > 0$$

The way we do this is first by showing the base case $0 + 1 > 0$, and then showing that if $n + 1 > 0$ it holds that $(n + 1) + 1 > 0$.

Notice here we applied the constructor of the natural numbers (the successor function) to get the inductive case.

The same principle holds on any inductive data type; let's prove that sentences in $\Gamma$ never have the same parity of $a$'s and $b$'s.

The base case is $a$. Here we have one $a$ and no $b$'s, so the statement holds.

Let $S$ be any sentence in $\Gamma$ and suppose that $S$ does not have the same parity of $a$'s and $b$'s. We show this property holds over the two constructors of $\Gamma$:

$aSb$ has one more $a$ and one more $b$ than $S$. Hence, it does not have the same parity of $a$'s and $b$'s and the inductive case 1 holds.

$Sbb$ adds two $b$'s to $S$. This does not change the parity of number of $b$'s in $S$. Hence by the inductive hypothesis, $a$ and $b$ do not have the same parity, and inductive case 2 holds.

Since all cases hold, we have shown that any sentence in $S$ cannot have $a$ and $b$ occurring both an even or odd number of times.

So to answer question 1, we can use induction any time we are proving things on an inductive data type. As to using weak or strong induction, the two can be shown to be equivalent.

To prove induction in general, suppose we want to prove a property $P$ across an inductive data type $\Gamma$. We take an element $S$ of $\Gamma$ and prove that by breaking it into it's constructors, we can get a 'smaller' element. For example, we could take the sentence $aabbb$ and turn it into either $abb$ by reversing the second rule, or $aab$ by reversing the third.

In order for this to be a valid proof, we need to give an ordering on our set. In this example, ordering first by length and then dictionary order works fine. Since each constructor adds characters, it follows that $S < aSb$ and $S < Sbb$. Hence each reverse rule gives us a smaller string, until we are left with a base case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy