Sottomonoidi dei naturali

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Sottomonoidi dei naturali

Messaggio da rand » 16 nov 2006, 11:12

Provare che l'insieme dei sottomonoidi additivi di $ N $ è numerabile.

Avatar utente
hydro
Messaggi: 218
Iscritto il: 07 apr 2005, 17:11
Località: milano

Messaggio da hydro » 16 nov 2006, 12:40

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.

EvaristeG
Site Admin
Messaggi: 4790
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 16 nov 2006, 13:34

Hmm non dovresti anche dimostrare che quelli sono tutti i sottomonoidi? Cioè che non esiste un sottomonoide con infiniti elementi?

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 16 nov 2006, 15:50

EvaristeG ha scritto:Hmm non dovresti anche dimostrare che quelli sono tutti i sottomonoidi? Cioè che non esiste un sottomonoide con infiniti elementi?
che mi sembra un po' falso..
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..)

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 16 nov 2006, 16:32

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...
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).
bonus question: e i sottomonoidi moltiplicativi di $ \mathbb{N} $?
Ultima modifica di ma_go il 16 nov 2006, 20:30, modificato 1 volta in totale.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 16 nov 2006, 17:25

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."

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 16 nov 2006, 17:44

uhm...
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ì :P

MindFlyer

Messaggio da MindFlyer » 16 nov 2006, 19:58

ma_go ha scritto:prendiamo un rappresentante di ciascuna
Bisogna prendere il minimo rappresentante, altrimenti non funziona.

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 16 nov 2006, 20:29

sì, chiaro.. era quello che intendevo.
edito.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 17 nov 2006, 08:55

ma_go ha scritto:intendi quel simpatico fatterello per cui [...] certo, sottointende un po' di passaggi
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.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 17 nov 2006, 10:59

ah, non sapevo si chiamasse così..
comunque, resta la mia bonus question, di un paio di post sopra..

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 17 nov 2006, 15:41

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.

Rispondi