Abbiamo un insieme di almeno n+1 insiemi con al più n elementi ciascuno.
Comunque ne prendiamo n+1, questi hanno un elemento in comune.
Dimostrare che tutti gli insiemi hanno un elemento in comune.
Ma noi... abbiamo qualcosa in comune?
Se gli insiemi sono n+1 è banale.
Se sono di più voglio dimostrare che, comunque presi n+2 insiemi, questi hanno un elemento in comune.
Fatto questo ho finito: mi ritrovo nelle ipotesi iniziali con n+1 al posto di n, dunque posso dimostrare che anche n+3 insiemi hanno sempre un elemento in comune, e così via fino alla fine.
Per dimostrare quello che mi serve prendo n+2 insiemi che chiamo $ S_1, S_2, ... , S_{n+2} $;
considero ad esempio l'ultimo: per ipotesi contiene
$ ~c_1 $ in comune con $ ~S_2, S_3, ... , S_{n+1} $
$ ~c_2 $ in comune con $ ~S_1, S_3, ... , S_{n+1} $
...
$ ~c_{n+1} $ in comune con $ ~S_1, S_2, ... , S_n $
ma poiché non ha più di n elementi, almeno due tra i $ ~c_i $ sono lo stesso elemento: è evidente che quel particolare elemento è comune a tutti gli n+2 insiemi.
Se sono di più voglio dimostrare che, comunque presi n+2 insiemi, questi hanno un elemento in comune.
Fatto questo ho finito: mi ritrovo nelle ipotesi iniziali con n+1 al posto di n, dunque posso dimostrare che anche n+3 insiemi hanno sempre un elemento in comune, e così via fino alla fine.
Per dimostrare quello che mi serve prendo n+2 insiemi che chiamo $ S_1, S_2, ... , S_{n+2} $;
considero ad esempio l'ultimo: per ipotesi contiene
$ ~c_1 $ in comune con $ ~S_2, S_3, ... , S_{n+1} $
$ ~c_2 $ in comune con $ ~S_1, S_3, ... , S_{n+1} $
...
$ ~c_{n+1} $ in comune con $ ~S_1, S_2, ... , S_n $
ma poiché non ha più di n elementi, almeno due tra i $ ~c_i $ sono lo stesso elemento: è evidente che quel particolare elemento è comune a tutti gli n+2 insiemi.
Come non detto...
Il caso n+2 mi torna perfettamente. Non mi torna invece questo:
Dimostrazione alternativa, non per induzione:
Chiamo gli insiemi $ A_1, A_2, \dots A_m $, con $ m \geqslant n+1 $.
Per ogni $ i = 1, \dots, m $ definisco $ B_i = \bigcap_{k=1}^i A_k $, l'intersezione dei primi $ i $ insiemi.
La successione dei $ B_i $ è decrescente (in senso largo) e il primo elemento ha al max $ n $ elementi. Considero ora la successione dei $ B_i $, a cui ho cancellato gli elementi ripetuti. Tale sottosuccessione può avere al massimo $ n+1 $ termini, perché tante sono le cardinalità distinte possibili $ \leqslant n $.
Considero ora gli insiemi $ A_i $ quando $ i $ si trova in corrispondenza di un $ B_i $ in cui cambia la cardianlità. Detto in altri termini, considero solo gli $ A_i $ t.c. $ B_i \subsetneq B_{i-1} $ [oltre ad $ A_1 $] Per quanto detto sopra, tali insiemi sono al massimo $ n+1 $ e quindi, per ipotesi, la loro intersezione è non vuota. Ma è facile vedere che la loro intersezione è, per costruzione, $ B_m $. Il fatto che $ B_m $ non sia vuoto è la tesi. []
EDIT: No. Ho capito. Ora mi torna.Hammond ha scritto:Fatto questo ho finito: mi ritrovo nelle ipotesi iniziali con n+1 al posto di n, dunque posso dimostrare che anche n+3 insiemi hanno sempre un elemento in comune, e così via fino alla fine.
Dimostrazione alternativa, non per induzione:
Chiamo gli insiemi $ A_1, A_2, \dots A_m $, con $ m \geqslant n+1 $.
Per ogni $ i = 1, \dots, m $ definisco $ B_i = \bigcap_{k=1}^i A_k $, l'intersezione dei primi $ i $ insiemi.
La successione dei $ B_i $ è decrescente (in senso largo) e il primo elemento ha al max $ n $ elementi. Considero ora la successione dei $ B_i $, a cui ho cancellato gli elementi ripetuti. Tale sottosuccessione può avere al massimo $ n+1 $ termini, perché tante sono le cardinalità distinte possibili $ \leqslant n $.
Considero ora gli insiemi $ A_i $ quando $ i $ si trova in corrispondenza di un $ B_i $ in cui cambia la cardianlità. Detto in altri termini, considero solo gli $ A_i $ t.c. $ B_i \subsetneq B_{i-1} $ [oltre ad $ A_1 $] Per quanto detto sopra, tali insiemi sono al massimo $ n+1 $ e quindi, per ipotesi, la loro intersezione è non vuota. Ma è facile vedere che la loro intersezione è, per costruzione, $ B_m $. Il fatto che $ B_m $ non sia vuoto è la tesi. []
[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."