Questo problema forse sembrerà semplice, ma mi è sembrato interessante, per cui se qualche esperto problem solver riderà di me per l\'ovvietàdella tesi giuro che non si è fatto apposta...
<BR>Dato un sottoinsieme A di Z, composto da un numero finito di elementi, dimostrare che A possiede un massimo e un minimo.
<BR>
<BR>P.S. Ho provato a cercare nei forum vecchi se ci fosse qualcosa del genere, ma non ho trovato niente. Se mi sono sbagliato, scusatemi... <IMG SRC="images/forum/icons/icon_cool.gif"> [addsig]
[N] Massimi e minimi di insiemi finiti
Moderatore: tutor
-
MindFlyer
Fallo per induzione.
<BR>(che non è un\'infrazione calcistica, e nemmeno un aggeggio erotico)
<BR>
<BR>Comunque, come hai detto tu, è una proposizione ovvia, ed in àmbito olimpico non viene dimostrata. Semplicemente, la si dà per scontata.
<BR>Se invece vuoi sentirti tutta la storiella dei legami di questo teorema con l\'induzione e la discesa infinita, hai sbagliato forum.
<BR>(che non è un\'infrazione calcistica, e nemmeno un aggeggio erotico)
<BR>
<BR>Comunque, come hai detto tu, è una proposizione ovvia, ed in àmbito olimpico non viene dimostrata. Semplicemente, la si dà per scontata.
<BR>Se invece vuoi sentirti tutta la storiella dei legami di questo teorema con l\'induzione e la discesa infinita, hai sbagliato forum.
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-03 14:47, MindFlyer wrote:
<BR>Se invece vuoi sentirti tutta la storiella dei legami di questo teorema con l\'induzione e la discesa infinita, hai sbagliato forum.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Dissento da M/Flyer.
<BR>
<BR>Questo, IMHO, è il posto azzeccato anche per questi quesiti, che hanno tante belle dimostrazioni olympic-style. E già che ci siamo, perché non aggiungere ...?
<BR>
<BR>Es.2 (Principio del Buon Or[d]inamento)
<BR>Ogni sott\'insieme <!-- BBCode Start --><B>non vuoto</B><!-- BBCode End --> di N (non necessariamente finito, si badi) ammette minimo.
<BR>
<BR>N.B. L\'ipotesi \"non vuoto\" serve anche per l\'esercizio originario di Sisifo.
<BR>
<BR>Ciao. M.
<BR>On 2005-01-03 14:47, MindFlyer wrote:
<BR>Se invece vuoi sentirti tutta la storiella dei legami di questo teorema con l\'induzione e la discesa infinita, hai sbagliato forum.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Dissento da M/Flyer.
<BR>
<BR>Questo, IMHO, è il posto azzeccato anche per questi quesiti, che hanno tante belle dimostrazioni olympic-style. E già che ci siamo, perché non aggiungere ...?
<BR>
<BR>Es.2 (Principio del Buon Or[d]inamento)
<BR>Ogni sott\'insieme <!-- BBCode Start --><B>non vuoto</B><!-- BBCode End --> di N (non necessariamente finito, si badi) ammette minimo.
<BR>
<BR>N.B. L\'ipotesi \"non vuoto\" serve anche per l\'esercizio originario di Sisifo.
<BR>
<BR>Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
MindFlyer
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-03 15:11, marco wrote:
<BR>Dissento da M/Flyer.
<BR>Questo, IMHO, è il posto azzeccato anche per questi quesiti, che hanno tante belle dimostrazioni olympic-style.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Mah, per me c\'è il rischio di andarsi ad impantanare in questioni logico-fondazionali del tipo \"se prendo l\'induzione come assioma, allora deduco il minimo intero, e viceversa\", e checché ne dicano alcuni, questi non sono argomenti olimpici, e non enfatizzano nemmeno un modo di ragionare olimpico.
<BR>On 2005-01-03 15:11, marco wrote:
<BR>Dissento da M/Flyer.
<BR>Questo, IMHO, è il posto azzeccato anche per questi quesiti, che hanno tante belle dimostrazioni olympic-style.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Mah, per me c\'è il rischio di andarsi ad impantanare in questioni logico-fondazionali del tipo \"se prendo l\'induzione come assioma, allora deduco il minimo intero, e viceversa\", e checché ne dicano alcuni, questi non sono argomenti olimpici, e non enfatizzano nemmeno un modo di ragionare olimpico.
Premesso che io la soluzione la conosco, volevo solo presentare un problema che <B>a me</B> era sembrato non così ovvio <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> .
<BR>Capisco che voi siate abituati a problemi ben più complessi, ma non smontatemi così dicendo subito la soluzione <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> .
<BR>
<BR>P.S. sono veramente appassionato di questioni logiche, ma non pensavo che centrassero con la soluzione di questo povero piccolo quesito...<BR><BR>[ Questo Messaggio è stato Modificato da: Sisifo il 03-01-2005 19:39 ]
<BR>Capisco che voi siate abituati a problemi ben più complessi, ma non smontatemi così dicendo subito la soluzione <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> .
<BR>
<BR>P.S. sono veramente appassionato di questioni logiche, ma non pensavo che centrassero con la soluzione di questo povero piccolo quesito...<BR><BR>[ Questo Messaggio è stato Modificato da: Sisifo il 03-01-2005 19:39 ]
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
-
MindFlyer
Beh, Sisifino, adesso ti dico tutto, visto che sei interessato e che ho un pochino di tempo, e stamattina mi sono svegliato di buon umore (sono allegro senza motivo, come i malati mentali terminali).
<BR>
<BR>Dunque, quello che ho detto sulla banalità del problema non era volto a \"smontarlo\", intendevo dire che se in una dimostrazione olimpica usi quel teorema, non devi curarti di dimostrarlo perché molto intuitivo. Addirittura, in alcuni casi potresti usarlo senza nemmeno citarlo esplicitamente.
<BR>
<BR>L\'intuitività deriva dal fatto che, se l\'insieme è finito, allora è limitato, quindi esiste un intero M maggiore di tutti quelli nell\'insieme. Considerando nell\'ordine M-1, M-2, M-3, etc, in un numero finito di passi arriverai ad un elemento dell\'insieme (perché è non vuoto), che è appunto il suo massimo. Discorso analogo per il minimo.
<BR>
<BR>Tutto questo si può formalizzare per induzione, ed il motivo per cui ho \"snobbato\" il problema è che non è una pratica olimpicamente utile andare a dimostrare formalmente una proposizione della cui vertà si ha una perfetta intuizione. Comunque la dimostrazione è per induzione sul numero di elementi: per 1 elemento è ovvio, perché è lui stesso sia minimo che massimo. Consideriamo ora un insieme di n>1 elementi, e togliamone uno quelunque, che chiamiamo x. Ci resta un nuovo insieme con n-1 elementi, che per ipotesi induttiva ha minimo e massimo m e M, con m<=M. Ora, se x<m, allora x è il nuovo minimo, se x>M è il nuovo massimo, altrimenti m e M continuano ad essere minimo e massimo.
<BR>
<BR>Nota che questa dimostrazione vale per tutti i sottoinsiemi finiti di Z, e quindi di N. Nota anche che per N continua ad essere vera l\'esistenza del minimo elemento per sottoinsiemi non vuoti sia finiti che infiniti. E questo è il principio del minimo intero o di buon ordinamento. Si dimostra che è equivalente ad un mucchio di roba, come il principio di induzione e la discesa infinita (ovvero: non esiste una successione strettamente decrescente a valori in N). Questo significa che se prendi gli assiomi di Peano per i naturali, puoi sostituire il principio di induzione con uno qualunque di questi altri, senza cambiare i modelli della teoria. Ovvero, l\'unico modello della teoria di Peano continua ad essere N (a meno di isomorfismi), sia che consideri l\'uno o l\'altro assioma al posto dell\'induzione.
<BR>
<BR>D\'altro canto, i principio del minimo intero su sottoinsiemi finiti di N (la prima \"metà\" del tuo teorema) è equivalente all\'induzione su segmenti iniziali di N, ovvero: sia P(x) un predicato, sia vero P(0) e valga l\'implicazione P(n-1) --> P(n) per n<M, con M fissato. Allora P(x) è vero per tutti i naturali da 0 a M. Puoi divertirti a dimostrare anche questo.
<BR>
<BR>Tutto questo è vero nella logica del 2° ordine: puoi esprimere il principio d\'induzione quantificando su tutte le proposizioni, ed hai una teoria che caratterizza esattamente l\'insieme che vuoi descrivere, ovvero N con +, * e < o roba isomorfa. Purtroppo, l\'impossibilità di definire un sistema di regole d\'inferenza che dimostri teoremi nell\'aritmetica di Peano del 2° ordine (impossibilità dovuta alla non ricorsiva enumerabilità dell\'insieme delle proposizioni vere in N), spinge ad abbandonare la logica del 2° ordine, in favore di quella del 1° ordine, meno espressiva. Insomma, l\'assioma di induzione si trasforma in un insieme infinito di assiomi, ognuno riferito ad una proposizione esprimibile con formule del 1° ordine (quindi senza dover quantificare su tutte le proposizioni). Ovviamente si perde qualcosa, perché non tutte le proposizioni sono esprimibili con formule del 1° ordine, e da qui scaturiscono cose carine come la non unicità del modello (cioè la presenza di modelli non standard, non isomorfi a N), e l\'incompletezza di Goedel. Rispetto all\'ordine, esiste solo un modello di Peano non standard che sia anche numerabile, che è quello con una copia iniziale di N seguita da tante copie di Z ordinate come gli elementi di Q. Riguardo alle operazioni + e *, si dimostra invece che nessuna di esse è una funzione calcolabile sui modelli non standard, ovvero non esiste un programma che dati 2 elementi del modello, calcoli la loro somma o il loro prodotto. Cosa che, ovviamente, si può fare nel modello standard N.
<BR>
<BR>Dunque, quello che ho detto sulla banalità del problema non era volto a \"smontarlo\", intendevo dire che se in una dimostrazione olimpica usi quel teorema, non devi curarti di dimostrarlo perché molto intuitivo. Addirittura, in alcuni casi potresti usarlo senza nemmeno citarlo esplicitamente.
<BR>
<BR>L\'intuitività deriva dal fatto che, se l\'insieme è finito, allora è limitato, quindi esiste un intero M maggiore di tutti quelli nell\'insieme. Considerando nell\'ordine M-1, M-2, M-3, etc, in un numero finito di passi arriverai ad un elemento dell\'insieme (perché è non vuoto), che è appunto il suo massimo. Discorso analogo per il minimo.
<BR>
<BR>Tutto questo si può formalizzare per induzione, ed il motivo per cui ho \"snobbato\" il problema è che non è una pratica olimpicamente utile andare a dimostrare formalmente una proposizione della cui vertà si ha una perfetta intuizione. Comunque la dimostrazione è per induzione sul numero di elementi: per 1 elemento è ovvio, perché è lui stesso sia minimo che massimo. Consideriamo ora un insieme di n>1 elementi, e togliamone uno quelunque, che chiamiamo x. Ci resta un nuovo insieme con n-1 elementi, che per ipotesi induttiva ha minimo e massimo m e M, con m<=M. Ora, se x<m, allora x è il nuovo minimo, se x>M è il nuovo massimo, altrimenti m e M continuano ad essere minimo e massimo.
<BR>
<BR>Nota che questa dimostrazione vale per tutti i sottoinsiemi finiti di Z, e quindi di N. Nota anche che per N continua ad essere vera l\'esistenza del minimo elemento per sottoinsiemi non vuoti sia finiti che infiniti. E questo è il principio del minimo intero o di buon ordinamento. Si dimostra che è equivalente ad un mucchio di roba, come il principio di induzione e la discesa infinita (ovvero: non esiste una successione strettamente decrescente a valori in N). Questo significa che se prendi gli assiomi di Peano per i naturali, puoi sostituire il principio di induzione con uno qualunque di questi altri, senza cambiare i modelli della teoria. Ovvero, l\'unico modello della teoria di Peano continua ad essere N (a meno di isomorfismi), sia che consideri l\'uno o l\'altro assioma al posto dell\'induzione.
<BR>
<BR>D\'altro canto, i principio del minimo intero su sottoinsiemi finiti di N (la prima \"metà\" del tuo teorema) è equivalente all\'induzione su segmenti iniziali di N, ovvero: sia P(x) un predicato, sia vero P(0) e valga l\'implicazione P(n-1) --> P(n) per n<M, con M fissato. Allora P(x) è vero per tutti i naturali da 0 a M. Puoi divertirti a dimostrare anche questo.
<BR>
<BR>Tutto questo è vero nella logica del 2° ordine: puoi esprimere il principio d\'induzione quantificando su tutte le proposizioni, ed hai una teoria che caratterizza esattamente l\'insieme che vuoi descrivere, ovvero N con +, * e < o roba isomorfa. Purtroppo, l\'impossibilità di definire un sistema di regole d\'inferenza che dimostri teoremi nell\'aritmetica di Peano del 2° ordine (impossibilità dovuta alla non ricorsiva enumerabilità dell\'insieme delle proposizioni vere in N), spinge ad abbandonare la logica del 2° ordine, in favore di quella del 1° ordine, meno espressiva. Insomma, l\'assioma di induzione si trasforma in un insieme infinito di assiomi, ognuno riferito ad una proposizione esprimibile con formule del 1° ordine (quindi senza dover quantificare su tutte le proposizioni). Ovviamente si perde qualcosa, perché non tutte le proposizioni sono esprimibili con formule del 1° ordine, e da qui scaturiscono cose carine come la non unicità del modello (cioè la presenza di modelli non standard, non isomorfi a N), e l\'incompletezza di Goedel. Rispetto all\'ordine, esiste solo un modello di Peano non standard che sia anche numerabile, che è quello con una copia iniziale di N seguita da tante copie di Z ordinate come gli elementi di Q. Riguardo alle operazioni + e *, si dimostra invece che nessuna di esse è una funzione calcolabile sui modelli non standard, ovvero non esiste un programma che dati 2 elementi del modello, calcoli la loro somma o il loro prodotto. Cosa che, ovviamente, si può fare nel modello standard N.