A Demonstração por Indução

Esta postagem é a segunda da série sobre os números naturais. Na primeira enunciamos os chamados Axiomas de Peano e nesta vamos volver nossa atenção para o quinto deles, chamado de Princípio da Indução:

Princípio da Indução. Se $X\subset\mathbb{N}$ é tal que $1 \in X$ e, para todo $x \in X$, tem-se $s(x) \in X$ então $X = \mathbb{N}$.

Vale salientar que na maioria das apresentações, o axioma da indução é sempre o último a ser enunciado, mas não necessariamente o quinto. Em algumas exposições ele ocupa o terceiro lugar ou até mesmo o quarto (isso se deve ao fato de que dependendo da linguagem que se adota não são necessárias cinco sentenças para expressar todas as ideias. Nós poderíamos, por exemplo, ter estabelecido já no segundo axioma a injetividade de $s$ dizendo "existe uma função injetiva" dispensando, assim, a necessidade do terceiro).

Mas vamos ao que interessa:

O método de demonstração por indução é, geralmente, utilizado para provar que uma certa propriedade vale para todos os números naturais. Deste modo, se queremos mostrar que todos os números naturais têm a propriedade $P$, o que fazemos é:

• Considerar o conjunto $X = \{x \in ℕ \mid x \text{ tem a propriedade } P\}$ (ou seja, considerar o conjunto dos números naturais que têm a propriedade $P$);

• Mostrar que o número $1$ pertence a $X$ (isto é, mostrar que o número $1$ tem a propriedade $P$);

• Mostrar que se $n \in X$ então $s(n) \in X$ (ou seja, mostrar que do fato do número n possuir a propriedade $P$ é possível concluir que seu sucessor também tem a propriedade $P$);

• Concluir (em virtude do princípio da indução) que $X = \mathbb{N}$ (ou seja, que $X$ contém todos os números naturais - o que significa que todos os números naturais têm a propriedade $P$).

Exemplo 1) Prove que nenhum número natural é igual ao seu sucessor.

• Seja $X = \{n \in\mathbb N\mid n \neq s(n)\}$ (ou seja, estamos definindo $X$ como sendo o conjunto de todos os naturais que são diferentes de seus sucessores. Note que neste caso "ter a propriedade $P$" significa "ser diferente do seu sucessor");

• O quarto axioma nos diz que $1 \notin s(\mathbb N)$. Em outros termos: $1 \neq s(n)$ para qualquer que seja o natural $n$, donde segue que $1 \neq s(1)$ (ou seja, $1$ é diferente do sucessor de qualquer número, inclusive dele mesmo). Segue-se disto que $1 \in X$;

• Como $s$ é injetiva (em virtude do terceiro axioma), concluímos (em virtude da própria definição de função injetiva) que $n \neq s(n)\Rightarrow s(n) \neq s(s(n))$ (ou seja, se $n$ é diferente de seu sucessor então o sucessor de $n$ também é diferente de seu sucessor). Isto significa que se $n \in X$ então $s(n) \in X$;

• Como $1 \in X$ e como o sucessor de cada um dos elementos de $X$ pertencem a $X$ concluímos que $X = \mathbb N$ (ou seja, concluímos que todos os números naturais são diferentes de seus respectivos sucessores ou ainda: que nenhum natural é igual ao seu sucessor).

Observe que um modo alternativo de enunciar este resultado é dizer que "existem números naturais diferentes de $1$", pois ficou estabelecido que $1 \neq s(1) \neq s(s(1)) \neq s(s(s(1)))$, etc.

A propósito, vale salientar que o sucessor de $1$ é, usualmente, designado por $2$ (e chamado de dois), o sucessor do sucessor de $1$ é representado por $3$ (e chamado de três), o sucessor do sucessor do sucessor de $1$ é representado por $4$ (e chamado de quatro), logo a última expressão do parágrafo precedente pode ser escrita como $1 \neq 2 \neq 3 \neq 4$ (expressão esta que reflete um fato nada estranho a todos nós e que é uma consequência dos axiomas).

Exemplo 2) Prove que o número $1$ é o único número natural que não é sucessor de algum outro.

• Seja $X = \{1\} \cup s(\mathbb N) = \{x\mid  x \in \{1\}\text{ ou } x \in s(\mathbb N)\}$ (ou seja, estamos definindo $X$ como sendo o conjunto que contém o $1$ e todos os naturais que são sucessores de algum outro natural. Isto significa que $x \in X$ se $x$ é $1$ ou $x$ é sucessor);

• Pela própria definição do conjunto $X$ concluímos que $1 \in X$;

• Também pela definição de $X$, concluímos que se $n \in X$ então $n = 1$ ou $n \in s(\mathbb N)$. No primeiro caso $s(n) \in X$ (pois teremos $s(n) = s(1)$ e como $1$ é um número natural $s(1) \in s(\mathbb N)$). No segundo caso observe que $n \in s(\mathbb N)$ implica $n \in \mathbb N$ (pois já que o contradomínio de $s$ é $\mathbb N$ temos $s(\mathbb N) \subset \mathbb N$) que por sua vez implica $s(n) \in s(\mathbb N)$ (pois $s(\mathbb N)$ contém o sucessor de todo natural) que finalmente implica $s(n) \in X$ (pela própria definição de $X$). Assim, em qualquer dos dois casos possíveis, do fato de $n$ pertencer a $X$ podemos concluir que $s(n)$ também pertence;

• Como $1\in X$ e como o sucessor de cada um dos elementos de $X$ pertence a $X$ concluímos que $X = \mathbb N$ (ou seja, concluímos que dado um número natural qualquer, ou ele é igual a $1$ ou então ele é sucessor de alguém, donde segue que se um número é diferente de $1$ então ele é sucessor de algum outro).

Observe que um modo alternativo de enunciar este resultado é dizer que todo número, com exceção do $1$, tem um antecessor (ou ainda, que $1$ é o único número que não tem antecessor). Para isso, tudo o que precisamos é fazer a seguinte definição: diz-se que $n$ é antecessor de $m$ quando $m = s(n)$; em outros termos: o antecessor do número $m$ é o número $n$ cujo sucessor é $m$. A propósito desta definição, vale a pena salientar que cada número tem um único antecessor (isto é uma consequência direta do terceiro axioma). Vejamos a demonstração: se $n$ e $k$ são ambos antecessores de $m$ então $m$ é sucessor tanto de $n$ quanto de $k$, ou seja, $s(n) = m$ e $s(k) = m$, donde segue $s(n) = s(k)$. Mas $s$ é injetiva, logo $n = k$.

Na próxima postagem da série veremos a definição de adição. Além disso voltaremos a usar a indução (para demonstrar as propriedades da adição, como por exemplo a comutatividade).

Referências: livro "Análise Real" (de Elon Lages Lima); livro "A Matemática do Ensino Médio, volume1" (de Elon e outros); livro "Introdução à Álgebra Abstrata" (de Evaristo e Perdigão); este texto.

Erros podem ser relatados aqui.