Principio di induzione

[giordi22]

Ciao,

Ex. Dimostrare per induzione che il numero di sottoinsiemi di un insieme non vuoto
di n elementi ($n>=1$) è $2^n.

Sia $A$ un un insime non vuoto.
$P(n) := 2^n$ è il numero dei suoi elementi(qualcuno mi spieghi come mettere i doppi apici...)
Un insieme $A$ con un elemento ha 2 sottoinsiemi ${{a_0}, ø}$ quindi $p(1)$ verifica
la formula $p(n)$ e implica $ AAn P(n) => P(n + 1)$ che è vera.
Un insieme $A$ con due elementi ha ${{a_0}, {a_1}, {a_0, a_1}, ø}$ 4 sottoinsiemi
continuando a verificare l' implicazione $ AAn P(n) => P(n + 1)$.

DOMANDA DA UN MILIONE DI DOLLARI: SE UN DOCENTE ASSEGNASSE UN ESERCIZIO DEL
GENERE LA RISPOSTA SOPRA E' VALIDA?? IL PRINCIPIO DI INDUZIONE E' STATO APPLICATO
EFFICACEMENTE?????

[NeoLex]

Ora ho capito perfettamente grazie ^^
Un'ultima cosa: sarà per le mie scarse doti matematiche ma il passaggio $7^{n+1}-1$ a $7(7^{n} - 1) + 6$ è chiaramente derivato da $7*7^{n} - 1$ e posso intuirne logicamente il metodo, ma non mi ricordo proprio se è una proprietà e di cosa, probabilmente una di quelle base un po' offuscata però.. zero xD

[Rinhos]

"NeoLex":Ora ho capito perfettamente grazie ^^
Un'ultima cosa: sarà per le mie scarse doti matematiche ma il passaggio $7^{n+1}-1$ a $7(7^{n} - 1) + 6$ è chiaramente derivato da $7*7^{n} - 1$ e posso intuirne logicamente il metodo, ma non mi ricordo proprio se è una proprietà e di cosa, probabilmente una di quelle base un po' offuscata però.. zero xD

non saprei, io ci sono arrivato facendo semplicemente il ragionamento che se prima sottrai 1 a $7^n$ e poi moltiplichi per 7, in pratica lasci 7 "uni" per strada rispetto a $7^n*7 = 7^(n+1)$, e quindi togliendo 1 a $7^(n+1)$ i numeri "lasciati per strada" sono solo 6 nulla di profondo. Ossia, in generale:

$a^n-1 = a*(a^((n-1))-1)+a-1$

$AA a,n \in NN$

probabilmente anche questa relazione si può dimostrare per induzione

[NeoLex]

Stesso ragionamento.. Ok proverò a fare altri esercizi allora ^^
Grazie ancora

[gianni802]

il discorso della macchina va bene perchè la macchina si muove sullo piastrelle a terra che sono discrete e numerabili;-)
cmq bella metafora

[G.D.5]

"giordi22":Ciao NeoLex,

il principio di induzione è la dimostrazione che la proposizione "$AAn p(n)$"è vera dove $n$ è un numero naturale
qualsiasi o meglio un numero maggiore o uguale ad un determinato $n_0$

Ragazzi non abusate del linguaggio!
Lo so che sono noioso, ma dimostrare che è vero l'enunciato [tex]\forall n \in \mathbb{N}, \mathcal{P}(n)[/tex] non è il Principio di Induzione Matematica (di seguito abbreviato in PIM):
1) il PIM è uno degli assiomi di Peano per l'assiomatizzazione di [tex]\mathbb{N}[/tex], segnatamente è il seguente assioma: sia [tex]S \subseteq \mathbb{N}[/tex], se [tex]0 \in S \land \forall n, \mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex], allora [tex]S = \mathbb{N}[/tex];
2) il dimostrare che una certo enunciato [tex]\forall n \in \mathbb{N}, \mathcal{P}(n)[/tex] è vero attraverso la prova della verità di [tex]\mathcal{P}(0)[/tex] e di [tex]\forall n \in \mathbb{N}, \mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex] si chiama più propriamente dimostrazione per induzione (o ricorsiva o induttiva) e che tale metodo dimostrativo funzioni è a sua volta una cosa che va dimostrata; ma nella pratica spesso (e io aggiungerei purtroppo) si chiama PIM la tecnica di dimostrazione per induzione;
3) la dimostrazione della verità della formula enunciativa [tex]\forall n \in \mathbb{N}, \mathcal{P}(n)[/tex] potrebbe non essere unica, quindi ammeso e non concesso che sia tollerabile la confusione di cui al punto 2), sarebbe più idoneo usare "una" al posto di "la" (vedasi il grassetto nel quotato).

"giordi22":
Sia $P(n)$ il predicato (o funzione proposizionale)

Attenzione che in un sistema formale una funzione è una cosa e un predicato è n'altra: nell'alfabeto di un sistema formale i simboli per funzioni vanno distinti da quelli per i predicati.