[MATEMATICA] Principio di induzione

[nin]

Ciao a tutti!

Ragazzi sarà una cosa gnocchissima ma io ho saltato la lezione di analisi sul principio di induzione e adesso non so assolutamente cosa fare...

Il primo es (andiamo con calma..) è questo:

2^n>=n+1

che è vero per n=1 e devo dimostrare per n=(n+1)
quindi:

2^(n+1)>=(n+1)+1

Io non so che pesci prendere..se qualche buon'anima riuscisse a svolgere questo penso avrei buone probabilità di capire anche gli altri..mi sfugge proprio la logica!

Grazie a tutti gli ing,fis,mat, etc etc che mi aiuteranno!

[nin]

..mh nessuno sa che pesci prendere?

[Qwertid]

Non so se questi esempi possono esserti utili ma se ti può far sentir meglio (dubito ) neanche io l'ho mai capito... Magari leggendo questi hai l'illuminazione... Buono studio!

E' un pò mangiata di lato ma la piegatura del libro è stretta

[nin]

Originariamente inviato da Qwertid
Non so se questi esempi possono esserti utili ma se ti può far sentir meglio (dubito ) neanche io l'ho mai capito... Magari leggendo questi hai l'illuminazione... Buono studio!

E' un pò mangiata di lato ma la piegatura del libro è stretta

Hey grazie!

Faccio un pò fatica a leggere..vedrò cosa riesco a fare!

Io torno sabato, se qualcuno intanto potesse aiutarmi magari risolvendo quella postata + sopra..O anche anche dando esempi come il gentilissimo Qwertid!

Cavolo stò maledetto principio...

Va beh che adesso devo anche fare limiti e calcolo complesso..

Thanks, byez!

[ChristinaAemiliana]

Vediamo se riesco a ricordarmi qualcosa...Analisi I...qualcosa come dieci anni fa!!!

Il principio di induzione matematica nei miei ricordi suona più o meno così: se una proprietà P(n) definita su N (insieme dei numeri naturali) vale per n=0 (o n=1, dipende da dove parti...) e, nel caso valga per un qualunque numero naturale n vale certamente anche per il successivo, allora la proprietà è vera per tutti gli n.

Per dimostrare che una proprietà vale su tutto N applicando il principio di induzione allora devi verificare che:

1) valga per n=0 (o n=1);

2) ipotizzando che valga per n, ne consegua che vale anche per n+1.

Se (1) e (2) sono verificate, allora la proprietà è vera per ogni n, e quindi su tutto l'insieme ambiente N.

Nel tuo caso devi dimostrare che:

2^n >= n+1

1) 2^0 >= 1 -------> vero

2) Ipotesi induttiva: 2^n >= n+1.
Devi verificare che: 2^(n+1) >= (n+1)+1.
Per esempio puoi procedere così:

2^(n+1) = 2*2^n >= 2*(n+1) = 2n+2 > n+2

c.v.d.

[casacup]

ci avevo riflettuto ultimamente...

il principio di induzione è un principio più che matematico logico, dico bene? e a ben rifletterci la matematica, la fisica, le scienze in generali si basano proprio su questo principio logico.

e allora viene da chiedersi...qual'è la dimostrazione del principio di induzione? semplice, il principio di induzione si dimostra col principio di induzione stesso

però qua sorge un problema... eh già, dove si è mai visto che qualcosa si dimostra tramite l'oggetto stesso dell'analisi? è come, a dirla in maniera volgare, se in una qualsiasi dimostrazione ipotesi e tesi coincidessero, o quasi.

a voi questa cosa non da da pensare? fondamentalmente credo sia uno dei motivi per cui la matematica, la fisica e tutto il resto non sono "vere" in maniera assoluta ma solo in maniera relativa, ovvero sono vere quel tanto che basta per avere un riscontro nella realtà (calcore integrali, costruire frigoriferi ecc).

che ne pensate gente?

[r_howie]

Originariamente inviato da casacup

che ne pensate gente?

Che devi assolutamente leggere il libro di Hofstadter, di cui uno dei temi è proprio l'incompletezza dei sistemi formali.

[Axe!]

Originariamente inviato da casacup

ci avevo riflettuto ultimamente...

il principio di induzione è un principio più che matematico logico, dico bene? e a ben rifletterci la matematica, la fisica, le scienze in generali si basano proprio su questo principio logico.

e allora viene da chiedersi...qual'è la dimostrazione del principio di induzione? semplice, il principio di induzione si dimostra col principio di induzione stesso

però qua sorge un problema... eh già, dove si è mai visto che qualcosa si dimostra tramite l'oggetto stesso dell'analisi? è come, a dirla in maniera volgare, se in una qualsiasi dimostrazione ipotesi e tesi coincidessero, o quasi.

a voi questa cosa non da da pensare? fondamentalmente credo sia uno dei motivi per cui la matematica, la fisica e tutto il resto non sono "vere" in maniera assoluta ma solo in maniera relativa, ovvero sono vere quel tanto che basta per avere un riscontro nella realtà (calcore integrali, costruire frigoriferi ecc).

che ne pensate gente?

Non è proprio così, ed affido la spiegazione ad un passaggio dell'opera di Corrado Brogi:
"
I numeri naturali 1,2,3,…sono alla base della teoria dei numeri. Essi non sono definibili, e per essi valgono i 3 assiomi di Peano:
Detto N l’insieme dei numeri naturali:
1° Assioma: esiste il numero 1 e l’insieme N-{1} non è vuoto
2° Assioma: ogni numero naturale possiede un successivo
3° Assioma: ogni numero naturale si ottiene da 1 contando in successione

Questi tre assiomi costituiscono la base logica di tutta la teoria dei numeri. Da questi tre assiomi discende immediatamente il principio di induzione matematica che assicura che una affermazione è vera per ogni n appartenente ad N se è vera per n=1 ed, essendo vera per n, lo è anche per n+1.
Questo principio può essere utilizzato ogni volta in cui si vuole dimostrare l’esattezza di una affermazione legata ai numeri naturali.
"

Tutto ciò fermo restando il problema dell'incompletezza dei sistemi formali.

[Ziosilvio]

Originariamente inviato da casacup

il principio di induzione si dimostra col principio di induzione stesso

Non proprio.

A volte, nei corsi di Analisi, si dà una dimostrazione del Principio di induzione completa in cui si sfrutta in modo nascosto il buon ordinamento dei numeri naturali, secondo cui ogni insieme non vuoto di numeri naturali è dotato di minimo.
Tale enunciato è però equivalente al Principio di induzione completa, ossia i numeri naturali sono ben ordinati se e solo se il Principio di induzione è vero. (ESERCIZIO: dimostrare.)
Dato che in realtà non c'è un vero motivo per cui il Principio di induzione debba essere vero --- ossia: ci sono aritmetiche "non standard" in cui è falso; vedere ad esempio QUI --- esso viene assunto come assioma nell'aritmetica di Peano, che è la teoria al primo ordine che al momento sembra in grado di formalizzare meglio l'aritmetica del mondo reale.

[casacup]

mmm sì ma c'è un fatto: il principio di induzione è un principio logico, ed i numeri naturali si naturali sono stari "creati" basandosi su questo principio. e forse è proprio da questo che non si possono creare insieme completi, o detto più volgarmente privi di incongruenze e paradossi: proprio perchè il tutto si basa su questo principio logico che a sua volta si basa sulla logica umana, probabilmente non abbastanza evoluta.

basti pensare alla definizione di insieme: una classe per la quale esiste una legge di natura qualsiasi che consente di sapere se un elemento appartiene a quella classe o no. C'è un famoso paradosso a proposito, ovvero l'insieme che contiene tutti gli insiemi: definita questa precisa legge, questo insieme, in quanto tale, dovrebbe essere contenuto in se stesso, quindi dovrebbe esistere un altro insieme che contiene tutti gli insiemi più quello definito e così via, all'infinito...

[nin]

Originariamente inviato da r_howie

Che devi assolutamente leggere il libro di Hofstadter, di cui uno dei temi è proprio l'incompletezza dei sistemi formali.

Ho letto critiche entusiastiche per questo libro..Confermate?

Comunque mi sono accorto, dopo questo up, di non aver mai ringraziato ChristinaAemiliana per l'aiuto..
Meglio tardi che mai, thanks a suo tempo mi servì

[casacup]

l'argomento trattato è estremamente interessante perchè porta ai numerosi inghippi e magie della matematica...

a suo tempo feci dele belle riflessioni, ora purtroppo, causa esami, non posso dedicarmi a risviscerare l'argomento, però mi riprometto di riportare le riflessioni e quella dimostrazione del principio tramite il principio stesso, per sentire chi sicuramente ne sa più di me cosa ne pensa...

In ogni caso credo che il discorso vada oltre la matematica, non dico la filosofia ma almeno credo sia nell'ambito della logica e del ragionamento umano. per questo ho un pò di riserve a riguardo....

[Axe!]

Originariamente inviato da casacup

l'argomento trattato è estremamente interessante perchè porta ai numerosi inghippi e magie della matematica...

a suo tempo feci dele belle riflessioni, ora purtroppo, causa esami, non posso dedicarmi a risviscerare l'argomento, però mi riprometto di riportare le riflessioni e quella dimostrazione del principio tramite il principio stesso, per sentire chi sicuramente ne sa più di me cosa ne pensa...

In ogni caso credo che il discorso vada oltre la matematica, non dico la filosofia ma almeno credo sia nell'ambito della logica e del ragionamento umano. per questo ho un pò di riserve a riguardo....

Hai centrato la questione. Non a caso questa è trattata su un paio di libri divulgativi del famoso logico matematico Odifreddi.

[Ziosilvio]

Originariamente inviato da casacup

il principio di induzione è un principio logico, ed i numeri naturali si naturali sono stari "creati" basandosi su questo principio.

I numeri naturali esistono indipendentemente dagli esseri umani.

forse è proprio da questo che non si possono creare insieme completi, o detto più volgarmente privi di incongruenze e paradossi: proprio perchè il tutto si basa su questo principio logico che a sua volta si basa sulla logica umana, probabilmente non abbastanza evoluta.

Non contraddittorietà, completezza e decidibilità sono proprietà strutturali delle singole teorie al primo ordine, e non hanno niente a che vedere col modo in cui gli uomini ragionano.
In particolare, una teoria al primo ordine che sia non contraddittoria, ricorsivamente assiomatizzabile, e in grado di rappresentare le funzioni ricorsive, è necessariamente incompleta e non decidibile per via ricorsiva: e questo, indipendentemente dallo stato dell'evoluzione della logica umana.

A proposito: l'aritmetica di Presburger è completa e non contraddittoria.

basti pensare alla definizione di insieme: una classe per la quale esiste una legge di natura qualsiasi che consente di sapere se un elemento appartiene a quella classe o no. C'è un famoso paradosso a proposito, ovvero l'insieme che contiene tutti gli insiemi: definita questa precisa legge, questo insieme, in quanto tale, dovrebbe essere contenuto in se stesso, quindi dovrebbe esistere un altro insieme che contiene tutti gli insiemi più quello definito e così via, all'infinito...

Al di là del fatto che come la metti tu è detta piuttosto male (confusione tra appartenenza e inclusione), va detto che è la definizione ingenua di insieme ad avere questo problema.
Il motivo è che il principio per cui "data una proprietà P, la collezione di tutti gli oggetti che soddisfano P è un insieme" è troppo potente per non portare a contraddizioni.
La cosa viene messa a posto nella teoria degli insiemi di Zermelo-Fraenkel (in breve: ZF), secondo cui, tra le altre cose, "dati un insieme X e una proprietà P, la collezione di tutti gli elementi di X che soddisfano P è un insieme".
Messe così le cose, è un teorema di ZF che nessun insieme è elemento di se stesso, e i vari paradossi di Cantor, Russell ecc. non sussistono.

[casacup]

Ziosilvio sicuro che i numeri naturali esistano indipendentemente da noi esseri umani? e non che sono una nostra astrazione mentale che andiamo poi ad utilizzare nella vita di tutti i giorni?
credo che quando si parli di numeri (in generale) si intenda l'uso di quei concetti logici di quantità che il nostro cervello utilizza per ragionare.
vedo un oggetto (o un insieme di oggetti)? lo utilizzo come unità, e da lì si crea la distinzione tra "uno" e "più di uno". poi, prendendo l'unità come unità di misura, vedo quante unità sono contenute in un dato insieme, e chiamo 1 unità +1 unità = 2 unità e così via.

Per il resto...vorrei pensarci un pò, anche perchè sono un semplice studente universitario neanche di matematica o fisica e te lo dimostra la superficialità con cui ho illustrato quel paradosso (detto da uno che ne capiva, un matematico del quale non ricordo il nome, mica da me sia chiaro).

In ogni caso, premesso che secondo me non è vero che i naturali esistono indipendentemente dagli uomini, credo che l'incompletezza delle teorie sia data dal fatto che la logica umana non è affatto perfetto. e quindi tutto ciò che produce ha dentro di sè dei paradossi e delle contraddizioni...

[Banus]

Originariamente inviato da casacup

Ziosilvio sicuro che i numeri naturali esistano indipendentemente da noi esseri umani? e non che sono una nostra astrazione mentale che andiamo poi ad utilizzare nella vita di tutti i giorni?

Qui si tocca un argomento molto complesso, e del tutto OT
Le definizioni le trovi qui:
http://it.wikipedia.org/wiki/Filosof...ero_platonismo
http://en.wikipedia.org/wiki/Philoso...atical_realism
La posizione espressa da ZioSilvio è essenzialmente quella del platonismo, condivisa da matematici famosi come Gödel e Erdös.

[Ziosilvio]

Originariamente inviato da casacup

Ziosilvio sicuro che i numeri naturali esistano indipendentemente da noi esseri umani?

Sì.
E anche che un albero che cade in una foresta, fa rumore anche se nessuno lo sente.

credo che quando si parli di numeri (in generale) si intenda l'uso di quei concetti logici di quantità che il nostro cervello utilizza per ragionare.
vedo un oggetto (o un insieme di oggetti)? lo utilizzo come unità, e da lì si crea la distinzione tra "uno" e "più di uno". poi, prendendo l'unità come unità di misura, vedo quante unità sono contenute in un dato insieme, e chiamo 1 unità +1 unità = 2 unità e così via.

L'idea è proprio questa: ma si tratta di una scoperta, e non di una invenzione.

vorrei pensarci un pò

Allora ti suggerisco di farlo davanti a un buon libro.
Vai alla biblioteca della tua città e prendi in prestito la "Introduzione alla logica matematica" di Elliott Mendelson, edito da Boringhieri.

credo che l'incompletezza delle teorie sia data dal fatto che la logica umana non è affatto perfetto. e quindi tutto ciò che produce ha dentro di sè dei paradossi e delle contraddizioni

Come ti ho già detto: dipende.
L'aritmetica di Peano è incompleta; quella di Presburger è completa, ma non permette di rappresentare tutte le funzioni ricorsive.

Per inciso: va detto che sul frangente della completezza c'è un po' di confusione.
In Logica matematica, esistono una completezza sintattica, per cui ogni formula ben formata (FBF) è un teorema oppure la negazione di un teorema; ed una completezza semantica, per cui ogni FBF che sia vera in tutti i modelli della teoria, è anche un teorema della teoria.
Kurt Goedel, nel suo famoso Teorema di incompletezza, dimostrò che l'aritmetica di Peano, se è consistente, allora è sintatticamente incompleta. (Nota: a partire da una contraddizione si può dimostrare qualsiasi cosa, quindi ogni teoria inconsistente è completa.)
Lo stesso Goedel, però, soltanto l'anno prima aveva dimostrato la completezza semantica del calcolo predicativo al primo ordine, e quindi di tutte le teorie al primo ordine. (Nota: il calcolo predicativo al secondo ordine è semanticamente incompleto.)
In realtà, di solito "incompletezza" sottintende "sintattica", e si preferisce parlare di "adeguatezza" invece che di "completezza semantica".

[lowenz]

Oh, bello

Queste teorie sostengono che il pensiero matematico è un prodotto naturale dell'apparato cognitivo umano che si trova nel nostro universo fisico. Per esempio il concetto astratto di numero deriva dall'esperienza del contare oggetti discreti. Si sostiene anche che la matematica non è universale e non possiede una sua esistenza in senso reale, al di fuori del cervello umano. Gli umani costruiscono la matematica, non la scoprono.

Condivido

[casacup]

Originariamente inviato da Morkar Karamat

Continuo l'OT di Banus

La posizione che mi sento di condividere, seppur ad un'analisi molto superficiale, è la seguente:

Teorie della mente incorporata

Queste teorie sostengono che il pensiero matematico è un prodotto naturale dell'apparato cognitivo umano che si trova nel nostro universo fisico. Per esempio il concetto astratto di numero deriva dall'esperienza del contare oggetti discreti. Si sostiene anche che la matematica non è universale e non possiede una sua esistenza in senso reale, al di fuori del cervello umano. Gli umani costruiscono la matematica, non la scoprono.

L'universo fisico viene quindi visto come il fondamento ultimo della matematica; esso ha guidato l'evoluzione del cervello e successivamente ha determinato quali questioni questo cervello considera degne di investigazione. Tuttavia la mente umana non avanza pretese sulla "realtà" o sugli approcci alla realtà costruita mediante la matematica. Se un costrutto come l'identità di Eulero, \,e^{i \pi} + 1 = 0 \, è "vero", è tale in quanto mappa della mente umana e della cognizione, non in quanto mappa di qualcosa che la mente è in grado di "vedere".

Si spiega quindi facilmente l'efficacia della matematica: questa disciplina è stata costruita dal cervello al fine di costituire uno strumento efficace in questo nostro universo.

La trattazione più accessibile, famosa e infamata di questa prospettiva è Where Mathematics Comes From (Da dove proviene la matematica) di George Lakoff e Rafael E. Núñez. Questo libro è stato pubblicato per la prima volta nel 2000 e dovrebbe essere tuttora una delle sole trattazioni di questa prospettiva. Per saperne di più sulla scienza che ha ispirato questa prospettiva, vedi Scienza cognitiva della matematica.

mi piace molto questo punto di vista, dato che mi sembra una definizione molto più completa rispetto alla mia ma che comunque si basa sullo stesso principio... ovvero la matematica ce la facciamo noi, con tutti i pregi ed i limiti del fatto