Opomba: na predavanjih bomo najprej še definirali produkte in koprodukte družin množic.

Lastnosti preslikav

Mnogi ste v srednji šoli že spoznali osnovne lastnosti preslikav, kot so injektivnost, surjektivnost in bijektivnost preslikave. V tej lekciji ponovimo te pojme in jih povežemo še s pojmoma monomorfizem in epimorfizem, ki sta pomembna v algebri

Osnovne lastnosti preslikav

Injektivna, surjektivna, bijektivna preslikava

Definicija: Preslikava f : A → B je

• injektivna, ko velja ∀ x y ∈ A . f(x) = f(y) ⇒ x = y
• surjektivna, ko velja ∀ y ∈ B . ∃ x ∈ A . f(x) = y
• bijektivna, ko je surjektivna in injektivna

Opomba: Pogosto vidimo definicijo injektivnosti, ki pravi, da f slika različne elemente v različne vrednosti, se pravi ∀ x y ∈ A . x ≠ y ⇒ f(x) ≠ f(y). Ta definicija je ekvivalentna naši, a jo ne priporočamo, ker je manj uporabna. Naša definicija namreč podaja recept, kako preverimo injektivnost: predpostavimo f(x) = f(y) in od tod izpeljemo x = y tako, da predelamo enačbo f(x) = f(y) v enačbo x = y. To je v splošnem lažje kot predelava neenačb v neenačbe.

Naloga: primerjaj definicijo injektivnosti z zahtevo, da mora biti prirejanje, ki določa preslikavo, enolično.

Naloga: primerjaj definicijo surjektivnost z zahtevo, da mora biti prirejanje, ki določa preslikavo, celovito.

Monomorfizmi in epimorfizmi

Definicija: Preslikava f : A → B je

• monomorfizem (mono), ko jo lahko krajšamo na levi: ∀ C ∈ Set ∀ g, h : C → A . f ∘ g = f ∘ h ⇒ g = h

• epimorfizem* (epi), ko jo lahko krajšamo na desni: ∀ C ∈ Set ∀ g, h : B → C . g ∘ f = h ∘ f ⇒ g = h

Pojma monomorfizem in epimorfizem sta uporabna, ker nam omogočata, da krajšamo funkcije, ki nastopajo v enačbah. Na vajah boste reševali naloge, kjer to pride prav.

Izrek 1: Naj bosta f : A → B in g : B → C preslikavi.

1. Kompozicija monomorfizmov je monomorfizem.
2. Kompozicija epimorfizmom je epimorfizem.
3. Če je g ∘ f monomorfizem, je f monomorfizem.
4. Če je g ∘ f epimorfizem, je g epimorfizem.

Dokaz:

1. Naj bosta f : A → B in g : B → C monomorfizma. Dokazujemo, da je g ∘ f tudi monomorfizem. Naj bosta h, k : D → A preslikavi, za kateri velja (g ∘ f) ∘ h = (g ∘ f) ∘ k. Dokazujemo h = k. Ker je kompozicija preslikav asociativna, velja g ∘ (f ∘ h) = (g ∘ f) ∘ h = (g ∘ f) ∘ k g ∘ (f ∘ k). Ker je g monomorfizem, ga smemo krajšati na levi, torej dobimo f ∘ h = f ∘ k. Ker je f monomorfizem, ga smemo krajšati in dobimo želeno enakost h = k.

2. Dokaz je podoben 1, le vloga leve in desne strani se spremeni (vaja).

3. Dokaz je podoben 4, le vloga leve in desne strani se spremeni (vaja).

4. Naj bosta f : A → B in g : B → C preslikavi in g ∘ f epimorfizem. Dokazujemo, da je g epimorfizem. Naj bosta h, k : C → D taki preslikavi, da velja h ∘ g = k ∘ g. Dokazujemo, da je h = k. Iz h ∘ g = k ∘ h sledi (h ∘ g) ∘ f = (k ∘ g) ∘ f. Če upoštevamo asociativnost kompozicije, dobimo h ∘ (g ∘ f) = k ∘ (g ∘ f). Ker je g ∘ f epimorfizem, ga smemo krajšati na desni, od koder dobimo želeno enakost h = k. □

Izrek 2: Za preslikavo f : A → B velja

1. f je monomorfizem ⇔ f je injektivna
2. f je epimorfizem ⇔ f je surjektivna
3. f je izomorfizem ⇔ f je bijektivna

Dokaz:

1. Če je f monomorfizem in f(x) = f(y), tedaj je (f ∘ (u ↦ x)) () = f(x) = f(y) = (f ∘ (u ↦ y)) (), torej (u ↦ x) = (u ↦ y) torej x = y.

   Če je f injektivna in f ∘ g = f ∘ h, potem je za vsak x f(g(x)) = f(h(x)), torej g(x) = h(x) za vsak x, torej g = h.

2. Če je f epimorfizem: obravnavajmo množico

    S = { z ∈ B | ∃ x ∈ A . f(x) = z }

   ter preslikavi χ_S : B → 2 in (y ↦ ⊤) : B → 2. Ker velja χ_S ∘ f = (y ↦ ⊤) ∘ f, sledi χ_S = (y ↦ ⊤), torej S = B, kar je surjektivnost.

   Če je f surjektivna in g ∘ f = h ∘ f: naj bo y ∈ B. Obstaja x ∈ A, da je f(x) = y. Torej je

    g(y) = g(f(x)) = h(f(x)) = h(y).

   Torej je g = h.

3. Če je f izomorfizem, potem

   • f je epi, ker je id_B = f ∘ f⁻¹ epi
   • f je mono, ker je id_A = f⁻¹ ∘ f mono

   Če je f bijektivna, potem je njen inverz f⁻¹ definiran s predpisom

   f(y) = ι x ∈ A . f(x) = y “tisti x, ki ga f slika v y”

   Dokazati je treba ∃! x . f(x) = y:

   • ∃ x . f(x) = y je surjektivnost f
   • ∀ x₁ x₂ . f(x₁) = y ∧ f(x₂) = y ⇒ x₁ = x₂ sledi iz injektivnosti f □

Retrakcija in prerez

Spoznajmo še pojem retrakcije in prereza. Na predavanjih bomo s sliko pojasnili, zakaj se tako imenujeta.

Definicija: Če sta f : A → B in g : B → A taki preslikava, da velja f ∘ g = id_B, pravimo:

• f je levi inverz g
• g je desni inverz f
• g je prerez preslikave f
• f je retrakcija iz B na A

Opomba: retrakcija in prerez ni isto kot izomorfizem!

Izrek 3: Retrakcija je epimorfizem, prerez je monomorfizem.

Dokaz:

Denimo, da velja f ∘ g = id, torej je f retrakcija in g prerez. Ker je id monomorfizem, je po izreku 1 tudi g monomorfizem. In ker je id epimorfizem, je po istem izreku f monomorfizem. □

Slike in praslike

Izpeljane množice

Naj bo f : A → B preslikava. Tedaj definiramo izpeljano množico

{ f(x) | x ∈ A } := { y ∈ B | ∃ x ∈ A . y = f(x) }

ter izpeljano množico s pogojem

{ f(x) | x ∈ A | φ(x) } := { y ∈ B | ∃ x ∈ A . φ(x) ∧ y = f(x) }

Običajno se piše izpeljano množico s pogojem kar

{ f(x) | x ∈ A ∧ φ(x) }

Primer: Množica vseh kvadratov naravnih števil je izpeljana množica { n² | n ∈ N }.

Slike in praslike

Definicija: Naj bo f : A → B preslikava:

1. Praslika podmnožice S ⊆ B je f^*(S) := { x ∈ A | f(x) ∈ S }.
2. Slika podmnožice T ⊆ A je f_*(T) := { y ∈ B | ∃ x ∈ A . f(x) = y }.

Kot vidimo, lahko sliko zapišemo tudi kot izpeljano množico

f_*(T) := { f(x) | x ∈ T }

Običajni zapis za prasliko f^*(S) je tudi f⁻¹(S), vendar tega zapisa mi ne bomo uporabljali, ker napačno namiguje, da ima f inverz. Boste pa ta zapis videli marsikje drugje, ker so matematiki pravzaprav precej konzervativni in ne marajo sprememb.

Običajni zapis za sliko f_*(S) je tudi f(S) ali f[S]. Predvsem f(S) se uporablja v praksi, a tudi tega odsvetujemo. Kako naj pri takem zapisu ločimo med f(x) in f_*({x})?

Zaloga vrednosti je slika domene, torej f_*(B).

Slike in praslike kot preslikave višjega reda

Naj bo f : A → B. Tedaj sta tudi f^* in f_* preslikavi:

• f^* : P(B) → P(A) je določena s predpisom S ↦ { x ∈ A | f(x) ∈ S }
• f_* : P(A) → P(B) je določena s predpisom T ↦ { f(x) | x ∈ T }

Še več, tudi “zgoraj zvezdica ^*” in “spodaj zvezdica _*” sta preslikavi

^* : B^A → P(A)^P(B)
_* : B^A → P(B)^P(A)

Ker slikata preslikave v preslikave, pravimo, da sta to preslikavi višjega reda. Primer preslikave višjega reda je tudi odvod, ki funkciji priredi njen odvod.

Lastnosti slike in praslike

Izrek 4: Naj bo f : A → B preslikava:

• praslike so monotone: če je S ⊆ T ⊆ A, potem je f_*(S) ⊆ f_*(T)
• slike so monotone: če je X ⊆ Y ⊆ B, potem je f^*(X) ⊆ f^*(Y).

Dokaz: Vaja.

Izrek 5: Prasike ohranjajo preseke in unije: za vse f : A → B in S : I → P(B) velja

• f^* (⋃_{i ∈ I} S_i) = ⋃_{i ∈ I} f^*(S_i)
• f^* (⋂_{i ∈ I} S_i) = ⋂_{i ∈ I} f^*(S_i)

Dokaz: Dokažimo prvo izjavo, druga je zelo podobna, le da ∃ zamenjamo z ∀.

Dokazujemo f^* (⋃_{i ∈ I} S_i) ⊆ ⋃_{i ∈ I} f^*(S_i). Naj bo x ∈ f^* (⋃_{i ∈ I} S_i) in dokazujemo x ∈ ⋃_{j ∈ I} f^*(S_j). Ker je f x ∈ ⋃_{i ∈ I} S_i obstaja k ∈ I, da je f x ∈ S_k, torej je x ∈ f^* S_k ⊆ ⋃_{i ∈ I} f^*(S_i). □

Izrek 6: Naj bo f : A → B in T : I → P(A). Tedaj je

• f_* (⋃_{i ∈ I} T_i = ⋃_{i ∈ I} f_*(T_i).
• f_* (∩_{i ∈ I} T_i) ⊆ ⋂_{i ∈ I} f_*(S_i).

Dokaz: Vaja.

Naloga: Iz zgornjih dveh izrekov izpeljite naslednja dejstva:

• f^*(∅) = ∅
• f_*(∅) = ∅
• f^*(B) = A
• f^*(S ∪ T) = f^*(S) ∪ f^*(T)
• f^*(S ∩ T) = f^*(S) ∩ f^*(T)

Poleg tega imamo za S ⊆ B

f^*(Sᶜ) = (f^*(S))ᶜ.