7.2: Властивості відносин

Якщо\(R\) це відношення від\(A\) до\(A\), то\(R\subseteq A\times A\); ми говоримо, що\(R\) це відношення на\(\mathbf{A}\).

Визначення

\(R\)Відносини на\(A\), як кажуть,

• рефлексивний якщо\((a,a)\in R\,a\) для всіх\(a\in A\),
• іррефлексивний якщо\((a,a)\notin R\) для всіх\(a\in A\),
• симетричний якщо\((a,b)\in R \Rightarrow (b,a)\in R\) для всіх\(a,b\in A\),
• антисиметричний якщо\([(a,b)\in R\,\wedge\,(b,a)\in R] \Rightarrow a=b\) для всіх\(a,b\in A\),
• перехідний якщо\([(a,b)\in R\,\wedge\,(b,c)\in R] \Rightarrow (a,c)\in R\) для всіх\(a,b,c\in A\).

Це важливі визначення, тому повторимо їх, використовуючи реляційні позначення\(a\,R\,b\):

• рефлексивний якщо\(a\,R\,a\) для всіх\(a\in A\),
• іррефлексивний якщо\(a\!\not\!R\,a\) (тобто\(\overline{a\,R\,a}\)) для всіх\(a\in A\),
• симетричний якщо\(a\,R\,b \Rightarrow b\,R\,a\) для всіх\(a,b\in A\),
• антисиметричний якщо\([(a\,R\,b) \wedge (b\,R\,a)] \Rightarrow a=b\) для всіх\(a,b\in A\),
• перехідний якщо\([(a\,R\,b) \wedge (b\,R\,c)] \Rightarrow a\,R\,c\) для всіх\(a,b,c\in A\).

Зауваження

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

Зауваження

Багато студентів вважають поняття симетрії і антисиметрії заплутаним. Незважаючи на те, що назва може підказати про це, антисиметрія не є протилежністю симетрії. Можливо, щоб відношення було як симетричним, так і антисиметричним, а також можливе, щоб відношення було як несиметричним, так і неантисиметричним. Хороший спосіб зрозуміти антисиметрію - подивитися на її контрапозитив:\[a\neq b \Rightarrow \overline{(a,b)\in R \,\wedge\, (b,a)\in R}. \nonumber\] Таким чином, якщо два різних елементи\(a\) і\(b\) пов'язані між собою (не кожна пара елементів повинна бути пов'язана), то або\(a\) пов'язана з\(b\), або\(b\) пов'язана з\(a\), але ні обидва. Отже, якщо знайти різні елементи\(a\) і\(b\) такі, що\((a,b)\in R\) і\((b,a)\in R\),\(R\) то не антисиметрично.

Приклад\(\PageIndex{1}\label{eg:SpecRel}\)

Порожнє відношення є підмножиною\(\emptyset\). Він явно іррефлексивний, отже, не рефлексивний. Щоб перевірити симетрію, ми хочемо знати, чи\(a\,R\,b \Rightarrow b\,R\,a\) для всіх\(a,b\in A\). Більш конкретно, ми хочемо знати, чи є\((a,b)\in \emptyset \Rightarrow (b,a)\in \emptyset\). Оскільки\((a,b)\in\emptyset\) завжди брехня, підтекст завжди вірний. Таким чином, відношення симетричне. Так само він антисиметричний і перехідний.

Повне співвідношення - це весь набір\(A\times A\). Він явно рефлексивний, отже, не іррефлексивний. Також банально, що він симетричний і перехідний. Це не антисиметричний хіба що\(|A|=1\).

Співвідношення ідентичності складається з впорядкованих пар виду\((a,a)\), де\(a\in A\). Іншими словами,\(a\,R\,b\) якщо і тільки якщо\(a=b\). Він є рефлексивним (отже, не іррефлексивним), симетричним, антисиметричним і перехідним.

Приклад\(\PageIndex{2}\label{eg:proprelat-02}\)

Розглянемо відношення\(R\) на множині,\(A=\{1,2,3,4\}\) визначене\[R = \{(1,1),(2,3),(2,4),(3,3),(3,4)\}. \nonumber\]

Оскільки\((2,2)\notin R\), і\((1,1)\in R\), відношення не є ні рефлексивним, ні нерефлексивним.

Ми маємо\((3,2)\notin R\),\((2,3)\in R\) але, таким\(R\) чином, не симетрично.

Для будь-якого\(a\neq b\), тільки одна з чотирьох можливостей\((a,b)\notin R\),\((b,a)\notin R\)\((a,b)\in R\), або\((b,a)\in R\) може виникнути, так\(R\) є антисиметричним.

Пройшовши всі впорядковані пари в\(R\), ми перевіряємо\((b,c)\in R\), чи є\((a,b)\in R\) і, ми завжди маємо\((a,c)\in R\). Це показує, що\(R\) є перехідним.

Тому\(R\) є антисиметричним і перехідним.

Приклад\(\PageIndex{3}\label{eg:proprelat-03}\)

Визначте відношення\(S\) на множині\(A=\{1,2,3,4\}\) відповідно до\[S = \{(2,3),(3,2)\}. \nonumber\]

Оскільки\((1,1),(2,2),(3,3),(4,4)\notin S\), відношення\(S\) є іррефлексивним, отже, воно не є рефлексивним.

Оскільки у нас всього дві впорядковані пари, і зрозуміло, що всякий раз\((a,b)\in S\), у нас теж є\((b,a)\in S\). Значить,\(S\) симетрична.

У нас є\((2,3)\in S\) і те й\((3,2)\in S\) інше, але\(2\neq3\). Значить, не\(S\) є антисиметричним.

Оскільки\((2,3)\in S\) і\((3,2)\in S\), але\((2,2)\notin S\), відношення не\(S\) є перехідним.

Робимо висновок, що\(S\) є безрефлексивним і симетричним.

практичні вправи\(\PageIndex{1}\label{he:proprelat-01}\)

\(R\)Визначте відношення множини\(\mathbb{R}\) як\[a\,R\,b \,\Leftrightarrow\, a\leq b. \nonumber\] Визначте, чи\(R\) є рефлексивним, іррефлексивним, симетричним, антисиметричним або перехідним.

практичні вправи\(\PageIndex{2}\label{he:proprelat-02}\)

Відношення\(S\) на множині\(\mathbb{R}^*\) визначається як\[a\,S\,b \,\Leftrightarrow\, ab>0. \nonumber\] Визначити, чи\(S\) є рефлексивним, іррефлексивним, симетричним, антисиметричним або перехідним.

Приклад\(\PageIndex{4}\label{eg:geomrelat}\)

Ось два приклади з геометрії. \({\cal T}\)Дозволяти набір трикутників, які можна намалювати на площині. Визначте відношення\(S\) на\({\cal T}\) таке, що\((T_1,T_2)\in S\) якщо і тільки якщо два трикутника схожі. Легко перевірити, що\(S\) є рефлексивним, симетричним та перехідним.

\({\cal L}\)Дозволяти бути множиною всіх (прямих) ліній на площині. Визначте відношення\(P\) на\({\cal L}\) відповідно до\((L_1,L_2)\in P\) якщо і тільки якщо\(L_1\) і\(L_2\) є паралельними лініями. Знову ж таки, очевидно, що\(P\) є рефлексивним, симетричним і перехідним.

Приклад\(\PageIndex{5}\label{eg:proprelat-04}\)

\(T\)Відношення на\(\mathbb{R}^*\) визначається як\[a\,T\,b \,\Leftrightarrow\, \frac{a}{b}\in\mathbb{Q}. \nonumber\]

Оскільки\(\frac{a}{a}=1\in\mathbb{Q}\) відношення\(T\) є рефлексивним; з цього випливає, що не\(T\) є іррефлексивним.

Відношення\(T\) симетричне, тому що якщо\(\frac{a}{b}\) може бути записано як\(\frac{m}{n}\) для деяких цілих чисел\(m\) і\(n\), то так само є його зворотним\(\frac{b}{a}\), тому що\(\frac{b}{a}=\frac{n}{m}\).

Оскільки\(\sqrt{2}\;T\sqrt{18}\) і\(\sqrt{18}\;T\sqrt{2}\), тим не менш\(\sqrt{2}\neq\sqrt{18}\), робимо висновок, що не\(T\) є антисиметричним.

Якщо\(\frac{a}{b}, \frac{b}{c}\in\mathbb{Q}\), то\(\frac{a}{b}= \frac{m}{n}\) і\(\frac{b}{c}= \frac{p}{q}\) для деяких ненульових цілих чисел\(m\)\(n\),\(p\),, і\(q\). Потім\(\frac{a}{c} = \frac{a}{b}\cdot\frac{b}{c} = \frac{mp}{nq} \in\mathbb{Q}\). Отже,\(T\) є перехідним.

Тому відношення\(T\) є рефлексивним, симетричним і перехідним.

практичні вправи\(\PageIndex{3}\label{he:proprelat-03}\)

Розглянемо відношення\(T\) на\(\mathbb{N}\) визначеному\[a\,T\,b \,\Leftrightarrow\, a\mid b. \nonumber\] Визначити, чи\(T\) є рефлексивним, іррефлексивним, симетричним, антисиметричним або перехідним.

практичні вправи\(\PageIndex{4}\label{he:proprelat-04}\)

Відношення\(U\) на множині\(\mathbb{Z}^*\) визначається як\[a\,U\,b \,\Leftrightarrow\, a\mid b. \nonumber\] Визначити, чи\(U\) є рефлексивним, іррефлексивним, симетричним, антисиметричним або перехідним.

Приклад\(\PageIndex{6}\label{eg:proprelat-05}\)

\(U\)Відношення на\(\mathbb{Z}\) визначається як\[a\,U\,b \,\Leftrightarrow\, 5\mid(a+b). \nonumber\]

• Відношення не\(U\) є рефлексивним, тому що\(5\nmid(1+1)\).
• Це також не є іррефлексивним, тому що\(5\mid(10+10)\).
• Якщо\(5\mid(a+b)\), то очевидно, що\(5\mid(b+a)\) тому\(a+b=b+a\). Таким чином,\(U\) є симетричним.
• Ми стверджуємо, що\(U\) це не антисиметрично. Наприклад,\(5\mid(2+3)\) і\(5\mid(3+2)\), поки\(2\neq3\).
• Він також не є перехідним. Наприклад,\(5\mid(1+4)\) і\(5\mid(4+6)\), але\(5\nmid(1+6)\).
• \(U\)Відношення симетричне.

практичні вправи\(\PageIndex{5}\label{he:proprelat-05}\)

Визначте, чи\(\cal U\) є таке відношення\(V\) на якомусь універсальному множині рефлексивним, іррефлексивним, симетричним, антисиметричним або перехідним:\[(S,T)\in V \,\Leftrightarrow\, S\subseteq T. \nonumber\]

Приклад\(\PageIndex{7}\label{eg:proprelat-06}\)

Розглянемо відношення\(V\) на множині\(A=\{0,1\}\) визначається відповідно до\[V = \{(0,0),(1,1)\}. \nonumber\]

Відношення\(V\) є рефлексивним, тому що\((0,0)\in V\) і\((1,1)\in V\). Отже, це не є нерефлексивним.

Вона явно симетрична, тому що\((a,b)\in V\) завжди має на увазі\((b,a)\in V\).

Дійсно\((a,b)\in V\), всякий раз\(a=b\), ми також повинні мати, тому що\(V\) складається лише з двох впорядкованих пар, обидві вони мають форму\((a,a)\). Звідси\(V\) випливає, що теж антисиметричний.

Подібний аргумент показує, що\(V\) є перехідним.

Відношення є рефлексивним, симетричним, антисиметричним і перехідним.

практичні вправи\(\PageIndex{6}\label{he:proprelat-06}\)

Визначте, чи рефлексивним, симетричним, антисиметричним або перехідним є наступне відношення\(W\) на непорожній набір осіб у спільноті:\[a\,W\,b \,\Leftrightarrow\, \mbox{$a$ and $b$ have the same last name}. \nonumber\]

Приклад\(\PageIndex{8}\label{eg:proprelat-07}\)

\(W\)Визначте відношення до непорожнього набору осіб у спільноті як\[a\,W\,b \,\Leftrightarrow\, \mbox{$a$ is a child of $b$}. \nonumber\]

• Ніхто не може бути дитиною себе чи себе, отже,\(W\) не може бути рефлексивним. Натомість це нерефлексивно.
• Очевидно, що\(W\) не може бути симетричним.
• Це може здатися дивним з визначення, яке\(W\) є антисиметричним:\[(a \mbox{ is a child of } b) \wedge (b\mbox{ is a child of } a) \Rightarrow a=b, \label{eqn:child}\] але це правда! Причина в тому, якщо\(a\) є дитиною\(b\), то\(b\) не може бути дитиною\(a\). Це робить кон'юнкцію\[(a \mbox{ is a child of } b) \wedge (b\mbox{ is a child of } a) \nonumber\] false, що робить імплікацію (\ ref {eqn:child}) істинним.
• Подібний аргумент має, якщо\(b\) є дитиною\(a\), і якщо ні\(a\) є дитиною,\(b\) ні\(b\) є дитиною\(a\). Незалежно від того, що відбувається, імплікація (\ ref {eqn:child}) завжди вірна. Тому\(W\) є антисиметричним.
• Це може допомогти, якщо ми подивимося на антисиметрію під іншим кутом. Контрапозитив початкового визначення стверджує\(a\neq b\), що коли можуть статися три речі:

1. \(a\)і\(b\) незрівнянні (\(\overline{a\,W\,b}\)і\(\overline{b\,W\,a}\)), тобто\(a\) і не\(b\) пов'язані між собою;

а якщо\(a\) і\(b\) пов'язані, то або

1. \(a\,W\,b\)але\(\overline{b\,W\,a}\), або
2. \(b\,W\,a\)але\(\overline{a\,W\,b}\).

Використовуючи це спостереження, легко зрозуміти,\(W\) чому антисиметричний.

• Зрозуміло, що не\(W\) є перехідним.

Відношення буває іррефлексивним і антисиметричним.

Замість того, щоб використовувати два рядки вершин у диграфі, який представляє відношення на множині\(A\), ми можемо використовувати лише один набір вершин для представлення елементів\(A\). Спрямована лінія з'єднує\(a\) вершину з вершиною\(b\) тоді і тільки тоді,\(a\) коли елемент пов'язаний з елементом\(b\). Якщо\(b\) це також пов'язано з\(a\), дві вершини будуть з'єднані двома спрямованими лініями, по одній у кожному напрямку. Якщо\(a\) це пов'язано з самим собою, є цикл навколо вершини, що представляє\(a\). Див. Завдання 10 у Вправи 7.1.

З графічного подання визначаємо,\(R\) що відношення

• Рефлексивний, якщо є петля на кожній вершині\(G\).
• Іррефлексивний, якщо\(G\) є безпетельним.
• Симетричний, якщо кожна пара вершин з'єднана жодною або рівно двома спрямованими лініями в протилежних напрямках.
• Антисиметричний, якщо кожна пара вершин з'єднана жодною або точно однією спрямованою лінією.
• Перехідний, якщо для кожного односпрямованого шляху, що з'єднує три вершини\(a,b,c\), у такому порядку також існує спрямована лінія, що приєднується\(a\) до\(c\).

Матриця випадковості\(M=(m_{ij})\) для відношення на\(A\) є квадратною матрицею. Ми знаходимо,\(R\) що

• Рефлексивний, якщо кожен запис на головній діагоналі\(M\) дорівнює 1.
• Irreflexive, якщо кожен запис на головній діагоналі\(M\) дорівнює 0.
• \(M\)Симетричний якщо симетричний, тобто\(m_{ij}=m_{ji}\) коли завгодно\(i\neq j\).
• Антисиметричний якщо\(i\neq j\) має на увазі, що принаймні один з\(m_{ij}\) і\(m_{ji}\) дорівнює нулю, тобто\(m_{ij} m_{ji} = 0\).
• Перехідний якщо\((M^2)_{ij} > 0\) має на увазі\(m_{ij}>0\) коли завгодно\(i\neq j\).

Наприклад, матриця випадковості для відношення ідентичності складається з 1s на головній діагоналі та 0 скрізь. Це називається матрицею ідентичності. Якщо відношення\(R\) на\(A\) є одночасно симетричним і антисиметричним, його недіагональні записи є нулями, тому воно є підмножиною відношення ідентичності.

Це цікава вправа, щоб довести тест на транзитивність. Застосуйте його до Прикладу 7.2.2, щоб побачити, як це працює.

Резюме та огляд

• Відношення від\(A\) множини до себе називається відношенням на\(A\).
• З огляду\(R\) на будь-яке відношення до множини\(A\), нас цікавлять п'ять властивостей, які\(R\) можуть мати або не мати.
• \(R\)Відношення, як кажуть, є рефлексивним, якщо кожен елемент пов'язаний із самим собою, тобто якщо\(x\,R\,x\) для кожного\(x\in A\).
• \(R\)Відношення, як кажуть, є іррефлексивним, якщо жоден елемент не пов'язаний із самим собою, тобто якщо\(x\not\!\!R\,x\) для кожного\(x\in A\).
• Рефлексивне властивість та іррефлексивне властивість є взаємовиключними, і не можливо, щоб відношення не було ні рефлексивним, ні іррефлексивним.
• \(R\)Відношення, як кажуть, симетричне, якщо відношення може йти в обох напрямках, тобто якщо\(x\,R\,y\) мається\(y\,R\,x\) на увазі для будь-якого\(x,y\in A\).
• \(R\)Відношення, як кажуть, є антисиметричним, якщо дано будь-які два різних елементи\(x\)\(x\) і\(y\), або (i) і ніяк не\(y\) пов'язані, або (ii) якщо\(x\) і\(y\) пов'язані, вони можуть бути пов'язані лише в одному напрямку.
• Компактний спосіб визначення антисиметрії: якщо\(x\,R\,y\) і\(y\,R\,x\), то ми повинні мати\(x=y\).
• Нарешті, зв'язок, як кажуть, є перехідним, якщо ми можемо пройти уздовж відношення і пов'язати два елементи, якщо вони пов'язані через третій елемент.
• Точніше,\(R\) є перехідним, якщо\(x\,R\,y\) і\(y\,R\,z\) має на увазі, що\(x\,R\,z\).

Вправа\(\PageIndex{1}\label{ex:proprelat-01}\)

Для кожного співвідношення в задачі 1 у Вправи 1.1 визначте, які з п'яти властивостей задовольняються.

Вправа\(\PageIndex{2}\label{ex:proprelat-02}\)

Для кожного співвідношення в задачі 3 у Вправи 1.1 визначте, які з п'яти властивостей задовольняються.

Вправа\(\PageIndex{3}\label{ex:proprelat-03}\)

Для співвідношення в задачі 6 у вправах 1.1 визначте, які з п'яти властивостей задовольняються.

Вправа\(\PageIndex{4}\label{ex:proprelat-04}\)

Для співвідношення в задачі 7 у вправах 1.1 визначте, які з п'яти властивостей задовольняються.

Вправа\(\PageIndex{5}\label{ex:proprelat-05}\)

Для співвідношення в задачі 8 у Вправи 1.1 визначте, які з п'яти властивостей задовольняються.

Вправа\(\PageIndex{6}\label{ex:proprelat-06}\)

Для співвідношення в задачі 9 у вправах 1.1 визначте, які з п'яти властивостей задовольняються.

Вправа\(\PageIndex{7}\label{ex:proprelat-07}\)

\(S\)Дозволяти бути непорожній набір і визначити відношення\(A\) на\(\wp(S)\) по\[(X,Y)\in A \Leftrightarrow X\cap Y=\emptyset. \nonumber\] Зрозуміло,\(A\) що симетрично.

1. Поясніть\(A\), чому не рефлексивно.
2. Поясніть\(A\), чому не є іррефлексивним.
3. Чи є\(A\) перехідним?
4. Нехай\(S=\{a,b,c\}\). Намалюйте орієнтований граф і знайдіть матрицю падіння, яка представляє\(A\).\(A\)

Вправа\(\PageIndex{8}\label{ex:proprelat-08}\)

Для кожного з цих відносин по\(\mathbb{N}-\{1\}\), визначте, які з п'яти властивостей задовольняються.

1. \(A_1=\{(x,y)\mid x\)і\(y\) є відносно простими\(\}\)
2. \(A_2=\{(x,y)\mid x\)і не\(y\) є відносно простими\(\}\)

Вправа\(\PageIndex{9}\label{ex:proprelat-09}\)

Для кожного з наступних відносин по\(\mathbb{N}\), визначте, які з п'яти властивостей задовольняються.

1. \(R_1=\{(x,y)\mid x\)ділить\(y\}\)
2. \(R_2=\{(x,y)\mid x+y\)є парним\(\}\)
3. \(R_3=\{(x,y)\mid xy\)є парним\(\}\)

Вправа\(\PageIndex{10}\label{ex:proprelat-10}\)

Для кожного з наступних відносин по\(\mathbb{N}\), визначте, які з п'яти властивостей задовольняються.

1. \(S_1=\{(x,y)\mid y\)ділить\(x\}\)
2. \(S_2=\{(x,y)\mid x+y\)є непарним\(\}\)
3. \(S_3=\{(x,y)\mid xy\)є непарним\(\}\)

Вправа\(\PageIndex{11}\label{ex:proprelat-11}\)

Для кожного з наступних відносин по\(\mathbb{Z}\), визначте, які з п'яти властивостей задовольняються.

1. \(U_1=\{(x,y)\mid x \leq y\}\)
2. \(U_2=\{(x,y)\mid x-y\)непарна}\(\}\)
3. \(U_3=\{(x,y)\mid 3\)ділить\(x+2y\}\)

Вправа\(\PageIndex{12}\label{ex:proprelat-12}\)

Для кожного з наступних відносин по\(\mathbb{Z}\), визначте, які з п'яти властивостей задовольняються.

1. \(V_1=\{(x,y)\mid xy>0\}\)
2. \(V_2=\{(x,y)\mid x-y\)є парним\(\}\)
3. \(V_3=\{(x,y)\mid x\)є кратним\(y\}\)