Everything should be made as simple as possible, but not one bit simpler.
A. Einstein
durante le esercitazioni di analisi I ho notato uno strano fenomeno. appena si spiega ai ragazzi che esiste una tecnica chiamata "dimostrazione per assurdo", essi ne diventano immediatamente dipendenti, e dimostrano per assurdo anche proposizioni che possono essere dimostrate direttamente. peggio: ogni tanto affermano di aver dimostrato per assurdo cose che hanno dimostrato direttamente.
chiarisco il concetto: devono dimostrare la proposizione A. cominiciano la dimostrazione col dire: supponiamo che A sia falsa. poi dimostrano direttamente che A e´ vera. concludono quindi: cio´ contraddice la mia ipotesi che A fosse falsa, e quindi ho dimostrato per assurdo che A e´ vera. divertente, no?
anche matematici piu´ anziani non sono esenti da questo difetto. come viene dimostrato il teorema dei numeri primi, classicamente? per assurdo! supponiamo ce ne siamo n, ne costruisco un n+1esimo, e quindi mi ero sbagliato. si vede pero´ che questa e´ una dimostrazione per induzione, e non per assurdo.
Proposizione
Per ogni n numero naturale esistono p(1),...,p(n) distinti numeri primi.
Dimostrazione
Lo si dimostra per induzione completa su N. Per n=1 e´ evidentemente vero, dato che 2 e´ primo. Siano p(1),...,p(n) primi. Si definisca q=[p(1) x p(2) x...x p(n)]+1. Si consideri la (univoca) fattorizzazione di q=q(1)^a(1) x...x q(m)^a^(m). Per costruzione nessuno dei q(i) e´ in {p(1),...,p(n)}. Si definisca p(n+1):=q(1). Adesso p(1),...,p(n+1) sono primi distinti, e cosi´ il passo induttivo e´ provato, qed.
Iscriviti a:
Commenti sul post (Atom)
9 commenti:
Secondo me in questo caso si tratta di una sottigliezza. Se il tuo procedimento fosse stato un meccanismo per trovare *il successivo* numero primo dati i *primi n numeri primi*, non avrei esitato a darti ragione. Ma siccome la dimostrazione si puo' effettuare in una volta sola (senza spezzarla in una base e poi un passo d'induzione) e siccome la stessa proposizione puo' essere riformulata senza alcun riferimento all'n generico tipico del passo d'induzione (i numeri primi sono infiniti), non vedrei un grande errore nel chiamare tale dimostrazione "per assurdo".
Anzi, io girerei la frittata e offrirei il tuo esempio prorpio per mostrare che il concetto di "dimostrazione per assurdo" e di "dimostrazione per induzione" possono non essere cosi' rigidamente definiti...
non e´ cosi´ tanto una sottigliezza. il problema e´ capire cosa vuol dire che i numeri primi sono infiniti. in pratica e´ necessario trovare una applicazione ingettiva dei numeri naturali nei numeri primi. e per fare questo e´ evidentemente necessario procedere per induzione completa su N.
a parte questo, sono d´accordo sul fatto che la differenza fra le varie tecniche di dimostrazione e´ abbastanza sfumata.
Ci sono molti modi "pratici" per dire che un insieme e' infinito, quello della iniezione con N e' solo uno dei tanti. Ad esempio dimostrando una biiezione con una sua parte propria. O, per un insieme ordinabile come quello dei numeri primi, si puo' fare ad esempio dimostrando che non ammette un estremo superiore. E il tuo "passo d'induzione" puo' facilmente essere modificato (io la dimostrazione "classica" la conoscevo proprio cosi'...) perche' dimostri l'assurdo del pretendere un estremo superiore.
Senza alcun carattere induttivo.
non sono d´accordo. come funzionerebbe una dimostrazione per assurdo per l´estremo superiore? immagino che l´idea sarebbe quella di prendere p1 < p2 <...< pn = a e sfruttare il fatto che pixp2x...xpn + 1=:an e´ maggiore di a. il problema e´ che a non e´ necessariamente primo.
quello che puoi notare e´ che i fattori primi di an sono tutti maggiori di a (per evidenti motivi). pero´ questa e´ di nuovo una dimostrazione costruttiva e non per assurdo.
in questo caso stai infatti dimostrando, costruendolo, che per ogni n esiste un primo strettamente maggiore di n. pero´ questa e´ una formulazione equivalente della mia precedente dimostrazione diretta.
1+Prod_i(p_i) e' primo se i p_i considerati sono *tutti* i primi minori del(l'assunto per assurdo) massimo numero primo.
Se modifichi la dimostrazione introducendo il numero n di numeri primi "a un certo stadio" (petizio principii del fatto che sia una dimostrazione induttiva) e mostrando che per ogni ennupla di numeri primi puoi costruire un enne+1-upla di numeri primi, riuscirai sempre a pretendere che la dimostrazione si dica "induttiva".
Ma io non nego che sia cosi'. Dico solo che e' possibile fare una dimostrazione che, ragionevolmente (non "assolutamente", perche' come avevamo gia' convenuto il carattere di una dimostrazione e' un concetto sfumato) essere considerata "per assurdo".
Ma ci stiamo pian piano spostando a discutere del sesso degli angeli... :)
Una domanda da pirla: ma se sottraessi 1 invece di sommare, otterrei comunque un primo diverso?Immagino di no, altrimenti avrei dimostrato che esistono infinite coppie di primi che differiscono di 2.
abbi pazienza, ho vaghi ricordi al riguardo, cancella pure se è una minchiata troppo grossa :)
non so bene che succede se si sottrae uno, a dire il vero. se si aggiunge uno e´ evidente che il numero ottenuto e´ congruente modulo 1 a tutti i primi p(1) fino a p(n). mi verrebbe da affermare che allora sottraendo uno si ottenga la congruenza modulo p(i)-1, cosa che pero´ crea problemi, dato che in quella lista di numeri primi c´e´ il 2 per passo induttivo. di piu´ non mi viene in mente cosi´ su due piedi, e sono un po´ di fretta, per cui...
Intendevi l'inverso: congruente a 1 modulo ciascuno dei primi p(i).
La congruenza a -1 è meno "utile" perchè siamo interessati alla divisibilità.
Un controesempio concreto può aiutare a chiarire: 2*3*5*7-1=209 che non è primo (209=19*11). Il punto, come si intuisce, è che possono esserci numeri primi fra il massimo numero primo considerato e il numero ottenuto dalla produttoria.
Del resto l'infinità del numeri primi gemelli è ancora una congettura (questo solo per dire che il problema è "difficile"):
Wikipedia: congettura dei numeri primi gemelli
man lernt nie aus...
Posta un commento