Indução matemática e implicação

Question

Prefácio : (Pule esta parte se você quiser ir direto à minha pergunta. Estou escrevendo isso, então espero que não receba uma duplicata, pois ainda não consegui encontrar uma resposta satisfatória no mathstackexchange) . Olá, gostaria de perguntar por que não estou entendendo que a Indução Matemática é sempre válida. Estou ciente de que esta é uma pergunta muito comum e sei que existem muitas tentativas de explicar o porquê, mas eu tenho essa pergunta há muito tempo (na verdade, volto aqui para perguntar, já que não tive sucesso por meses). Acredite em mim, eu li muitos posts e respostas relacionadas a este tópico em diferentes sites e nenhum deles ainda satisfez minha compreensão (incluindo mathstackexchange). Vou tentar explicar claramente onde estou confuso, então espero que alguém possa me ajudar.

Então, pelo que eu sei, a indução matemática prova que uma declaração $P(n)$ é verdadeiro para todos os números naturais se:

1. $P(0)$ é verdade.

(Meu entendimento: afirmação matemática é verdadeira quando $n = 0$.)

1. Assumindo $P(n)$ é verdade para todos os números naturais e se eu puder mostrar que a implicação $P(n) \rightarrow P(n+1)$ é verdade.

(Meu entendimento: o que significa que não sabemos se a afirmação P (n) é verdadeira ou falsa. Mas se mostrarmos que a implicação $P(n) \rightarrow P(n+1)$ mantém então isso é o suficiente para a indução matemática para determinar se a declaração $P(n)$ é verdade ou não).

Se essas condições (1) e (2), são válidas, isso prova que a declaração $P(n)$ é verdadeiro para todos os números naturais.

É aqui que acho a indução matemática suspeita.

Estou bem com essa lógica de indução matemática sempre que a declaração $P(n)$é realmente verdadeiro e as condições (1) e (2) satisfazem. Então, posso concordar com as respostas comuns que tenho visto: Se$P(0)$ é verdade e desde $P(n) \rightarrow P(n+1)$ é verdade, $P(1)$é verdade. Desde a$P(1)$ é verdade com a mesma lógica $P(2)$ é verdade e assim por diante ...

Mas, pelo que sei, a implicação lógica tem uma tabela de verdade em forma:

Portanto, está dizendo que a implicação só é falsa quando a afirmação é verdadeira, mas o resultado é falso. O que significa que também é possível que a implicação seja verdadeira quando a declaração inicial$P$é falso. Se estou entendendo a implicação corretamente (corrija-me se estiver errado), quando a declaração$P \rightarrow Q$é verdade , isso significa que depois de aplicar etapas lógicas válidas à declaração inicial$P$ (se a declaração $P$ é verdadeiro ou não), você pode obter a declaração resultante $Q$.

Eu estava bem com a declaração falsa implicando que o resultado falso era verdadeiro e a declaração falsa implicando que a declaração verdadeira era verdadeira com os seguintes exemplos:

ex1) A declaração falsa implica que a declaração falsa pode ser verdadeira :

Deixe a declaração $P$ estar $-1 = 1$ e resultado $Q$ estar $0 = 2$. Estou assumindo$P$ e $Q$são ambos falsos por motivos óbvios. Agora, uma vez que a implicação é aplicar etapas lógicas, posso adicionar$1$ para ambos os lados da declaração $P$. Isto resulta em$-1 + (1) = 1 + 1 \rightarrow 0 = 2$ qual é a declaração $Q$. Portanto, a implicação é verdadeira.

ex2) A afirmação falsa implica que a afirmação verdadeira pode ser verdadeira :

Deixe a declaração $P$ estar $-1 = 1$ e resultado $Q$ estar $1 = 1$. Estou assumindo$P$ é falso por motivos óbvios, mas $Q$é verdade. Agora, uma vez que a implicação é a aplicação de etapas lógicas, posso enquadrar os dois lados da declaração$P$. Isto resulta em$(-1)^2 = (1)^2 \rightarrow 1 = 1$ qual é a declaração $Q$. Portanto, a implicação é verdadeira.

Agora, de volta à indução matemática, temos $P(0)$ sendo verdade, assumimos a declaração $P(n)$ é verdade para todos os números naturais não apenas $0$ (o que significa que também pode ser falso para alguns números maiores que $0$, mas não sabemos) e mostramos que a implicação $P(n) \rightarrow P(n+1)$é verdade. Mas pela lógica que acabei de dizer,$P(n)$ pode ser falso e ainda implicar $P(n) \rightarrow P(n+1)$é verdade. E se$P(n)$ é uma afirmação verdadeira, aplicar etapas lógicas deve me levar a $P(n+1)$porque é assim que a matemática é construída (para obter uma resposta lógica a partir de etapas lógicas). Mas se não sabemos se a declaração$P(n)$é falso e a implicação acaba sendo verdadeira, então o quê? Ainda parece a lógica do If$P(0)$ é verdade e desde $P(n) \rightarrow P(n+1)$ é verdade, $P(1)$é verdade. Desde a$P(1)$ é verdade com a mesma lógica $P(2)$é verdade e assim por diante ... deve funcionar. Mas, como eu disse, se descobrir que$P(n)$ não é verdade para todos os números naturais, não deveria ser o caso e não consigo imaginar qual seria o resultado.

Estou assumindo que deve haver alguma declaração $P(n)$ sendo falso para algum número natural (verdadeiro para $P(0)$), mas ainda verdadeiro para $P(n) \rightarrow P(n+1)$ já que a lógica diz que é possível que uma declaração falsa implique uma declaração verdadeira e há infinitas declarações que podem satisfazer isso (estou assumindo ...).

Eu tentei inventar meu próprio exemplo disso e não consegui, mas caso isso ajude as pessoas que lêem isso a entenderem melhor onde estou errando, ainda assim colocarei:

Deixe a declaração $P(n)$ no número natural seja $$\sum_{n=0}^k (n+1)^{3n} = k!3^k$$.

Podemos mostrar o caso base $P(0)$ é verdade.

Supondo que essa afirmação seja verdadeira para todos os números naturais e aplicando etapas lógicas, recebo uma contradição e não mostro que a implicação é falsa. (Talvez seja possível mostrar que a implicação é verdadeira fazendo truques inteligentes?). Neste caso, o exemplo falha, mas acredito que deveria haver tal declaração$P(n)$ isso iria satisfazer meu raciocínio.

Então, onde estou errando? Por que estou pensando que tal$P(n)$ deveria existir e por que não deveria existir?

Espero ter sido claro e se houver alguma ambigüidade ou dúvida, pergunte.

Answer 1

O Princípio da Indução Matemática

Para qualquer predicado unário $P$ temos:

$$P(0) \land \forall a\in N:[P(a) \implies P(a+1)] \implies \forall b\in N: P(b)~~~~(1)$$

Ou equivalente:

$$\exists b\in N: \neg P(b) \implies [P(0) \implies \exists a\in N:[P(a) \land \neg P(a+1)]]~~~~(2)$$

Suponha que você queira provar a hipótese de que $\forall b\in N: P(b)$ e que você já mostrou que $P(0)$ é verdade.

Deixei $k$ ser qualquer elemento de $N$.

Nós podemos provar isso $P(k)\implies P(k+1)$ da maneira usual, primeiro assumindo que $P(k)$ é verdade e então prova que $P(k+1)$ também deve ser verdade.

Tecnicamente, também podemos fazer o seguinte (não necessariamente a mesma coisa para cada valor de $k$):

• Prove ambos $P(k)$ e $P(k+1)$ são verdadeiras (correspondendo à linha 1 da tabela verdade)
• Presumir $P(k)$ é verdade e $P(k+1)$é falso. Em seguida, obtenha uma contradição (correspondente à linha 2 da tabela verdade)

Que tal simplesmente provar $P(k)$é falso como você sugeriu (correspondendo às linhas 3 e 4 da tabela verdade)? Como vemos em (2) acima, fazer isso falsificaria a hipótese inicial.

Answer 2

Comentário longo

Etapa 2), a chamada etapa indutiva é um pouco diferente ...

Vamos supor que $P(n)$ é verdade e prova $P(n+1)$, isso equivale a provar o condicional: $P(n) → P(n+1)$.

Em termos de prova, assumimos que $P(n)$ vale para um "não especificado" $n$ e nós provamos $P(n) \to P(n+1)$. Devido ao fato de$n$seja o que for, podemos "generalizar" para$\forall n (P(n) \to P(n+1)$.

Agora funciona ...

Começamos com $P(0)$: é verdade. Então use$\forall n (P(n) \to P(n+1)$e instanciá- lo com$n=0$, que significa: $P(0) \to P(0+1)$.

Usar $P(0)$e Modus Ponens para obter:$P(1)$.

E assim por diante ... A estrutura da prova indutiva nos garantirá que a "cadeia" de inferência nunca se romperá.