Inducción e implicación matemáticas

Question

Prefacio : (Omita esta parte si desea ir directamente a mi pregunta. Estoy escribiendo esto, así que espero que no obtenga un duplicado ya que todavía no pude encontrar ninguna respuesta satisfactoria en mathstackexchange) . Hola, me gustaría preguntar por qué no entiendo que la inducción matemática siempre es válida. Soy consciente de que esta es una pregunta muy común que se hace y sé que hay muchos intentos de explicar por qué, pero he tenido esta pregunta durante mucho tiempo (en realidad, vuelvo aquí para preguntar porque no tuve éxito durante meses). Créame, he leído muchas publicaciones y respuestas relacionadas con este tema en los diferentes sitios web y ninguno de ellos todavía satisfizo mi comprensión (incluido mathstackexchange). Trataré de explicar claramente dónde estoy confundido, así que espero que alguien pueda ayudarme.

Entonces, por lo que sé, la inducción matemática demuestra que una declaración $P(n)$ es cierto para todos los números naturales si:

1. $P(0)$ es verdad.

(Según tengo entendido: la afirmación matemática es verdadera cuando $n = 0$.)

1. Asumiendo $P(n)$ es cierto para todos los números naturales y si puedo demostrar que la implicación $P(n) \rightarrow P(n+1)$ es verdad.

(A mi entender: lo que significa que no sabemos si el enunciado P (n) es verdadero o falso. Pero si mostramos que la implicación $P(n) \rightarrow P(n+1)$ sostiene entonces que es suficiente para que la inducción matemática se mantenga si el enunciado $P(n)$ es realmente cierto o no).

Si se cumplen estas condiciones (1) y (2), entonces eso prueba que la declaración $P(n)$ es cierto para todos los números naturales.

Aquí es donde encuentro que la inducción matemática es sospechosa.

Estoy bien con esta lógica de inducción matemática siempre que la declaración $P(n)$es realmente cierto y se cumplen las condiciones (1) y (2). Entonces puedo estar de acuerdo con las respuestas comunes que he visto: Si$P(0)$ es cierto y desde $P(n) \rightarrow P(n+1)$ es verdad, $P(1)$es verdad. Ya que$P(1)$ es cierto con la misma lógica $P(2)$ es cierto y así sucesivamente ...

Pero por lo que sé, la implicación lógica tiene una tabla de verdad de una forma:

Por lo tanto, está diciendo que la implicación solo es falsa cuando la declaración es verdadera pero el resultado es falso. Lo que significa que también es posible que la implicación sea verdadera cuando la declaración inicial$P$Es falso. Si entiendo la implicación correctamente (corríjame si me equivoco), cuando la declaración$P \rightarrow Q$es verdadero , significa que después de aplicar pasos lógicos válidos a la declaración inicial$P$ (si la declaración $P$ es cierto o no), puede acceder a la declaración resultante $Q$.

Estaba de acuerdo con una declaración falsa que implica que el resultado falso es verdadero y una declaración falsa que implica que la declaración verdadera es verdadera con los siguientes ejemplos:

ex1) Una declaración falsa implica que la declaración falsa puede ser verdadera :

Deja la declaración $P$ ser $-1 = 1$ y resultado $Q$ ser $0 = 2$. Estoy asumiendo$P$ y $Q$ambos son falsos por razones obvias. Ahora que la implicación es aplicar pasos lógicos, puedo agregar$1$ a ambos lados de la declaración $P$. Esto resulta en$-1 + (1) = 1 + 1 \rightarrow 0 = 2$ cual es la declaración $Q$. Por tanto, la implicación es verdadera.

ex2) La declaración falsa implica que la declaración verdadera puede ser verdadera :

Deja la declaración $P$ ser $-1 = 1$ y resultado $Q$ ser $1 = 1$. Estoy asumiendo$P$ es falso por una razón obvia pero $Q$es verdad. Ahora que la implicación es aplicar pasos lógicos, puedo cuadrar ambos lados de la declaración$P$. Esto resulta en$(-1)^2 = (1)^2 \rightarrow 1 = 1$ cual es la declaración $Q$. Por tanto, la implicación es verdadera.

Ahora, de vuelta a la inducción matemática, tenemos $P(0)$ siendo cierto, asumimos la afirmación $P(n)$ es cierto para todos los números naturales, no solo $0$ (lo que significa que también podría ser falso para algunos números mayores que $0$, pero no lo sabemos) y mostramos que la implicación $P(n) \rightarrow P(n+1)$es verdad. Pero por la lógica que acabo de decir,$P(n)$ podría ser falso y aún implicar $P(n) \rightarrow P(n+1)$es verdad. Si$P(n)$ es una afirmación verdadera, la aplicación de pasos lógicos debería llevarme a $P(n+1)$porque así es como se construyen las matemáticas (Para obtener una respuesta lógica a partir de pasos lógicos). Pero si no sabemos si la declaración$P(n)$es falso y la implicación resulta ser cierta, ¿entonces qué? Todavía parece que la lógica de If$P(0)$ es cierto y desde $P(n) \rightarrow P(n+1)$ es verdad, $P(1)$es verdad. Ya que$P(1)$ es cierto con la misma lógica $P(2)$es cierto y así sucesivamente ... debería funcionar. Pero como dije si resulta que$P(n)$ no es cierto para todos los números naturales, este no debería ser el caso y no puedo imaginar cuál sería el resultado.

Supongo que debería existir alguna declaración $P(n)$ siendo falso para algún número natural (verdadero para $P(0)$) pero sigue siendo cierto para $P(n) \rightarrow P(n+1)$ ya que la lógica dice que es posible que una declaración falsa implique una declaración verdadera y hay infinitas declaraciones que pueden satisfacer esto (estoy asumiendo ...).

Traté de dar mi propio ejemplo de esto y no pude, pero en caso de que esto ayude a las personas que leen esto a entender mejor en qué me estoy equivocando, aún lo pondré:

Deja la declaración $P(n)$ en número natural sea $$\sum_{n=0}^k (n+1)^{3n} = k!3^k$$.

Podemos mostrar el caso base $P(0)$ es verdad.

Suponiendo que esta afirmación es verdadera para todos los números naturales y aplicando pasos lógicos, obtengo una contradicción y no puedo demostrar que la implicación es falsa. (¿Quizás sea posible demostrar que la implicación es cierta haciendo trucos inteligentes?). En este caso, el ejemplo resulta fallar, pero creo que debería haber tal declaración$P(n)$ eso satisfaría mi razonamiento.

Entonces, ¿dónde me equivoco? ¿Por qué estoy pensando que tal$P(n)$ debería existir y por qué no debería existir?

Espero haber sido claro y si hay alguna ambigüedad o preguntas, por favor pregunte.

Answer 1

El principio de inducción matemática

Para cualquier predicado unario $P$ tenemos:

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

O equivalente:

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

Suponga que quiere probar la hipótesis de que $\forall b\in N: P(b)$ y que ya has demostrado que $P(0)$ es verdad.

Dejar $k$ ser cualquier elemento de $N$.

Podemos probar eso $P(k)\implies P(k+1)$ de la forma habitual asumiendo primero que $P(k)$ es cierto y luego demostrar que $P(k+1)$ también debe ser cierto.

Técnicamente, también podríamos hacer cualquiera de las siguientes cosas (no necesariamente lo mismo para cada valor de $k$):

• Demuestra ambos $P(k)$ y $P(k+1)$ son verdaderas (correspondientes a la línea 1 de la tabla de verdad)
• Asumir $P(k)$ es verdad y $P(k+1)$Es falso. Luego obtenga una contradicción (correspondiente a la línea 2 de la tabla de verdad)

¿Qué tal simplemente probar $P(k)$es falso como sugirió (correspondiente a las líneas 3 y 4 de la tabla de verdad)? Como vemos en (2) arriba, hacerlo falsearía la hipótesis inicial.

Answer 2

Comentario largo

Paso 2), el llamado paso inductivo es un poco diferente ...

Asumamos que $P(n)$ es verdad y prueba $P(n+1)$, eso equivale a probar el condicional: $P(n) → P(n+1)$.

En términos de prueba, asumimos que $P(n)$ se mantiene para un "no especificado" $n$ y probamos $P(n) \to P(n+1)$. Debido al hecho de que$n$es lo que sea, podemos "generalizarlo" a$\forall n (P(n) \to P(n+1)$.

Ahora funciona...

Empezamos con $P(0)$: es verdad. Entonces usa$\forall n (P(n) \to P(n+1)$y instanciarlo con$n=0$, eso significa: $P(0) \to P(0+1)$.

Utilizar $P(0)$y Modus Ponens para obtener:$P(1)$.

Y así sucesivamente ... La estructura de la prueba inductiva nos garantizará que la "cadena" de inferencia nunca se romperá.