Ciao P(N), quanto sei alto?

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Ciao P(N), quanto sei alto?

Messaggio da edriv » 11 dic 2007, 14:34

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 $

Avatar utente
wolverine
Messaggi: 59
Iscritto il: 11 nov 2007, 12:35

Messaggio da wolverine » 11 dic 2007, 21:21

Qui c'era la soluzione, ma l'avevo messa troppo presto. Adesso l'ho tolta. tra uan settimana la rimetto.
Ultima modifica di wolverine il 11 dic 2007, 21:48, modificato 1 volta in totale.

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 11 dic 2007, 21:26

Bravo! :D

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

Avatar utente
wolverine
Messaggi: 59
Iscritto il: 11 nov 2007, 12:35

Messaggio da wolverine » 12 dic 2007, 08:45

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} $

?
I'm the best there is at what I do. But what I do best isn't very nice.

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 12 dic 2007, 14:23

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

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

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 30 ago 2008, 13:12

up

pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Messaggio da pic88 » 04 ott 2008, 14:11

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!

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 04 ott 2008, 14:25

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 :D

Rispondi