Introdução ao primeiro princípio da indução finita §

---

O princípio da indução matemática é uma técnica poderosa para tratar com tipos de dados que exibem uma relação de boa ordem.

Note

Uma relação de boa ordem é aquela em que cada subconjunto não-vazio do tipo de dado possui um elemento mínimo de acordo com essa relação.

Um exemplo clássico que ilustra essa propriedade é o conjunto dos números naturais, representado por , que possui a relação de ordem usual (). Essa relação assegura que, em qualquer subconjunto não vazio de números naturais, existe sempre um número mínimo.

Podemos aplicar esse princípio não apenas aos números naturais, mas também a conjuntos de funções discretas, desde que a relação de boa ordem seja mantida.

Para compreender melhor esse princípio, considere a seguinte situação:

Note

Imagine uma fila de dominós alinhados, e seu objetivo é derrubar todos eles. Para garantir que você alcançará esse objetivo, é necessário estabelecer duas condições:

I. O primeiro dominó deve ser derrubado em direção aos demais. II. Se um dominó estiver suficientemente próximo do próximo na fila, derrubá-lo fará com que o dominó vizinho também seja derrubado.

Assumindo que a primeira condição (I) seja válida, podemos afirmar que o primeiro dominó será derrubado. Em seguida, assumindo que a condição (II) seja válida, o segundo dominó será derrubado, e assim por diante. Para qualquer número natural , podemos afirmar que, sob as condições (I) e (II), o dominó i-ésimo será derrubado.

Portanto, podemos concluir que, para qualquer número natural n maior ou igual a 1, o dominó n-ésimo será derrubado. Esta afirmação é a base do Primeiro Princípio da Indução Finita, frequentemente abreviado como PIF-I. A condição (I) é denominada de “base de indução”, enquanto a condição (II) é conhecida como “passo indutivo”.

Referências §

---