Множини і відношення

D₁ = {(a₁, b₁ ), (a₁, b₂ ),..., (a₁, b_n ),... },

D₂ = {(a₂, b₁ ), (a₂, b₂ ),..., (a₂, b_n ),... },

...........................................

D_k = {(a_k, b₁ ), (a_k, b₂ ),..., (a_k, b_n ),... },

...........................................

Зокрема, множина всіх точок координатної площини з раціональними координатами зліченна.

Наслідок 1.4.4. Декартів добуток P_n=A₁A₂...A_n зліченних множин A₁, A₂,..., A_n - є зліченною множиною для довільного n.

Доведення проведемо методом математичної індукції.

Для n=1 P₁=A₁ і справедливість твердження випливає з умови зліченності множини A₁. Нехай P_k-1=A₁A₂...A_k-1 - зліченна множина. Тоді зліченність множини P_k = P_k-1A_k випливає з наслідку 1.4.3.

Наслідок 1.4.5. Множина P усіх многочленів p(x) = a₀xⁿ+a₁x^n-1+...+a_n-1x+a_n з раціональними коефіцієнтами a_iQ, i=0,1,...,n, n=0,1,2,..., є зліченною множиною.

Множину P можна подати у вигляді об'єднання зліченної сукупності множин P_n, де P_n - це множина многочленів з раціональними коефіцієнтами, степінь яких не перевищує n, n=0,1,2,.... Разом із тим, будь-якому многочлену p(x)=a₀xⁿ+a₁x^n-1+ ...+a_n-1x+a_n з множини P_n можна поставити у відповідність кортеж (a₀,a₁,a₂,...,a_n), який складається з раціональних чисел a_i - коефіцієнтів цього многочлена. Очевидно, ця відповідність є взаємно однозначною. Отже, P_n ~ Qⁿ⁺¹. Тоді з наслідків 1.4.2 і 1.4.4 випливає, що множина P_n - зліченна, а тому зліченною є і множина P.

Назвемо число алгебраїчним, якщо воно є коренем деякого многочлена з раціональними коефіцієнтами. Відомо, що кожен такий многочлен має скінченну кількість коренів (не більшу від степені многочлена). Таким чином, множину всіх алгебраїчних чисел можна подати у вигляді об'єднання зліченної сукупності скінченних множин. Отже, має місце

Наслідок 1.4.6. Множина всіх алгебраїчних чисел зліченна.

Наслідок 1.4.7. Множина A всіх слів у заданому скінченному алфавіті A зліченна.

Справедливість твердження випливає з того, що

A^* = {e} A A² A³ ...,

тобто множина A^* є зліченним об'єднанням скінченних множин {e} і Aⁿ, де Aⁿ - множина всіх слів довжини n в алфавіті A.

9. Незліченні множини

Наступні питання, які логічно випливають із висловленого вище припущення про рівнопотужність усіх нескіченних множин: чи всі нескінченні множини зліченні, або чи існують нескінченні множини, які не будуть зліченними? Факт існування множин, які не є зліченними (незліченних множин), вперше був встановлений Г.Кантором за допомогою запропонованого ним діагонального методу, який набув згодом фундаментального значення в різних розділах математики. Зокрема, цей метод лежить в основі доведення наступної важливої теореми, яка належить Г.Кантору.

Теорема 1.5. Множина всіх дійсних чисел з інтервалу (0,1) незліченна.

Доведення. Відомо, що кожному дійсному числу з інтервалу (0,1) можна поставити у відповідність нескінченний десятковий дріб 0,a₁a₂a₃.... Для ірраціональних чисел цей нескінченний десятковий дріб є неперіодичним. Для кожного раціонального числа, яке зображується скінченним десятковим дробом, з двох можливих варіантів запису його у вигляді нескінченного періодичного десяткового дробу (з періодом 0 або періодом 9) зафіксуємо період 9. Наприклад, число 0,123 (або 0,123000...) будемо записувати у вигляді 0,122999..., а число 0,7 - у вигляді 0,699.... Очевидно, що запропонована відповідність буде взаємно однозначною.

Проведемо доведення теореми методом від супротивного. Припустімо, що сформульоване твердження хибне і множина всіх дійсних чисел з інтервалу (0,1) зліченна. Тобто існує нумерація цих чисел x₁,x₂,...,x_n,.... Перепишемо у вигляді нескіченних десяткових дробів усі числа з інтервалу (0,1) в порядку їхньої нумерації

x₁ = 0, a₁₁ a₁₂ a₁₃ ... a_1n...,

x₂ = 0, a₂₁ a₂₂ a₂₃ ... a_2n...,

x₃ = 0, a₃₁ a₃₂ a₃₃ ... a_3n...,

...............................

x_n = 0, a_n1 a_n2 a_n3 ... a_nn...,

...............................

Рухаючись по діагоналі (вказаної стрілками), утворимо новий нескінченний десятковий дріб 0,b₁b₂...b_n... такий, що b₁ a₁₁, b₂a₂₂,...,b_na_nn,.... Додатково для того, щоб уникнути ситуації з можливістю зображення одного й того ж раціонального числа у двох формах, будемо вибирати значення цифр b_i так, щоб b_i0 і b_i9, i=1,2,.... Утворений дріб є записом деякого дійсного числа y з інтервалу (0,1), однак він не належить розглядуваній зліченній множині. Справді, побудований дріб відрізняється від кожного з дробів нашої нумерації x₁,x₂,...,x_n,... принаймні однією цифрою. Точніше, yx_n тому, що дроби y і x_n відрізняються принаймні n-ю цифрою після коми (n=1,2,...). З одержаної суперечності випливає, що не існує переліку для множини всіх дійсних чисел з інтервалу (0,1). Отже, припущення щодо її зліченності хибне і розглядувана множина - незліченна. Теорема доведена.

Будь-яка множина, рівнопотужна множині всіх дійсних чисел з інтервалу (0,1), називається континуальною, або множиною потужності континуум.

З наведених вище прикладів 1.12 (3,4) і зауваження про рівнопотужність усіх інтервалів і відрізків дійсної прямої, а також твердження про рівнопотужність будь-якого відрізка і всієї дійсної прямої випливає, що всі ці множини точок будуть континуальними.

Теорема 1.6. Якщо M - незліченна множина, а A - скінченна або зліченна підмножина множини M, то множини M\A і M рівнопотужні, тобто M \ A ~ M.

Доведення. Очевидно, що множина M \ A незліченна. Якби множина M'=M \ A була зліченною, то за теоремою 1.4 множина M = M' A була б також зліченною, що суперечило б умові теореми. Тоді за теоремою 1.2 множина M' містить зліченну підмножину B (BM \ A). Позначимо C=(M\A)\B, тоді маємо M \ A=BC і M=(AB)C. Множина AB зліченна. Тоді з рівнопотужностей B~(AB) і C ~ C, а також того, що CB= і C(AB)=, випливає співвідношення BC~(AB)C, тобто M \ A ~ M.

Сформулюємо декілька наслідків, які випливають із доведених теорем.

Наслідок 1.6.1. Якщо M - нескінченна множина, а множина A - скінченна або зліченна, то M A ~ M.

Будемо вважати, що MA=. Якщо MA, то у доведенні можна використати скінченну або зліченну множину A' = A \ M таку, що MA=MA' і MA' =.

Якщо M зліченна множина, то MA також зліченна множина (теорема 1.4), отже M A ~ M.

Якщо M незліченна множина, то M A також незліченна множина. Тоді за теоремою 1. 6 (M A) \ A ~ M A, тобто M ~ M A, оскільки (MA) \ A = M.

Наслідок 1.6.2. Множина всіх ірраціональних чисел континуальна.

Число, яке не є коренем жодного многочлена з раціональними коефіцієнтами, називається трансцендентним.

Наслідок 1.6.3. Множина всіх трансцендентних чисел континуальна.

Справедливість наслідків 1.6.2 і 1.6.3 випливає з континуальності множин R і C всіх дійсних і комплексних чисел відповідно, зліченності множин усіх раціональних і всіх алгебраїчних чисел та теореми 1.6.

Із доведених теорем випливає також рівнопотужність інтервалів (0,1) ~ [0,1) ~ (0,1] ~ [0,1].

Сформульована нижче теорема встановлює певний зв'язок між зліченними і континуальними множинами і у своєму доведенні знову використовує діагональний метод Кантора.

Теорема 1.7. Множина (A) всіх підмножин зліченної множини A має потужність континуум.

Доведення. Оскільки всі зліченні множини рівнопотужні множині N натуральних чисел, то достатньо довести континуальність булеана (N) множини N. Маючи взаємно однозначну відповідність між множиною N і деякою множиною A, неважко побудувати взаємно однозначну відповідність між їхніми булеанами (N) і (A).

Проведемо доведення теореми методом від супротивного. Припустімо, що множина (N) зліченна й існує нумерація всіх її елементів, тобто (N)={M₁,M₂,...,M_k,...}, де M_kN, k=1,2,.... Поставимо у відповідність кожній множині M_k послідовність t_k з нулів і одиниць m₁^(k), m₂^(k),...,m_i^(k),... за таким законом

1, якщо iM_k,

m_i^(k) =

0, якщо iM_k.

Очевидно, ця відповідність є взаємно однозначною.

Розташуємо всі елементи множини (N) і відповідні їм послідовності у порядку нумерації:

M₁ - m₁⁽¹⁾, m₂⁽¹⁾,...,m_k⁽¹⁾,...

M₂ - m₁⁽²⁾, m₂⁽²⁾,...,m_k⁽²⁾,...

............................................

M_k - m₁^(k), m₂^(k),...,m_k^(k),...

............................................

Використовуючи діагональний метод Кантора, побудуємо нову послідовність L з нулів і одиниць l₁,l₂,..., l_k,... таку, що l_k m_k^(k), тобто

1, якщо m_k^(k)=0,

l_k =

0, якщо m_k^(k)=1, k = 1,2,3,....

Послідовності L відповідає деяка підмножина MN, а саме M={ n | l_n=1, n=1,2,...}. Очевидно, підмножина M не входить у вказаний перелік M₁,M₂,...,M_k,..., оскільки послідовність L відрізняється від кожної з послідовностей t_k принаймні в одній k-й позиції. Отже, і множина M відрізняється від кожної з множин M_k, k=1,2,.... Ця суперечність означає, що не існує переліку для елементів множини (N). Таким чином, множина (N) незліченна.

Крім того, кожній послідовності t_k можна поставити у відповідність нескінченний двійковий дріб 0,m₁^(k)m₂^(k)...m_k^(k)..., який зображує деяке дійсне число з інтервалу (0,1) у двійковій системі числення. I навпаки, будь-яке число з інтервалу (0,1) можна однозначно записати у вигляді нескінченного двійкового дробу. Виняток становлять числа зі зліченної множини раціональних чисел, які записуються за допомогою скінченних двійкових дробів і тому можуть мати дві різні форми зображення у вигляді нескінченних двійкових дробів - з періодом 0 і періодом 1.

Кожному з таких чисел відповідають дві різні послідовності t' і t'', а отже, і два різні елементи множини (N): один - для зображення з періодом 0, другий - з періодом 1. Позначимо через T множину тих підмножин множини N, які при побудованій вище відповідності зіставляються нескінченним двійковим дробам із періодом, T(N). Тоді існує взаємно однозначна відповідність між множиною всіх дійсних чисел з інтервалу (0,1) і множиною (N) \ T. Однак, оскільки множина T зліченна, то за теоремою 1.6 маємо (N) ~ (N) \ T. Таким чином, множина (N), а значить і множина (A) для будь-якої зліченної множини A, мають потужність континуум.

10. Кардинальні числа

Нехай A - деяка множина і S = { B | B ~ A} - сукупність усіх множин, рівнопотужних множині A. Очевидно, що всі множини з S рівнопотужні. Кардинальним числом (позначається |A|, або Card A) будемо називати деякий об'єкт для позначення потужності будь-якої множини із сукупності S.

Зокрема, для скінченної множини A кардинальним числом |A| є натуральне число, яким позначається кількість елементів будь-якої з множин сукупності S. Таким чином, можна вважати, що кардинальне число є узагальненням поняття числа елементів.

Природно виникає питання про порівняння кардинальних чисел нескінченних множин.

Нехай A і B нескінченні множини, тоді логічно можливі такі чотири випадки:

1. Iснує взаємно однозначна відповідність між A і B, тобто A ~ B і |A|=|B|.

2. Існує взаємно однозначна відповідність між множиною A і деякою власною підмножиною B' множини B. Тоді кажуть, що потужність множини A не менша від потужності множини B і записують |A||B|.

3. Множина A рівнопотужна деякій підмножині множини B і, навпаки, множина B рівнопотужна деякій підмножині множини A, тобто A~B'B і B~A'A.

За теоремою Кантора-Бернштейна, доведення якої наведено нижче, у цьому випадку виконується A ~ B, тобто |A|=|B|.

4. Не існує взаємно однозначної відповідності між множиною A і жодною підмножиною множини B і, також, не існує взаємно однозначної відповідності між множиною B і жодною підмножиною множини A. З цієї ситуації випливало б, що потужності множин A і B непорівнювані між собою.

Однак більш глибокі дослідження в теорії множин показали, що, спираючись на аксіому вибору (див.розд.1.13), можна довести неможливість четвертого випадку.

Таким чином, потужності будь-яких двох множин A і B завжди порівнювані між собою. Отже, для кардинальних чисел |A| і |B| довільних множин A і B виконується одне з трьох співвідношень: |A|=|B|, |A||B| або |B||A|.

Якщо |A||B|, однак множина A нерівнопотужна множині B, то писатимемо |A|<|B|.

Теорема 1.8 (теорема Kантора-Бернштейна).

Якщо множина A рівнопотужна деякій підмножині B₁ множини B, A~B₁B і, одночасно, множина B рівнопотужна деякій підмножині A₁ множини A, B~A₁A, то множини A і B рівнопотужні.

Доведення. Зрозуміло, що роблячи припущення про існування таких підмножин B₁B і A₁A, що A₁ ~ B і B₁ ~ A, вважаємо, що A₁ і B₁ є власними підмножинами множин A і B відповідно. Якщо A₁ = A або B₁=B, то справедливість теореми очевидна.

Нехай f₀B A взаємно однозначна відповідність між B і A. Тоді з того, що B₁B випливає, що існує множина A₂ = f₀(B₁)A₁ така, що f₁B₁A₂BA₁, f₁f₀ і f₁ є взаємно одозначною відповідністю між B₁ і A₂, тобто B₁~A₂. За умовою теореми A~B₁, отже A~A₂. Це означає, що існує взаємно однозначна відповідність f₂ між множинами A і A₂, f₂AA₂.

Образом f₂(A₁) підмножини A₁A при відповідності f₂ буде деяка множина A₃A₂. Відповідність f₃A₁A₃, f₃f₂ є взаємно однозначною, отже A₁~A₃. Аналогічно, образом f₃(A₂) підмножини A₂A₁ при відповідності f₃ буде деяка множина A₄A₃, а відповідність f₄A₂A₄, f₄f₃ буде взаємно однозначною, тобто A₂~A₄.

Продовжуючи ці міркування, одержимо нескінченний ланцюг строгих включень AA₁A₂A₃...A_n.... При цьому виконуються такі співвідношення:

A ~ A₂ ~ A₄ ~... ~ A_2k ~ A_2k+2 ~...,

A₁ ~ A₃ ~ A₅ ~... ~ A_2k+1 ~ A_2k+3 ~...,

f₀f₁f₂f₃... f_n ...

Із наведених співвідношень випливає, що відповідності

f'₂ = f₂ \ f₃ (A \ A₁ )(A₂ \ A₃ ),

f'₄ = f₄ \ f₅ (A₂ \ A₃ )(A₄ \ A₅ ),

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

f'_2k+2 = f_2k+2 \ f_2k+3 (A_2k \ A_2k+1 )(A_2k+2 \ A_2k+3 ),

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

є взаємно однозначними.

Отже,

(A \ A₁) ~ (A₂ \ A₃ ) ~ (A₄ \ A₅ ) ~...~ (A_2k \ A_2k+1) ~ (A_2k+2 \ A_2k+3) ~....

Оскільки рівнопотужні множини (A \ A₁), (A₂ \ A₃ ), (A₄ \ A₅ ),..., (A_2k \ A_2k+1),... попарно не перетинаються, то множини

C₁ = (A \ A₁) (A₂ \ A₃ ) (A₄ \ A₅ ) ... (A_2k \ A_2k+1)...,

C₂ = (A₂ \ A₃ ) (A₄ \ A₅ ) (A₆ \ A₇ ) ... (A_2k+2 \ A_2k+3)...

також рівнопотужні, тобто C₁ ~ C₂.

Позначимо через D = AA₁A₂A₃...A_n....

Неважко переконатись, що

A = D (A \ A₁) (A₁ \ A₂ ) (A₂ \ A₃ ) ... (A_n \ A_n+1)...,

A₁ = D (A₁ \ A₂ ) (A₂ \ A₃ ) ... (A_n \ A_n+1)...,

Нехай D₀ = D (A₁ \ A₂ ) (A₃ \ A₄ ) ... (A_2k+1 \ A_2k+2)...,

тоді попередні співвідношення можна подати у вигляді:

A = D₀ [(A \ A₁) (A₂ \ A₃ ) (A₄ \ A₅ ) ... (A_2k \ A_2k+1)...] = D₀ C₁,

A = D₀ [(A₂ \ A₃ ) (A₄ \ A₅ ) (A₆ \ A₇ ) ... (A_2k+2 \ A_2k+3)...] = D₀ C₂.

Оскільки між множинами C₁ і C₂ існує взаємно однозначна відповідність g, а D₀C₁= і D₀C₂=, то i_D0 g є взаємно однозначною відповідністю між A і A₁, отже, A~A₁. Через i_D0D₀D₀ позначено тотожню взаємно однозначну відповідність між елементами множини D₀ : i_D0 = { (d,d) | dD₀ }.

З умови теореми B ~ A₁, одержаного співвідношення A~A₁ і властивостей симетричності і транзитивності відношення рівнопотужності маємо B ~ A.

Теорема доведена.

Наслідок 1.8.1. Якщо виконуються включення A₂A₁A і A₂~A (|A₂|=|A |), то A₁ ~ A (|A₁|=|A|).

Справедливість твердження випливає з того, що A ~ A₂A₁ і A₁~A₁A.

Наслідок 1.8.2. Якщо AB, то |A| |B|.

Для кардинальних чисел зліченних і континуальних множин, враховуючи їхню поширеність і популярність в сучасній математиці, введені спеціальні позначення. Так кардинальне число множини N всіх натуральних чисел, а значить, і будь-якої зліченної множини позначають через ₀ (читається "алеф-нуль"). Кардинальне число континуальних множин позначають через c або ₁ ("алеф-один"). Якщо порівняти доведення теорем 1.1 і 1.7, то неважко помітити аналогію у встановленні взаємно однозначної відповідності між підмножинами множини A і двійковими послідовностями (скінченними в теоремі 1.1 і нескінченними в теоремі 1.7). Враховуючи цю аналогію, часто записують співвідношення |(A)| =2^|A| як для скінченних, так і для нескінченних множин. Зокрема, за теоремою 1.7 ₁ =2₀.

Наступне питання, яке виникло в теорії множин: чи існує найбільше кардинальне число, тобто, чи існує множина найбільшої потужності? Негативну відповідь на це питання дає наступна важлива теорема, доведення якої належить Г.Кантору.

Теорема 1.9. Потужність множини (A) підмножин будь-якої непорожньої множини A більша, ніж потужність даної множини A: | (A)| > |A|.

Доведення. Оскільки існує тривіальна взаємно однозначна відповідність f між множиною A і підмножиною множини (A): f = { (a,{a}) | aA, {a}(A)}, то достатньо довести, що множини A і (A) нерівнопотужні.

Доведення проведемо від супротивного. Припустимо, що існує взаємно однозначна відповідність g між множинами A і (A): g = { (b,B) | bA і B(A)}. У кожній парі відповідності перша координата b - це елемент множини A, а друга координата B - деяка підмножина множини A. Тому для кожної пари (b,B)g виконується одне з двох співвідношень: або bB, або bB. Побудуємо нову множину K = { b | bA і bB для (b,B)g }.

З того, що (A) випливає, що K .

Оскільки K є підмножиною множини A (K(A)), то при взаємно однозначній відповідності g підмножина K відповідає деякому елементові kA, тобто існує пара (k,K)g. Тоді відносно елемента kA і підмножини KA можливі дві ситуації: або kK, або kK.

Нехай kK, тоді з умови (k,K)g і правила побудови множини K випливає, що kK.

З іншого боку, якщо припустити, що kK, то з (k,K)g і правила побудови множини K повинно виконуватись kK.

Одержана суперечність доводить неможливість встановлення взаємно однозначної відповідності між A і (A). Таким чином, |A| < | (A)|.

Наслідок 1.9.1. Не існує множини, яка має найбільшу потужність, тобто не існує найбільшого кардинального числа.

Справді, розглянувши множини N, (N), ((N)),..., одержимо нескінченно зростаючу послідовність відповідних кардинальних чисел ₀ ,₁ =2₀,₂ =2₁, ...

На закінчення зупинимось ще на одній цікавій класичній проблемі теорії множин, сформульованій ще у 1884 році Г.Кантором:

гіпотеза континуума, яка стверджує, що не існує множини, кардинальне число якої розташоване між ₀ і ₁, тобто ₀ < < ₁.

Ця гіпотеза припускає узагальнення, яке носить назву узагальненої гіпотези континуума:

для довільного кардинального числа деякої нескінченної множини з нерівності ' > для будь-якого кардинального числа ' випливає ' > 2.

Проблему гіпотези континуума майже вісім десятків років намагалися розв'язати найкращі математики світу. I лише у 1963 році тридцятирічний американський математик Пол Коен довів, що гіпотезу континуума не можна ні довести, ні спростувати, виходячи з аксіом теорії множин. Отже, прийняття або відхилення гіпотези континуума є однаково законними, що веде до можливості побудови двох різних несуперечливих теорій множин.

11. Відношення. Властивості відношень

Підмножина R декартового степеня Mⁿ деякої множини M називається n-місним або n-арним відношенням на множині M. Кажуть, що елементи a₁,a₂,...,a_nM знаходяться у відношенні R, якщо (a₁,a₂,...,a_n)R.

При n=1 відношення RM називають одномісним або унарним. Таке відношення часто називають також ознакою або характеристичною властивістю елементів множини M. Кажуть, що елемент a M має ознаку R, якщо aR і RM. Наприклад, ознаки "непарність" і "кратність 7" виділяють із множини N натуральних чисел унарні відношення R = {2k-1 | kN } і R = {7k | kN }, відповідно.

Найбільш популярними в математиці є двомісні або бінарні відношення, на вивченні властивостей яких ми зупинимось детальніше. Далі скрізь під словом "відношення" розумітимемо бінарне відношення. Якщо елементи a,bM знаходяться у відношенні R (тобто (a,b)R), то це часто записують у вигляді aRb. Зауважимо, що бінарні відношення іноді розглядають, як окремий випадок відповідностей, а саме - як відповідності між однаковими множинами.

Приклад 1.13. Наведемо приклади бінарних відношень на різних множинах.

1. Відношення на множині N натуральних чисел:

R₁ - відношення "менше або дорівнює", тоді 4R₁9, 5R₁5, 1R₁m для будь-якого m N ;

R₂ - відношення "ділиться на", тоді 4R₂3, 49R₂7, mR₂1 для будь-якого mN ;

R₃ - відношення "є взаємно простими", тоді 15R₃8, 366R₃121, 1001R₃612;

R₄ - відношення "складаються з однакових цифр", тоді 127R₄721, 230R ₄ 302, 3231R ₄3213311.

2. Відношення на множині точок координатної площини R²:

R₅ - відношення "знаходяться на однаковій відстані від початку координат", тоді (3,2) R₅ (,-), (0,0)R ₅ (0,0) ;

R₆ - відношення "симетричні відносно осі ординат", тоді (1,7)R₆(-1,7) і взагалі (a,b)R₆(-a,b) для будь-яких a,bR ;

R₇ - відношення "менше або дорівнює". Вважаємо, що (a,b)R₇(c,d), якщо a c і b d. Зокрема, (1,7)R₇(20,14), (-12,4)R₇(0,17).

3. Відношення на множині студентів даного вузу:

R₈ - відношення "є однокурсником",

R₉ - відношення "є молодшим за віком від".

Для задання відношень можна користуватись тими ж способами, що і при заданні множин. Наприклад, якщо множина M скінченна, то довільне відношення R на M можна задати списком пар елементів, які знаходяться у відношенні R.

Зручним способом задання бінарного відношення R на скінченній множині M = {a₁,a₂,...,a_n} є задання за допомогою так званої матриці бінарного відношення. Це квадратна матриця C порядку n, в якій елемент c_ij, що стоїть на перетині i-го рядка і j-го стовпчика, визначається так

1, якщо a_iRa_j,

c_ij =

0, в противному разі.

Приклад 1.14. Для скінченної множини M = {2,7,36,63,180} матриці наведених вище відношень R₁, R₂, R₃ мають такий вигляд

Рис.1.5.

Оскільки відношення на M є підмножинами множини M ², то для них означeні всі відомі теоретико-множинні операції. Наприклад, перетином відношень "більше або дорівнює" і "менше або дорівнює" є відношення "дорівнює", об'єднанням відношень "менше" і "більше" є відношення "не дорівнює", доповненням відношення "ділиться на" є відношення "не ділиться на" тощо.

Аналогічно відповідностям для відношень можна означити поняття оберненого відношення і композиції відношень.

Відношення R^-1 називається оберненим до відношення R, якщо bR^-1a тоді і тільки тоді, коли aRb. Очевидно, що (R^-1)^-1=R. Наприклад, для відношення "більше або дорівнює" оберненим є відношення "менше або дорівнює", для відношення "ділиться на" - відношення "є дільником".

Композицією відношень R₁ і R₂ на множині M (позначається R₁R₂ ) називається відношення R на M таке, що aRb тоді і тільки тоді, коли існує елемент cM, для якого виконується aR₁c і cR₂b. Наприклад, композицією відношень R₁ - "є сином" і R₂ - "є братом" на множині чоловіків є відношення R₁R₂ - "є небожем".

Наведемо список важливих властивостей, за якими класифікують відношення.

Нехай R - деяке відношення на множині M.

а). Відношення R називається рефлексивним, якщо для всіх aM має місце aRa.

Очевидно, що відношення R₁,R₂,R₄,R₅,R₇ - рефлексивні.

б). Відношення R називається антирефлексивним (іррефлексивним), якщо для жодного aM не виконується aRa.

Відношення "більше", "менше", "є сином" антирефлексивні. В той же час, відношення R₆ не є ні рефлексивним, ні антирефлексивним.

Всі елементи головної діагоналі матриці C для рефлексивного відношення на скінченній множині M дорівнюють 1, а для антирефлексивного відношення дорівнюють 0.

в). Відношення R називається симетричним, якщо для всіх a,bM таких, що aRb маємо bRa.

г). Відношення R називається антисиметричним, якщо для всіх a,bM таких, що aRb і bRa маємо a = b.

Наприклад, відношення R₃,R₄,R₅,R₆,R₈ - симетричні, а відношення R₁,R₂,R₇ - антисиметричні.

Неважко переконатись, що відношення R симетричне тоді і тільки тоді, коли R=R^-1.

д). Відношення R називається транзитивним, якщо зі співвідношень aRb і bRc випливає aRc.

Наприклад, відношення R₁,R₂,R₄,R₅,R₇,R₈,R₉ - транзитивні, а відношення R₃,R₆ - не транзитивні.

Неважко переконатись, що відношення R транзитивне тоді і тільки тоді, коли RRR.

Зауважимо, якщо відношення R має будь-яку з перерахованих вище властивостей, то обернене відношення R^-1 також має ту саму властивість. Таким чином, операція обернення зберігає всі п'ять властивостей відношень.

Для довільного відношення R означимо нову операцію. Відношення R^* називається транзитивним замиканням відношення R на M, якщо aR^*b, a,bM, тоді і тільки тоді, коли у множині M існує послідовність елементів a₁,a₂,...,a_n така, що a₁ = a, a_n = b і a₁Ra₂, a₂Ra₃,...,a_n-1Ra_n.

Наприклад, нехай M - це множина точок на площині і aRb, a,bM, якщо точки a і b з'єднані відрізком. Тоді cR^*d, c,dM, якщо існує ламана лінія, яка з'єднує точки c і d.

Можна довести, що відношення R транзитивне тоді і тільки тоді, коли R^*=R.

Деякі відношення займають особливе місце в математиці. Розглянемо ці відношення окремо.

12. Відношення еквівалентності

Відношення R на множині M називається відношенням еквівалентності (або просто еквівалентністю), якщо воно рефлексивне, симетричне і транзитивне.

Враховуючи важливість відношення еквівалентності, дамо розгорнуте означення цього поняття. Таким чином, відношення R на множині M є відношенням еквівалентності або евівалентністю, якщо

1. aRa для всіх aM (рефлексивність);

2. Якщо aRb, то bRa для a,bM (симетричність);

3. Якщо aRb і bRc, то aRc для a,b,cM (транзитивність).

Приклад 1.15. 1. Відношення рівності i_M на будь-якій множині M є відношенням еквівалентності. Рівність - це мінімальне відношення еквівалентності, бо при видаленні бодай одного елемента з i_M відношення перестає бути рефлексивним, а отже, і відношенням еквівалентності.

2. Відношення рівнопотужності множин є еквівалентністю.

3. Важливу роль відіграє в математиці відношення "мають однакову остачу при діленні на k" або "конгруентні за модулем k", яке є відношенням еквівалентності на множині N натуральних чисел для будь-якого фіксованого kN. Відношення конгруентності за модулем k часто позначають a b (mod k). Цьому відношенню належать, наприклад, пари натуральних чисел (17,22), (1221,6), (42,57) для k=5, тобто 17 22(mod 5), 1221 6 (mod 5), 42 57 (mod 5).

4. Еквівалентністю є відношення подібності на множині всіх трикутників.

Сукупність множин { B_i | iI} називається розбиттям множини A, якщо B_i=A і B_iB_j = для ij. Множини B_i, iI є підмножинами множини A і називаються класами, суміжними класами, блоками або елементами розбиття. Очевидно, що кожний елемент aA належить одній і тільки одній множині B_i, iI.

Припустимо, що на множині M задано відношення еквівалентності R. Виконаємо таку побудову. Виберемо деякий елемент aM і утворимо підмножину S_a^R = { x | xM і aRx}, яка складається з усіх елементів множини M еквівалентних елементу a. Відтак, візьмемо другий елемент bM такий, що bS_a^R і утворимо множину S_b^R = { x | xM і bRx } з елементів еквівалентних b і т.д. Таким чином одержимо сукупність множин (можливо, нескінченну) {S_a^R,S_b^R,...}. Побудована сукупність множин { S_i^R | iI} називається фактор-множиною множини M за еквівалентністю R і позначається M/R.

Приклад 1.16. 1. Фактор-множина за відношенням рівності E для будь-якої множини M має вигляд M/E = { {a} | aM}.

2. Фактор-множина для відношення "конгруентні за модулем 3" на множині N натуральних чисел складається з трьох класів { 3k | kN }, { 3k-1 | kN } і { 3k-2 | kN}.

Доведемо, що фактор-множина M/R є розбиттям множини M. Оскільки за побудовою кожний елемент множини M належить принаймні одній з множин S_i^R, iI, то S_i^R = M. Відтак припустимо, що для деяких S_a^RS_b^R існує елемент cS_a^RS_b^R. Тоді з cS_a^R випливає aRc, а з cS_b^R випливає bRc. Iз симетричності і транзитивності відношення R виводимо aRb і bRa. Iз співвідношення aRb і правила побудови множини S_a^R маємо S_a^RS_b^R, а з bRa і правила побудови множини S_b^R одержуємо протилежне включення S_b^RS_a^R. Отже, S_a^R=S_b^R, і з одержаної суперечності випливає справедливість сформульованого твердження.

Очевидно, що будь-які два елементи з одного класу S_i^R еквівалентні між собою, в той час як будь-які два елементи з різних класів фактор-множини M/R нееквівалентні. Класи S_i^R називають класами еквівалентності за відношенням R. Клас еквівалентності, який містить елемент aM часто позначають через [a]_R.

Потужність фактор-множини |M/R| називається індексом розбиття або індексом відношення еквівалентності R.

З іншого боку, припустімо, що для множини M задано деяке розбиття {S_i | iI }. Побудуємо відношення T на множині M за таким правилом: aTb для a,bM тоді і тільки тоді, коли a і b належать тій самій множині S_i розбиття. Неважко переконатись, що відношення T є рефлексивним, симетричним і транзитивним, тобто є відношенням еквівалентності на множині M.

Отже, справедлива така теорема.

Теорема 1.10. Iснує взаємно однозначна відповідність між усіма можливими еквівалентностями на множині M і всіма розбиттями множини M. Тобто, кожному відношенню еквівалентності на множині M відповідає єдине розбиття даної множини на класи і, навпаки, кожне розбиття множини M однозначно задає деяке відношення еквівалентності на M.

Нехай R відношення еквівалентності на множині M. Відображення множини M на фактор-множину M/R, яке кожному елементу aM ставить у відповідність клас еквівалентності S_a^R, якому належить елемент a, називається канонічним або природним відображенням множини M на фактор-множину M/R.

13. Відношення порядку

Відношення R на множині M називається відношенням часткового (нестрогого) порядку, якщо воно рефлексивне, антисиметричне і транзитивне, тобто

1. aRa для всіх aM (рефлексивність),

2. Якщо aRb і bRa, то a = b (антисиметричність),

3. Якщо aRb і bRc, то aRc (транзитивність).

Множина M, на якій задано деякий частковий порядок, називається частково впорядкованою множиною. Елементи a,bM назвемо порівнюваними за відношенням R, якщо виконується aRb або bRa.

Частково впорядкована множина M, в якій будь-які два елементи є порівнюваними між собою, називається лінійно впорядкованою множиною або ланцюгом. Відповідне відношення R, задане на лінійно впорядкованій множині, називається лінійним (досконалим) порядком. Таким чином, відношення R на множині M називається відношенням лінійного порядку, якщо воно рефлексивне, антисиметричне, транзитивне і для будь-якої пари елементів a,bM виконується aRb або bRa.

Для позначення відношень порядку будемо використовувати знаки і , які повторюють звичайні математичні знаки і . Тобто для відношення порядку R замість aRb будемо записувати a b або b a і читати "a менше або дорівнює b" або "b більше або дорівнює a" відповідно. Очевидно, що є оберненим відношенням до відношення .

За кожним відношенням часткового порядку на довільній множині M можна побудувати інше відношення < на M, поклавши a < b тоді і лише тоді, коли ab і ab. Це відношення називається відношенням строгого порядку на множині M. Зрозуміло, що відношення строгого порядку антирефлексивне, транзитивне, а також задовольняє умові так званої сильної антисиметричності або асиметричності, тобто для жодної пари a,bM не може одночасно виконуватись a<b і b<a.

З іншого боку, за довільним відношенням строгого порядку < на множині M однозначно можна побудувати відповідне відношення часткового (нестрогого) порядку , поклавши a b тоді і тільки тоді, коли a < b або a = b, a,bM. З огляду на такий простий зв'язок між відношеннями часткового (нестрогого) і строгого порядку можна обмежитись вивченням лише одного з цих порядків, наприклад, .

Приклад 1.17. 1. Відношення і < ( і > ) є відношеннями відповідно часткового і строгого порядку на множинах чисел N, Z і R. Більше того, множини N, Z і R, а також будь-які їхні підмножини, є лінійно впорядкованими множинами за відношеннями або .

2. Частковим порядком є відношення рівності i_M на будь-якій множині M. Цей порядок іноді називають тривіальним.

3. Відношення нестрогого включення є відношенням часткового порядку, а відношення - відношенням строгого порядку на множині (A) всіх підмножин (булеані) заданої множини A.

4. Задамо відношення і < на множині R кортежів дійсних чисел довжини n наступним чином: (a₁,a₂,...,a_n)(b₁,b₂,...,b_n ), якщо a₁b₁, a₂b₂,..., a_nb_n; аналогічно (a₁,a₂,...,a_n)<(b₁,b₂,...,b_n), якщо (a₁,a₂,...,a_n)(b₁,b₂,...,b_n) і принаймні для однієї координати i=1,,...,n виконується a_i<b_i.

...