Appunti di Algebra 1

13.10.2021

Equivalenze e partizioni

Relazione di equivalenza: A insieme, corrispondenza di A in A = P ⊆ A x A [apb]

Corrispondenza p di un insieme A in un insieme B = P ⊆ A x B

Una relazione ~ su A si dice:

• a. riflessiva: a ~ a ∀ a ∈ A
• b. simmetrica: a ~ b ⇒ b ~ a ∀a,b ∈ A
• c. transitiva: a ~ b e b ~ c ⇒ a ~ c ∀ a,b,c ∈ A

~ è una relazione di equivalenza (o equivalenza): se ≝, R ≡ S, ~ ≡ ≡ ≡

Sia A insieme, R una relazione di su A. ∀ a ∈ A sia [a]_~ = {x ∈ A|x ~ a}

Si chiama classe di equivalenza di a modulo ~.

Sia A/~ = {[a] | a ∈ A} insieme quoziente di A modulo ~.

14.10.2021

Grafi orientati

Collegoi elementi in relazione tra loro da delle frecce

Partizioni di un insieme

Def: A insieme, una partizione di A è una famiglia 'F' di sottoinsiemi di A t.c.

• a. x ≠ ∅ ∀ x ∈ F
• b. ∪ x = A
• c. x,y ∈ F e x ≠ y ⇒ x ∩ y = ∅

Prop: se l insieme, ~ è una relazione di equivalenza su A, allora A/~ è una partizione di A.

Dim: A/~ = {[a] | a ∈ A} e [a]_~ = {x ∈ A | x ~ a} ⊆ A ⇒ A/~ è una famiglia di sottoinsiemi di di F.

1. [a]_~ ≠ ∅ ∀a ∈ A (per prop.R) ⇒ a ∈ [a]_~ ⇒ [a]_~ ≠ ∅ ∀a ∈ A

2. [a]_~ ⊆ A ⇒ ∪_{a∈ A} [a]_~ ⊆ A

As ∪_A [a]_~, se x ∈ A ⇒ x ∈ [x]_~ ⊆ ∪_{a∈ A} [a]_~ ⇒ ∪_{a∈ A} [a]_~ = A

C. dobbiamo dim. che se x ∈ X e y ∈ N e x ≠ y ⇒ x ∩ y = ∅

Per assurdo:

Suggeriamo x,y ∈ A/1, x ≠ y e x ∩ y ≠ ∅ ⇒ x = [a]_~, y = [a]_~, per qualche a,a'_~ ∈ A, [a]_~ ≠ [a']_~ e [a]_~ ∩ [a']_~ ≠ ∅ ⇒ ∃ ce ∈ ([a]_~ ∩ [a]₁)_~ ⇒ c ~ a, c ~ a' ⇒ a ~ c ~ a' ⇒ a ~ a'.

Mostriamo che [a]_~ = [a']_~

(S) Se [a]_~ ~ b ∈ A, b ~ a ⇒ b ~ a' ⇒ b ∈ [a']_~

(S) se [a']_~ ~ a ⇒ a ~ a' ⇒ a' ~ a ⇒ a' ~ d ⇒ d ∈ [a]_~

⇒ [a]_~ = [a']_~ e contraddice [a]_~ ≠ [a]_~

Esercizio 1:

A insieme, relaz. di equivalenza su A, a,b∈A.

[a]_~∩[b]_~≠∅ ⇔ a∼b

(⇒) Sia [a]_~∩[b]∼ ⇒ a∈[a]_~ - [b]_~ ⇒ a∼b

(⇐) a∼b Mostriamo che [a]_~∩[b]_~ ≠ ∅:

a. (C) x∈[a]_~ ⇔ x∈A, x∼a ⇒ x∼b ⇒ x∈[b]_~

b. (2) x∈[b]_~ ⇒ x∈A, x∼b ⇒ b∼a ⇒ x∼a ⇒ x∈[a]_~

Esercizio 2:

A insieme, ∼ un'equivalenza, a,b∈A.

[a]_∼∩[b]_∼ = ∅ ⇐⇒ ⊬ a∼b

Se a∼b ⇒ [a]_∼ ≠ [b]_∼ ⇒ [a]_∼∩[b]_∼ = ∅

Se invece a∼b ⇒ [a]_∼∩[b]_∼ ≠ ∅ ⇔ [a]_∼∩[b]_∼ = [a]_∼∩[a]_∼ = [a]_∼ = [b]_∼ ⇒ a ∼ b

Prop.: Sia A insieme e X una partiz. di A. Sia ∼_X la relazione su A definita

∀ a,b ∈A, a∼_X b ⇔ ∃X∈X t.c. a ∈ X e b ∈ X ⇒ ∼_X è una relaz. di

equivalenza su A.

Dim.: ∼_X è riflessiva: Se a∈A ⇒ X=∪³ X ⇒ ∃X ∈ X t.c. a∈X ⇒ a∈X e a∈X

∼_X è simmetrica: Se a, b∈A e a∼_Xb ⇒ ∃X ∈ X t.c. a∈X e b∈X ⇒ b∈X e

a∈X ⇒ b∼_X a

∼_X è transitiva: a,b,c∈A, a∼_Xb, b∼_X c ⇒ ∃X∈X³ t.c. a∈X e b∈X ed

∃Y∈X³ t.c. b∈Y e c∈Y ⇒ b∈X∩Y ≠ ∅ ⇒ X∩Y ≠ ∅ ⇒ x = y ⇒ x∈a∈X,c∈Y = x

⇒ a∼_X c

A insieme

{∼ relaz. e su A} ⇔ {X^1-1 [X]^X partizione di A}

(∼)

∼_X ⊭

Esercizi per Casa: 7.5, 7.6, 7.13, 7.14

a,b congrui modulo n se n|(a-b) [= _n]

relazione banale ∼ ≪A×A⊆A×A≫ [= _a]

uguaglianza ≡ congruenza modulo 0 [= ₀]

→ ψ è biunivoca

λ: ℤ → ℚ

z ↦ χ(z) = { z se z≥0 -z se -z≥0

sia ρ: ℕ → ℤ biunivoca

χoρ: ℕ →ℚ biunivoca →ℚ è numerabile

Prop. 9.18: ℝ non è numerabile

Dim. notazione: ∀r ∈ R . In notazione decimale, r = r_n r_n-1 r_n-2 ... r₁r₀ . r_-1r_-2 ... r_-n

∃p ∈ℕ t.c. p = ±(r_n) = ... = 9

per assurdo ∃p : ℕ → ℝ → biunivoca

n → p(n)

definisco ∀i∈ N, b_i = { 0 se f_i è cifre no nel punto · poi i ± 0 1/2 se f_i dea cifre no nel punto · poi i_i = 0

costruisco un reale b ∈ (0,1) t.c. b_j ≠ p_j — contradd.

n.t. b₁b₂b₃... ∈ decim. sono 0 ≤ ≤1

b≠p(n), se per assurdo b=p(n), n ∃cifra n ≠ p(n)_n= &sumorall; or b_n = 1

vé = p(n), ∃ke 1 ogni p, n_p è l'uguale

∴ un reale b ∈ℝ → ℝ non è numerabile𝕋

22.10.2021 NO lezione [Insiemi parzialmente o totalmente ordinati]

27.10.2021

Correzione es da 10.4 a 10.7

guardare esercizi

(A, ≤), (B,≤) due insiemi parzialmente ordinati; Un'applicazione f : A → B si dice: a. Un omomorfismo (di ins. parzialmente ordinati) se ∀a,a' ∈ A, a ≤ a' ⇒ f(a) ≤ f(a')

b. un isomorfismo se f è una biiezione e ∀a,a'∈ A, a≤a'⇔ f(a)≤f(a')

Un insieme parzialmente ordinato si dice bene ordinato se ogni sottoinsieme≠∅ di A Ha minimo

(N, ≤) è bene ordinato

(Z, ≤) non è bene ordinato ( ℤ non ha minimo )

(R, ≤) non è bene ordinato

28.10.2021

Reticolo

Un reticolo L è un insieme parzialm. ordinato tale ∀x,y ∈ L ∃ estremi inferiore e superiore di x,y.

11.7

da guardare

ret. distributivo - V distribuisce rispetto a ∧ e ∨ distribuisce rispetto a ∨.

ret. limitato = ∃0,1; = max e l.

ret. L limitato. Un elemento a è complemento di un elem. b (a/b) se a∨b=1 e a∧b=0.

proposizione: sia L un reticolo distributivo e limitato. Se a ∈ L ha un complement, allora tale complement è unico.

ret. booleano = ret. Limitato Complementato e distributivo.

esempi ed esercizi

Grafi

Un grafo è un insieme V≠∅ con 1 relazione E su V che è simmetrica e non riflessiva (∀a∈V, a ∉ a?). β′ = ∀ a ∈ V, aρa) ⇒ ∃ a∈V t.c. a β′a

∀u,v ∈ V, aρa, a ≤ b se aρb

Terminologia

• Archi incidenti
• Vertici adiacenti
• Isomorfismo di grafi: se G=(V,L) e G’=(V’,L’) sono 2 grafi, un isomorfismo di G in G’ è una biezione φ: V→V‘ t.c. ∀v,r,w ∈ V ∃v’,w∈V’ t.c. {v,r}∈L ⇔ {v’,w}∈L’

Sottografo: G’=(V’,L’), G’=(V’,L’) grafi. G’ si dice un sottografo di G se V’⊆V e L⊆L’

Un grafo G=(V,L) è finito se V è finito. V finito con card. n ⇒ |δ(V)|=2n ⇒ |L|