1.3: Відносини

\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)

Відносини відіграють фундаментальну роль в теорії ймовірностей, як і в більшості інших областей математики.

Визначення та конструкції

Припустимо, що\(S\) і\(T\) є множинами. Відношення від\(S\) до\(T\) - це підмножина множини продукту\(S \times T\).

1. Домен\(R\) - це набір перших координат:\(\text{domain}(R) = \left\{x \in S: (x, y) \in R \text{ for some } y \in T\right\}\).
2. Діапазон\(R\) - це набір других координат:\(\text{range}(R) = \left\{y \in T: (x, y) \in R \text{ for some } x \in S\right\}\).

Відношення від\(S\) множини до себе - це відношення на\(S\).

Як випливає з назви, відношення\(R\) від\(S\) в\(T\) повинен визначити зв'язок між елементами і елементами\(T\),\(S\) і тому ми зазвичай використовуємо більш сугестивні позначення,\(x\,R\,y\) коли\((x, y) \in R\). Зверніть увагу, що область\(R\) - це проекції\( R \) на,\( S \) а діапазон\( R \) - це проекція\( R \) на\( T \).

Основні приклади

Припустимо, що\(S\) це множина і нагадаємо, що\(\mathscr{P}(S)\) позначає потужність\(S\) множини, колекція всіх підмножин\(S\). Співвідношення членства\(\in\) від\(S\) до\(\mathscr{P}(S)\) - це, мабуть, найважливіший і основний зв'язок у математиці. Дійсно, для нас це примітивні (невизначені) відносини - дано\(A\),\(x\) і ми припускаємо, що розуміємо сенс твердження\(x \in A\).

Іншим основним примітивним відношенням є відношення рівності\(=\) на заданому наборі об'єктів\(S\). Тобто дається два об'єкти\(x\) і\(y\), ми припускаємо, що розуміємо сенс висловлювання\(x = y\).

Інші основні відносини, які ви бачили

1. Відношення\(\subseteq\) підмножини on\(\mathscr{P}(S)\).
2. Відношення порядку\(\le\) на\(\R\)

Ці два належать до особливого класу відносин, відомого як часткові порядки, які ми вивчимо в наступному розділі. Зауважте, що функція\(f\)\(S\) from\(T\) into - це особливий тип відношення. Щоб порівняти два типи позначень (відношення і функції), зверніть увагу, що\(x\,f\,y\) це означає\(y = f(x)\).

Конструкції

Оскільки відношення - це просто набір впорядкованих пар, операції множини можуть бути використані для побудови нових відносин з існуючих.

якщо\(Q\) і\(R\) є відносини від\(S\) до\(T\), то так і є\(Q \cup R\),\(Q \cap R\),\(Q \setminus R\).

1. \(x(Q \cup R)y\)якщо і тільки якщо\(x\,Q\,y\) або\(x\,R\,y\).
2. \(x(Q \cap R)y\)якщо і тільки якщо\(x\,Q\,y\) і\(x\,R\,y\).
3. \(x(Q \setminus R)y\)якщо і тільки якщо\(x\,Q\,y\), але ні\(x\,R\,y\).
4. Якщо\(Q \subseteq R\) потім\(x\,Q\,y\) має на увазі\(x\,R\,y\).

Якщо\(R\) відношення від\(S\) до\(T\) і\(Q \subseteq R\), то\(Q\) це відношення від\(S\) до\(T\).

Обмеження відношення визначає нове відношення.

Якщо\(R\) це відношення на,\(S\) а\(A \subseteq S\) потім\(R_A = R \cap (A \times A)\) є відношення на\(A\), називається обмеженням\(R\) до\(A\).

Обернене відношення також визначає нове відношення.

Якщо\(R\) відношення від\(S\) до\(T\), обернене\(R\) - це відношення від\(T\) до,\(S\) визначене\[ y\,R^{-1}\,x \text{ if and only if } x\,R\,y \]

Рівнозначно,\(R^{-1} = \{(y, x): (x, y) \in R\}\). Зауважте, що будь-яка функція\(f\)\(T\) from\(S\) into має зворотне відношення, але лише тоді, коли один до одного є зворотним відношенням також функція (обернена функція).\(f\) Композиція - ще один природний спосіб створення нових відносин з існуючих.

Припустимо, що\(Q\) це відношення від\(S\) до\(T\) і\(R\) що відношення від\(T\) до\(U\). Склад\(Q \circ R\) - це відношення від\(S\) до\(U\) визначається наступним чином: для\(x \in S\) і\(z \in U\),\(x(Q \circ R)z\) якщо і тільки в тому випадку, якщо існує\(y \in T\) таке, що\(x\,Q\,y\) і\(y\,R\,z\).

Зауважте, що позначення не відповідає позначенню, використовуваному для композиції функцій, по суті тому, що відносини читаються зліва направо, тоді як функції читаються справа наліво. Сподіваємося, невідповідність не викличе плутанини, так як ми завжди будемо використовувати позначення функцій для функцій.

Основні властивості

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

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

1. \(R\)є рефлексивним, якщо\(x\,R\,x\) для всіх\(x \in S\).
2. \(R\)є нерефлексивним, якщо не\(x \in S\) задовольняє\(x\,R\,x\).
3. \(R\)симетрична, якщо\(x\,R\,y\) має\(y\,R\,x\) на увазі для всіх\(x, \, y \in S\).
4. \(R\)є антисиметричним, якщо\(x\,R\,y\) і\(y\,R\,x\) має\(x = y\) на увазі для всіх\(x, \, y \in S\).
5. \(R\)є перехідним, якщо\(x\,R\,y\) і\(y\,R\,z\) має\(x\,R\,z\) на увазі для всіх\(x, \, y, \, z \in S\).

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

\(R\)Відношення на\(S\) є рефлексивним тоді і лише тоді, коли відношення рівності\(=\) на\(S\) є підмножиною\(R\).

Доказ

Це випливає з визначень. \( R \)є рефлексивним, якщо і тільки якщо\( (x, x) \in R \) для всіх\( x \in S \).

Відношення\(R\) на\(S\) є симетричним, якщо і тільки якщо\(R^{-1} = R\).

Доказ

Припустимо,\( R \) що симетрично. Якщо\( (x, y) \in R \) то\( (y, x) \in R \) і звідси\( (x, y) \in R^{-1} \). Якщо\( (x, y) \in R^{-1} \) то\( (y, x) \in R \) і звідси\( (x, y) \in R \). Таким чином\( R = R^{-1} \). І навпаки, припустимо\( R = R^{-1} \). Якщо\( (x, y) \in R \) то\( (x, y) \in R^{-1} \) і звідси\( (y, x) \in R \).

Відношення\(R\) на\(S\) є перехідним, якщо і тільки якщо\(R \circ R \subseteq R\).

Доказ

Припустимо, що\( R \) це перехідний характер. Якщо\( (x, z) \in R \circ R \) тоді існує\( y \in S \) таке, що\( (x, y) \in R \) і\( (y, z) \in R \). Але потім\( (x, z) \in R \) по транзитивності. Звідси\( R \circ R \subseteq R \). І навпаки, припустимо, що\( R \circ R \subseteq R \). Якщо\( (x, y) \in R \) і\( (y, z) \in R \) то\( (x, z) \in R \circ R \) і звідси\( (x, z) \in R \). Звідси\( R \) є перехідним.

\(R\)Відношення на\(S\) є антисиметричним тоді і лише тоді, коли\(R \cap R^{-1}\) є підмножиною відношення рівності\(=\) на\(S\).

Доказ

Повторно, цей результат\( R \) є антисиметричним, якщо і лише тоді, коли\( (x, y) \in R \cap R^{-1} \) має на увазі\( x = y \). Таким чином, припустимо, що\( R \) це антисиметрично. Якщо\( (x, y) \in R \cap R^{-1} \) тоді\( (x, y) \in R \) і\( (x, y) \in R^{-1} \). Але тоді\( (y, x) \in R \) так антисиметрією,\( x = y \). І навпаки, припустимо, що це\( (x, y) \in R \cap R^{-1} \) означає\( x = y \). Якщо\( (x, y) \in R \) і\( (y, x) \in R \) то\( (x, y) \in R^{-1} \) і звідси\( (x, y) \in R \cap R^{-1} \). Таким чином\( x = y \), так\( R \) є антисиметричним.

Припустимо, що\(Q\) і\(R\) є відносини далі\(S\). Для кожного властивості нижче, якщо обидва\(Q\) і\(R\) мають властивість, то так і відбувається\(Q \cap R\).

1. рефлексивний
2. симетричні
3. перехідний

Доказ

1. Припустимо, що\( Q \) і\( R \) є рефлекторними. Потім\( (x, x) \in Q \) і\( (x, x) \in R \) для кожного,\( x \in S \) а значить,\( (x, x) \in Q \cap R \) для кожного\( x \in S \). Таким чином\( Q \cap R \), є рефлексивним.
2. Припустимо, що\( Q \) і\( R \) симетричні. Якщо\( (x, y) \in Q \cap R \) тоді\( (x, y) \in Q \) і\( (x, y) \in R \). Звідси\( (y, x) \in Q \) і\( (y, x) \in R \) так\( (y, x) \in Q \cap R \). \( Q \cap R \)Звідси симетрична.
3. Припустимо, що\( Q \) і\( R \) є перехідними. Якщо\( (x, y) \in Q \cap R \) і\( (y, z) \in Q \cap R \) то\( (x, y) \in Q \),\( (x, y) \in R \),\( (y, z) \in Q \), і\( (y, z) \in R \). Звідси\( (x, z) \in Q \) і\( (x, z) \in R \) так\( (x, z) \in Q \cap R \). Звідси\( Q \cap R \) є перехідним.

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

1. Дати явне визначення властивості \(R\)не рефлексивно.
2. Дати явне визначення властивості не\(R\) є безрефлексивним.
3. \(R\)Чи є які-небудь з властивостей\(R\) рефлексивним, не рефлексивним, не \(R\)є\(R\) іррефлексивним, не є іррефлексивним еквівалентом?

Відповідь

1. \( R \)не є рефлексивним тоді і тільки тоді, коли існує\( x \in S \) таке, що\( (x, x) \notin R \).
2. \( R \)не є іррефлексивним тоді і тільки тоді, коли існує\( x \in S \) таке, що\( (x, x) \in R \).
3. Ні.

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

1. Дайте явне визначення для властивості \(R\)не симетрично.
2. Дайте явне визначення для властивості \(R\)не антисиметрично.
3. \(R\)Чи є будь-яке з властивостей\(R\) симетричне, не симетричне, \(R\)антисиметричне, не\(R\) є антисиметричним еквівалентом?

Відповідь

1. \( R \)не симетрична тоді і тільки тоді, коли існують\( x, \, y \in S \) такі, що\( (x, y) \in R \) і\( (y, x) \notin R \).
2. \( R \)не є антисиметричним тоді і тільки тоді, коли існують відмінні\( x, \, y \in S \) такі, що\( (x, y) \in R \) і\( (y, x) \in R \).
3. Ні.

Обчислювальні вправи

\(R\)Дозволяти відношення, визначене\(\R\) на\(x\,R\,y\) якщо і тільки якщо\(\sin(x) = \sin(y)\). Визначте\(R\), чи має кожне з наступних властивостей:

1. рефлексивний
2. симетричні
3. перехідний
4. іррефлексивний
5. антисиметричний

Відповідь

1. так
2. так
3. так
4. ні
5. ні

\(R\)Відношення в попередній вправі є членом важливого класу відносин еквівалентності.

\(R\)Дозволяти відношення, визначене\(\R\) на\(x\,R\,y\) якщо і тільки якщо\(x^2 + y^2 \le 1\). Визначте\(R\), чи має кожне з наступних властивостей:

1. рефлексивний
2. симетричні
3. перехідний
4. іррефлексивний
5. антисиметричний

Відповідь

1. ні
2. так
3. ні
4. ні
5. ні