Induction Principles (Basis Step Required)

by Dave
(DAVE)—

In this video, I discuss various forms of mathematical induction, including strong induction. I establish that the base case of an induction argument is required. Also, I explain the differences between the second-order logic induction principle and the first-order statement.


Many people use induction arguments, especially all kinds of mathematicians and computer scientists. But what really do we mean by “induction”? So what are induction principles? Firstly, let’s begin by exploring whether the base case of an induction argument is really even necessary.

Is the Basis Step Required with an Induction Principle?

Question. Is it true that $n + (n+1) = 2n$ for all natural numbers $n$?

Suppose I say: yes it is. Then I attempt an induction proof but I decide to skip the base case. Then what happens?

What do we mean by induction principles?

Base case flexibility

Example. Use mathematical induction to prove that $2^{n-1}>n$ for all positive integers $n\geq 3.$

The Strong Form of Induction

Strong Induction. If $P\subseteq\mathbb{N}$ and $P$ has these properties
$ \hspace{1cm} (i) \ 0\in P$ and
$ \hspace{1cm} (ii) \ \forall k\in \mathbb{N}, \ 0,\ldots,k\in P\implies k+1\in P$,
then $P=\mathbb{N}$.

Induction Principles: Various Forms of Induction

First-order version of Mathematical Induction

Notice the following statement has quantification over variables that are elements of $\mathbb{N}$. So this is a statement in a first-order logic.

First-Order Induction Principle I. If $P(n)$ is a mathematical statement with the properties
$ \hspace{1cm} (i) \ P(0)$ is true and
$ \hspace{1cm} (ii) \ \forall k\in \mathbb{N}, P(k)$ is true implies $P(k+1)$ is true
then $P(n)$ is true for all $n\in \mathbb{N}$.

Second-order version of Mathematical Induction

Notice the following statement has quantification over sets of variables that are subsets of $\mathbb{N}$. So this is a statement in a second-order logic.

Second-Order Induction Principle II. If $P\subseteq\mathbb{N}$ and $P$ has these properties
$ \hspace{1cm} (i) \ 0\in P$ and
$ \hspace{1cm} (ii) \ \forall k\in \mathbb{N}, k\in P\implies k+1\in P$,
then $P=\mathbb{N}$.

Mathematical Induction: first-order version vs second-order version

Here are some of the key differences between these induction principles:

  • There are countable infinite many statements $P(n)$ and there are uncountably many subsets $P$ of $\mathbb{N}$. For example, every set of the form $$\{n\in \mathbb{N}:P(n) \text{ is true }\}$$ is a subset of $\mathbb{N}$, but there are many more subsets of $\mathbb{N}$ not of this form.
  • The first induction principle is used as an axiom in the Peano’s Axioms (First-Order Arithmetic). In doing so, you must include addition and multiplication as additional axioms. However, with the second induction principle, (Second Order Arithmetic) addition and multiplication can de defined without additional axioms.

Conclusion

There are many versions of induction, hence the term induction principles. If you are interested only in number theory statements, then just use the first-order form of induction. However, if you are also interested in mathematical logic or the foundations of mathematics, then the second-order principles are also enjoyable.

To learn a great deal more on this topic, consider taking the online course The Natural Numbers.