OliForum Matematico

Sia $ ~ A \subset \mathcal{P}(\mathcal{P}(\mathbb{N})) $ un insieme di sottoinsiemi di $ ~ \mathbb{N} $.
Ora, un insieme $ ~ B \subset \mathbb{N} $ si dice k-saturo se ogni suo sottoinsieme di k elementi appartiene ad A, oppure nessun suo sottoinsieme di k elementi appartiene ad A.

Dimostrare che per ogni n esiste un insieme infinito, k-saturo per ogni $ ~ k \le n $.

Tanto per capirsi... A è fissato a priori giusto?

Sìsì. Per ogni A, per ogni n, esiste un B, per ogni $ ~ k \le n $, per ogni k-sottoinsieme. Questo è l'ordine giusto dei quantificatori. Ho vinto qualcosa?

Si, uno scherzo
(Questa la capiremo in due ma fa niente, era troppo "telefonata" )

Prescindendo dall'elitario humour con cui si e' aperto questo thread, provo a dare una dimostrazione di un risultato ancora piu' bello (a dire il vero, sostanzialmente equivalente..). Si dovrebbe vedere in che modo implica il claim di edriv, chi non capisce perche' chieda pure, anche se forse conviene chiedere a qualcuno che sa spiegarsi meglio di me...

Fatto bellobello (noto anche come teorema di Ramsey-Fogari):

Sia B un insieme di cardinalita' infinita. Sia k(insieme) l'insieme dei sottoinsiemi di k elementi dell'insieme di partenza. Ora, se noi coloriamo k(B) con un numero finito di colori (diciamo n), allora esiste un $ C\subset B $ tale che:

1) $ k(C) $ e' monocromatico

2) $ |C|=\infty $

Agiamo, come al solito, per induzione:

k=1: e' il pigeonhole.

Supponiamo che la tesi sia vera per k, e dimostriamo per k+1.

Scegliamo un elemento di B a caso (chiamiamolo $ b_1 $).

Per ogni sottoinsieme di k+1 elementi che contiene b, coloriamo tale sottoinsieme a meno di $ b_1 $ (ovverosia un insieme di k elementi) del colore di cui era il sottoinsieme di partenza. Per ipotesi induttiva esiste un insieme $ B_1\subset B-\{ b_1\} $ che rispetta le condizioni 1) e 2) (diciamo che e' blu scuro). A questo punto prendiamo un elemento di $ B_1 $ (diciamo $ b_2 $) tale che, colorando allo stesso modo di prima esista un insieme monocromatico blu scuro, diciamo $ B_2\subset B_1-\{ b_2\} $ E se questa cosa la facciamo all'infinito, i $ b_i $ sono un insieme infinito con le caratteristiche richeste..
Ma forse a un certo punto questo giochetto non si potra' piu' fare, allora cosa si fa? prendiamo l'ultimo insieme a cui siamo arrivati, scegliamo un elemento a caso e si ricomincia! (evidentemente a quel punto il colore che capita non sara' piu' il blu scuro, ma diciamo il bianco). Per discesa infinita da un certo punto in poi lavoreremo con lo stesso colore, e quindi ci vien fuori un insieme infinito come richiesto.

Perfetto, la mia dimostrazione era leggermente diversa, costruivo (non son sicuro se sia necessario usare Dependent Choice, credo di sì) la successione $ ~ (b_0,B_0), (b_1,B_1),\ldots $ in modo che $ ~ b_{i+1} \ge b_i $, $ ~ b_{i} \in B_i $, $ ~ B_{i+1} \subsetneq B_i $ e che i k+1-sottoinsiemi di $ ~ B_i $ contenenti $ ~ b_i $ siano monocromatici. In questo modo ad ogni i associo un colore. Siccome i colori sono finiti, esiste una sottosuccessione infinita $ ~ (b_{i_n}, B_{i_n}) $ e un colore c tale che i k+1-sottoinsiemi di $ ~ B_{i_n} $ contenenti $ ~ b_{i_n} $ abbiano il colore c, per ogni n.
Allora $ ~ \bigcup_{n\in \mathbb{N}} b_{i_n} $ ha la proprietà voluta: per ogni suo k+1-sottoinsieme, prendo il suo elemento minimo $ ~ b_{i_k} $: allora gli altri elementi sono contenuti in $ ~ B_{i_k} $ e quindi hanno il colore c.

Come implica il claim del primo post: prendo un insieme 1-saturo infinito, prendo un suo sottoinsieme 2-saturo infinito, ..., prendo un suo sottoinsieme n-saturo infinito.