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))ᶜ.
