Si dimostri l’esistenza, sull’insieme N dei numeri naturali, di
una famiglia infinita non numerabile di sottoinsiemi Ci
tali che Ci ∩ Cj abbia cardinalità finita per ogni i diverso j.
Famiglie non numerabili!
-
- Messaggi: 11
- Iscritto il: 10 ott 2007, 20:23
- Località: Aci Catena
Bel problema, alexlor8083!
Sia $ ~ p_1,p_2,\ldots $ la successione dei numeri primi in ordine crescente.
Sia $ ~ a_1,a_2,\ldots $ una successione crescente di numeri naturali.
Definiamo la successione crescente $ ~ a' $ come $ ~ a'_n = \prod_{i=1}^n p_{a_i} $. La funzione che alla successione a associa a' è chiaramente iniettiva.
Ora supponiamo che per un certo n e per due successioni crescenti a,b si abbia $ ~ a'_n = b'_n $. Essendo $ ~ a'_n $ il prodotto dei primi di indice $ ~ a_1,a_2,\ldots,a_n $ e $ ~ b'_n $ il prodotto dei primi di indice $ ~ b_1,b_2,\ldots,b_n $, con la fattorizzazione unica degli interi concludiamo che $ ~ a_i = b_i $ per $ ~ i=1,2,\ldots,n $. Quindi due successioni a',b', se sono uguali per infiniti termini, coincidono, e coincidono anche le successioni a,b.
Identificando un sottoinsieme di N con la successione crescente dei suoi elementi, abbiamo la tesi.
Per completare il problema, dimostrate questo:
se n è un naturale e una famiglia di sottoinsiemi di N è tale che l'intersezione tra due suoi elementi distinti ha cardinalità al più n, allora tale famiglia è numerabile.
Sia $ ~ p_1,p_2,\ldots $ la successione dei numeri primi in ordine crescente.
Sia $ ~ a_1,a_2,\ldots $ una successione crescente di numeri naturali.
Definiamo la successione crescente $ ~ a' $ come $ ~ a'_n = \prod_{i=1}^n p_{a_i} $. La funzione che alla successione a associa a' è chiaramente iniettiva.
Ora supponiamo che per un certo n e per due successioni crescenti a,b si abbia $ ~ a'_n = b'_n $. Essendo $ ~ a'_n $ il prodotto dei primi di indice $ ~ a_1,a_2,\ldots,a_n $ e $ ~ b'_n $ il prodotto dei primi di indice $ ~ b_1,b_2,\ldots,b_n $, con la fattorizzazione unica degli interi concludiamo che $ ~ a_i = b_i $ per $ ~ i=1,2,\ldots,n $. Quindi due successioni a',b', se sono uguali per infiniti termini, coincidono, e coincidono anche le successioni a,b.
Identificando un sottoinsieme di N con la successione crescente dei suoi elementi, abbiamo la tesi.
Per completare il problema, dimostrate questo:
se n è un naturale e una famiglia di sottoinsiemi di N è tale che l'intersezione tra due suoi elementi distinti ha cardinalità al più n, allora tale famiglia è numerabile.
Ultima modifica di edriv il 20 ott 2007, 18:17, modificato 1 volta in totale.
Credo che gli a_i siano naturali crescenti. Dovrebbe essere così:
per ogni sottoinsieme A di N, ordini in maniera crescente gli elementi ottenendo gli a_i; poi produci i numeri a'_i, che tutti insieme formano il sottoinsieme A' di N.
I sottoinsiemi A' sono più che numerabili (in corrispondenza biunivoca con le parti di N) e due di loro hanno sempre intersezione finita, oppure coincidono.
EDIT : ah ok ... post contemporaneo.
per ogni sottoinsieme A di N, ordini in maniera crescente gli elementi ottenendo gli a_i; poi produci i numeri a'_i, che tutti insieme formano il sottoinsieme A' di N.
I sottoinsiemi A' sono più che numerabili (in corrispondenza biunivoca con le parti di N) e due di loro hanno sempre intersezione finita, oppure coincidono.
EDIT : ah ok ... post contemporaneo.