Ekvivalenčne relacije in kvocientne množice

Ekvivalenčne relacije

Definicija: Relacija R ⊆ A × A je ekvivalenčna relacija, če je refleksivna, tranzitivna in simetrična. Kadar velja x R y, pravimo, da sta x in y ekvivalentna (glede na R).

Opomba: Kdor reče "ekvivalentna relacija", je noob. Kdor reče, da sta "x in y ekvivalenčna", je rookie.

Ekvivalenčne relacije se običajno označuje s simboli, ki so podobni znaku za enakost: ≡, ∼, ≃, ≅.

Primeri:

  1. Prazna relacija ∅ ⊆ A × A je ekvivalenčna le v primeru, da je A = ∅.
  2. Polna relacija A × A je ekvivalenčna.
  3. Diagonala (oz. enakost) je ekvivalenčna relacija.
  4. Ostali primeri: vzporednost premic, skladnost trikotnikov, podobnost trikotnikov.

Posebej pomemben je primer ekvivalenčne relacije porojene (ali inducirane) s preslikavo: naj bo f : A → B preslikava in definirajmo relacijo ∼_f ⊆ A × A s predpisom

x ∼_f y ⇔ f(x) = f(y)

Tedaj je ∼_f ekvivalenčna relacija:

Ali je vsaka ekvivalenčna relacija porojena z neko preslikavo?

Primer: premici sta vzporedni natanko tedaj, ko imata enaka smerna vektorja. Če je torej P množica vseh premic, R² množica vektorjev v ravnini, in s : P → R² preslikava, ki premici P priredi enotski smerni vektor, ki leži v zgornji polravnini ali na pozitivnem delu osi x, tedaj velja

p ∥ q ⇔ s(p) = s(q)

Torej je vzporednost porojena s preslikavo s.

Ekvivalenčni razredi in kvocientne množice

Definicija: Naj bo E ⊆ A × A ekvivalenčna relacija. Ekvivalenčni razred elementa x ∈ A je množica [x]_A := { y ∈ A ∣ x E y }.

Opomba: Kdor reče "ekvivalentni razred", je newbie.

Definicija: Naj bo E ⊆ A × A ekvivalenčna relacija. Kvocientna množica ali kvocient A/E je množica vseh ekvivalenčnih razredov:

A/E := { ξ ⊆ P(A) | ∃ x ∈ A . ξ = [x]_A }.

Z izpeljanimi množicami lahko to zapišemo bolj razumljivo (a tudi bolj zavajajoče):

A/E = { [x]_E | x ∈ A }.

Kanonična kvocientna preslikava q_E : A → A/E je preslikava, ki vsakemu elementu priredi njegov ekvivalenčni razred: q_E(x) := [x]_A.

Kvocientni množici včasih pravimo tudi faktorska množica.

Izrek: Vsaka ekvivalenčna relacija je porojena z neko preslikavo.

Dokaz. Naj bo E ekvivalenčna relacija na A. Najprej ugotovimo naslednje: za vse x, y ∈ A velja

x E y ⇔ [x]_E = [y]_E

Dokaz ⇒: če je x E y potem je [x]_E ⊆ [y]_E, ker iz z E x in x E y sledi z E y. Simetrično dokažemo [y]_E ⊆ [x]_E.

Dokaz ⇐: če je [x]_E = [y]_E potem je y ∈ [y]_E = [x]_E, torej po definiciji [x]_E dobimo x E y.

Sedaj izrek sledi zlahka: q_E(x) = q_E(y) ⇔ [x]_E = [y]_E ⇔ x E y □

Razdelitev množice

Definicija: Razdelitev ali particija množice A je množica nepraznih, paroma disjunktnih množic, ki tvorijo pokritje A (kar pomeni, da je A enaka njihovi uniji). Se pravi, to je množica S ⊆ P(A), za katero velja:

  1. Elementi razdelitve so neprazni: ∀ B ∈ S . B ≠ ∅
  2. Vsaka dva elementa razdelitve sta bodisi enaka bodisi disjunktna: ∀ B, C ∈ S . B = C ∨ B ∩ C = ∅
  3. Elementi razdelitve tvorijo pokritje A: A = ⋃ S.

Primer: navpične premice tvorijo razdelitev ravnine. Množici sodih in lihih števil tvorita razdelitev naravnih števil.

Izrek: Naj bo E ⊆ A × A ekvivalenčna relacija. Njeni ekvivalenčni razredi tvorijo razdelitev množice A.

Dokaz.

  1. Naj bo ξ ∈ P(A) ekvivalenčni razred za E. Tedaj obstaja x ∈ A, da je ξ = [x]_A, torej je x ∈ ξ in zato ξ ≠ ∅.

  2. Naj bosta ζ, ξ ∈ P(A). Dokazali bomo ζ ∩ ξ ≠ ∅ ⇒ ζ = ξ. Če je x ∈ ζ ∩ ξ, potem velja ζ ⊆ ξ ker: naj bo y ∈ ζ, tedaj je y E x in ker je x ∈ ξ velja y ∈ ξ. Simetrično dokažemo `ξ ⊆ ζ.

  3. Očitno je unija vseh ekvivalenčnih razredov podmnožica A, saj je vsak ekvivalenčni razred podmnožica A. Zagotovo pa je vsak x ∈ A v kakem ekvivalenčnem razredu, namreč x ∈ [x]_A. □

Torej vsaka ekvivalenčna relacija na A določa razdelitev mnnožice A, namreč na ekvivalenčne razrede. Velja pa tudi obrat: vsaka razdelitev S ⊆ P(A) določa ekvivalenčno relacijo na A, namreč ≃_S definiran s predpisom

x ≃_S y ⇔ ∃ B ∈ S . x ∈ B ∧ y ∈ B

Z besedami: x in y sta ekvivalentna, kadar sta v istem elementu razdelitve. Prazvzaprav smo ugotovili, da imamo izomorfizem množic:

{ E ⊆ A × A | E je ekvivalenčna relacija } ≅ { S ⊆ P(A) | S je razdelitev A }

V eno smer izomorfizem ekvivalenčni relaciji E priredi njeno razdelitev, v drugo pa razdelitvi priredimo ekvivalenčno relacijo, kakor smo to opisali zgoraj. (Premislite, da sta ti preslikavi inverza.)

Prerezi kvocientne preslikave in aksiom izbire

Ekvivalenčni razred je natanko določen že z enim od svojih elementov, zato pogosto želimo namesto ekvivalenčnih razredov navesti le njihove predstavnike.

Primer: naj bo n > 1 in definirajmo ∼ na množici celih števil Z s predpisom

a ∼ b ⇔ n | a - b

Števili a in b sta ekvivalentni, če dasta enak ostanek pri deljenju z n. Torej velja

[a]_∼ = { n · k + a | k ∈ Z }

Ali lahko na kak koristen način iz razreda [a]_∼ izberemo enega predstavnika? (Pozor: če rečemo, da smo iz razreda [a]_∼ izbrali kar a, to ni dobra definicija, saj a ni enolično določen z razredom [a]_∼, velja na primer [a]_∼ = [a + 3 n]_∼.) Po izreku o deljenju celih števil, obstaja natanko eno število r ∈ {0, 1, …, n-1}, da je r ∈ [a]_∼, in tega lahko vzamemo za prestavnika.

Naj bo E ekvivalenčna relacija na A. Izbor predstavnikov ekvivalenčnih razredov za E je pravzaprav preslikava c : A/E → A, da velja [c(ξ)]_E ∈ ξ za vse ξ ∈ A/E, kar lahko zapišemo tudi kot

q_E ∘ c = id_{A/E}

Torej je izbor predstavnikov ekvivalenčnih razredov kar prerez kvocientne preslikave. Slika takega izbora c je množica

{ c(ξ) ∈ A | ξ ∈ A/E }

ki vsak ekvivalenčni razred seka natanko enkrat. V splošnem množici C ⊆ A, ki vsak ekvivalenčni razred relacije E seka natanko enkrat, imenujemo izbor predstavnikov (ekvivalenčnih razredov) za relacijo E. Kot smo videli, vsak prerez q_E določa izbor predstavnikov. Velja pa tudi obratno: vsak izbor predstavnikov C ⊆ A določa prerez c : A/E → A, definiran s predpisom:

c(ξ) := tisti x ∈ A, da je x ∈ C ∩ ξ

Pa ima vsaka ekvivalenčna relacija izbor predstavnikov?

Izrek: Naslednje izjave so ekvivalentne:

  1. Vsaka surjektivna preslikava ima desni inverz (prerez).
  2. Vsaka ekvivalenčna relacija ima izbor predstavnikov ekvivalenčnih razredov.
  3. Vsaka družina nepraznih množic ima funkcijo izbire.
  4. Produkt družine nepraznih množic je neprazen.

Dokaz.

(1 ⇒ 2): Naj bo E ⊆ A × A ekvivalenčna relacija na A. Tedaj je q_E : A → A/E surjektivna, zato ima po predpostavki (1) prerez, ki določa izbor predstavnikov.

(2 ⇒ 3): Naj bo A : I → Set družina nepraznih množic. Naj bo ∼ ekvivalenčna relacija na koproduktu K := ∐_{i ∈ I} A_i, porojena s prvo projekcijo π_1 : S → I, t.j.,

ι_i(x) ∼ ι_j(y) ⇔ i = j

Po predpostavki (2) obstaja izbor predstavnikov za ∼, se pravi taka množica C ⊆ K, da za vsak u ∈ K obstaja natanko en v ∈ C, da je π_1(u) = π_1(v). Definirajmo f : I → ⋃ A s predpisom

f(i) := tisti x ∈ A_i, za katerega je ι_i(x) ∈ C

Očitno je f funkcija izbire za družino A, če je le dobro definirana:

(3 ⇒ 4): Elementi produkta so funkcije izbire, zato je produkt res neprazen, če obstaja kaka funkcija izbire.

(4 ⇒ 1): Naj bo f : X → Y surjektivna. Definirajmo družino A : Y → Set s predpisom A_y = f^*({y}). Ker je f surjektivna, je A družina nepraznih množic. Po predpostavki (4) ima funkcijo izbire c : Y → ⋃ A_y, se pravi, da je f(c(y)) = y za vsak y ∈ Y. Opazimo še, da je ⋃ A = Y, torej je c prerez f. □

Izbor prestavnikov je torej ekvivalenten še nekaterim drugim trditvam. Pa te veljajo? Za to potrebujemo aksiom.

Aksiom izbire: Vsaka družina nepraznih množic ima funkcijo izbire.

Se pravi, če je A : I → Set taka družina množica, da za vsak i ∈ I velja A_i ≠ ∅, tedaj obstaja f : I → ⋃ A, za katerega je f(i) ∈ A_i za vse i ∈ I.

O aksiomu izbire bomo še govorili.

Univerzalna lastnost kvocientne množice

Naj bo E ekvivalenčna relacija na A in B množica. Pogosto želimo definirati preslikavo

f : A/E → B

s pomočjo preslikave A → B. Kdaj lahko to naredimo?

Izrek: Naj bo E ekvivalenčna relacija na A in g : A → B preslikava, ki je skladna z E, kar pomeni da g slika ekvivalentne elemente v enake, se pravi ∀ x, y ∈ A . x E y ⇒ g(x) = g(y). Tedaj obstaja natanko ena preslikava f : A/E → B, da je f([x]_E) = g(x) za vse x ∈ A, ali drugače povedano, f ∘ q_E = g.

Dokaz.

Dokažimo najprej, da imamo največ eno tako preslikavo. Denimo da za f₁ : A/E → B in f₂ : A/E → B velja f₁ ∘ q_E = f₂ ∘ q_E. Ker je q_E surjektivna, je epi in jo smemo krajšati na desni, od koder res sledi f₁ = f₂.

Sedaj dokažimo, da f obstaja. V ta namen naj bo φ ⊆ A/E × B relacija

φ(ξ, y) ⇔ ∃ x ∈ A . x ∈ ξ ∧ g(x) = y

Trdimo, da je φ funkcijska relacija:

Naj bo f : A/E → B preslikava, ki je določena s funkcijsko relacijo φ. Za x ∈ A velja φ([x]_E, f([x]_E)), od tod pa iz definicije φ sledi tudi g(x) = f([x]_E). □

Kanonična razčlenitev preslikave

Naj bo f : A → B preslikava. Naj bo ∼_f ekvivalenčna relacija na A, ki jo porodi f, in q_f : A → A/E kanonična kvocientna preslikava (morali bi jo pisati q_{∼_f}, kar je nečitljivo). Naj bo i : f_*(A) → B kanonična inkluzija slike f v kodomeno. Preslikava f : A → f_*(A) je skladna s ∼_f, zato obstaja (natanko ena) preslikava b_f : A/f → f_*(A), da velja b_f([x]_∼) = f(x). Trdimo:

  1. f = i_f ∘ b_f ∘ q_f
  2. q_f je surjektivna, b_f je bijektivna in i_f je injektivna.

Računajmo: f(x) = b_f([x]_~) = i_f(b_f([x]_~)) = i_f(b_f(q_f(x))), za vse x ∈ A, od koder sledi prva trditev.

Vemo že, da je kanonična kvocientna preslikava surjektivna in kanonična inkluzija injektivna. Ostane nam še bijektivnost preslikave b_f: