Dimostrare l'induzione estesa

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
atat1tata
Messaggi: 34
Iscritto il: 25 lug 2008, 17:27

Dimostrare l'induzione estesa

Messaggio da atat1tata »

Assumendo il principio di induzione:

$ {P_0 \atop \forall n P_n \to P_{n+1}}\}\Rightarrow\forall n P_n $

(e quindi anche il principio del minimo intero)
è possibile dimostrare quello esteso

$ {P_0 \atop P_0\land P_1\land \dots \land P_n \to P_{n+1}}\}\Rightarrow\forall n P_n $

supponendo per assurdo che tra $ P_0, P_1, \dots , P_n $ ce ne siano di false e tra queste sia possibile trovare il primo $ i $ per cui $ P_i $ è falsa e trovando che non può esserlo perché consegue dalle precedenti?

A me questa dimostrazione non convince più di tanto....
pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Messaggio da pic88 »

Beh se devi dimostrare P(n) con l'induzione estesa si tratta di dimostrare

Q(n)= "per ogni k minore od uguale ad n, vale P(n)"

con l'induzione semplice, ed è facile vedere che $ \forall n P(n) $ e $ \forall n Q(n) $si equivalgono.
Rispondi