Nozioni preliminari Flashcards
Assiomi di Peano
Il matematico italiano Giuseppe Peano propose una
presentazione assiomatica dell’insieme N dei numeri naturali:
1. 0 ∈ N;
2. se n ∈ N, allora succ (n) ∈ N;
3. non esiste nessun n ∈ N tale che 0 = succ (n);
4. se succ (n) = succ (m) allora n = m;
5. se S ⊆ N è tale che 0 ∈ S ed inoltre succ (n) ∈ S se n ∈ S, allora S = N.
Quando un algebra si dice induttiva
Un’algebra (A, γ) si dice induttiva quando: (γ si legge gamma)
1. le γi sono tutte iniettive (ossia gli el di A con la funzione yi hanno tutti immagini distinte);
2. le loro immagini sono disgiunte e
3. soddisfano il principio di induzione, ovvero: se un insieme S ⊆ A è chiuso rispetto a ciascuna delle γi allora S = A.
Le γi sono chiamate costruttori di A. Un costruttore γi è chiamato base se αi = 0, ossia se il dominio della funzioneγi è A^0 (piu eventuali parametri esterni).
Cos’è un algebra (A, γ)
Un’algebra (A, γ) di segnatura I è una struttura matematica costituita da un insieme A, chiamato carrier o insieme sostegno della struttura, ed una famiglia γ = {γi} con i∈I di funzioni con segnatura γi : A^αi × Ki → A
ossia γ={γ1,γ2,…,γI} dove γi è una funzione dell’algebra (A, γ). Ogni funzione è fatta γi : A^αi × Ki → A ossia la funziona di nome γi ha come dominio:
-un prodotto cartesiano dell’insieme sostegno A per αi volte, e
-una sequenza Ki1x Ki2 x…x Kini di eventuali insieme esterni;
l’arietà della funzione i è dunque αi + |Ki|.
Omomorfismo tra due algebre (A, γ) → (B, δ)
Un omomorfismo tra due algebre (A, γ) → (B, δ)con la stessa segnatura I è una funzione h : A → B tale che, per ogni i ∈ I con αi = n e m parametri esterni,
h(γi(a1, . . . , an, k1, . . . km)) = δi(h(a1), . . . , h(an), k1, . . . km).
Altra def: un omomorfismo è un’applicazione tra due strutture algebriche dello stesso tipo che conserva le operazioni in esse definite
Ad esempio, considerando insiemi con una singola operazione binaria (un magma), la funzione f:B–>A è un omomorfismo se vale:
f(u*v) = f(u)#f(v)
per ogni coppia u, v di elementi di A, dove * e # sono le operazioni binarie di A e B rispettivamente.
Isomorfismo
Un isomorfismo è un omomorfismo bigettivo.
Monoide
Un monoide è una struttura algebrica dotata dell’operazione binaria associativa e di un elemento neutro
Esempio di un omomorfismo tra algebre
Sia W l’insieme di tutte le parole su un alfabeto A, ovvero le sequenze finite di elementi di A. W ha una ovvia struttura di monoide, con l’operazione binaria append : A × A → A di concatenazione (che è associativa, come richiesto in un monoide), e un elemento neutro <> i : 1 → A, la parola vuota. La funzione length : W → N che associa ad ogni parola la sua lunghezza soddisfa le equazioni length (<>) = 0 e length (append (w, w0 )) = length (w) + length (w0), ed è dunque un omomorfismo nel monoide (N, +, 0)
Quando un insieme si dice chiuso rispetto a una funzione f
Sia f : A^n × K → A una operazione su A con parametri esterni in K = K1 × · · · × Km. Un insieme S ⊆ A si dice chiuso rispetto ad f quando a1, . . . , an ∈ S implica f(a1, . . . , an, k1, . . . , km) ∈ S.
