7.1: Відносини

Хоча не існує узгодженого універсального визначення математики, можна стверджувати, що математика зосереджена на вивченні закономірностей і взаємозв'язків. Певні типи відносин відбуваються знову і знову в математиці. Одним із способів формалізації абстрактного характеру та структури цих відносин є поняття відносин. У розділі 8 ми побачимо, що функція - це особливий тип відношення.

Нагадаємо з розділу 3.5, що декартовим добутком двох множин\(A\) і\(B\), написано\(A\times B\), є сукупністю всіх впорядкованих пар\((a,b)\), де\(a\in A\) і\(b\in B\). Тобто,\(A\times B=\{(a,b)\mid a\in A, b\in B\}\).

Визначення 7.1. Нехай\(A\) і\(B\) будуть набори. \(R\)Відношення від\(A\) до \(B\)є підмножиною\(A \times B\). Якщо\(R\) це відношення від\(A\) до\(B\) і\((a,b)\in {R}\), то ми говоримо, що\(a\) пов'язано з \(b\)і ми можемо написати\(aR\) \(b\) замість\((a,b)\in{R}\). Якщо\(R\) відношення від\(A\) до тієї ж множини\(A\), то ми говоримо, що\(R\) це відношення на \(A\).

Приклад 7.2. Множина\(\mathbb{N}\times \mathbb{R}\) з Задача 3.55 є прикладом відношення на\(\mathbb{R}\) так як\(\mathbb{N}\times \mathbb{R}\) є підмножиною\(\mathbb{R}\times \mathbb{R}\).

Важливо зауважити, що має значення порядок, в якому ми пишемо речі для відносин. Зокрема, якщо\(R\) це відношення від\(A\) до\(B\) і\(a R b\), то це може бути, а може бути і не так\(bR a\).

Приклад 7.3. Якщо\(A=\{a,b,c,d,e\}\) і\(B=\{1,2,3,4\}\), то множина впорядкованих пар\[R=\{(a,1),(a,2),(a,4),(c,2),(d,2),(e,2),(e,4)\}\] є прикладом відношення від\(A\) до\(B\). У цьому випадку ми могли б написати\((c,2)\in{R}\) або\(cR 2\). Можна також сказати, що\(a\) це пов'язано з 1, 2 та 4.

Приклад 7.4. Як і в попередньому прикладі, нехай\(A=\{a,b,c,d,e\}\). Одне з можливих\(A\) співвідношень на задається\[R=\{(a,a),(a,b),(a,c),(b,b),(b,a),(b,c),(c,d),(c,e),(d,d),(d,a),(d,c),(e,a)\}.\]

Приклад 7.5. Розглянемо набір акаунтів\(A\) на платформі соціальних медіа Twitter. У Twitter кожен обліковий запис має набір облікових записів, за якими вони стежать. Ми можемо змоделювати цю ситуацію математично, використовуючи відношення на\(A\). Визначте\(T\) на\(A\) через,\(xTy\) якщо\(x\) слід\(y\) на Twitter. Як набір\[T=\{(x,y)\in A\times A\mid x\text{ follows }y\text{ on Twitter}\}.\]

Приклад 7.6. Ви вже знайомі з багатьма відносинами. Наприклад,\(=\)\(\leq\), і\(<\) є кожним прикладом відносин на дійсних числах. Можна сказати, що\((3,\pi)\) це у відношенні\(\leq\) та відношенні,\(<\) оскільки\(3\leq \pi\) і\(3<\pi\). Однак\((3,\pi)\) це не у відношенні\(=\) з тих пір\(3\neq \pi\). Крім того, зверніть увагу, що порядок має значення для відносин\(\leq\) і\(<\) ще не для\(=\). Наприклад,\((-\sqrt{2}, 4)\) знаходиться в відношенні\(\leq\) поки\((4,-\sqrt{2})\) немає.

Приклад 7.7. Визначте відношення\(S\) від\(\{-1,1\}\) до\(\mathbb{Z}\) via,\(1Sx\) якщо\(x\) парне, а\(-1Sx\) якщо\(x\) непарне. \(1\)Тобто пов'язана з усіма парними цілими числами і\(-1\) пов'язана з усіма непарними цілими числами.

Приклад 7.8. Нехай\(A\) буде будь-який набір. Так як\(\emptyset \subseteq A\times A\), порожній набір утворює відношення on\(A\). Це відношення називається порожнім відношенням на\(A\).

Відносини можна представити за допомогою диграфів. Диграф (скорочено від орієнтованого графа) - це дискретний граф, який складається з безлічі вершин, з'єднаних ребрами, де ребра мають напрямок, пов'язаний з ними. Якщо\(R\) відношення від\(A\) до\(B\), то елементи\(A\) і\(B\) є вершинами диграфа і є спрямованим ребром від\(a\in A\) до\(b\in B\) if \((a,b)\)знаходиться в співвідношенні\(R\) (тобто\(aR b\)). Ми можемо візуально представляти диграфи, використовуючи точки для представлення вершин і стрілок для представлення спрямованих країв. Ми не будемо робити різниці між диграфом та його візуальним зображенням. Використання диграфа для представлення відношення може бути недоцільним, якщо є велика кількість вершин або спрямованих ребер.

Приклад 7.9. Розглянемо відношення, наведене в прикладі 7.3. Відповідний диграф зображений на малюнку 7.1. Зверніть увагу, що ми розмістили вершини, відповідні елементам зліва, а елементи\(B\) праворуч.\(A\) Це стандартна практика, але насправді важливо крайові з'єднання, а не те, як вершини розміщуються на сторінці.

= [коло, малювати, заливка = сірий, внутрішній SEP = 0pt, мінімальний розмір = 5 мм] = [малювати, -стелс]

Завдання 7.10. Нехай\(A=\{1,2,3,4,5,6\}\) і\(B=\{1,2,3,4\}\) і визначити\(D\) від\(A\) до\(B\) через\((a,b)\in D\) якщо\(a-b\) ділиться на 2. Перерахуйте впорядковані пари\(D\) і намалюйте відповідний диграф.

Якщо\(R\) це відношення на\(A\) (тобто відношення від\(A\) до\(A\)), то ми можемо спростити структуру диграфа, використовуючи лише одну копію\(A\) для вершин. У цьому випадку ми можемо спрямувати ребра, які вказують від вершини до себе. При малюванні диграфів для відношення на множині ми будемо за замовчуванням використовувати цей спрощений диграф (як той, що зображений на малюнку 7.2 (b)).

Приклад 7.11. Рисунок 7.2 (a) представляє відношення Прикладу 7.4 як диграф від\(A\) до,\(A\) тоді як диграф на малюнку 7.2 (b) забезпечує обтічне уявлення того ж відношення, яке використовує елементи\(A\) лише один раз, а не двічі.

Завдання 7.12. Нехай\(A=\{1,2,3,4,5,6\}\) і визначити\(|\) на\(A\) через\(x|y\) якщо\(x\) ділить\(y\). Перерахуйте впорядковані пари\(|\) і намалюйте відповідний диграф.

Рисунок 7.1: Диграф для відношення від A = {a, b, c, d, e} до B = {1,2,3,4}.

Рисунок 7.2: Дві варіації диграфів для співвідношення на A = {a, b, c, d, e}.

Завдання 7.13. Дозвольте\(A=\{a,b,c,d\}\) і визначте\(R\) на\(A\) через\[{R}=\{(a,a),(a,b),(a,c),(b,b),(b,a),(b,c),(c,c),(c,a),(c,b),(d,d)\}.\]

1. Намалюйте диграф для\(R\).
2. Намалюйте диграф для порожнього відношення\(A\).

Ми також можемо візуально представляти відношення шляхом побудови точок у відношенні. Зокрема, якщо\(R\) це відношення від\(A\) до\(B\) і\(aR b\), ми можемо побудувати всі точки,\((a,b)\) які задовольняють\(aR b\) у двох вимірах, де ми інтерпретуємо\(A\) множину як горизонтальна вісь і\(B\) повинна бути вертикальною віссю. Ми будемо називати це візуальне уявлення відношення як графік відношення.

Приклад 7.14. Коли ми пишемо\(x^2+y^2=1\), ми неявно визначаємо відношення. Зокрема, відношення - це сукупність впорядкованих пар\((x,y)\) задовольняють\(x^2+y^2=1\), а саме\(\{(x,y)\in \mathbb{R}^2 \mid x^2+y^2=1\}\). Графік цього співвідношення в\(\mathbb{R}^2\) є одиничною окружністю, центрованою на початку в площині, як показано на малюнку 7.3.

Малюнок 7.3: Графік співвідношення, визначеного x ² + y ² = 1.

Завдання 7.15. Для кожного з наведених нижче параметрів намалюйте частину графіка, яка представляє відношення як підмножину\(\mathbb{R}^2\).

1. \(\{(x,y)\in \mathbb{R}^2 \mid y=x^2\}\)
2. \(\{(x,y)\in \mathbb{Z}^2 \mid y=x^2\}\)
3. \(\{(x,y)\in \mathbb{R}^2 \mid y^2=x\}\)
4. \(\{(x,y)\in \mathbb{N}\times \mathbb{R} \mid y^2=x\}\)

Завдання 7.16. Намалюйте частину графіка, яка представляє відношення\(\leq\) на\(\mathbb{R}\).

Для відношення на множині природно розглядати сукупність елементів, з якими пов'язаний даний елемент. Наприклад, «Список підписів» користувача у Twitter - це набір облікових записів у Twitter, за якими користувач стежить.

Визначення 7.17. \(R\)Дозволяти відношення на множині\(A\). Для кожного\(a\in A\) ми визначаємо набір родичів\(a\) по відношенню до \(R\)через\[rel(a,R):= \{b\in A\mid aR b\}.\] Ми також визначаємо колекцію наборів родичів \(R\)по відношенню до\[Rel(R):= \{rel(a)\mid a\in A\}.\]

Якщо\(R\) зрозуміло з контексту, ми зазвичай\(rel(a)\) пишемо замість\(rel(a,R)\). З точки зору диграфів,\(rel(a)\) це сукупність вершин, які мають спрямоване ребро, спрямоване на них від вершини, позначеної\(a\). У теорії графів ця колекція вершин називається поза сусідством\(a\) і кожна така вершина називається поза сусідом. Зверніть увагу, що\(Rel(R)\) це набір наборів. Зокрема, елемент в\(Rel(R)\) є підмножиною\(A\) —еквівалентно, елементом\(\mathcal{P}(A)\).

Завдання 7.18. Розглянемо відношення, наведене в прикладі 7.4. Оглядаючи впорядковані пари в\(R\) або дивлячись на диграф на малюнку 7.2 (b), ми бачимо, що\[rel(a) = \{a,b,c\},\ rel(b) = \{a,b,c\},\ rel(c) = \{d,e\},\ rel(d) = \{a,c,d\},\ rel(e) = \{a\},\] так\(Rel(R) = \{\{a,b,c\},\{d,e\},\{a,c,d\},\{a\}\}\).

Завдання 7.19. Розглянемо відношення, наведене в задачі 7.13 (а). Знайти\(Rel(R)\), визначаючи\(rel(x)\) для кожного\(x\in A\).

Проблема 7.20. Опишіть збірник множин родичів щодо порожнього відношення з завдання 7.13 (б).

Завдання 7.21. \(P\)Дозвольте позначити набір всіх людей з обліковими записами на Facebook і визначити відношення\(F\) на\(P\) через\(xFy\) якщо\(x\) дружить з\(y\). Опишіть\(rel(\text{Maria})\), де Марія - ім'я конкретного користувача Facebook. Що таке\(Rel(F)\)?

Завдання 7.22. Визначте відношення\(\equiv_5\) на\(\mathbb{Z}\) via\(a\equiv_5 b\)\(a-b\) if ділиться на 5. Знайти\(rel(1)\),\(rel(2)\), і\(rel(6)\). Скільки різних наборів в\(Rel(\equiv_5)\)? Перерахуйте різні набори в\(Rel(\equiv_5)\).

Завдання 7.23. Розглянемо відношення\(\leq\) далі\(\mathbb{R}\). Якщо\(x\in \mathbb{R}\), що таке\(rel(x)\)?

Проблема 7.24. Припустимо,\(R\) це відношення на\(A=\{1,2,3,4,5\}\) таке\(rel(1)=\{1,3,4\}\), що\(rel(2)=\{4\}\),\(rel(3)=\{3,4,5\}\),\(rel(4)=\{1,2\}\),, і\(rel(5)=\emptyset\). Перерахуйте впорядковані пари\(R\) і намалюйте відповідний диграф.

Зараз ми розглянемо три важливі властивості, якими може володіти зв'язок на множині.

Визначення 7.25. \(R\)Дозволяти відношення на множині\(A\).

1. Відношення\(R\) є рефлексивним, якщо для всіх\(a\in A\),\(aR a\).
2. \(R\)Відношення симетричне якщо для всіх\(a,b\in A\), якщо\(aR b\), то\(bR a\).
3. \(R\)Відношення є перехідним якщо для всіх\(a,b,c\in A\), якщо\(aR b\) і\(bR c\), то\(aR c\).

Приклад 7.26. Ось кілька прикладів, які ілюструють поняття в попередньому визначенні.

1. Відношення\(=\) на\(\mathbb{R}\) є рефлексивним, симетричним і перехідним.
2. \(\leq\)Відношення є рефлексивним і перехідним\(\mathbb{R}\), але не симетричним. Однак зверніть увагу, що\(<\) є перехідним\(\mathbb{R}\), але ні симетричним, ні рефлексивним.
3. Якщо\(S\) множина, то\(\subseteq\) on\(\mathcal{P}(S)\) є рефлексивним і перехідним, але не симетричним.

Завдання 7.27. Визначте, чи є відносини, наведені в кожному з наступних, рефлексивним, симетричним або перехідним.

1. Приклад 7.4
2. Проблема 7.13

Завдання 7.28. Припустимо,\(R\) це відношення на множині\(A\).

1. Поясніть, що це означає\(R\), щоб не бути рефлексивним.
2. Поясніть, що означає\(R\), щоб не бути симетричним.
3. Поясніть, що це означає\(R\), щоб не бути перехідним.

Завдання 7.29. Нехай\(A=\{a,b,c,d,e\}\).

1. \(R\)Визначте відношення\(A\), яке є рефлексивним, але не симетричним або перехідним.
2. \(S\)Визначте відношення\(A\), яке є симетричним, але не рефлексивним або перехідним.
3. \(T\)Визначте відношення\(A\), яке є перехідним, але не рефлексивним або симетричним.

Завдання 7.39. Задано відношення\(R\) на скінченній множині\(A\), опишіть, як виглядає кожен з рефлексивних, симетричних і транзитивних з точки зору диграфа. Тобто малюйте картинки, які представляють кожну з рефлексивних, симетричних і перехідних. Одна річ, яку слід пам'ятати, полягає в тому, що елементи, що використовуються у визначеннях симетричних та перехідних, не повинні бути різними. Отже, вам може знадобитися розглянути кілька випадків.

Нижче ми надаємо скелетні докази, щоб довести, що відношення є рефлексивним, симетричним або перехідним. Зверніть увагу, що скелетний доказ доказу того, що відношення є рефлексивним, є окремим випадком Skeleton Proof 2.81. Аналогічно, скелетні докази, що включають симетричні та перехідні, є окремими випадками Skeleton Proof 2.82. Важливо зазначити, що кожне відношення на порожній множині є вакуумно рефлексивним, симетричним та перехідним. У скелет доказів нижче, ми неявно припускаємо, що набір, про який йде мова, непорожній. У деяких обставин може знадобитися згадати про можливість порожнього набору.

Скелет Доказ 7.31. Ось загальна структура доведення того, що відношення є рефлексивним.

Припустимо,\(R\) це відношення на\(A\) визначене (або задовольняє)... [Використовуйте дане визначення (або опишіть дану властивість)\(R\)]. Нехай\(a\in A\).

\(\ldots\)[Використовуйте визначення (або властивість),\(R\) щоб перевірити, що\(aR a\)]\(\ldots\)

Тому відношення\(R\) є рефлексивним на\(A\).

Скелет Доказ 7.32. Ось загальна структура для доведення того, що відношення симетричне.

Припустимо,\(R\) це відношення на\(A\) визначене (або задовольняє)... [Використовуйте дане визначення (або опишіть дану властивість)\(R\)]. Нехай\(a, b\in A\) і припустимо\(aR b\).

\(\ldots\)[Використовуйте припущення, що\(aR b\) з визначенням (або властивістю)\(R\) для перевірки цього\(bR a\)]\(\ldots\)

Тому відношення\(R\) симетричне на\(A\).

Скелет Доказ 7.33. Ось загальна структура для доведення того, що відношення є перехідним.

Припустимо,\(R\) це відношення на\(A\) визначене (або задовольняє)... [Використовуйте дане визначення (або опишіть дану властивість)\(R\)]. Нехай\(a, b, c\in A\) і припустимо\(aR b\) і\(bR c\).

\(\ldots\)[Використовуйте припущення, що\(aR b\) і\(bR c\) з визначенням (або властивістю)\(R\) перевірити, що\(aR c\)]\(\ldots\)

Тому відношення\(R\) є перехідним далі\(A\).

Завдання 7.34. Визначте, чи є кожне з наступних відносин рефлексивним, симетричним або перехідним. У кожному конкретному випадку слід або надати конкретний зустрічний приклад, або доказ.

1. Розглянемо співвідношення,\(T\) описане в прикладі 7.5.
2. Розглянемо співвідношення,\(F\) описане в Задачі 7.21.
3. Розглянемо відношення,\(\equiv_5\) описане в Задачі 7.22.
4. \(P\)Дозволяти бути набір всіх людей і визначити\(H\) через\(xHy\) якщо\(x\) і\(y\) мати однакову висоту.
5. \(P\)Дозволяти бути набір всіх людей і визначити\(T\) через\(xTy\)\(x\) якщо вище, ніж\(y\).
6. Розглянемо відношення «ділить» на\(\mathbb{N}\).
7. \(L\)Дозволяти бути набір рядків і визначити\(||\) через\(l_1||l_2\)\(l_1\) якщо паралельно\(l_2\).
8. \(C[0,1]\)Дозволяти бути набір безперервних функцій на\([0,1]\). Визначте\(f\sim g\), якщо\[\int_0^1|f(x)|\ dx=\int_0^1|g(x)|\ dx.\]
9. Визначте\(R\) на\(\mathbb{N}\) через\(n+m\),\(nR m\) якщо навіть.
10. Визначте\(D\) на\(\mathbb{R}\) через\((x,y)\in D\) if\(x=2y\).
11. Визначте\(F\) на\(\mathbb{Z}\times \left(\mathbb{Z}\setminus \{0\}\right)\) через\((a,b)F(c,d)\) if\(ad=bc\). Чи визнаєте ви це відношення? Подумайте про дробах.
12. Визначте\(\sim\) на\(\mathbb{R}^2\) через\((x_1,y_1)\sim (x_2,y_2)\) if\(x_1^2+y_1^2=x_2^2+y_2^2\).
13. Визначити\(S\) на\(\mathbb{R}\) via\(xS y\) if\(\lfloor x\rfloor =\lfloor y\rfloor\), де\(\lfloor x\rfloor\) найбільше ціле число менше або дорівнює\(x\) (наприклад,\(\lfloor \pi\rfloor=3\),\(\lfloor -1.5\rfloor=-2\), і\(\lfloor 4\rfloor=4\)).
14. Визначте\(C\) на\(\mathbb{R}\) через\(xCy\) if\(|x-y|<1\).