Prova usando indução no comprimento de uma fórmula $\phi$.

Question

Trabalhando no livro: Derek Goldrei. " Cálculo proposicional e predicado "

Na pág. 19, o princípio da indução é estabelecido da seguinte forma:

Como antes, primeiro prove que $0 \in A$ e então provar isso para todos $n \in A$, E se $k \in A$ para todos $k \leq n$, então $k \in A$ para todos $k \leq n + 1$, para concluir que $A = N$.

Na pág. 32, antes de provar:

Teorema 2.1 Qualquer fórmula$\phi$ contém um número igual de colchetes esquerdos (e colchetes direitos).

o autor explica

Mostre primeiro que o resultado é válido para todas as fórmulas de comprimento 0 - a base da indução. Em seguida, fazemos a etapa indutiva: suponha que o resultado seja válido para todas as fórmulas do tipo dado com comprimento$\leq n$ - esta é a hipótese de indução para $n$ - e com isso mostrar que vale para todas as fórmulas de comprimento $\leq n + 1$. Como estamos assumindo que a hipótese é válida para todas as fórmulas de comprimento$\leq n$, isso se resume a mostrar que a hipótese vale para fórmulas cujo comprimento é exatamente $n + 1$.

Talvez esteja faltando alguma coisa, mas geralmente penso como o princípio da indução dessa forma. Provando uma propriedade$P$ vale para todos $n \in \mathbb{N}$, equivale a:

• exposição $P(0)$ detém.
• exposição $\forall k \in \mathbb{N}(k \geq 0 \land P(k) \to P(k + 1))$

Então, minhas perguntas são:

• De que forma a definição usada pelo autor está relacionada com a definição comum de prova por indução?

• Eu estava acostumada a ver $k \geq 0$ e não $k \leq n$. Esta suposição está usando$\leq$ relacionado de alguma forma a $k \geq 0$?

Answer 1

A definição do autor é logicamente equivalente à usual.

É apenas "mais forte" no sentido de que torna a aplicação da indução mais fácil. Sua definição pode ser bastante útil em alguns casos, por exemplo, se a prova para$N+1$ requer que você saiba que a afirmação não é verdadeira apenas para $N$, mas também para alguns valores menores do que $N$ (diga para $N-1$ e $N-2$)

Nesse caso, assumindo que a afirmação é verdadeira para todos $k \le N$ torna a vida mais fácil.

Eu digo "mais forte" (entre aspas) porque não é realmente mais forte, apenas disse que é logicamente equivalente. É apenas mais conveniente em alguns casos.

Esta prova, por exemplo, com o número de colchetes, parece ser um desses casos.