Ma noi... abbiamo qualcosa in comune?

[edriv]

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.

[moebius]

Ok, visto il possibile sproloquio scritto nell'altro, stampo questo...

[edriv]

Non sprecar carta, se quello era ovvio, questo è una cavolata pazzesca!

[moebius]

Troppo tardi
Tanto paga il dipartimento

[Hammond]

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.

[dimpim]

Si intende n insiemi non vuoti, giusto?

[fph]

Si intende n insiemi non vuoti, giusto?

Se c'è un insieme vuoto, le ipotesi non sono mai soddisfatte e il teorema è vero "a vuoto".

[Marco]

Il caso n+2 mi torna perfettamente. Non mi torna invece questo:

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.

EDIT: No. Ho capito. Ora mi torna.

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. []