OliForum Matematico

Dimostrare che esiste un insieme A di sottoinsiemi di $ ~ \mathbb{N} $ tale che:
- dati due elementi $ ~ X,Y \in A $ si abbia $ ~ X \subset Y $ oppure $ ~ Y \subset X $
- non esista una funzione iniettiva $ ~ f: A \rightarrow N $

Qui c'era la soluzione, ma l'avevo messa troppo presto. Adesso l'ho tolta. tra uan settimana la rimetto.

Bravo!

qui c'erano infamissimi insulti perchè mi aveva stroncato subito il problema, ma ci siam capiti

Per farmi perdonare del tutto da edriv aggiungo questo problema in tema:

E' possibile trovare una famiglia $ A $ di sottoinsiemi di $ \mathbb N $ tale che

1) se $ X $ e $ Y $ appartengono ad $ A $ e $ X\neq Y $, allora l'intersezione $ X\cap Y $ e' un insieme finito.

2) non esiste alcuna applicazione iniettiva $ A\to{\mathbb N} $

?

Quest'altro è stato già sciupato:
viewtopic.php?t=9402

... ma non fa male ripeterlo perchè è proprio bello!

up

Farò di più, cioè costruirò un A di quel tipo che abbia la cardinalità di R. Ad ogni numero in [0,1[ associo un sottoinsieme di N in modo da rispettare l'ordine. Per farlo, scrivo tutto in base 2, magari evitando tutti gli 1 periodico (cosa utile nel momento in cui devo scrivere una condizione per x<y).

Prendo dunque x in [0,1[, e provo ad associargli un insieme T, costruendolo ricorsivamente. Definisco $ S_{1}=\mathbb{N}_0 $. Definisco anche $ {f} $, funzione che ad un sottoinsieme X di N associa l'insieme Y contenente tutti e soli i numeri di X che occupano posto dipari (avendo scritto gli elementi di X in modo crescente). Ad esempio $ f(S_1)=\{1,3,5,...\}, f(f(S_1))=\{1,5,9,...\} $.
Se la $ k $-esima cifra dopo la virgola di x è 1, allora in T metto tutti i numeri $ f(S_k) $, e pongo $ S_{k+1}:=S_k\backslash f(S_k) $.
Se invece la $ k $-esima cifra dopo la virgola di x è 0, allora metto semplicemente $ S_{k+1}:=f(S_k) $.

Ad esempio se x=0,11... dopo i primi due passi T conterrà {1,3,5,7...} e {2,6,10,14...}; se invece x=0,01 allora dopo i primi due passi T conterrà {1,5,9,13,..}.

Ora, dovrebbe essere chiaro che questa costruzione rispetta l'ordine: x < y vuol dire che costruisco T(x) come T(y) fino a una certa cifra k, ove avrò uno 0 in x e un 1 in y; da quel momento in poi gli elementi di T(x) vivranno nell' $ f(S_{k}) $ (che è lo stesso per x e per y), il quale è contenuto in T(y). Questo mostra $ T(x)\subseteq T(y) $. Per vedere che l'inclusione è stretta, basta osservare che gli elementi di T(x) non copriranno tutto quell'$ f(S_{k}) $, poiché, avendo escluso gli 1 periodici, prima o poi comparirà un altro 0 nell'espressione di x, e questo ci costringerà a restringere nuovamente il campo. Quindi l'applicazione è strettamente crescente; in particolare, è iniettiva.

Ciao!

Bravo per la soluzione perfetta ed elementare.

Per chi avesse conoscenze più avanzate (tipo, cosa sono i numeri razionali, e sapere che sono in corrispondenza biunivoca con N) c'era quest'altra soluzione:
considerare le sezioni di numeri razionali