OliForum Matematico

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.

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

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

Troppo tardi
Tanto paga il dipartimento

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.

Si intende n insiemi non vuoti, giusto?

dimpim ha scritto:Si intende n insiemi non vuoti, giusto?

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

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

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.

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