## Real Analysis – Inductive Sets

— 4. Inductive Sets —

After proving that ${ 0 < 1}$ we can build the natural numbers by ${ 0+1 < 1+1}$ and define ${ 1+1=2}$; then ${ 1 < 2\Rightarrow 1+1 < 2+1}$ and define ${ 2+1=3}$. And following this train of thought we could define the natural numbers, but of course this method would lack a lot of rigour and this isn’t very satisfying for our mathematical aspirations.

But of course we can introduce the natural numbers in a more rigorous way. To do that first we need to define an inductive set.

 Definition 9 ${ X\subset \mathbb{R}}$ is said to be an inductive set if ${ x \in X \Rightarrow x+1 \in X}$.

As an example of an inductive set we have ${ \mathbb{R}}$ itself. One important thing to notice is that an intersection of a number (even an infinite number) of inductive sets has as result an inductive set.

Let us now consider the collection of all inductive sets that have ${ 0\,}$ as an element. The intersection of all these sets is still an inductive set, which contains ${ 0\,}$, and we’ll define this new set as being the set of the natural members and denote it by ${ \mathbb{N}}$. From this approach we could deduce a number of properties of the natural numbers that we are used to.

— 4.1. Peano’s Axioms —

Another way to approach this is to construct the natural numbers in an axiomatic way. The most used axioms are the ones introduced by Peano and in them the primitive concepts are: natural number, zero, and successor:

1. ${ \forall n \in \mathbb{N}\, n=n}$. The equality relationship is reflexive in ${ \mathbb{N}}$.
2. ${ \forall n,p \in \mathbb{N}\, n=p \Rightarrow p=n}$. Te equality relationship is symmetric in ${ \mathbb{N}}$.
3. ${ \forall n,p,q \in \mathbb{N}\, n=p, p=q \Rightarrow n=q}$. The equality relationship is transitive in ${ \mathbb{N}}$.
4. If ${ a \in\mathbb{R}}$ and ${ b=a}$ then ${ b \in \mathbb{N}}$. The natural numbers are closed under the equality relationship, whose properties were made explicit by the three previous axioms.
5. ${ 0\,}$ is a natural number.
6. ${ S}$ is an application that associates every natural number ${ n}$ to its successor. Symbolically ${ S(n)=n+1}$
7. ${ \forall n \in \mathbb{N} \, S(n)\neq 0}$. This axiom states ${ 0\,}$ as the first natural number.
8. ${ \forall m,n \in \mathbb{N}, \, S(m)=S(n) \Rightarrow m=n}$. This axiom states that ${ S}$ is an injective application (we’ll have time to see what this last term means when we get to the linear algebra part of this blog).
9. If ${ {\mathrm K}}$ is a set and ${ 0 \in {\mathrm K}}$ and ${ \forall n \in \mathbb{N} \, n\in {\mathrm K} \Rightarrow S(n) \in {\mathrm K}}$ then ${ {\mathrm K}=\mathbb{N}}$.

This last statement is sometimes called in the literature as the principle of finite induction. It serves as a base of a very powerful method of proving statements on ${ K \subset \mathbb{N}}$ (we may have the case ${ K=\mathbb{N}}$).

— 4.2. Method of Finite Induction —

This method is called the method of finite induction and it goes like this: Suppose that we want to prove some condition, ${ C(n)}$, which is supposed to be true whenever ${ n}$ is a natural number. The method of finite induction tells us that we don’t ave to prove the veracity of ${ C(n)}$ for all (infinite) cases. What we need to prove is:

1. ${ C(0)}$ is a true condition. Strictly speaking it doesn’t has to be ${ 0\,}$ but whichever first natural number, ${ p}$, that makes the condition hold.
2. ${ \forall n \in \mathbb{N}\quad C(n) \Rightarrow C(n+1)}$. Translating this to vernacular: Whenever the condition holds for a given natural number it’ll also hold for its successor.

And this is the formal statement of the method of finite induction, but perhaps it is better for us to provide a mental picture which captures the spirit of this method.

Let us suppose that our goal is to prove a given condition for all natural members. First of all we need to prove that the condition holds for ${ 0\,}$. After this is done we have to prove that whenever the condition holds for a given natural number it also holds for the natural number following it. And our job is done!

We have just proved that the condition holds for all natural numbers. And how is this so? Well, this is so because of this: in 1 we we proved that the proposition is true for ${ 0\,}$ and in 2 we proved that whenever the proposition was true for a natural number it would have to be true for its successor. So, after proving 1 we know that the condition holds for ${ 0\,}$ and by 2 it also holds for ${ 1}$. But now, by 2 it also holds for ${ 2}$! But now, by 2 it also holds for ${ 3}$! But now by 2 it also holds for ${ 4}$

I know that for the neophytes this may seem a little too abstract so I’ll give an example that hopefully will make things easier to grasp.

 Proposition 12 $\displaystyle \begin{array}{rcl} \sum_{i=1}^ni &=& 1+2+\dots+n\\ &=& \frac{n(n+1)}{2} \end{array}$ Proof: To follow the method of finite induction we need to prove the veracity of that equality for ${ n=1}$ (${ C(1)}$). So: ${ \displaystyle\sum_{i=1}^1i=\frac{1(1+1)}{2}}$. The left hand side of this equality is a sum with just one number and we get ${ 1=1\times 2/2 \Rightarrow 1=1}$ which is a true statement. The first step is now complete and it’s time to go to the second part. What we need now to prove is that if ${ C(n)}$ holds than necessarily ${ C(n+1)}$ also holds. Pay attention to the fact that now we are assuming that ${ C(n)}$ is a true statement for some ${ n}$ and what we intend to prove is that the veracity of ${ C(n+1)}$ follows. Sorry if I seem repetitive, but from my personal experience that is the point most people miss and end up not understanding the method of finite induction and why/how it works. I just hope I didn’t end up confusing people more with all the extra words. Away we go to the second part then. Now we assume that ${ \displaystyle\sum_{i=1}^ni=\frac{n(n+1)}{2}}$ for some ${ n}$ and want to prove ${ \displaystyle\sum_{i=1}^{n+1}i=\frac{(n+1)(n+2)}{2}}$. $\displaystyle \begin{array}{rcl} \sum_{i=1}^{n+1}i &=&1+2+\dots+n+n+1 \\ &=& (1+2+\dots+n)+n+1\\ &=& \sum_{i=1}^n i+n+1 \\ &=& \frac{n(n+1)}{2}+n+1 \end{array}$ where the last equality is valid by the inductive hypothesis. Continuing: $\displaystyle \begin{array}{rcl} \frac{n(n+1)}{2}+n+1 &=& \frac{n(n+1)}{2}+\frac{2(n+1)}{2}\\ &=& \frac{n(n+1)+2(n+1)}{2} \\ &=& \frac{(n+2)(n+1)}{2} \\ &=& \frac{(n+1)(n+2)}{2} \end{array}$ By assuming the validity of ${ \displaystyle\sum_{i=1}^ni=\frac{n(n+1)}{2}}$ for some ${ n}$ we were able to prove the validity of ${ \displaystyle\sum_{i=1}^{n+1}i=\frac{(n+1)(n+2)}{2}}$ (${ C(n) \Rightarrow C(n+1)}$) which is the expected result. Now ${ \displaystyle\sum_{i=1}^ni=\frac{n(n+1)}{2}}$ is proved to be valid for all ${ n \in \mathbb{N}}$ and not just some particular ${ n}$ as we assumed in the inductive hypothesis. $\Box$

As a powerful method as it is I, at least, always feel somewhat dissatisfied with it. Yes, we can prove the truth of a proposition, but we don’t get to understand why such a proposition is true. And this always makes me wonder how the first guy (or girl) was able to discern on the validity of such a proposition.

Anyway, let’s see a different proof of the previous proposition which enables to understand why it is how it is.

${ \displaystyle\sum_{i=1}^ni=S=1+2+3+\dots+n}$.

But on the other hand ${ \displaystyle\sum_{i=1}^ni=S=n+(n-1)+(n-2)+\dots+1}$.

Summing both equations term by term we get

$\displaystyle \begin{array}{rcl} 2S &=& (n+1)+(n-1+2)+\dots+(n+1) \\ &=& (n+1)+(n+1)+\dots+(n+1) \end{array}$

This is a sum of a lot numbers all of them being equal to ${ n+1}$. But how many numbers are we summing? Well in ${ \displaystyle\sum_{i=1}^n i}$ we are summing ${ (n-1)+1=n}$ terms. And the sum of ${ n}$ equal numbers is what we know as a multiplication.

$\displaystyle (n+1)+(n+1)+\dots+(n+1)=n(n+1)$

Hence

$\displaystyle \begin{array}{rcl} 2S &=& n(n+1) \Rightarrow \\ S &=& \dfrac{n(n+1)}{2} \Rightarrow \\ \sum_{i=1}^n i &=& \frac{n(n+1)}{2} \end{array}$

This time we get to understand why the ${ n}$, why the ${ n+1}$, and why the ${1/2}$.