Un bel problemino di teoria combinatoria:
<BR>
<BR>Sia A un insieme finito, dia P l\'insieme delle parti di A. Sia f : P --> P tale che
<BR>a s.ins. b ==> f(a) s.ins. f(b) (monotona) (s.ins. = sottoinsieme). Dimostrare che esiste un g in P tale che g = f(g).
<BR>
<BR>(Questa e\' una versione semplificata del teorema di Tarski per i punti fissi).<BR><BR>[ Questo Messaggio è stato Modificato da: Catraga il 06-02-2004 15:10 ]
Tarski
Moderatore: tutor
Introduciamo in P(A) (l\'insieme delle parti di A) la seguente relazione binaria:
<BR>per ogni X,Y€P(A), poniamo \"X ≤ Y\" se \"X è un sottoinsieme di Y\"; in particolare, se \"X è propriamente contenuto in Y\", scriviamo più semplicemente \"X < Y\". Si può dimostrare che la relazione \"≤\" così definita induce in P(A) un ordinamento parziale dei suoi elementi.
<BR>
<BR>Ciò premesso, supponiamo quindi per assurdo che la tesi non sia rispondente a verità; ovvero ammettiamo che, comunque scelto un X€P(A): f(X) != X. Per ipotesi, A è un insieme finito. Diciamo n la sua cardinalità (n€N). Allora, anche
<BR>P(A) è un insieme finito, e in particolare: card[P(n)] = 2<sup>n</sup> (si veda in proposito la dimostrazione di questo fatto fornita, fra gli altri, da AleX_ZeTa nel topic aperto da 10/81 sotto la voce \"1.PATTERN\"). Ad esser franchi, quest\'ultimo risultato ci servirà a ben poco nel prosieguo, ma in ogni caso ho inteso richiamarlo perché così ve l\'andiate a rivedere!
<BR>
<BR>Bene, ciò stabilito, introduciamo la successione {x<sub>n</sub>} a valori in P(A) costruita ricorsivamente ponendo x<sub>1</sub> := A ed x<sub>n+1</sub> := f(x<sub>n</sub>), per ogni n€N<sub>0</sub>.
<BR>
<BR>Intendiamo provare che {x<sub>n</sub>} è una successione monotòna (strettamente) decrescente in P(A) rispetto alla relazione d\'ordine parziale \"≤\"; ovvero che, per ogni n€N<sub>0</sub>: x<sub>n+1</sub> < x<sub>n</sub>. Ora, per ogni X€P(A): X ≤ A, poiché (per definizione) ogni elemento di P(A) è un sottoinsieme di A; dunque, nello specifico: x<sub>2</sub> := f(x<sub>1</sub>) =
<BR>f(A) < A =: x<sub>1</sub>, poiché f(-) è una funzione di P(A) in P(A) priva di punti fissi per contraddizione della tesi. Del resto, se si ammette per valida la proprietà di monotòna decrescenza della f(-) per un generico n€N<sub>0</sub> e si sfrutta la proprietà di monotonia cui d\'altro canto soggiace (per ipotesi) questa medesima funzione, è immediato allora concludere (per via induttiva) che, effettivamente: x<sub>n+1</sub> < x<sub>n</sub>, per ogni n€N<sub>0</sub>.
<BR>
<BR>Di qui l\'assurdo, pur di considerare che una sequenza \"decrescente\" di sottoinsiemi di A può contenere al più un numero finito di elementi di P(A), pari ad n+1 nel <!-- BBCode Start --><I>migliore</I><!-- BBCode End --> dei casi possibili. L\'assurdo, nato dall\'aver supposto che f(-) non fosse dotata di alcun punto fisso in P(A), induce di converso ad affermare la generale consistenza dell\'asserto, q.e.d.<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 06-02-2004 20:41 ]
<BR>per ogni X,Y€P(A), poniamo \"X ≤ Y\" se \"X è un sottoinsieme di Y\"; in particolare, se \"X è propriamente contenuto in Y\", scriviamo più semplicemente \"X < Y\". Si può dimostrare che la relazione \"≤\" così definita induce in P(A) un ordinamento parziale dei suoi elementi.
<BR>
<BR>Ciò premesso, supponiamo quindi per assurdo che la tesi non sia rispondente a verità; ovvero ammettiamo che, comunque scelto un X€P(A): f(X) != X. Per ipotesi, A è un insieme finito. Diciamo n la sua cardinalità (n€N). Allora, anche
<BR>P(A) è un insieme finito, e in particolare: card[P(n)] = 2<sup>n</sup> (si veda in proposito la dimostrazione di questo fatto fornita, fra gli altri, da AleX_ZeTa nel topic aperto da 10/81 sotto la voce \"1.PATTERN\"). Ad esser franchi, quest\'ultimo risultato ci servirà a ben poco nel prosieguo, ma in ogni caso ho inteso richiamarlo perché così ve l\'andiate a rivedere!
<BR>
<BR>Bene, ciò stabilito, introduciamo la successione {x<sub>n</sub>} a valori in P(A) costruita ricorsivamente ponendo x<sub>1</sub> := A ed x<sub>n+1</sub> := f(x<sub>n</sub>), per ogni n€N<sub>0</sub>.
<BR>
<BR>Intendiamo provare che {x<sub>n</sub>} è una successione monotòna (strettamente) decrescente in P(A) rispetto alla relazione d\'ordine parziale \"≤\"; ovvero che, per ogni n€N<sub>0</sub>: x<sub>n+1</sub> < x<sub>n</sub>. Ora, per ogni X€P(A): X ≤ A, poiché (per definizione) ogni elemento di P(A) è un sottoinsieme di A; dunque, nello specifico: x<sub>2</sub> := f(x<sub>1</sub>) =
<BR>f(A) < A =: x<sub>1</sub>, poiché f(-) è una funzione di P(A) in P(A) priva di punti fissi per contraddizione della tesi. Del resto, se si ammette per valida la proprietà di monotòna decrescenza della f(-) per un generico n€N<sub>0</sub> e si sfrutta la proprietà di monotonia cui d\'altro canto soggiace (per ipotesi) questa medesima funzione, è immediato allora concludere (per via induttiva) che, effettivamente: x<sub>n+1</sub> < x<sub>n</sub>, per ogni n€N<sub>0</sub>.
<BR>
<BR>Di qui l\'assurdo, pur di considerare che una sequenza \"decrescente\" di sottoinsiemi di A può contenere al più un numero finito di elementi di P(A), pari ad n+1 nel <!-- BBCode Start --><I>migliore</I><!-- BBCode End --> dei casi possibili. L\'assurdo, nato dall\'aver supposto che f(-) non fosse dotata di alcun punto fisso in P(A), induce di converso ad affermare la generale consistenza dell\'asserto, q.e.d.<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 06-02-2004 20:41 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
Catraga, santi numi! Dirichlet e il suo <!-- BBCode Start --><I>boxing-in</I><!-- BBCode End --> saranno pure carucci, ma personalmente prediligo il costruttivismo... come dire... è più ingegneristico!?! Se Hecht e Nielsen avessero fornito una dimostrazione costruttiva del teorema di Kolmogorov, beh (nel bene o nel male) probabilmente <!-- BBCode Start --><I>matrix</I><!-- BBCode End --> sarebbe stato già oggi una realtà, altro che finzione cinematrogafica... ed io ne sarei stato di certo il pappa digitale!!! <IMG SRC="images/forum/icons/icon_razz.gif"><BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 09-02-2004 19:06 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
Allora, il problema di Tarski e\' risolto in poco piu\' di una facciata del Pacific Journal of Mathematics nella sua versione piu\' generale (1955). Ok, il metodo costruttivo e\' interessante, ma devi considerare che nella versione generale dove (K,&) e\' un qualsiasi insieme ordinato non risulta cosi\' facile. Infatti mi sembra che tu dia per scontato l\'essere poset completo dell\'insieme delle parti...
Aladin to the genius: "Oh, great spirit! My desire is that you do not fullfill my desire"
The genius was enlightened.
The genius was enlightened.
<!-- 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 2004-02-10 09:00, Catraga wrote:
<BR>Allora, il problema di Tarski e\' risolto in poco piu\' di una facciata del Pacific Journal of Mathematics nella sua versione piu\' generale (1955). Ok, il metodo costruttivo e\' interessante, ma devi considerare che nella versione generale dove (K,&) e\' un qualsiasi insieme ordinato non risulta cosi\' facile. Infatti <!-- BBCode Start --><B>mi sembra che tu dia per scontato l\'essere poset completo dell\'insieme delle parti</B><!-- BBCode End -->...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ma scusa... a cosa è riferito? Alla mia dimostrazione? Beh, non capisco allora dove stia il problema!!! Perdona la mia pochezza... ma non mi è chiaro il senso della tua osservazione! Magari, se volessi essermi prodigo di maggiori dettagli...<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 10-02-2004 16:49 ]
<BR>On 2004-02-10 09:00, Catraga wrote:
<BR>Allora, il problema di Tarski e\' risolto in poco piu\' di una facciata del Pacific Journal of Mathematics nella sua versione piu\' generale (1955). Ok, il metodo costruttivo e\' interessante, ma devi considerare che nella versione generale dove (K,&) e\' un qualsiasi insieme ordinato non risulta cosi\' facile. Infatti <!-- BBCode Start --><B>mi sembra che tu dia per scontato l\'essere poset completo dell\'insieme delle parti</B><!-- BBCode End -->...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ma scusa... a cosa è riferito? Alla mia dimostrazione? Beh, non capisco allora dove stia il problema!!! Perdona la mia pochezza... ma non mi è chiaro il senso della tua osservazione! Magari, se volessi essermi prodigo di maggiori dettagli...<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 10-02-2004 16:49 ]
<center>Le cose cambiano... e i sentimenti pure...</center>