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. Relacija “vzporednost” med premicami v ravnini.
  2. Relacija “skladnost” med trikotniki v ravnini.
  3. Relacija “podobnost” med trikotniki v ravnini.
  4. Relacija “isti ostanek pri deljenju s 7” na množici ℕ.
  5. Prazna relacija ∅ ⊆ A × A je ekvivalenčna le v primeru, da je A = ∅.
  6. Polna relacija A × A je ekvivalenčna.
  7. Diagonala (oz. enakost) je ekvivalenčna relacija.

Ekvivalenčna relacija porojena s preslikavo

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 njen 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 }. Z besedami: ekvivalenčni razred x je množica vseh elementov, ki so mu ekvivalentni.

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/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. Podobno 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:

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.

Definicija: Naj bo E ekvivalenčna relacija na A. Množico C ⊆ A, ki vsak ekvivalenčni razred relacije E seka natanko enkrat, imenujemo izbor predstavnikov (ekvivalenčnih razredov) za relacijo E.

Izbor predstavnikov C ⊆ A za E določa preslikavo c : A/E → A, ki priredi ekvivalenčnemu razredu ξ tisti x ∈ ξ, ki je element C:

c : A/E → A
c : ξ ↦ (ι x ∈ ξ . x ∈ C)

Preslikava c : A/E → A je prerez kvocientne preslikave q_E : A → A/E.

Trditev: Če je s : A/E → A prerez kvocientne preslikave q_E : A → A/E, potem je njegova slika s_*(A/E) = { c(ξ) | ξ ∈ A/E } izbor predstavnikov za E.

Dokaz: Vaja. □

Ker izbor predstavnikov in prerez kvocientne preslikave določata drug drugega, včasih tudi prerez imenujemo “izbor predstavnikov”.

Primer: Definirajmo ∼ na množici celih števil Z s predpisom

a ∼ b ⇔ 7 | a - b

Torej sta števili a in b ekvivalentni, če dasta enak ostanek pri deljenju s 7, na primer 13 ~ 20 in ¬ (13 ~ 15).

Ekvivalenčni razred števila a dobimo tako, da a prištejemo vse večkratnike števila 7:

[a]_∼ = { a + 7 · k | k ∈ ℤ }

Na primer,

[13]_~ = { 7 · k + 13 | k ∈ ℤ }
       = { ..., -22, -15, -8, -1, 6, 13, 20, 27, 34, 41, ...}

Koliko pa je ekvivalenčnih razredov? Toliko, kot je ostankov pri deljenju s 7, torej 7. Izbor predstavnikov za ~ je torej množica {0, 1, 2, 3, 4, 5, 6}, saj je vsako celo število ekvivalentno natanko enemu od teh števil mo modulu 7.

Ni pa to edini izbor! Tudi {0, 1, 2, 3, 4, 5, 6, 13} je izbor, prav tako pa {-7, -6, -5, -4, -3, -2, -1}.

(Konec primera.)

Ali ima vsaka ekvivalenčna relacija izbor predstavnikov? Da to vprašanje ni tako enostavno, kot se zdi na prvi pogled, doma premislite o nalslednji nalogi.

Naloga: Na množici realnih števil ℝ definiramo relacijo E s predpisom

x E y  ⇔  x - y ∈ ℚ

Se pravi, da sta števili ekvivalentni, če je njuna razlika racionalno število. Podajte kak izbor predstavnikov za E.

Izrek: Naslednje izjave so ekvivalentne:

  1. Vsaka surjektivna preslikava ima desni inverz (prerez).
  2. Vsaka ekvivalenčna relacija ima izbor predstavnikov.
  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 pr₁ : S → I, t.j.,

inᵢ(x) ∼ inⱼ(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 pr₁(u) = pr₁(v). Definirajmo f : I → ⋃ A s predpisom

f(i) := tisti x ∈ A_i, za katerega je inᵢ(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) je produkt te družine neprazen, torej vsebuje neko 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: