Strutture algebriche

Strutture algebriche

Una legge di composizione interna n-aria è una funzione:

w: A x ... x A → A^n-volte

Notazione e casi di interesse

Saremo interessati al caso n = 0, 1, 2 (n = 0 equivale a scegliere un elemento di A).

Notazione (caso binario): w(a, b) è la notazione prefissa/funzionale. Come per esempio +: ℕ x ℕ → ℕ. Not. funz. +(a, b), ma per op. binarie si utilizza la notazione infissa a + b invece di +(a, b).

Esempi di operazioni

• Addizione: +: ℤ x ℤ → ℤ (a, b) ↦ a + b, op. interna binaria.
• L'opposto/inverso: -: ℤ → ℤ, a ↦ -a, op. interna unaria.
• Domanda: ℝ x ℝ → ℝ (a, b) ↦ a/b è op. interna binaria?

Non è una funzione dato che x · 0 = 0 non è definita, lo sarebbe definita in ℝ₀ × ℝ₀ → ℝ₀. 0/6 è op. wt. binaria.

Informa: x in ℕ → ℕ (x – b) → a - b è op. binaria interna? No. Non è più interna! (1,5) +3₄ ∉ ℕ! Lo sarebbe in ℤ x ℤ → ℤ → ℚ.

Operazioni su matrici e altri esempi

• (_mM_n (ℝ) × _mM_n (ℝ)) → _mM_n (ℝ): (A, B) → A + B è op. int. binaria: (A, B) → A • B. ℝ_nn (ℝ) → _mM_n (ℝ) è op. wt. unaria A → A^t.
• P(x) × P(x) → P(x): (A, B) → A ∩ B è op. wt. binaria: P(x) → P(x) A >> A^c è op. int. unaria.
• È P un PTO E: A × A → A op. bin. interna, possiamo costruire la sua tabella moltiplicativa:

Definizione di struttura algebrica

Una struttura algebrica è una coppia (A, Ω) dove Ω = {ω₁, ..., ω_k} è un insieme di operazioni.

Di semigruppo: (A, Ω) è: A × A → A è op. int. binaria che è associativa:

∀a, b, c ∈ A: a (b c) = (a b).c

Oss: L'associatività mi permette di togliere le parentesi:

a . (b . (c . d)) = (a . (b . c)) . d = ((a . b) . (c . d))

Se ∀ a, b ∈ A a . b . b . a allora (S, °) si dice semigruppo commutativo.

Esempi di semigruppo

• (ℕ_min(ℝ), +), (ℤ, +), (ℤ, +), (ℝ, +) semigruppi commutativi
• (ℕ_min(ℝ), .) è un semigruppo non è commutativo:

Un altro esempio di semigruppo

(A, ★) con tabella:

Non è un semigruppo: (a ★ b) ★ a = a ★ a = a a ★ (b ★ a) = a ★ c = c non è associativa!

Esempio importante in informatica

∑^* = {0,1} ∑⁺ = {Stringhe su {0,1,0}} = {0,1,00,11,01,10,...}

Su ∑⁺ definiamo l'op. di concatenazione •

∑^{+x∑+➡∑+} ∀ w₁, w₂ ∈ ∑⁺ w₁w₂ = w₁w₂ (110.001 = 111001) (∑⁺, •) è un semigruppo non commutativo.

Operazioni su ℤ_n

Su ℤ_n = {a ∈ ℤ | a = ℤ_n} ℤ_m = (a ≡ b) (mod n) a, b hanno lo stesso resto div. n ℤ₃ = {0₃, [1]₃, [2]₃}

Possiamo definire due op. bw. interne:

⊕: ℤ_n x ℤ_n ➡ ℤ_n [a]_n ⊕ [b]_n = [a+b]_n (somma su ℤ)

⊙: ℤ_n x ℤ_n ➡ ℤ_n [a]_n ⊙ [b]_n = [a⊙b]_n (prodotto su ℤ)

È ben definita: cioè [a]_n = [a']_n e [b]_n = [b']_n allora [a+b]_n = [a'+b']_n, sì!

Si infatti: a-a' = k₁.n e b-b' = k₂.n → (k+n)_n = (a-a₁) + (b-b₁) = (a+b) - (a₁+b₁) cioè a₁ ≡ a₁'; b₁ ↔ (a+b)_n ≡ (a₁'+b₁')

Sia ⊕, ○ sono associative: [a_n ⊕ (b_n]