Strutture geometriche e algebriche - esercizi

COGNOME E NOME ………………..

MATRICOLA ……………………...

(Luglio 10)

Sia (S₄, ∘) il gruppo delle permutazioni sull'insieme X = {1,2,3,4} ed H il sottoinsieme di S₄ così definito: H = {f ∈ S₄ / f(1) = 1}

1. Provare che H è un sottogruppo di (S₄,∘).
2. Determinare i sottogruppi di H.
3. Dire se H è ciclico.
4. Dire se H' = {f ∈ S₄ / f(1) = 2} è un sottogruppo di (S₄, ∘).

Si determini la generica soluzione del seguente sistema di equazioni congruenziali:

• x ≡ 2 (mod 2)
• x ≡ 1 (mod 3)
• x ≡ 3 (mod 5)
• x ≡ 6 (mod 11)

• Definire il ricoprimento completo associato una relazione di compatibilità e provare che l’applicazione che ad ogni relazione di compatibilità associa il ricoprimento completo associato è iniettiva.
• Provare che un albero non singolare finito possiede almeno due vertici di grado 1.
• Provare che un gruppo finito avente per ordine un numero primo è un gruppo ciclico.
• Provare che un grafo associato ad una relazione d’ordine non contiene circuiti di lunghezza maggiore di uno.

Ex. 2

X ≡ 1 (mod 2) X ≡ 1 (mod 3) X ≡ 3 (mod 5) X ≡ 6 (mod 12)

Πm_i ≡ m₁m₂m₃m₄ = 330

Π₂ = Π/m₁ = 165 Π₃ = Π/m₂ = 110 Π₅ = Π/m₃ = 66 Π₁₂ = Π/m₄ = 30

Π₂ X₁ ≡ 1 [mod m₁] X₁ 1 X₁ [q - 1 = m₁k] ⇒ k = 82 X₁ = 1

Π₃ X₂ ≡ 1 [mod m₂] 10 X₂ - 1 = 3k ⇒ k = 23 X₂ = 2

Π₅ X₃ ≡ 1 [mod m₃] 66 X₃ - 1 = 5k ⇒ k = 13 X₃ = 1

Π₁₂ X₄ ≡ 1 [mod m₄] 30 X _{- 1 = 11k ⇒ k=73 X4 = 7}

X = Π₂ X₁ a₁ + Π₃ X₂ a₂ + Π₅ X₃ a₃ + Π₁₂ X₄ a₄ = 330 + 220 + 198 + 1260 = 2008

X - ~X = Πk ~X = X - Πk = 2008 - 330k = 28 X = 28 + 330k

Definizione

Il raggruppamento completo associato ad una relazione di compatibilità è l'insieme che si ottiene dalla scomposizione di tutte le relazioni di compatibilità associate al raggruppamento completo associato, o relazione, su A.

Il raggruppamento completo di un insieme A associato ad una relazione di compatibilità è l'insieme delle famiglie degli insiemi C_β(A) ottenuti dalla collezione di tutti i singoli insiemi di compatibilità massimali ottenuti da ^α su A.

Se α e β sono relazioni di compatibilità in A, tale che C_β(A) ∈ C_α(A) ∩ α allore a f

sono a e b elementi di A relativi a tra loro, l’insieme {a, b} è compatibile rispetto ad ε, ed è pertanto contenuto in un insieme compatibile massimo C₁. L’insieme C₁ appartiene a C_α(A) e quindi anche a C_β(A). Gli elementi a e b appartengono ad un insieme compatibile rispetto a β e quindi sono in relazione tra di loro. Si prova che aαb ⇒ aβb.

Scambieremo i ruoli delle relazioni e otteniamo l'applicazione inversa e quindi le uguaglianze tra α e β.