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).


(*) A leitura desta secção não é essencial à plena compreensão do resto do artigo.

(**) A construção do contraexemplo \(M\) para 1) usava um elemento (diferente do primeiro) sem antecessor, e num conjunto bem ordenado não vazio um tal elemento existe se e só se houver um conjunto infinito majorado. Mas um conjunto infinito bem ordenado sem partes infinitas majoradas é, do ponto de vista da relação de ordem, perfeitamente equivalente a \(\mathbb{N}\). Em \(\mathbb{N}\) verificam-se 1) e 2) e essa situação é por vezes designada por princípio da indução finita precisamente por a hipótese de indução se referir sempre a um conjunto finito de valores.

Página seguinte