Appunti di Algebra 1

13.10.2021 Equivalenze e partizioni

Relazione di equivalenza: A insieme, corrispondenza di A in A = ρ ⊆ A x A [aρb]

Corrispondenza ρ di un insieme A in un insieme B = ρ ⊆ A x B

Una relazione ρ su A si dice:

1. Riflessiva: aρa ∀a ∈ A
2. Simmetrica: aρb ⇒ bρa ∀a,b ∈ A
3. Transitiva: aρb e bρc ⇒ aρc ∀a,b,c ∈ A

d) una relazione di equivalenza (o equivalenza): se ρ, R, S = ⊤ [~ , ≅, ≡, =]

Sia A insieme, e ρ una relazione di equivalenza 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

Servono per rappresentare le relazioni di equivalenza. Collego gli elementi in relazione tra loro da delle frecce.

Partizioni di un insieme

Def: sia A insieme, una partizione di A è una famiglia di sottoinsiemi di A

1. a. x ≠ ∅ ∀ x ∈ U x = A
2. x, y ∈ e x ≠ y ⇒ x ∩ y = ∅

Prop: se ρ è un insieme, e ~ è 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 A.

a. [a₁] ≠ ∅ per prop. R) ⇒ a ∈ [a₁] ⇒ [a₁] ≠ ∅ ∀a ∈ A

b. [a₁] ⊆ A ⇒ ⋃_{a ∈ A} [a₁] = A & ⊆ ⋃_{a ∈ A} [a₁] = A

A ⊆ ⋃ [a₁] se x ∈ A ⇒ x ∈ [x₁] ⊆ ⋃ [a₁]

c. dobbiamo dim. che x, y ∈ A/ ρ e x ≠ y ⇒ x ∩ y = ∅

Per assurdo: scegliamo x, y ∈ i A/ ρ, x ≠ y e x ∩ y ≠ ∅ ⇒ x = [x_..], y = [y_..] per qualche a',a" ∈ A, [a₁,_..] ≠ [a₂,_..] e [a₁,_..] ∩ [a₁"] ≠ ∅ ⇒ ∃ c ∈ [a₁] ∩ [a₁"] ⇒ x ~ a₁ ⇔~ a' = a ∩ c ⇒ a ~ a'

Mostriamo che [a₁] = [a₁"].

(c) b ∈ [a_..] ⇒ b ∈ A, b ∈ a' ⇒ b ~ a' ⇒ b ~ a ⇒ b ∈ [a₁"](sa) d ∈ [a₁"] ⇒ d ~ a' ⇒ a' ~ a ⇒ d ~ a ⇒ d ∈ [a₁] = [a₁"] = [a₁"] è contraddice [a₁], ≠ [a₁"]

13.10.2021 Equivalenze e partizioni

pag. 59

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 P su A si dice:

1. Riflessiva: aPa ∀ a ∈ A
2. Simmetrica: aPb ⇒ bPa ∀ a,b ∈ A
3. Transitiva: aPb ∧ bPc ⇒ aPc ∀ a,b,c ∈ A

di una relazione di equivalenza (o equivalenza): se ∀ R, S ⊆ T [~, , &sub1;] e [~, =, ⊆]

Sia A insieme, ~ una relazione di or. 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

Servono per rappresentare le relazioni di equivalenza. Collego gli elementi in relazione tra loro da delle frecce.

Partizioni di un insieme

Def: sia A insieme, una partizione di A è una famiglia ϖ³ di sottoinsiemi di A

1. c.: X ≠ Ø ∀ x ∈ ϖ
2. ∪ X = A
3. X, Y ∈ ϖ e X ≠ Y ⇒ X ∩ Y = Ø

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

Dim: A/~ = { [a_α] | α ∈ I } e [a_α] = { x ∈ A | x ~ a_α } ⊆ A = A/~ è una famiglia di sottoinsiemi di A.

a. [ ]_α e A/ = {x ∈ A | x ~ a}_α ⇒ a ε [a] θ ⇒ [a]_α ≠ Ø ∀ e ∈ A

b. [ ]_α ⊆ A = ∪_αε [ ]_α = A

A ⊆ ∪ [a]_α: se x ε A ⇒ x ε [x]_θ ∪_αε[ ]_θ = ∪_θ = A

c. dobbiamo dim. che x ε Y ε A/∆ e X ≠ Y ⇒ X ∩ Y = Ø

Per assurdo scegliamo x, Y ε A/ ∆ X ≠ Y ε X ∩ Y ≠ Ø ⇒ x ~= x ~ o o a~ A & b[~]n per qualche o a, β ε A, [ ]_α ≠ [ ]_Ø ∩ [ ]_Ø ¬= Ø ⇒ c [a]_n ⇒ c ~= a₁:

Mostriamo che [ ]_Ø = [ ]2

(c) b ε [a]~