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 $
Ciao P(N), quanto sei alto?
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} $
?
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} $
?
I'm the best there is at what I do. But what I do best isn't very nice.
Quest'altro è stato già sciupato:
viewtopic.php?t=9402
... ma non fa male ripeterlo perchè è proprio bello!
viewtopic.php?t=9402
... ma non fa male ripeterlo perchè è proprio bello!
-
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
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!
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!