Semigruppo

Da Wikipedia, l'enciclopedia libera.

In matematica, un semigruppo è un insieme non vuoto munito di una operazione binaria associativa. In altre parole per semigruppo si intende una struttura algebrica espressa da una coppia (A,*) con A insieme non vuoto ed * funzione definita su tutto A × A a valori in A per la quale si ha

.

Equivalentemente si può definire come semigruppo ogni magma associativo.

Osserviamo che in talune formulazioni, contrariamente a quanto fa l'attuale, si consente che anche l'insieme vuoto possa costituire un semigruppo.

Indice 1 Primi esempi 2 Semigruppi e monoidi 3 Altri esempi di semigruppi 4 Isomorfismi, sottosemigruppi e ideali 5 Generazione di sottosemigruppi 6 Semigruppi e gruppi 7 Semigruppi di endofunzioni

[modifica] Primi esempi

Si incontrano molti esempi di semigruppi, finiti e infiniti. Consideriamone alcuni facilmente definibili.

(1) L'insieme dei numeri interi positivi munito dell'addizione (operazione notoriamente associativa).

(2) L'insieme dei numeri interi naturali munito della moltiplicazione (anche questa operazione è notoriamente associativa).

(3) L'insieme munito della operazione "scelta del massimo tra due numeri" che possiamo scrivere : per la associatività basta osservare che, evidentemente,

(4) L'insieme di tutte le endofunzioni definite entro un insieme S, ad es. entro , munito della composizione di funzioni. La composizione di funzioni è infatti associativa.

(5) L'insieme, numerabile, di tutte le stringhe sopra un dato alfabeto munito della giustapposizione di stringhe. La giustapposizione di stringhe è una specie di archetipo delle operazioni binarie associative. Questo semigruppo si chiama semigruppo libero sull'alfabeto prefissato.

Il semigruppo (3) è un semigruppo finito, ha 4 elementi. La sua tavola di moltiplicazione consiste nella matrice

Si tratta quindi evidentemente di un'operazione commutativa. In un caso come questo si parla di semigruppo commutativo o semigruppo abeliano. Anche i semigruppi (1) e (2) sono commutativi.

Non è invece commutativo il semigruppo libero (5), se viene costruito su un alfabeto di due o più caratteri: ad esempio

.

Non è commutativo neppure il semigruppo delle endofunzioni di un qualsiasi insieme ambiente S formato da 2 o più elementi. Per questo basta considerare il controesempio di due endofunzioni che non commutano: se a e b sono due elementi diversi dell'ambiente S, introduciamo le due funzioni a valore costante e , che conviene considerare come trasformazioni postfisse, da scrivere a destra dell'argomento e quindi definire mediante

.

Con tale notazione risulta chiaro che per le due composizioni di queste due funzioni si ha

.

[modifica] Semigruppi e monoidi

Un semigruppo dotato di un elemento neutro, cioè un semigruppo unitale o unitario di solito viene chiamato monoide. Ogni semigruppo S può essere fatto diventare un monoide semplicemente aggiungendogli un elemento e non facente parte di S e definendo ee := e ed es := s =: se per ogni s in S. Un tale ampliamento può essere effettuato più volte.

Viceversa dato un monoide lo si riduce a semigruppo eliminando semplicemente l'elemento unità e riga e colonna corrispondenti della tavola di moltiplicazione; questo semigruppo potrebbe contenere o non contenere un altro elemento neutro. Dunque lo studio dei monoidi aggiunge ben poco allo studio dei semigruppi: le due specie di strutture sono sostanzialmente equivalenti.

Un monoide con base si definisce monoide libero: esso è un semigruppo con elemento neutro dotato di base per i suoi elementi. Il linguaggio di un automa a stati finiti rappresentato dall'insieme delle stringhe su un certo alfabeto Σ è un esempio importante di monoide libero.

[modifica] Altri esempi di semigruppi

• Ogni gruppo può considerarsi un monoide.
• Ogni ideale di un qualsiasi anello, munito dell'operazione di moltiplicazione per l'anello.
• Ogni sottoinsieme di un semigruppo che sia chiuso per l'operazione di semigruppo.
• Un semigruppo la cui operazione è commutativa e idempotente è un semireticolo. Semireticoli di questo genere sono dati dalla collezione dei sottoinsiemi di un dato ambiente munita dell'intersezione (oppure dell'unione).
• L'insieme di tutte le relazioni entro un insieme munito della composizione tra relazioni.
• L'insieme di tutti i linguaggi su un dato alfabeto munito della giustapposizione fra linguaggi.

[modifica] Isomorfismi, sottosemigruppi e ideali

Introduciamo ora le relazioni e le costruzioni che costituiscono il normale armamentario per lo studio delle caratteristiche dele strutture algebriche della specie semigruppi. Per brevità, l'operazione del semigruppo generico viene presentata con la semplice giustapposizione, cioè xy denota il risultato della applicazione dell'operazione di semigruppo alla coppia ordinata (x, y). Se A e B sono sottoinsiemi di un semigruppo, allora AB denota l'insieme { ab | a in A e b in B }.

Due semigruppi S e T si dicono isomorfi se esiste una biiezione f : S → T con la proprietà che, per ogni coppia di elementi a, b in S, f(ab) = f(a)f(b). In questo caso f si dice isomorfismo di S su T. Se ci si limita a considerare le caratteristiche degli elementi dei semigruppi collegate alle operazioni di tali strutture due semigruppi isomorfi sono del tutto equivalenti: potranno invece essere distinti da altre proprietà derivanti dalle modalità secondo le quali sono stati costruiti.

Un sottoinsieme A non vuoto di un semigruppo S viene detto sottosemigruppo di S se è chiuso per la operazione di semigruppo, ovvero se AA è un sottoinsieme di A. A viene detto ideale destro se AS è sottoinsieme di A, e simmetricamente viene chiamato ideale sinistro se SA è sottoinsieme di A. Se A è contemporaneamente ideale sinistro e ideale destro, allora viene chiamato ideale bilatero o semplicemente ideale di S. Si vede rapidamente che l'intersezione di due ideali è anch'essa un idealeò se ne deduce che un semigruppo può avere al più un ideale minimale. Il generico ideale del semigruppo degli interi positivi muniti dell'addizione è l'insieme dei multipli di un qualsiasi intero positivo. Si vede quindi che il semigruppo additivo dei positivi non possiede ideale minimale. L'ideale minimale di un semigruppo commutativo, quando esiste, è un gruppo.

[modifica] Generazione di sottosemigruppi

Se S è un semigruppo, allora l'intersezione di ogni collezione di suoi sottosemigruppi è anch'essa un sottosemigruppo si S. Dunque i sottosemigruppi di S formano un reticolo completo. Per ogni sottoinsieme A di S tra i sottosemigruppi di S che contengono tale A ne esiste uno ed uno solo minimale per la inclusione; se lo denotiamo T, si dice che A genera T. Ogni elemento x di S genera il sottosemigruppo { xⁿ |: n intero positivo } che si denota <x>. Se tale sottoinsieme di S è finito si dice che x è di ordine finito, oppure che ha ordine finito; più precisamente si dice ordine di x in S la cardinalità del sottosemigruppo generato. Se viceversa <x> è infinito (evidentemente infinito numerabile) si dice che x è di, oppure ha, ordine infinito.

Si dice semigruppo periodico ogni semigruppo costituito solo da elementi di ordine finito. Chiaramente ogni semigruppo finito è periodico.

Si dice semigruppo monogenico ogni semigruppo che può considerarsi generato da un singolo elemento (talora viene detto anche semigruppo ciclico, ma questa espressione può indurre confusione). Ogni semigruppo monogenico infinito è isomorfo al semigruppo additivo degli interi positivi.

Anche i semigruppi monogenici finiti possono essere individuati in modo esauriente. Denotando x un suo generatore e n la sua cardinalità i suoi elementi possono essere elencati come successive potenze di x: x, x², ... ,xⁿ; la successiva potenza xⁿ⁺¹ deve coincidere con una potenza inferiore, scriviamola x^k. Gli interi n e k caratterizzano completamente il semigruppo. Consideriamo l'insieme di p:=n-k+1 elementi G := {m=k, k+1, ...,n :| x^m }. Chiaramente esso costituisce un sottosemigruppo di S; più precisamente si tratta di un gruppo, in quanto i suoi elementi vengono permutati quando vengono moltiplicati per uno di essi. Se k=1 il semigruppo è il gruppo ciclico di n elementi. L'unità del sottogruppo è un idempotente del semigruppo; ogni altro elemento del semigruppo moltiplicato per sé stesso porta ad un altro elemento. Dunque ogni semigruppo periodico finito contiene almeno un elemento idempotente e ogni semigruppo monogenico finito contiene esattamente un idempotente. Si osserva anche che il sottogruppo (gruppo ciclico) di un semigruppo monogenico finito è un ideale del semigruppo.

[modifica] Semigruppi e gruppi

Un sottosemigruppo di un semigruppo S che è anche un gruppo viene detto sottogruppo di S. Vi è una stretta relazione tra i sottogruppi di un semigruppo e i suoi idempotenti. Ogni sottogruppo contiene esattamente un idempotente, cioè l'elemento neutro del semigruppo. Per ogni idempotente e del semigruppo esiste un unico sottogruppo massimale che contiene e. Ogni sottogruppo massimale viene individuato in questo modo, e di conseguenza esiste una corrispondenza biunivoca tra idempotenti e sottogruppi massimali. (Si dovrebbe notare che il termine sottogruppo massimale viene qui usato in modo differente da come viene usato in teoria dei gruppi. In questa teoria un sottogruppo massimale si sottintende che sia un sottogruppo proprio. Quando è considerato come semigruppo, un gruppo possiede solo un sottogruppo massimale, cioè sé stesso.)

[modifica] Semigruppi di endofunzioni

Ogni semigruppo può considerarsi un semigruppo di endofunzioni: infatti si può associare ad ogni elemento y di un semigruppo S la endofunzione di S corrispondente alla moltiplicazione a destra per y dei suoi varielementi. Viceversa ad ogni insieme E di endofunzioni di un insieme ambiente A si associa il semigruppo <E> generato dagli elementi di E (e da tutti i loro prodotti). Se A è infinito il semigruppo <E> può essere finito o infinito; se A è finito <E> evidentemente deve essere finito.

Si possono considerare anche semigruppi generati da insiemi di relazioni entro un insieme ambiente. Si trova che questi semigruppi si possono ridurre a semigruppi di endofunzioni: si tratta di passare dalle relazioni entro un insieme A alle endofunzioni entro l'insieme delle parti di A. I semigruppi di endofunzioni entro insiemi finiti possono essere convenientemente trattati come semiautomi deterministici (a stati finiti), mentre i semigruppi di relazioni entro insiemi finiti possono essere trattati come semiautomi non-deterministici. In proposito v. teoria degli automi a stati finiti.

I risultati su questi semigruppi e questi automi possono essere formulati anche come fatti riguardanti relazioni di congruenza entro monoidi liberi su alfabeti finiti che forniscono quozienti finiti. In proposito v. teoria dei linguaggi razionali (o dei linguaggi regolari).

Sui semigruppi finiti visti nei modi precedenti si può dire molto di più. Notevoli risultati sulla classificazione delle strutture di tali semigruppi finiti sono ottenuti dalla teoria di Krohn-Rhodes.