Induzione matematica e implicazione

Question

Prefazione : (Salta questa parte se vuoi andare direttamente alla mia domanda. Sto scrivendo questo quindi spero che non ottenga un duplicato poiché non sono ancora riuscito a trovare una risposta soddisfacente a mathstackexchange) . Ciao, vorrei chiedere perché non riesco a capire che l'induzione matematica è sempre valida. Sono consapevole che questa è una domanda molto comune che viene posta e so che ci sono molti tentativi di spiegare perché, ma ho questa domanda da molto tempo (in realtà torno qui per chiedere dato che non ci sono riuscito per mesi). Credimi, ho letto molti post e risposte relativi a questo argomento in tutti i diversi siti Web e nessuno di loro ha ancora soddisfatto la mia comprensione (incluso mathstackexchange). Cercherò di spiegare chiaramente dove sono confuso, quindi spero che qualcuno possa aiutarmi.

Quindi da quello che so, l'induzione matematica dimostra che un'affermazione $P(n)$ è vero per tutti i numeri naturali se:

1. $P(0)$ è vero.

(La mia comprensione: l'affermazione matematica è vera quando $n = 0$.)

1. Supponendo $P(n)$ è vero per tutti i numeri naturali e se posso dimostrare che l'implicazione $P(n) \rightarrow P(n+1)$ è vero.

(La mia comprensione: significa che non sappiamo se l'affermazione P (n) è vera o falsa. Ma se mostriamo che l'implicazione $P(n) \rightarrow P(n+1)$ vale quindi che è sufficiente per l'induzione matematica a contenere l'affermazione $P(n)$ è effettivamente vero o no).

Se queste condizioni (1) e (2) sono valide, allora ciò dimostra che l'affermazione $P(n)$ è vero per tutti i numeri naturali.

Qui è dove trovo che l'induzione matematica sia sospetta.

Sto bene con questa logica di induzione matematica ogni volta che l'affermazione $P(n)$è effettivamente vero e le condizioni (1) e (2) soddisfano. Allora posso essere d'accordo con le risposte comuni che ho visto: If$P(0)$ è vero e da allora $P(n) \rightarrow P(n+1)$ è vero, $P(1)$è vero. Da$P(1)$ è vero con la stessa logica $P(2)$ è vero e così via ...

Ma da quello che so, l'implicazione logica ha una tabella di verità di una forma:

Quindi significa che l'implicazione è falsa solo quando l'affermazione è vera ma il risultato è falso. Significa che è anche possibile che l'implicazione sia vera quando l'affermazione iniziale$P$è falso. Se sto comprendendo correttamente le implicazioni (per favore correggimi se sbaglio), quando l'affermazione$P \rightarrow Q$è vero , significa che dopo aver applicato passaggi logici validi all'istruzione iniziale$P$ (se la dichiarazione $P$ è vero o no), puoi arrivare alla dichiarazione risultante $Q$.

Ero d'accordo con affermazioni false che implicano che il risultato falso sia vero e affermazione falsa che implica che l'affermazione vera sia vera con i seguenti esempi:

ex1) False statement implica False statement può essere vero :

Lasciate che la dichiarazione $P$ essere $-1 = 1$ e risultato $Q$ essere $0 = 2$. Sto assumendo$P$ e $Q$sono entrambi falsi per ovvie ragioni. Ora poiché l'implicazione sta applicando passaggi logici, posso aggiungere$1$ su entrambi i lati della dichiarazione $P$. Questo risulta in$-1 + (1) = 1 + 1 \rightarrow 0 = 2$ che è l'affermazione $Q$. Quindi l'implicazione è vera.

ex2) L'affermazione falsa implica che l'affermazione vera può essere vera :

Lasciate che la dichiarazione $P$ essere $-1 = 1$ e risultato $Q$ essere $1 = 1$. Sto assumendo$P$ è falso per ovvie ragioni ma $Q$è vero. Ora, poiché l'implicazione sta applicando passaggi logici, posso quadrare entrambi i lati dell'istruzione$P$. Questo risulta in$(-1)^2 = (1)^2 \rightarrow 1 = 1$ che è l'affermazione $Q$. Quindi l'implicazione è vera.

Ora torniamo all'induzione matematica, abbiamo $P(0)$ essendo vero, assumiamo l'affermazione $P(n)$ è vero per tutti i numeri naturali non solo $0$ (il che significa che potrebbe anche essere falso per alcuni numeri maggiori di $0$, ma non lo sappiamo) e dimostriamo che l'implicazione $P(n) \rightarrow P(n+1)$è vero. Ma dalla logica che ho appena detto,$P(n)$ potrebbe essere falso e comunque implicare $P(n) \rightarrow P(n+1)$è vero. Se$P(n)$ è un'affermazione vera, l'applicazione di passaggi logici dovrebbe portarmi a $P(n+1)$perché è così che è costruita la matematica (per ottenere una risposta logica dai passaggi logici). Ma se non sappiamo se l'affermazione$P(n)$è falso e l'implicazione risulta essere vera, allora cosa? Sembra ancora la logica di If$P(0)$ è vero e da allora $P(n) \rightarrow P(n+1)$ è vero, $P(1)$è vero. Da$P(1)$ è vero con la stessa logica $P(2)$è vero e così via ... dovrebbe funzionare. Ma come ho detto se si scopre che$P(n)$ non è vero per tutti i numeri naturali, non dovrebbe essere così e non riesco a immaginare quale sarebbe il risultato.

Suppongo che dovrebbe esistere qualche affermazione $P(n)$ essere falso per un numero naturale (vero per $P(0)$) ma ancora vero per $P(n) \rightarrow P(n+1)$ poiché la logica dice che è possibile che un'affermazione falsa implichi un'affermazione vera e ci sono infinitamente molte affermazioni che possono soddisfarla (presumo ...).

Ho provato a trovare il mio esempio di questo e non ho potuto, ma nel caso in cui questo aiuterà le persone che leggono questo può capire meglio dove sto sbagliando, lo metterò comunque:

Lasciate che la dichiarazione $P(n)$ sul numero naturale essere $$\sum_{n=0}^k (n+1)^{3n} = k!3^k$$.

Possiamo mostrare il caso di base $P(0)$ è vero.

Supponendo che questa affermazione sia vera per tutti i numeri naturali e applicando passaggi logici, ottengo una contraddizione e non riesco a dimostrare che l'implicazione è falsa. (Forse è possibile dimostrare che l'implicazione è vera facendo trucchi intelligenti?). In questo caso l'esempio si rivela fallimentare, ma credo che dovrebbe esserci una tale affermazione$P(n)$ che soddisferebbe il mio ragionamento.

Allora dove mi sbaglio? Perché penso che un tale file$P(n)$ dovrebbe esistere e perché non dovrebbe esistere?

Spero di essere stato chiaro e se ci sono ambiguità o domande per favore chiedi.

Answer 1

Il principio dell'induzione matematica

Per qualsiasi predicato unario $P$ noi abbiamo:

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

O equivalentemente:

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

Supponi di voler dimostrare l'ipotesi che $\forall b\in N: P(b)$ e questo lo hai già dimostrato $P(0)$ è vero.

Permettere $k$ essere qualsiasi elemento di $N$.

Lo possiamo provare $P(k)\implies P(k+1)$ nel solito modo assumendo prima quello $P(k)$ è vero e poi lo dimostra $P(k+1)$ deve anche essere vero.

Tecnicamente, potremmo anche eseguire una delle seguenti operazioni (non necessariamente la stessa cosa per ogni valore di $k$):

• Dimostrali entrambi $P(k)$ e $P(k+1)$ sono veri (corrispondenti alla riga 1 della tabella di verità)
• Assumere $P(k)$ è vero e $P(k+1)$è falso. Quindi ottieni una contraddizione (corrispondente alla riga 2 della tabella di verità)

Che ne dici di provare semplicemente $P(k)$è falso come hai suggerito (corrispondente alle righe 3 e 4 della tabella di verità)? Come vediamo da (2) sopra, così facendo falsificherebbe l'ipotesi iniziale.

Answer 2

Commento lungo

Passaggio 2), il cosiddetto passaggio induttivo è leggermente diverso ...

Supponiamo che $P(n)$ è vero e prova $P(n+1)$, ciò equivale a provare il condizionale: $P(n) → P(n+1)$.

In termini di prova, lo assumiamo $P(n)$ vale per un "non specificato" $n$ e noi dimostriamo $P(n) \to P(n+1)$. Dovuto al fatto che$n$è qualunque cosa, possiamo "generalizzarla" a$\forall n (P(n) \to P(n+1)$.

Ora funziona...

Cominciamo con $P(0)$: è vero. Quindi usa$\forall n (P(n) \to P(n+1)$e creane un'istanza con$n=0$, questo significa: $P(0) \to P(0+1)$.

Uso $P(0)$e Modus Ponens per ottenere:$P(1)$.

E così via ... La struttura della dimostrazione induttiva ci garantirà che la "catena" dell'inferenza non si spezzerà mai.