Indução sobre os números naturais e sobre as fórmulas

Afirmações sobre todas as fórmulas

Na aula sobre a linguagem da lógica proposicional, as fórmulas foram construídas a partir de dois símbolos, $\sigO$ e $\sigI$, que chamamos círculo e disco, e de uma só regra de formação. Há infinitas fórmulas, e muitas das afirmações que importam referem-se a todas: que toda fórmula termina com um disco, que nenhuma fórmula se lê de duas maneiras, que em toda fórmula há uma variável a mais que discos conectivos. Tais afirmações não são fórmulas da linguagem que estudamos, mas enunciados sobre ela, formulados na metalinguagem (o português, auxiliado pela notação matemática); sua demonstração não é, portanto, uma dedução dentro de um sistema formal, mas um raciocínio matemático ordinário cujo objeto é o sistema formal. Por isso são chamadas demonstrações metateóricas ou externas.

Ora, nenhuma quantidade de exemplos verificados demonstra uma afirmação sobre infinitos objetos. Segue-se que é preciso um princípio que permita concluir, a partir de um número finito de verificações, que uma propriedade vale em infinitos casos. Esse princípio é a indução. Apresenta-se primeiro sobre os números naturais, onde é mais familiar, e depois sobre as fórmulas, onde se apoia na anterior. O mesmo instrumento demonstrará, na unidade de metateoria, a correção e a completude do sistema dedutivo.