Sottomonoidi dei naturali
Sottomonoidi dei naturali
Provare che l'insieme dei sottomonoidi additivi di $ N $ è numerabile.
immagino che con $ (\mathbb{N};+) $ tu intenda $ (\mathbb{N}_0;+) $, poichè senza lo 0 non è un monoide (questione solamente di notazione)...
Comunque, l'insieme dei sottomonoidi di $ (\mathbb{N}_0;+) $ è costituito dall'unione di: tutti i sottomonoidi composti da 1 elemento (ovvero solo l'insieme $ \{ 0 \} $), tutti i sottomonoidi di 2 elementi, tutti quelli di 3 elementi e così via. Per ogni numero naturale k, la famiglia di sottomonoidi di esattamente k elementi è numerabile, poichè è costituita da infiniti sottoinsiemi delle parti finite di $ \mathbb{N} $, che sono un insieme numerabile (e sappiamo che ogni sottoinsieme infinito di un insieme al più numerabile è al più numerabile). Pertanto, l'unione di tutte queste famiglie è numerabile, in quanto unione infinita di insiemi numerabili.
Comunque, l'insieme dei sottomonoidi di $ (\mathbb{N}_0;+) $ è costituito dall'unione di: tutti i sottomonoidi composti da 1 elemento (ovvero solo l'insieme $ \{ 0 \} $), tutti i sottomonoidi di 2 elementi, tutti quelli di 3 elementi e così via. Per ogni numero naturale k, la famiglia di sottomonoidi di esattamente k elementi è numerabile, poichè è costituita da infiniti sottoinsiemi delle parti finite di $ \mathbb{N} $, che sono un insieme numerabile (e sappiamo che ogni sottoinsieme infinito di un insieme al più numerabile è al più numerabile). Pertanto, l'unione di tutte queste famiglie è numerabile, in quanto unione infinita di insiemi numerabili.
che mi sembra un po' falso..EvaristeG ha scritto:Hmm non dovresti anche dimostrare che quelli sono tutti i sottomonoidi? Cioè che non esiste un sottomonoide con infiniti elementi?
l'insieme dei multipli naturali di un intero fissato (compreso lo 0) non è un monoide?
d'altra parte mi sembra anche un po' difficile che esistano dei sottomonoidi FINITI di N, escluso {0}
(se ne esiste uno finito (diverso dal solo 0) e si prende il massimo, lui+lui dovrebbe stare nel sottomonoide..)
uh, assai carino...
devo ammettere che c'ho messo un po' a capire come dovessero girare le cose, dopo averci messo un pezzo a credere alla tesi :p
comunque, posto in bianco...
devo ammettere che c'ho messo un po' a capire come dovessero girare le cose, dopo averci messo un pezzo a credere alla tesi :p
comunque, posto in bianco...
bonus question: e i sottomonoidi moltiplicativi di $ \mathbb{N} $?dato un monoide additivo M in N, sarebbe bello provare a caratterizzarlo con dei "generatori": sappiamo che M ha un minimo, e lo chiamiamo m. adesso prendiamo le classi di resto modulo m che vengono prese da M, e prendiamo il minimo rappresentante di ciascuna di esse in M, e li chiamiamo m=m_0 < .. < m_k, con k<m.
in questo modo abbiamo associato a M una successione finita di naturali.
supponiamo che due monoidi M, M' diano la stessa successione, e prendiamo un elemento x che sta nel primo ma non nel secondo. chiaramente, x>m, e x cade in una classe di resto degli m_j, diciamo in m_i, e x>m_i. a questo punto, x = m_i +dm per un certo d, quindi x sta in ciascuno dei due moduli.
concludendo, abbiamo una funzione iniettiva dai monoidi additivi alle successioni finite di naturali (che sono numerabili).
Ultima modifica di ma_go il 16 nov 2006, 20:30, modificato 1 volta in totale.
Io l'ho fatto (la versione additiva) in un modo un po' diverso... o meglio... non è immediatamente ovvio se è lo stesso metodo oppure no. Inoltre mi sembra un po' più semplice di quello del Ma_go (ma forse è sbagliato...). Eccolo:
Sia M il monoide. Sia d=MCD(M). Wlog posso supporre d=1. (altrimenti divido tutti gli elementi per d, operazione che non pregiudica la [non]numerabilità).
Per Bézout, esiste un naturale x t.c. M contiene tutti i naturali da x in poi. Ma allora il complementare di M è finito, quindi i monoidi con d=1 sono non più delle parti finite di N, che sono numerabili. []
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
uhm...
per bezout intendi quel simpatico fatterello per cui
perché il bezout che conoscevo io diceva che
se intendi il primo, mi pare che la tua vada bene.. certo, sottointende un po' di passaggi, ma va benissimo così
per bezout intendi quel simpatico fatterello per cui
?dati a,b coprimi, allora ha+kb (con h,k positivi) assume tutti i valori naturali maggiori di ab-a-b
perché il bezout che conoscevo io diceva che
...dati a,b allora esistono h,k interi tali che ha+kb = (a,b)
se intendi il primo, mi pare che la tua vada bene.. certo, sottointende un po' di passaggi, ma va benissimo così
Sì, certo, la prima. Ora, è ben chiaro nel nostro problema, quantificare quel tal minimo non ci interessa (oltre tutto, per arbitrari termini mi pare sia un problema aperto...) Però l'esistenza è un fatto noto e del tutto elementare da considerarlo scontato qui nella sezione di MnE.ma_go ha scritto:intendi quel simpatico fatterello per cui [...] certo, sottointende un po' di passaggi
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
hanno la cardinalità del continuo:
chiaramente non sono di + perchè sono un sottoinsieme delle parti di N.
inoltre, se P è l'insieme dei primi di N, P è numerabile, e per ogni sottoinsieme A di P, possiamo considerare M_A=[naturali nella cui fattorizzazione in primi compaiono solo elementi di A (eventualmente con esponente 0)]. Questo è chiaramente un sottomonoide moltiplicativo, e l'associazione è iniettiva per l'unicità della fattorizzazione in primi in N.
Quindi i sottomonoidi moltiplicativi sono almeno |parti di P|=|parti di N|, fine.
chiaramente non sono di + perchè sono un sottoinsieme delle parti di N.
inoltre, se P è l'insieme dei primi di N, P è numerabile, e per ogni sottoinsieme A di P, possiamo considerare M_A=[naturali nella cui fattorizzazione in primi compaiono solo elementi di A (eventualmente con esponente 0)]. Questo è chiaramente un sottomonoide moltiplicativo, e l'associazione è iniettiva per l'unicità della fattorizzazione in primi in N.
Quindi i sottomonoidi moltiplicativi sono almeno |parti di P|=|parti di N|, fine.