7.1: Двійкові відносини

Нагадаємо, що за визначенням будь-яка функція\(f : A \rightarrow B\) являє собою набір впорядкованих пар. Точніше, кожен елемент\(f\) - це впорядкована пара\((a, b)\), така, що\(a \in A\) і\(b \in B\). Тому кожен елемент\(f\) є елементом\(A \times B\), тому\(f\) є підмножиною\(A \times B\). \[\text { Every function from } A \text { to } B \text { is a subset of } A \times B \text {. }\]

Приклад\(7.1.1\).

Функція\(\text {mother: PEOPLE } \rightarrow \text { PEOPLE }\) представлена множиною\[\{(p, m) \in \text { PEOPLE } \times \text { PEOPLE } \mid m \text { is the mother of } p\} .\]

Багато інших зв'язків також можуть бути представлені підмножинами\(\text {PEOPLE } \times \text { PEOPLE}\), навіть якщо вони не є функціями. Наприклад, син не є функцією, тому що у деяких людей більше одного сина (або тому, що у деяких людей взагалі немає синів). Однак ми можемо уявити це відношення множиною\[\{(p, s) \in \text { PEOPLE } \times \text { PEOPLE } \mid s \text { is a son of } p\} .\]

Насправді будь-які відносини, які ви можете визначити між двома людьми (або, якщо говорити про це офіційною мовою логіки, будь-який двійковий присудок на множині\(\text {PEOPLE}\)) може бути представлений підмножиною\(\text {PEOPLE } \times \text { PEOPLE}\). Кілька прикладів можливих відносин:

• \(x\)є сестрою\(y\)
• \(x\)\(y\)знав у старших класах
• \(x\)вище, ніж\(y\)
• \(x\)і\(y\) знаходяться в одному класі математики
• і т.д.

Визнаючи це, математики просто визначають відношення як набір впорядкованих пар; тобто відношення є будь-якою підмножиною\(A \times B\). На відміну від випадку функцій, обмежень немає — кожна підмножина є співвідношенням.

Визначення\(7.1.2\).

Припустимо\(A\) і\(B\) є множинами.

1. Будь-яка\(A \times B\) підмножина називається відношенням від\(A\) до\(B\).
2. Для особливого випадку\(A = B\), коли будь-яка підмножина\(A \times A\) називається двійковим відношенням on\(A\).

Ми в основному будемо займатися бінарними відносинами, а не відносинами від якогось набору\(A\) до якоїсь іншої множини\(B\).

Приклад\(7.1.3\).

Деякі приклади бінарних відносин на\(\text {PEOPLE}\):\(\text {brother, sister, aunt, uncle, mother, father, grandfather, cousin, etc.}\)

Визначення\(7.1.4\).

Ми можемо намалювати картинку, щоб представляти будь-яке задане двійкове відношення на будь-якому заданому наборі\(A\):

• Намалюйте крапку для кожного елемента\(A\).
• Для\(a, b \in A\), намалюйте стрілку від\(a\) до\(b\) якщо і тільки якщо\((a, b)\) є елементом відношення.

Отримана картинка називається диграфом. (Слово вимовляється «Die-graff» — це скорочення від «орієнтований граф».)

Приклад\(7.1.5\).

Нехай\(A = \{1, 2, 3, 4, 5\}\). Ми можемо визначити двійкове відношення\(R\) на,\(A\) дозволивши\[R=\left\{(x, y) \mid x^{2}+y<10\right\} .\]

Це двійкове відношення представлено наступним диграфом:

Наприклад, зверніть увагу на те\((x, 4) \in R \text { iff } x \in\{1,2\}\), що і диграф має стрілки від 1 до 4 і від 2 до 4.

Вправа\(7.1.6\).

Нехай\(B\) буде набір, що складається з вас, ваших братів і сестер, ваших батьків і ваших бабусь і дідусів. Намалюйте диграф, який представляє кожне з наступних двійкових відносин на\(B\).

1. Відносини «коли-небудь мали те ж прізвище, що і».
2. Відношення «є дитиною».
3. Відносини «коли-небудь були одружені».

Приклад\(7.1.7\).

Ця книга (як і інші підручники з математики) стосується в основному відносин на множині математичних об'єктів. Ось кілька відомих прикладів:

1. Відношення менше, ніж «\(<\)» - це двійкове відношення на\(\mathbb{R}\).
   Тобто для будь-яких дійсних чисел\(x\) і\(y\), твердження або\(x < y\) істинне, або помилкове.
2. Співвідношення рівності «\(=\)» - це бінарне відношення на всьому всесвіті дискурсу\(\mathcal{U}\).
3. Відношення підмножини «\(\subset\)» є двійковим відношенням на колекцію всіх множин в\(\mathcal{U}\).
4. Відношення «\(x\)isjoint from\(y\)» також є двійковим відношенням на колекцію всіх множин в\(\mathcal{U}\).

Позначення\(7.1.8\).

Припустимо,\(R\) це двійкове відношення на множині\(A\). Для\(a_{1}, a_{2} \in A\):

1. Щоб це позначити\((a_{1}, a_{2}) \in R\), ми можемо написати\(a_{1} R a_{2}\).
2. Щоб це позначити\(\left(a_{1}, a_{2}\right) \notin R\), ми можемо написати\(a_{1} \not R a_{2}\).

Існує три основні властивості, які може мати або не мати будь-яке задане двійкове відношення:

Визначення\(7.1.9\).

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

1. Ми говоримо, що\(R\) це рефлексивно iff\(\forall a \in A,(a R a)\).
2. Ми говоримо, що\(R\) це симетрично iff\(\forall a, b \in A,((a R b) \Rightarrow(b R a))\).
3. Ми говоримо, що\(R\) це перехідний iff\(\forall a, b, c \in A,(((a R b) \&(b R c)) \Rightarrow(a R c))\).

Приклад\(7.1.10\).

1. «\(=\)» є рефлексивним, симетричним і перехідним. »
2. «\(<\)» є перехідним, але ні рефлексивним, ні симетричним.
3. «\(\subset\)» є перехідним і рефлексивним, але не симетричним.

Приклад\(7.1.12\).

Розглянемо наступне двійкове відношення\(R\) на\(\{1, 2, 3\}\):\[R=\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}\]

1. \(R\)є рефлексивним, тому що\(1 R 1,2 R 2,\), і\(3 R 3\).
2. \(R\)є симетричним, тому що\((a, b) \in R\), для кожного,\((b, a)\) розворот також в\(R\).
3. \(R\)не є перехідним, тому що\(1 R 2\) і\(2 R 3\), але\(1 \not R 3\).

Вправа\(7.1.12\).

Знайдіть бінарні відносини на\(\{1, 2, 3\}\) які є:

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

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