Indução 
Outras formas de indução (*)
Propriedades do conjunto \(\mathbb{N}\) (dos números naturais) que foram implícita ou explicitamente usadas atrás:
Toda a parte não-vazia de \(\mathbb{N}\) tem primeiro elemento (traduz-se esta propriedade dizendo que o conjunto \(\mathbb{N}\) é bem ordenado).
- 1. \(\mathbb{N}\) é a única parte de \(\mathbb{N}\) satisfazendo as condições:
- a) tem o primeiro elemento de \(\mathbb{N}\);
- b) se tem um número, também tem o seguinte.
(Se houvesse em \(\mathbb{N}\) uma parte \(A\neq\mathbb{N}\) com estas propriedades, considerando o primeiro elemento \(b\) no complementar de \(A\) em \(\mathbb{N}\), o seu antecessor \(b-1\) estaria em \(A\) e, portanto, também estaria o sucessor de \(b-1\) que é \(b\)). Para uma afirmação \(P_{n}\) dependente de \(n\), chamando \(A\) ao conjunto dos \(n\) para os quais \(P_{n}\) é satisfeita, concluir que se \(A\) satisfaz aquelas duas condições então coincide com \(\mathbb{N}\) equivale a afirmar que, se \(P_{1}\) é verdadeira e se \(P_{n}\) implica \(P_{n+1}\) então \(P_{n}\) é verdadeira para todo o \(n\).
Consideremos agora as duas sucessões \((-\frac{1}{n})_{n}\) e \((1.1-\frac{1}{n})_{n}\) , que são crescentes e convergentes, designemos por \(A\) e \(B\) os respectivos contradomínios e por \(M\) a sua reunião.
Fig 9
Note-se que \(M\) é bem ordenado. Será que a indução, sob a forma atrás usada em \(\mathbb{N}\), funciona em \(M\)? A resposta é não. É verdade que: i) o primeiro número de \(M\), que é \(-1\), é negativo; e ii) se um número de \(M\) é negativo, o seguinte também é. Mas nem todos os números de \(M\) são negativos. E o primeiro número não negativo de \(M\), que é \(0.1\), não tem antecessor em \(M\), isto é, \(0.1\) não é o sucessor de nenhum número de \(M\) e, portanto, não podemos aplicar o argumento anterior. Há uma parte não-vazia de \(M\) diferente de \(M\), que satisfaz as duas condições. Conclusão: a indução, sob a forma atrás enunciada para \(\mathbb{N}\), não funciona para conjuntos só bem ordenados. Fortalecendo a condição 1b) para 2b) podemos afirmar o seguinte:
- 2.
- a) \(D\) tem o primeiro elemento de \(P\);
- b) se \(D\) tem todos os elementos menores do que um \(m\) de \(P\), também tem esse elemento \(m\).
Se \(D\) não coincidisse com \(P\), tomávamos o primeiro elemento \(m\) de \(P\) que não estivesse em \(D\) (existiria, por \(P\) ser bem ordenado e \(D\) ser não vazio devido a 2a)); os elementos menores do que \(m\) pertenceriam a \(D\), e 2b) implicaria que \(m\) também pertenceria a \(D\), o que contrariaria a forma como \(m\) foi escolhido.
Voltando ao contra-exemplo \(M\) indicado atrás, notemos que \(M\) já não serve como contra-exemplo(**) para o princípio da indução 2: só \(M\) satisfaz as duas condições 2. Deixa-se ao leitor a verificação de que o conjunto dos números negativos de \(M\) não satisfaz 2b).
