Matematica discreta - Teoria dei gruppi
Semigruppo
Un insieme finito o infinito $ 'S' $ con un'operazione binaria $ '\ omicron' $ (Composizione) è chiamato semigruppo se mantiene le seguenti due condizioni simultaneamente -
Closure - Per ogni coppia $ (a, b) \ in S, \ :( a \ omicron b) $ deve essere presente nell'insieme $ S $.
Associative - Per ogni elemento $ a, b, c \ in S, (a \ omicron b) \ omicron c = a \ omicron (b \ omicron c) $ deve valere.
Esempio
L'insieme di interi positivi (escluso lo zero) con operazione di addizione è un semigruppo. Ad esempio, $ S = \ lbrace 1, 2, 3, \ dots \ rbrace $
Qui la proprietà di chiusura vale come per ogni coppia $ (a, b) \ in S, (a + b) $ è presente nell'insieme S. Ad esempio, $ 1 + 2 = 3 \ in S] $
La proprietà associativa vale anche per ogni elemento $ a, b, c \ in S, (a + b) + c = a + (b + c) $. Ad esempio, $ (1 + 2) + 3 = 1 + (2 + 3) = 5 $
Monoide
Un monoide è un semigruppo con un elemento di identità. L'elemento identità (indicato con $ e $ o E) di un insieme S è un elemento tale che $ (a \ omicron e) = a $, per ogni elemento $ a \ in S $. Un elemento di identità è anche chiamato aunit element. Quindi, un monoide possiede tre proprietà contemporaneamente:Closure, Associative, Identity element.
Esempio
L'insieme di numeri interi positivi (escluso lo zero) con operazione di moltiplicazione è un monoide. $ S = \ lbraccia 1, 2, 3, \ punti \ rbraccia $
Qui la proprietà di chiusura vale come per ogni coppia $ (a, b) \ in S, (a \ volte b) $ è presente nell'insieme S. [Ad esempio, $ 1 \ volte 2 = 2 \ in S $ e così via]
La proprietà associativa vale anche per ogni elemento $ a, b, c \ in S, (a \ times b) \ times c = a \ times (b \ times c) $ [Ad esempio, $ (1 \ times 2) \ times 3 = 1 \ times (2 \ times 3) = 6 $ e così via]
La proprietà Identity vale anche per ogni elemento $ a \ in S, (a \ times e) = a $ [Ad esempio, $ (2 \ times 1) = 2, (3 \ times 1) = 3 $ e così via]. Qui l'elemento identità è 1.
Gruppo
Un gruppo è un monoide con un elemento inverso. L'elemento inverso (indicato con I) di un insieme S è un elemento tale che $ (a \ omicron I) = (I \ omicron a) = a $, per ogni elemento $ a \ in S $. Quindi, un gruppo possiede quattro proprietà contemporaneamente: i) Chiusura, ii) Associativo, iii) Elemento identità, iv) Elemento inverso. L'ordine di un gruppo G è il numero di elementi in G e l'ordine di un elemento in un gruppo è il numero intero meno positivo n tale che an è l'elemento identità di quel gruppo G.
Esempi
L'insieme di matrici non singolari $ N \ volte N $ forma un gruppo sotto l'operazione di moltiplicazione di matrici.
Il prodotto di due matrici non singolari $ N \ volte N $ è anche una matrice non singolare $ N \ volte N $ che detiene la proprietà di chiusura.
La stessa moltiplicazione di matrici è associativa. Quindi, la proprietà associativa vale.
L'insieme di matrici non singolari $ N \ times N $ contiene la matrice identità che detiene la proprietà dell'elemento identità.
Poiché tutte le matrici non sono singolari, hanno tutte elementi inversi che sono anche matrici non singolari. Quindi, vale anche la proprietà inversa.
Gruppo Abeliano
Un gruppo abeliano G è un gruppo per il quale la coppia di elementi $ (a, b) \ in G $ ha sempre legge commutativa. Quindi, un gruppo possiede cinque proprietà simultaneamente: i) Chiusura, ii) Associativo, iii) Elemento di identità, iv) Elemento inverso, v) Commutativo.
Esempio
L'insieme degli interi positivi (compreso lo zero) con operazione di addizione è un gruppo abeliano. $ G = \ lbrace 0, 1, 2, 3, \ dots \ rbrace $
Qui la proprietà di chiusura vale come per ogni coppia $ (a, b) \ in S, (a + b) $ è presente nell'insieme S. [Ad esempio, $ 1 + 2 = 2 \ in S $ e così via]
La proprietà associativa vale anche per ogni elemento $ a, b, c \ in S, (a + b) + c = a + (b + c) $ [Ad esempio, $ (1 +2) + 3 = 1 + (2 + 3) = 6 $ e così via]
La proprietà Identity vale anche per ogni elemento $ a \ in S, (a \ times e) = a $ [Ad esempio, $ (2 \ times 1) = 2, (3 \ times 1) = 3 $ e così via]. Qui, l'elemento Identity è 1.
La proprietà commutativa vale anche per ogni elemento $ a \ in S, (a \ times b) = (b \ times a) $ [Ad esempio, $ (2 \ times 3) = (3 \ times 2) = 3 $ e così sopra]
Gruppo ciclico e sottogruppo
UN cyclic groupè un gruppo che può essere generato da un singolo elemento. Ogni elemento di un gruppo ciclico è una potenza di un elemento specifico che viene chiamato generatore. Un gruppo ciclico può essere generato da un generatore "g", in modo tale che ogni altro elemento del gruppo possa essere scritto come potenza del generatore "g".
Esempio
L'insieme di numeri complessi $ \ lbrace 1, -1, i, -i \ rbrace $ sotto l'operazione di moltiplicazione è un gruppo ciclico.
Sono disponibili due generatori: $ i $ e $ –i $ come $ i ^ 1 = i, i ^ 2 = -1, i ^ 3 = -i, i ^ 4 = 1 $ e anche $ (- i) ^ 1 = -i, (–i) ^ 2 = -1, (–i) ^ 3 = i, (–i) ^ 4 = 1 $ che copre tutti gli elementi del gruppo. Quindi, è un gruppo ciclico.
Note - A cyclic groupè sempre un gruppo abeliano ma non tutti i gruppi abeliani sono un gruppo ciclico. I numeri razionali sotto addizione non sono ciclici ma abeliani.
UN subgroup H è un sottoinsieme di un gruppo G (indicato con $ H ≤ G $) se soddisfa le quattro proprietà contemporaneamente - Closure, Associative, Identity element, e Inverse.
Un sottogruppo H di un gruppo G che non include l'intero gruppo G è chiamato sottogruppo proprio (indicato da $ H <G $). Un sottogruppo di un gruppo ciclico è ciclico e anche un sottogruppo abeliano è abeliano.
Esempio
Sia un gruppo $ G = \ lbrace 1, i, -1, -i \ rbrace $
Quindi alcuni sottogruppi sono $ H_1 = \ lbrace 1 \ rbrace, H_2 = \ lbrace 1, -1 \ rbrace $,
Questo non è un sottogruppo - $ H_3 = \ lbrace 1, i \ rbrace $ perché $ (i) ^ {- 1} = -i $ non è in $ H_3 $
Set parzialmente ordinato (POSET)
Un insieme parzialmente ordinato è costituito da un insieme con una relazione binaria riflessiva, antisimmetrica e transitiva. "Set parzialmente ordinato" è abbreviato in POSET.
Esempi
L'insieme di numeri reali in un'operazione binaria minore o uguale a $ (\ le) $ è un poset.
Lascia che l'insieme $ S = \ lbrace 1, 2, 3 \ rbrace $ e l'operazione sia $ \ le $
Le relazioni saranno $ \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \ rbrace $
Questa relazione R è riflessiva come $ \ lbrace (1, 1), (2, 2), (3, 3) \ rbrace \ in R $
Questa relazione R è antisimmetrica, come
$ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace \ in R \ e \ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace ∉ R $
Questa relazione R è anche transitiva come $ \ lbrace (1,2), (2,3), (1,3) \ rbrace \ in R $.
Quindi, è un file poset.
L'insieme dei vertici di un grafo aciclico diretto sotto l'operazione "raggiungibilità" è un poset.
Diagramma di Hasse
Il diagramma di Hasse di un poset è il grafo diretto i cui vertici sono l'elemento di quel poset e gli archi coprono le coppie (x, y) nel poset. Se nel poset $ x <y $, il punto x appare più basso del punto y nel diagramma di Hasse. Se $ x <y <z $ nel poset, la freccia non viene mostrata tra x e z poiché è implicita.
Esempio
Il gruppo di sottoinsiemi di $ \ lbrace 1, 2, 3 \ rbrace = \ lbrace \ emptyset, \ lbrace 1 \ rbrace, \ lbrace 2 \ rbrace, \ lbrace 3 \ rbrace, \ lbrace 1, 2 \ rbrace, \ lbrace 1 , 3 \ rbrace, \ lbrace 2, 3 \ rbrace, \ lbrace 1, 2, 3 \ rbrace \ rbrace $ è mostrato dal seguente diagramma di Hasse -
Set ordinato linearmente
Un insieme ordinato linearmente o un insieme ordinato totale è un insieme parziale in cui ogni coppia di elementi è confrontabile. Si dice che gli elementi $ a, b \ in S $ sono comparabili se $ a \ le b $ o $ b \ le a $ sono validi. La legge della tricotomia definisce questo insieme ordinato totale. Un insieme totalmente ordinato può essere definito come un reticolo distributivo avente la proprietà $ \ lbrace a \ lor b, a \ land b \ rbrace = \ lbrace a, b \ rbrace $ per tutti i valori di aeb nell'insieme S.
Esempio
Il powerset di $ \ lbrace a, b \ rbrace $ ordinato da \ subseteq è un insieme totalmente ordinato come tutti gli elementi del power set $ P = \ lbrace \ emptyset, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace a, b \ rbrace \ rbrace $ sono confrontabili.
Esempio di set di ordini non totale
Un insieme $ S = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ sotto l'operazione x divide y non è un insieme ordinato totale.
Qui, per tutti i $ (x, y) \ in S, x | y $ deve tenere ma non è vero che 2 | 3, poiché 2 non divide 3 o 3 non divide 2. Quindi, non è un insieme ordinato totale.
Reticolo
Un reticolo è un poset $ (L, \ le) $ per il quale ogni coppia $ \ lbrace a, b \ rbrace \ in L $ ha un limite superiore minimo (indicato da $ a \ lor b $) e un limite inferiore massimo ( indicato con $ a \ land b $). LUB $ (\ lbrace a, b \ rbrace) $ è chiamato l'unione di a e b. GLB $ (\ lbrace a, b \ rbrace) $ è chiamato l'incontro di a e b.
Esempio
Questa figura sopra è un reticolo perché per ogni coppia $ \ lbrace a, b \ rbrace \ in L $, esistono un GLB e un LUB.
Questa figura sopra non è un reticolo perché $ GLB (a, b) $ e $ LUB (e, f) $ non esistono.
Alcuni altri reticoli sono discussi di seguito:
Lattice delimitato
Un reticolo L diventa un reticolo limitato se ha un elemento maggiore 1 e un elemento minimo 0.
Lattice integrato
Un reticolo L diventa un reticolo complementato se è un reticolo limitato e se ogni elemento nel reticolo ha un complemento. Un elemento x ha un complemento x 'se $ \ esiste x (x \ land x' = 0 e x \ lor x '= 1) $
Reticolo distributivo
Se un reticolo soddisfa le seguenti due proprietà di distribuzione, viene chiamato reticolo distributivo.
$ a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c) $
$ a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c) $
Lattice modulare
Se un reticolo soddisfa la seguente proprietà, si chiama reticolo modulare.
$ a \ land (b \ lor (a \ land d)) = (a \ land b) \ lor (a \ land d) $
Proprietà dei reticoli
Proprietà idempotenti
$ a \ lor a = a $
$ a \ land a = a $
Proprietà di assorbimento
$ a \ lor (a \ land b) = a $
$ a \ land (a \ lor b) = a $
Proprietà commutative
$ a \ lo b = b \ lo a $
$ a \ land b = b \ land a $
Proprietà associative
$ a \ lor (b \ lor c) = (a \ lor b) \ lo c $
$ a \ land (b \ land c) = (a \ land b) \ land c $
Doppio di un reticolo
Il duale di un reticolo si ottiene scambiando le operazioni "$ \ lor $" e "$ \ land $".
Esempio
Il doppio di $ \ lbrack a \ lor (b \ land c) \ rbrack \ è \ \ lbrack a \ land (b \ lor c) \ rbrack $