1.1: B.1- Introduction

Induction is an important proof technique which is used, in different forms, in almost all areas of logic, theoretical computer science, and mathematics. It is needed to prove many of the results in logic.

Induction is often contrasted with deduction, and characterized as the inference from the particular to the general. For instance, if we observe many green emeralds, and nothing that we would call an emerald that’s not green, we might conclude that all emeralds are green. This is an inductive inference, in that it proceeds from many particlar cases (this emerald is green, that emerald is green, etc.) to a general claim (all emeralds are green). Mathematical induction is also an inference that concludes a general claim, but it is of a very different kind than this “simple induction.”

Very roughly, an inductive proof in mathematics concludes that all mathematical objects of a certain sort have a certain property. In the simplest case, the mathematical objects an inductive proof is concerned with are natural numbers. In that case an inductive proof is used to establish that all natural numbers have some property, and it does this by showing that

1. \(0\) has the property, and (2)
2. whenever a number \(k\) has the property, so does \(k+1\).

Induction on natural numbers can then also often be used to prove general about mathematical objects that can be assigned numbers. For instance, finite sets each have a finite number \(n\) of elements, and if we can use induction to show that every number \(n\) has the property “all finite sets of size \(n\) are …” then we will have shown something about all finite sets.

Induction can also be generalized to mathematical objects that are inductively defined. For instance, expressions of a formal language such as those of first-order logic are defined inductively. Structural induction is a way to prove results about all such expressions. Structural induction, in particular, is very useful—and widely used—in logic.