[N] Massimi e minimi di insiemi finiti

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo »

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]
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
MindFlyer

Messaggio da 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.
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

<!-- 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.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
MindFlyer

Messaggio da 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.
Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo »

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 ]
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
MindFlyer

Messaggio da 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.
Bloccato