2. FUNKCIJOS

Funkcijos sa_{‘}voka yra viena iš pagrindiniu_{‘} matematikos sa_{‘}voku_{‘}. Priminsime, jei A ir B yra netuščios aibės, tai funkcija f, kurios apibrėžimo sritis yra aibė A, o reikšmiu_{‘} sritis – aibė B, kiekvienam a ∈ A priskiria vieninteli_{‘} elementa_{‘} b ∈ B. Elementas b vadinamas elemento a vaizdu ir žymimas b = f(a). Sakoma, kad yra žinoma funkcija f iš aibės A i_{‘} aibe_{‘} B ir žymima f : A → B.

Funkcijos f : A → B vaizdu vadiname aibe_{‘}

Im f = {f(a) | a ∈ A} = f(A) ⊆ B,

o aibė f^{−1}(b) = {a ∈ A | f(a) = b} ⊆ A vadinama elemento b ∈ B pirmavaizdžiu. Aibės B_{∘} ⊆ B pirmavaizdžiu vadinama aibė f^{−1}(B_{∘}) =

{a ∈ A | f(a) ∈ B_{∘}} = ⋃_{b∈B_{∘}} f^{−1}(b).

Binaru_{‘}ji_{‘} sa_{‘}ryši_{‘} suprantant kaip aibės A × B poaibi_{‘}, funkcija_{‘} f galima apibrėžti ir kaip sa_{‘}ryši_{‘} F ⊆ A × B, tenkinanti_{‘} sa_{‘}lyga_{‘}: su visais a ∈ A, b_{1}, b_{2} ∈ B iš (a, b_{1}) ∈ F, (a, b_{2}) ∈ F išplaukia b_{1} = b_{2}, t.y. aibės f(a) = {b | (a, b) ∈ F } galia ⩽ 1.

Kita vertus, kiekviena_{‘} binaru_{‘}ji_{‘} sa_{‘}ryši_{‘} R ⊆ A × B galima išreikšti funkcija f_{R} : A × B → {0, 1}. Priminsime, kad

f_{R}(a, b) = \{ \begin{matrix}1, & (a, b) ∈ R, \\ 0, & (a, b) ∉ R. \end{matrix}

Ši funkcija gali būti apibrėžta kaip sa_{‘}ryšis R_{f} ⊆ (A × B) × {0, 1}:

((a, b), c) ∈ R_{f} ⟺ f_{R}(a, b) = c.

Taigi tarp binariu_{‘} sa_{‘}ryšiu_{‘} ir funkciju_{‘} yra glaudus ryšis.

Aišku, kad funkcijai f : A → B ir sa_{‘}ryšiui F = {(a, b)|a ∈ A, b = f(a)} aibė F^{−1} = {(f(a), a) | (a, f(a)) ∈ F } yra sa_{‘}ryšis F^{−1} ⊆ B × A, bet ne visada funkcija iš B i_{‘} A.

3.1 pavyzdys. A = ℕ, B = ℕ, f : A → B ; f(n) = 2n, n ∈ ℕ.

Aibė f^{−1}(m) ≠ O / tada ir tik tada, kai m lyginis skaičius, todėl funkcijai F = {(n, 2n) | n ∈ ℕ} ⊆ A × B sa_{‘}ryšis F^{−1} = {(2n, n) | n ∈ ℕ} nėra funkcija iš B i_{‘} A.

3.2 pavyzdys. A = Z −{0}, B = {1, 4, 9, 16, …}, f : A → B; f(n) = n^{2}, n ∈ A.

Aibė f^{−1}(m) ≠ O / su visais m, bet funkcijai F = {(n, n^{2}) | n ∈ A} = A × B sa_{‘}ryšis F^{−1} = {(m, n) | n^{2} = m, n ∈ A, m ∈ B} nėra funkcija, nes f^{−1}(4) = {(4, 2), (4, −2)}.

3.3 apibrėžimai. 1. Funkcija f : A → B vadinama injektyvia_{‘}ja, arba injekcija, jeigu su visais a_{1}, a_{2} ∈ A, b ∈ B iš to, kad f(a_{1}) = b, f(a_{2}) = b išplaukia a_{1} = a_{2}, arba su visais a_{1}, a_{2} ∈ A ir a_{1} ≠ a_{2} gauname f(a_{1}) ≠ f(a_{2}).

2. Funkcija f : A → B vadinama siurjektyvia_{‘}ja, arba siurjekcija, jeigu f(A) = B, t.y. bet kuriam b ∈ B egzistuoja toks a ∈ A toks, kad f(a) = b.

3. Funkcija f : A → B vadinama bijektyvia_{‘}ja, arba bijekcija, jeigu ji yra ir injektyvi, ir siurjektyvi.

3.4 pavyzdžiai. 1. Tapati funkcija id_{A} : A → A, id_{A}(a) = a, a ∈ A yra bijekcija.

2. Funkcija f : ℕ → ℕ, kiekvienam natūraliajam n priskirianti Fibonačio skaičiu_{‘} fb_{n} : f(n) = fb_{n}, yra nei injektyvi, nes fb_{1} = fb_{2}, nei siurjektyvi, nes f^{−1}(4) = O /.

3. Funkcija φ_{n} : ℤ → ℤ_{n}, φ_{n}(a) = K_{n}(a) = \overline{a} yra siurjektyvi, nes bet koks sveikasis a ∈ \overline{a}, bet nėra injektyvi, nes φ_{n}(a) = φ_{n}(a + n), a ∈ ℤ.

4. Funkcija succ : ℕ → ℕ, apibrėžta formule succ(n) = n + 1, yra injektyvi, bet nėra siurjektyvi, nes succ^{−1}(1) = O /.

Jau matėme, kad ne visada funkcijai f sa_{‘}ryšis F^{−1} yra funkcija. Atsakysime i_{‘} klausima_{‘}, kada sa_{‘}ryšis F^{−1} yra funkcija. Tam talkins viena iš svarbiausiu_{‘} operaciju_{‘} su funkcijomis – funkciju_{‘} kompozicija (superpozicija, sandauga).

3.5 apibrėžimas. Funkciju_{‘} g : A → B ir f : B → C kompozicija vadinama funkcija iš aibės A i_{‘} aibe_{‘} C , žymima f ∘ g : A → C ir apibrėžta lygybe (f ∘ g)(a) = f(g(a)), ∀a ∈ A.

Funkciju_{‘} f ir g kompozicija_{‘}, kuria_{‘} vėliau žymėsime fg, patogu reikšti diagrama

\begin{aligned}A & ⟶ fg & C \\ ↘ g & & ↗ f \\ & B \end{aligned}

Ši diagrama vadina komutatyvia_{‘}ja, t.y. elemento a ∈ A vaizdas aibėje C nepriklauso nuo to, ar mes veiksime ši_{‘} elementa_{‘} funkcija fg, ar paveike_{‘} funkcija g, elementa_{‘} g(a) ∈ B veiksime funkcija f.

3.6 pavyzdžiai. 1. Jei f : A → B, tai f id_{A} = f, id_{B}f = f.

2. Tegu funkcija + : ℤ × ℤ → ℤ apibrėžta lygybe +(a, b) = a + b, o funkcija φ_{n} : ℤ → ℤ_{n}, φ_{n}(a) = K_{n}(a). Tai funkcija +_{n} = φ_{n} ∘+, apibrėžiama lygybe +_{n}(a, b) = K_{n}(a + b) = \overline{a + b}. Atskiru atveju, kai n = 5, tai +_{5}(3, 8) = \overline{3 + 8} = \overline{11} = \overline{1}.

Funkciju_{‘} kompozicija išsiskiria svarbia savybe:

3.7 teiginys (kompozicijos asociatyvumas). Jeigu h : A → B, g : B → C, f : C → D yra trys funkcijos, tai f(gh) = (fg)h.

I_{‘} rodymas. Kai a ∈ A, tai (f(gh))(a) = f((gh)(a)) = f(g(h(a))) =

(fg)(h(a)) = ((fg)h)(a).

△

3.8 pastaba. Funkciju_{‘} f, g : A → A kompozicija ne visada komutatyvi.

Pavyzdžiui, jei f : A → A, f(a) = b su visais a ∈ A, o g : A → A, g(a) = c su visais a ∈ A, b ≠ c, tai (fg)(a) = b ≠ c = (gf)(a) su visais a ∈ A.

3.9 apibrėžimas. Tegu f : A → B, g : B → A tokios funkcijos, kurioms apibrėžtos kompozicijos fg ir gf. Sakoma, kad funkcija g yra atvirkštinė funkcijai f, jeigu

gf = id_{A}, fg = id_{B}.

Žymima g = f^{−1}.

Pastebėsime, jeigu f(a) = b, tai f^{−1}(b) = a bet kokiems a ∈ A ir b ∈ B. Dabar esame pasirenge_{‘} pateikti funkcijos f atvirkštinės funkcijos f^{−1} egzistavimo sa_{‘}lyga_{‘}.

3.10 teiginys. Tegu f : A → B, g, g′ : B → A. Tada:

1) jeigu fg = fg′ = id_{B}, gf = g′f = id_{A}, tai g = g′ (atvirkštinės funkcijos vienatinumas);

2) funkcija f turi atvirkštine_{‘} tada ir tik tada, kai f yra bijekcija (atvirkštinės funkcijos egzistavimo sa_{‘}lyga).

I_{‘} rodymas. 1) g′ = id_{A}g′ = (gf)g′ = g(fg′) = g id_{B} = g.

2) Tegu egzistuoja f^{−1}. Tada, jeigu f(a) = f(a′), a, a′ ∈ A, tai a = id_{A}(a) = (f^{−1}f)(a) = f^{−1}(f(a)) = f^{−1}(f(a′)) = (f^{−1}f)(a′) = id_{A}(a′) = a′. Taigi funkcija f yra injekcija. Jeigu b ∈ B, tai b = id_{B}(b) = (f f^{−1})(b) = f(f^{−1}(b)), taigi f yra siurjekcija ir todėl bijekcija. Kita vertus, jei f yra bijektyvi funkcija, tai kiekvienam b ∈ B galima vienareikšmiškai priskirti toki_{‘} a ∈ A, kad galiotu_{‘} lygybė f(a) = b. Šis priskyrimas yra funkcija g : B → A, g(b) = a, išsiskirianti savybėmis: fg = id_{B}, gf = id_{A}. Taigi g = f^{−1}.

△

Pateiksime funkciju_{‘} ir ju_{‘} kompoziciju_{‘} savybes.

3.11 teiginys. Tegu f : A → B, g : B → C. Tada:

1) jeigu f, g yra injektyvios funkcijos, tai g ∘ f irgi injektyvi;

2) jeigu f, g yra siurjektyvios funkcijos, tai g ∘ f irgi siurjektyvi;

3) jeigu f, g yra bijektyvios funkcijos, tai g ∘ f irgi bijektyvi ir

(gf)^{−1} = f^{−1}g^{−1}.

I_{‘} rodymas. Mes i_{‘}rodysime 3) teiginio dali_{‘}, kitas palikdami i_{‘}rodyti savarankiškai.

Kadangi f ir g yra bijekcijos, tai egzistuoja ju_{‘} atvirkštinės funkcijos f^{−1} : B → A, g^{−1} : C → B ir šiu_{‘} funkciju_{‘} kompozicija f^{−1}g^{−1} : C → A. Ši funkciju_{‘} kompozicija yra atvirkštinė funkcijai gf, nes

\begin{aligned}(gf)(f^{−1}g^{−1}) & = ((gf)f^{−1})g^{−1} = (g(f f^{−1}))g^{−1} \\ & = (g id_{B})g^{−1} = g g^{−1} = id_{C}. \end{aligned}

\begin{aligned}(f^{−1}g^{−1})(gf) & = f^{−1}(g^{−1}(gf)) = f^{−1}((g^{−1}g)f) \\ & = f^{−1}(id_{B}f) = f^{−1}f = id_{A}. \end{aligned}

△

Baigtines aibes apibūdina toks teiginys:

3.12 teiginys. Aibė A yra baigtinė tada ir tik tada, kai patenkinta viena iš sa_{‘}lygu_{‘}:

1) jeigu f : A → A yra injekcija, tai f – bijekcija;

2) jeigu f : A → A yra siurjekcija, tai f – bijekcija;

3) egzistuoja toks natūralusis n ir bijekcija iš aibės A i_{‘} aibe_{‘} {1, 2, …, n}.

I_{‘} rodymas. I_{‘}rodysime tik tai, kad, jeigu A yra baigtinė aibė, o f : A → A yra injekcija, tai f – siurjekcija, kartu ir bijekcija.

Kadangi A – baigtinė aibė, tai kiekvienam a ∈ A begalinėje sekoje

\begin{aligned}a & = f^{0}(a), f^{1}(a), f^{2}(a) = f f(a), …, f^{k}(a) = f f^{k−1}(a) \\ & = \underbrace{(f f … f)}_{k}(a), … \end{aligned}

būtinai surasime du sutampančius elementus: f^{n}(a) = f^{m}(a), n > m. Jeigu m > 0, tai iš f injektyvumo ir lygybės f(f^{n−1}(a)) = f(f^{m−1}(a)) gausime f^{n−1}(a) = f^{m−1}(a), n−1 > m−1. Jeigu m−1 > 0, tai pakartoje_{‘} minėta_{‘} prastinima_{‘} baigtini_{‘} skaičiu_{‘} kartu_{‘}, turėsime f^{n−m}(a) = f^{0}(a) = a, n − m > 0. Tada f(f^{n−m−1}(a)) = a. Tai i_{‘}rodo f siurjektyvuma_{‘}.

△

Glaudžiausias ryšys tarp funkciju_{‘} ir ekvivalentumo sa_{‘}ryšiu_{‘} yra funkciju_{‘} faktorizacijos operacijoje.

Tegu f : A → B. Binarusis sa_{‘}ryšis E_{f} = {(a, a′) | f(a) = f(a′)} ⊆ A × A yra ekvivalentumo sa_{‘}ryšis, nes:

1) (a, a) ∈ E_{f}, t.y., f(a) = f(a);

2) jeigu (a, a′) ∈ E_{f}, tai (a′, a) ∈ E_{f}, t.y., jeigu f(a) = f(a′), tai f(a′) = f(a);

3) jeigu (a, a′), (a′, a′′) ∈ E_{f}, tai (a, a′′) ∈ E_{f}, t.y., jeigu f(a) = f(a′) ir f(a′) = f(a′′), tai f(a) = f(a′′).

Ekvivalentumo klasės K_{E_{f}} (a) = {a′ | f(a′) = f(a)} sudaro faktoraibe_{‘} A/E_{f}, kurioje apibrėžiama funkcija \overline{f} : A/E_{f} → B:

\overline{f}(K(a)) = f(a).

Funkcijos \overline{f} apibrėžimas yra korektiškas ta prasme, kad, jeigu a_{1}, a_{2} ∈ K(a), tai \overline{f}(K(a_{1})) = \overline{f}(K(a)) = f(a) = \overline{f}(K(a)) = \overline{f}(K(a_{2})), nes f(a_{1}) = f(a_{2}).

Sakoma, kad funkcija f indukuoja funkcija_{‘} \overline{f}.

3.13 teiginys. Tegu f : A → B, o siurjektyvioji funkcija p : A → A/E_{f}, p(a) = K_{E_{f}} (a) yra aibės A kanoninė projekcija faktoraibėje A/E_{f},

tai egzistuoja vienintelė funkcija \overline{f} : A/E_{f} → B, kurios dėka diagrama

A  ⟶ f  B
↘ p  ↗\overline{f}
A/E_{f}

yra komutatyvi, t.y. f = \overline{f} p; čia: \overline{f} – injekcija, o p – siurjekcija. Ši funkciju_{‘} \overline{f} ir p kompozicija ir vadinama funkcijos f faktorizacija.

I_{‘} rodymas. I_{‘}rodysime funkcijos \overline{f} vienatinuma_{‘}. Kiti teiginiai – tai tiesioginės apibrėžimu_{‘} išvados.

Tegu \overline{f}_{1} : A/E_{f} → B ir \overline{f}_{1}p = f, tada

\overline{f}_{1}(K(a)) = \overline{f}_{1}(p(a)) = (\overline{f}_{1}p)(a) = f(a) = \overline{f}(K(a)).
Taigi \overline{f}_{1} = \overline{f}.
△

3.14 pavyzdžiai. 1. Tegu f_{2} : ℤ → ℕ, f_{2}(n) = n^{2}, n ∈ ℤ. Tada funkcija f_{2} yra siurjekcijos p : ℤ → ℤ/E_{f_{2}} = {K_{f_{2}}(n) = {n, −n}, n ∈ ℤ} ir

injekcijos \overline{f}_{2} : ℤ/E_{f_{2}} → ℕ kompozicija f_{2} = \overline{f}_{2}p.

2. Tegu f_{1} : ℤ → ℕ, f_{1}(n) = |n|, n ∈ ℤ. Tada funkcija f_{1} yra siurjekcijos p : ℤ → ℤ/E_{f_{1}} = ℤ/E_{f_{2}} = {K_{f_{1}}(n) = {n, −n}, n ∈ ℤ} ir

injekcijos \overline{f}_{1} : ℤ/E_{f_{1}} → ℕ kompozicija: f_{1} = \overline{f}_{1}p.

Tegu E yra ekvivalentumo sa_{‘}ryšis aibėje A, o f : A → B – tokia funkcija, kurios ekvivalentumo sa_{‘}ryši_{‘} E_{f} atitinkantis aibės A skaidinys π_{f} yra sa_{‘}ryši_{‘} E atitinkančio aibės A skaidinio π viršskaidinys, t.y. jeigu π = {A_{i} | i ∈ I}, o π_{f} = {A′_{j} | j ∈ I}, tai bet kuriam i ∈ I egzistuoja toks j ∈ I, kad A_{i} ⊆ A′_{j}. Tokiu atveju sakoma, kad funkcija f yra suderinama su ekvivalentumo sa_{‘}ryšiu E: kai a_{1}Ea_{2}, tai f(a_{1}) = f(a_{2}). Tada vėl galime apibrėžti indukuota_{‘}ja_{‘} funkcija_{‘} \overline{f} : A/E → B, \overline{f}(K_{E}(a)) = f(a), kurios dėka diagrama

A ⟶ f B
↘ p  ↗\overline{f}
A/E

yra komutatyvi. Tiesa, funkcijos f faktorizacijoje f = \overline{f} p funkcija \overline{f} jau nebūtinai injektyvi funkcija.

3.16 pavyzdys.

ℤ  ⟶ φ_{2}  ℤ_{2}  φ_{2} = \overline{f} p,
↘ p  ↗\overline{f}  \overline{f}(K(2n)) = \overline{0},
ℤ/E_{|n|}  \overline{f}(K(2n + 1)) = \overline{1}, n ∈ ℤ.