1. AIBĖS IR SA_{‘}RYŠIAI

Viena iš matematikos sričiu_{‘} – aibiu_{‘} teorija, – aibės sa_{‘}vokos naudojima_{‘} apibrėžia aksiomomis. Tai aibiu_{‘} teorijos vystymosi rezultatas. Tačiau iš pradžiu_{‘} aibės sa_{‘}voka buvo suprantama intuityviai – tai ,,naivusis“ aibiu_{‘} teorijos periodas, kurio pradininkas buvo aibiu_{‘} teorijos kūrėjas G. Kantoras^{1}. Mūsu_{‘} reikmėms pakaks tokio intuityvaus aibės sa_{‘}vokos apibūdinimo.

1.1 apibrėžimas. 1. Sa_{‘}vokos ,,aibė“ ir ,,elementas priklauso aibei“ yra pirminės ir todėl neapibrėžiamos.

2. Jeigu elementas x priklauso aibei A, tai rašysime x ∈ A, o jeigu ne – x ∉ A.

3. Aibė, neturinti elementu_{‘}, bus vadinama tuščia_{‘}ja aibe. Žymėsime O /. Pastebėsime, su bet kuriuo x, x ∉ O /.

1.7 pavyzdys. Tegu A – baigtinė aibė, o skaičius 2 žymi aibe_{‘} {0, 1}. Šis žymuo paaiškinamas tuo, kad kiekvienam aibės A poaibiui B apibrėžiama funkcija f, kurios reikšmės yra aibėje 2,

f_{B}(x) = \{ \begin{matrix}1, & kai x ∈ B, \\ 0, & kai x ∉ B, \end{matrix}

o kiekviena funkcija f : A → 2 apibrėžia toki_{‘} aibės A poaibi_{‘}

B_{f} = {x | f(x) = 1},

kad f_{B_{f}} = f. Todėl abi aibes {f|f : A → 2} ir {B : B ⊆ A} žymime vienodai – 2^{A}. Be to, remiantis dvejopu aibės 2^{A} apibūdinimu, nesunku suprasti, kad aibės 2^{A} elementu_{‘} skaičius (aibės galia) |2^{A}| yra lygus 2^{|A|}.

Iš tikru_{‘}ju_{‘} kiekviena funkcija f ∈ 2^{A} kiekvienam x ∈ A gali i_{‘}gyti dvi reikšmes iš aibės {0, 1}. Vadinasi,

|2^{A}| = \underbrace{2 · 2 · . . . · 2}_{|A|} = 2^{|A|}.

1 G. Cantor, 1845–1918, – vokiečiu_{‘} matematikas.

1.8 pastaba. O / ∈ 2^{A}, A ∈ 2^{A}, bet 2O / ≠ O /, nes 2O / = {O /}! O5. Tegu B ir C – bet kokios aibės. Elementu_{‘} x ∈ B ir y ∈ C

,,poros“ sa_{‘}voka_{‘} suprasime intuityviai ir žymėsime žymeniu (x, y). Dvi poras (x_{1}, y_{1}) ir (x_{2}, y_{2}) vadinsime lygiomis, jeigu x_{1} = x_{2} ir y_{1} = y_{2}. Visu_{‘} poru_{‘} aibė {(x, y)|x ∈ B, y ∈ C} vadinama aibiu_{‘} B ir C dekartine sandauga ir žymima B × C :

B × C = {(x, y) | x ∈ B, y ∈ C}.

1.10 pavyzdys. Jei B = {1, 2}, C = {1, 2, 3}, tai

\begin{matrix}B × C = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)\}, \\ C × B = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)\}. \end{matrix}

1.11 pavyzdys. ℝ^{2} = ℝ × ℝ yra plokštumos, kurioje yra dekartinė koordinačiu_{‘} sistema, visu_{‘} tašku_{‘} koordinačiu_{‘} aibė.

1.12 pavyzdys. Aibės ℕ × ℕ elementus galima pavaizduoti taip:

._{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ℕ ℕ_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 0 1 2 3 … i … 1 2 3⋮j⋮  3^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}•(i, j)

Dekartinė sandauga apibendrinama bet kuriai baigtinei aibiu_{‘} A_{1}, A_{2}, ..., A_{n} sistemai. Elementu_{‘} x_{1} ∈ A_{1}, x_{2} ∈ A_{2}, ..., x_{n} ∈ A_{n} ,,sekos“ sa_{‘}voka_{‘} suprasime intuityviai ir žymėsime žymeniu (x_{1}, x_{2}, ..., x_{n}). Dvi sekos (x_{1}, x_{2}, ..., x_{n}) ir (y_{1}, y_{2}, ..., y_{n}) vadinamos lygiomis, jeigu x_{1} = y_{1}, x_{2} = y_{2}, ..., x_{n} = y_{n}. Visu_{‘} seku_{‘} aibė {(x_{1}, x_{2}, ..., x_{n}) | x_{1} ∈ A_{1}, x_{2} ∈ A_{2}, ..., x_{n} ∈ A_{n}} vadinama aibiu_{‘} A_{1}, A_{2}, ..., A_{n} dekartine sandauga ir žymima:

A_{1} × A_{2} × … × A_{n} = {(x_{1}, x_{2}, …, x_{n}) | x_{1} ∈ A_{1}, x_{2} ∈ A_{2}, …, x_{n} ∈ A_{n}}.

Jeigu A_{1} = A_{2} = … = A_{n}, tai rašoma A^{n} = A × A × … × A.

1.13 pavyzdys. Jei B = {−1, 0, 1}, C = {1, 2, 3}, tai

._{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} B C_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} • • •  • • • • • • -1 0 1 1 2 3

aibės B × C elementai pavaizduoti plokštumoje su dekartine koordinačiu_{‘} sistema, o aibės B ∪ C elementai pavaizduoti skaičiu_{‘} tiesėje

._{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} B  C • • • • • • -1 0 1 1 2 3

2.1 apibrėžimas. Binariniu sa_{‘}ryšiu R netuščioje aibėje A vadinamas dekartinės sandaugos A × A poaibis R ⊆ A × A. Sakoma, kad aibės A elementai a, b yra sa_{‘}ryšyje R, jeigu (a, b) ∈ R. Žymima aRb.

2.2 pavyzdys. Aibėje 2^{A} apibrėžiamas sa_{‘}ryšis R =,,⊆“:

R = {(B, C) | B, C ∈ 2^{A} ir B ⊆ C}.

2.3 pavyzdys. Sveiku_{‘}ju_{‘} skaičiu_{‘} aibėje ℤ apibrėžiamas sa_{‘}ryšis ,,mažiau“: {(n, m) | m − n yra teigiamas skaičius} ⊂ ℤ × ℤ. Rašome n < m.

Dažnai sa_{‘}ryšis R ⊆ A × A reiškiamas matrica. Matricos eilutės ir stulpeliai žymimi aibės A elementais, o pačios matricos elementai – 0 arba 1 apibrėžiami taip: jeigu aRb, tai eilutės, kurioje yra a, ir stulpelio, kuriame yra b, susikirtime yra 1, o jeigu (a, b) ∉ R, tai 0.

2.4 pavyzdys. A = {0, 1, 2}, 2^{A} = { O /; {0}; {1}; {2}; {0, 1}; {0, 2}; {1, 2}; {0, 1, 2}}. Sa_{‘}ryši_{‘} ,,⊆“ reiškiame matrica, kurios stulpeliai ir eilutės pažymėti aibės 2^{A} elementais. Stulpelio, kuri_{‘} žymi aibė B, ir eilutės, kuria_{‘} žymi aibė C, susikirtimo vietoje rašomas 1, jeigu B yra C poaibis, ir 0, jeigu B nėra C poaibis.

O / {0} {1} {2} {0, 1} {0, 2} {1, 2} {0, 1, 2} B
O /  1 0  0  0  0  0  0  0
{0} 1 1  0  0  0  0  0  0
{1} 1 0  1  0  0  0  0  0
{2} 1 0  0  1  0  0  0  0
{0, 1} 1 1  1  0  1  0  0  0
{0, 2} 1 1  0  1  0  1  0  0
{1, 2} 1 0  1  1  0  0  1  0
{0, 1, 2} 1 1  1  1  1  1  1  1
C

2.5 pavyzdys. Nagrinėkime aibės A tapatu_{‘}ji_{‘} sa_{‘}ryši_{‘} I_{A} = {(a, a)|a ∈ A} ⊆ A × A. Šio sa_{‘}ryšio matricoje tik pagrindinėje i_{‘}strižainėje yra 1.

1 0 0 0 …
0 1 0 0 …
0 0 1 0 …
0 0 0
. . . . . . . . .

Kiekvienam aibės A sa_{‘}ryšiui R ⊆ A × A apibrėžiamas atvirkštinis sa_{‘}ryšis R^{−1} = {(y, x) | (x, y) ∈ R}. Sa_{‘}ryšio R^{−1} matrica yra lygi transponuotai sa_{‘}ryšio R matricai. Aišku, kad (R^{−1})^{−1} = R.

2.6 pavyzdys. Sa_{‘}ryšiui ,,⊆“ aibėje 2^{A} atvirkštinis yra sa_{‘}ryšis ,,⊇“; o sa_{‘}ryšiui ,,<“ aibėje ℤ atvirkštinis yra sa_{‘}ryšis ,,>“.

2.7 apibrėžimas. Binarusis sa_{‘}ryšis E aibėje A vadinamas ekvivalentumo sa_{‘}ryšiu, jeigu jam galioja:

1) refleksyvumas – su visais a ∈ A teisinga aEa, t.y. (a, a) ∈ E, I_{A} ⊆ E;

2) simetriškumas – jei aEb, tai bEa, t.y. E = E^{−1};

3) tranzityvumas – jei aEb ir bEc, tai aEc.

2.8 pastaba. Ekvivalentumo sa_{‘}ryšio matrica yra simetrinė matrica, kurios pagrindinėje i_{‘}strižainėje yra tik vienetai.

2.9 pavyzdys. Lygybė yra ekvivalentumo sa_{‘}ryšis aibėje A:

1) a = a su visais a ∈ A;

2) jei a = b, tai b = a visiems a, b ∈ A;

3) jei a = b, b = c, tai a = c visiems a, b, c ∈ A.

2.10 apibrėžimas. Aibės A poaibiu_{‘} sistema π = π (A) = {A_{i} ∈ 2^{A} | i ∈ I} vadinama aibės A skaidiniu, jei:

1) A_{i} ∈ π, tai A_{i} ≠ O /;

2) A_{i} ∈ π ir A_{j} ∈ π, tai A_{i} ∩ A_{j} = O / su visais i, j ∈ I, i ≠ j;

3) ⋃ i ∈ IA_{i} = A.

2.11 pavyzdžiai.

1. π_{1}(A) = {{a} | a ∈ A}.

2. π_{2}(A) = {A}.

3. π({1, 2, 3, 4, 5, 6}) = {{1, 2, 3}, {4, 5, 6}}.

2.12 teiginys. Tegu π(A) = {A_{i} | i ∈ I} yra aibės A skaidinys, o sa_{‘}ryšis R_{π} aibėje A apibrėžiamas taip: aR_{π}b, a ∈ A_{i} ir b ∈ A_{j} tada ir tik tada, kai i = j. Tada R_{π} yra ekvivalentumo sa_{‘}ryšis.

I_{‘} rodymas. Nagrinėkime elementu_{‘} pora_{‘} a, b ∈ A. Kadangi π(A) yra nepersikertančiu_{‘} poaibiu_{‘} {A_{i}} sistema, todėl egzistuoja tik vienas toks i ∈ I ir vienas toks j ∈ I , kad a ∈ A_{i}, b ∈ A_{j}.

Sa_{‘}ryšio R_{π} refleksyvumas: jei aR_{π}a, a ∈ A_{i} ir a ∈ A_{j}, tai i = j. Sa_{‘}ryšio R_{π} simetriškumas: jei aR_{π}b, a ∈ A_{i} ir b ∈ A_{j}, tai i = j ir

todėl bR_{π}a.

Sa_{‘}ryšio R_{π} tranzityvumas: jei aR_{π}b ir bR_{π}c, ir a ∈ A_{i}, b ∈ A_{j}, c ∈ A_{k}, tai i = j, j = k, i = k ir aR_{π}c.

△

Tarp ekvivalentumo sa_{‘}ryšiu_{‘} ir skaidiniu_{‘} yra abipusiškai vienareikšmė atitiktis. Ne tik skaidinys apibrėžia ekvivalentumo sa_{‘}ryši_{‘}, bet ir ekvivalentumo sa_{‘}ryšis apibrėžia skaidini_{‘}.

2.13 apibrėžimas. Tegu a ∈ A ir E ⊆ A × A yra ekvivalentumo sa_{‘}ryšis. Tada aibė K_{E}(a) = {b | aEb} yra vadinama elemento a ekvivalentumo klase. Kai aišku, apie koki_{‘} ekvivalentumo sa_{‘}ryši_{‘} kalbama, ekvivalentumo klasė žymima K(a). Jeigu b, c ∈ K(a), tai b ir c vadinami ekvivalenčiaisiais elementais, arba ekvivalentumo klasės K(a) atstovais. Visu_{‘} ekvivalentumo klasiu_{‘} aibė {K_{E}(a) | a ∈ A} vadinama aibės A faktoraibe ekvivalentumo sa_{‘}ryšio E atžvilgiu ir žymima A/E.

2.14 teiginys. Tegu E yra ekvivalentumo sa_{‘}ryšis aibėje A. Tada faktoraibė A/E yra toks aibės A skaidinys π, kad R_{π} = E.

I_{‘} rodymas. Iš pradžiu_{‘} i_{‘}rodysime, kad {K_{E}(a) | a ∈ A} yra aibės A skaidinys.

1) Su visais a ∈ A K(a) ≠ O /, nes iš E refleksyvumo gauname, kad a ∈ K(a).

2) Tegu K(a)∩K(b) ≠ O /. Tada egzistuoja toks elementas c, c ∈ K(a) ir c ∈ K(b), t.y. cEa ir cEb. Iš E simetriškumo išplaukia aEc ir bEc, o iš E tranzityvumo – aEb. Jeigu x ∈ K(a), t.y. xEa, tai iš aEb arba bEa gauname (E tranzityvumas) xEb, t.y. x ∈ K(b). Taigi K(a) ⊆ K(b). Analogiškai i_{‘}rodome, kad K(b) ⊆ K(a). Vadinasi, K(a) = K(b).

Dabar i_{‘}rodysime, kad R_{π} = E.

1) Tegu aEb. Iš E simetriškumo gauname bEa ir a ∈ K(a) ∩ K(b), t.y. K(a) ∩ K(b) ≠ O /, todėl pagal 2) K(a) = K(b) ir aR_{π}b. Atvirkščiai, jeigu aR_{π}b, t.y. K(a) = K(b), tai a ∈ K(b) ir aEb.

2) Jeigu a ∈ K ∈ π, tai K(a) = K.

Taigi R_{π} = E.

△

2.15 pavyzdys. Aibėje ℤ×ℤ−{0} ekvivalentumo sa_{‘}ryši_{‘} ∼ apibrėšime taip: (a, b) ∼ (c, d) tada ir tik tada, kai ad = bc. Pavyzdžiui, (−40, 25) ∼ (8, −5), (3, 6) ∼ (−1, −2). Nesunku suprasti, kad šio ekvivalentumo sa_{‘}ryšio klasės gali būti sutapatintos su racionaliu_{‘}ju_{‘} skaičiu_{‘} aibe \{\frac{a}{b} | a ∈ ℤ, b ∈ ℤ − \{0\}\}. Iš tikru_{‘}ju_{‘} \frac{a}{b} = \frac{c}{d} ekvivalentu ad = bc.

2.16 pavyzdys. Tegu n ∈ ℕ. Sveiku_{‘}ju_{‘} skaičiu_{‘} aibėje ℤ apibrėšime sa_{‘}ryši_{‘} ≡ (mod n): {(a, b) | a − b = nk, a, b, k ∈ ℤ}, t.y. a ≡ b (mod n) (sakoma, a lygsta b moduliu n). Šis sa_{‘}ryšis yra ekvivalentumo sa_{‘}ryšis. (Patikrinkite!) Elemento a ekvivalentumo klasė K_{n}(a) = {a + nk | k ∈ ℤ}. Kai yra aišku, kuriuo moduliu n nagrinėjamas lygstamumas, klasė K_{n}(a) žymima trumpiau – \overline{a}. Faktoraibė šio ekvivalentumo sa_{‘}ryšio atžvilgiu žymima ℤ_{n}. Pavyzdžiui, kai n = 3, \overline{0} = \{…, −6, −3, 0, 3, 6, …\}, \overline{1} = \{…, −5, −2, 1, 4, …\}, \overline{2} = \{…, −4, −1, 2, 5, …\} ir ℤ_{3} = \{\overline{0}, \overline{1}, \overline{2}\}. Bendruoju atveju ℤ_{n} = \{\overline{0}, \overline{1}, …, \overline{n − 1}\}:

\overline{0} = \{…, −2n, −n, 0, n, 2n, …\},
\overline{1} = \{…, −2n + 1, −n + 1, 1, n + 1, 2n + 1, …\},
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
\overline{n − 1} = \{…, −n − 1, −1, n − 1, 2n − 1, 3n − 1, …\}.

Aibė ℤ_{n} dar vadinama likiniu_{‘} klasiu_{‘} moduliu n aibe.