1.2: Відносини. Відображення

Відносини

У §1 ми вже розглядали множини впорядкованих пар, такі як декартові добутки\(A \times B\) або множини виду\(\{(x, y) | P (x, y)\}\) (див. §§1—3, завдання 7). Якщо пара\((x, y)\) є елементом такого набору\(R\), пишемо

\[(x, y) \in R \label{eq1}\]

\((x, y)\)трактування як одне. Зверніть увагу, що це не означає, що\(x\) і\(y\) взяті окремо є членами\(R\) (в цьому випадку ми б писали\(x, y \in R\)). \(y\)Називаємо\(x\), умови\((x, y)\).

У математиці прийнято називати будь-який набір впорядкованих пар відношенням. Наприклад, всі множини, перераховані в Задача 7 з §1—3, є відносинами. Оскільки відносини є множинами, рівність\(R = S\) для відносин означає, що вони складаються з одних і тих же елементів (впорядкованих пар), т. Е.

\[(x, y) \in R \iff (x, y) \in S\]

Якщо\((x, y) \in R\), ми називаємо\(y\)\(R\)\(x\) -relative of; ми також говоримо,\(y\) що\(R\) пов'язане з\(x\) або що відношення\(R\) тримає між\(x\) і\(y\) (у цьому порядку). Замість того\((x, y) ∈ R\), ми також пишемо\(xRy\), і часто замінюємо «\(R\)» спеціальними символами на кшталт\(<\)\(∼\), і т.д. таким чином, у випадку (i) завдання 7 вище, «\(xRy\)» означає, що\(x < y\).

Замінивши всі пари\((x, y) \in R\) на зворотні пари\((y, x)\), отримаємо нове відношення, зване зворотним\(R\) і позначене\(R^{-1}\). Ясно,\(xR^{−1}y\) iff\(yRx\); таким чином

\[R^{-1} = \{(x, y) | yRx\} = \{(y, x) | xRy\}.\]

Звідси\(R\), в свою чергу, є зворотним\(R^{−1}\); тобто,

\[(R^{-1})^{-1} = R.\]

Наприклад, відносини\(<\) і\(>\) між числами обернені один одному; так само\(\subseteq\) і відносини і\(\supseteq\) між множинами. (Ми можемо розглядати «\(\subseteq\)» як ім'я множини всіх пар,\((X,Y)\) таких, що\(X \subseteq Y\) в заданому просторі.)

Якщо\(R\) містить пари\((x, x′), (y, y′), (z, z′), . . . \), ми напишемо

\[R = \begin{pmatrix} x & y & z & \ldots \\ x' & y' & z' & \text{ } \end{pmatrix}; \hskip 5pt e.g., \hskip 5pt R = \begin{pmatrix} 1 & 4 & 1 & 3 \\ 2 & 2 & 1 & 1 \end{pmatrix}. \]

Для отримання\(R^{−1}\) ми просто міняємо верхній і нижній рядки в Equation\ ref {eq1}.

Визначення 1

Безліч всіх \(x\)лівих членів пар\((x, y) \in R\) називається доменом\(R\), позначається\(D_{R}\). Безліч всіх правильних членів цих пар називається діапазоном\(R\), позначається\(D_{R}^{′}\). \(x \in D_{R}\)Зрозуміло, якщо\(xRy\) для деяких\(y\). В символах,

\[x \in D_{R} \iff (\exists y) \hskip 5pt xRy; \hskip 5pt \text{similarly,} \hskip 5pt y \in D_{R}^{'} \iff (\exists x) \hskip 5pt xRy.\]

У Equation\ ref {eq1},\(D_{R}\) є верхнім рядком і\(D_{R}^{′}\) нижнім рядком. Зрозуміло,

\[D_{R^{-1}} = D_{R}^{'} \hskip 5pt \text{and} \hskip 5pt D_{R^{-1}}^{'} = D_{R}.\]

Наприклад, якщо

\[R = \begin{pmatrix} 1 & 4 & 1 \\ 2 & 2 & 1 \end{pmatrix},\]

потім

\[D_{R} = D_{R^{-1}}^{'} = \{1, 4\} \hskip 5pt \text{and} \hskip 5pt D_{R}^{'} = D_{R^{-1}} = \{1, 2\}.\]

Визначення 2

Образ безлічі\(A\) під відношення\(R\) (коротко,\(R-image\) of\(A\)) являє собою сукупність всіх\(R\) -родичів елементів\(A\), що позначаються\(R[A]\). Обернене зображення\(A\) under\(R\) - це зображення\(A\) під зворотним співвідношенням, т. Е\(R^{−1}[A]\). Якщо А складається з одного елемента\(A = {x}\), то\(R[A]\) і також\(R^{−1}[A]\) записуються\(R[x]\) і\(R^{−1}[x]\), відповідно, замість\(R[{x}]\) і\(R^{−1}[{x}]\).

Приклад\(\PageIndex{1}\)

Нехай

\[R = \begin{pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 7 \\ 1 & 3 & 4 & 5 & 3 & 4 & 1 & 3 & 5 & 1 \end{pmatrix}, \hskip 5pt A = \{1, 2\}, \hskip 5pt B = \{2 , 4\}. \]

Тоді

\[\begin{array}{lll} R[1] = \{1 , 3 , 4\}; & R[2] = \{3, 5\}; & R[3] = \{1, 3, 4, 5\}; \\ R[5] = \emptyset; & R^{-1}[1] = \{1, 3, 7\}; & R^{-1}[2] = \emptyset; \\ R^{-1}[3] = \{1, 2, 3\}; & R^{-1}[4] = \{1, 3\}; & R[A] = \{1, 3, 4, 5\}; \\ R^{-1}[A] = \{1, 3, 7\}; & R[B] = \{3, 5\}. \end{array} \]

За визначенням,\(R[x]\) це сукупність всіх\(R\) -родичів\(x\). Таким чином

\[y \in R[x] \hskip 5pt \text{iff} \hskip 5pt(x, y) \in R; \hskip 5pt \text{i.e.,} \hskip 5pt xRy.\]

Більш загально,\(y \in R[A]\) це означає, що\((x, y) \in R\) для деяких\(x \in A\). В символах,

\[y \in R[A] \iff (\exists x \in A) (x, y) \in R.\]

Зверніть увагу,\(R[A]\) що завжди визначено.

Відображення

Ми зараз розглянемо особливо важливий вид відносин.

Визначення 3

\(R\)Відношення називається відображенням (map), або функцією, або перетворенням, якщо кожен елемент\(x \in D_{R}\) має унікальний\(R\) -відносний, так що\(R[x]\) складається з одного елемента. Цей унікальний елемент позначається\(R(x)\) і називається значенням функції at\(x\) (under\(R\)). Таким чином,\(R(x)\) є єдиним членом\(R[x]\).

Якщо, крім того, різні елементи\(D_{R}\) мають різні зображення,\(R\) називається один до одного (або один-один) карта. У цьому випадку

\[x \neq y\left(x, y \in D_{R}\right) \text{ implies } R(x) \neq R(y);\]

еквівалентно,

\[R(x)=R(y) \text{ implies } x=y.\]

Іншими словами, жодна дві пари, що належать, не\(R\) мають однакових лівих або однакових правих термінів. Це показує,\(R\) що один до одного\(R^{−1}\), iff, теж є карта. Відображення часто позначаються буквами і\(f, g, h, F, \psi\) т.д.

Відображення\(f\), як кажуть, «від\(A\) до\(B\)», якщо\(D_{f} = A\) і\(D_{f}^{′} \subseteq B\); ми потім пишемо

\[f : A \rightarrow B \quad\left("f \text{ maps } A \text{ into } B"\right)\]

Якщо, зокрема,\(D_{f} = A\) і\(D_{f}^{′} = B\), ми\(f\) називаємо карту\(A\) на\(B\), і пишемо

\[f : A \underset{\mathrm{onto}}{\longrightarrow} B \quad\left("f \text{ maps } A \text{ onto } B"\right)\]

Якщо\(f\) є як на, так і один до одного, ми пишемо

\[f : A \longleftrightarrow B\]

(\(f: A \longleftrightarrow B\)означає,\(f\) що один до одного).

Усі пари, що належать до відображення,\(f\) мають вигляд,\((x, f(x))\) де\(f(x)\) знаходиться значення функції at\(x\), тобто унікальне\(f\) -відносне значення\(x, x \in D_{f}\). Тому, щоб визначити якусь функцію\(f\), досить вказати її домен\(D_{f}\) і значення функції\(f(x)\) для кожної\(x \in D_{f}\). Ми будемо часто використовувати такі визначення. Прийнято говорити, що\(f\) визначається на\(A\) (або «\(f\)є функція включена\(A\)») iff\(A = D_{f}\).

Приклад\(\PageIndex{2}\)

(а)
\[R=\{(x, y) | x \text{ is the wife of } y\}\]
Відносини - це карта «один до одного» набору всіх дружин на безлічі всіх чоловіків. \(R^{-1}\)тут одна до одного карта безлічі всіх чоловіків\(\left(=D_{R}^{\prime}\right)\) на
безлічі всіх дружин\(\left(=D_{R}\right)\).

(б) Відносини
\[f=\{(x, y) | y \text{ is the father of } x\}\]

це карта безлічі всіх людей на безлічі їхніх батьків. Це не один до одного, оскільки кілька осіб можуть мати одного батька (\(f\)-родича), і тому не\(x \neq x^{\prime}\) означає\(f(x) \neq f\left(x^{\prime}\right) .\)

(c) Нехай

\[g=\left( \begin{array}{cccc}{1} & {2} & {3} & {4} \\ {2} & {2} & {3} & {8}\end{array}\right)\]

Тоді\(g\) це карта\(D_{g}=\{1,2,3,4\}\) onto\(D_{g}^{\prime}=\{2,3,8\},\) з

\[g(1)=2, g(2)=2, g(3)=3, g(4)=8\]

(Як зазначалося вище, ці формули можуть служити для визначення\(g .)\) Це не один до одного, оскільки\(g(1)=g(2),\)\(g^{-1}\) це не карта.

(d) Розглянемо

\[f : N \rightarrow N, \text{ with } f(x)=2x \text{ for each } x \in N\]

За тим, що було сказано вище,\(f\) добре визначено. Це один до одного, оскільки\(x \neq y\) має\(D_{f}=N(\) на увазі\(2 x \neq 2 y .\) тут природні,\(),\) але\(D_{f}^{\prime}\) складається навіть з натуральних тільки. Таким чином\(f\), не на\(N\) (він знаходиться на меншому наборі, навіть природних);\(f^{-1}\) відображає навіть природні на всі\(N .\)

Домен і діапазон відношення можуть бути досить довільними множинами. Зокрема, можна розглянути функції,\(f\) в яких кожен елемент домену сам по собі\(D_{f}\) є впорядкованою парою\((x, y)\) або\(n\) -кортежем.\(\left(x_{1}, x_{2}, \ldots, x_{n}\right) .\) Такі відображення називаються функціями двох (відповідно\(n )\) змінних). Будь-якому\(n\) -кортежу\(\left(x_{1}, \ldots, x_{n}\right)\), який належить\(D_{f},\) функції,\(f\) присвоюється унікальне значення функції, позначається\(f\left(x_{1}, \ldots, x_{n}\right) .\) Це зручно розглядати\(x_{1}, x_{2}, \ldots, x_{n}\) як певні змінні; тоді значення функції теж стає змінною в залежності від\(x_{1}, \ldots, x_{n}\). Часто\(D_{f}\) складається з усіх упорядкованих\(n\) -кортегів елементів, взятих з множини\(A\), тобто\(D_{f}=A^{n}\) (крос-добуток\(n\) множин, кожен дорівнює\(A ) .\) діапазону, може бути довільним множиною\(B ;\) так\(f : A^{n} \rightarrow B\). Аналогічно,\(f : A \times B \rightarrow C\) є функція двох змінних, з\(D_{f}=A \times B, D_{f}^{\prime} \subseteq C\).

Функції двох змінних також називаються (бінарними) операціями. Наприклад, додавання натуральних чисел може розглядатися як карта\(f : N \times N \rightarrow N,\) з\(f(x, y)=x+y .\)

Визначення 4

\(R\)Відношення вважається
(i) рефлексивним, якщо ми маємо\(x R x\) для кожного\(x \in D_{R}\);
(ii) симетричний iff\(x R y\) завжди має на увазі\(y R x\);
(iii) перехідний iff у\(x R y\) поєднанні з\(y R z\) завжди має на увазі\(x R z\).

\(R\)називається співвідношенням еквівалентності на множині\(A\) iff\(A=D_{R}\) і\(R\) має всі три властивості (i), (ii) та (iii). Наприклад, таке відношення рівності на\(A\) (також називається карта ідентичності на\(A )\) позначеному

\[I_{A}=\{(x, y) | x \in A, x=y\}\]

Відносини еквівалентності часто позначаються спеціальними символами, що нагадують рівність, такими як\(\equiv, \approx, \sim,\) і т.д. формула,\(x R y,\) де\(R\) знаходиться такий символ, читається

\["x \text{ is equivalent (or} R \text{-equivalent) to } y,"\]

і\(R[x]=\{y | x R y\}\) (тобто,\(R\) -image of\(x )\) називається класом\(R\) -еквівалентності (коротко\(R\) -клас)\(x\) в\(A ;\) ньому складається з усіх елементів, які\(R\) -еквівалентні\(x\) і, отже, до кожного інші (для\(x R y\) і\(x R z\) мають\(y R x,\) на увазі спочатку симетрію, а значить і\(y R z,\) транзитивність). Кожен такий елемент називається представником даного\(R\) -класу, або його генератором. Ми часто пишемо\([x]\) для\(R[x]\).

Приклад\(\PageIndex{3}\)

(a ') Відношення нерівності\(<\) між дійсними числами є перехідним, оскільки

\[x<y \text{ and } y<z \text{ implies } x<z\]

він не є ні рефлексивним, ні симетричним. (Чому?)

(b ') Відношення включення\(\subseteq\) між множинами є рефлексивним (for\(A \subseteq A \)) і перехідним\((\) для\(A \subseteq B\) і\(B \subseteq C\) передбачає,\(A \subseteq C),\) але воно не є симетричним.

(c ') Співвідношення членства\(\in\) між елементом і множиною не є ні рефлексивним, ні симетричним, ні перехідним\((x \in A\) і\(A \in \mathcal{M}\) не передбачає\(x \in \mathcal{M} )\).

(d')\(R\) Дозволяти відношення паралелізму між лініями в площині, тобто множина всіх пар\((X, Y),\) де\(X\) і\(Y\) є паралельними лініями. Написання\(\|\) для\(R,\) нас\(X\|X, X\| Y\) має на увазі\(Y \| X,\)\((X \| Y\) і і\(Y\)\ |\(Z)\) означає\(R\),\(X \| Z,\) що це відношення еквівалентності. \(R\)Клас -тут складається з усіх ліній, паралельних заданій лінії в площині.

(e ') Конгруентність трикутників - це відношення еквівалентності. (Чому?)

Теорема\(\PageIndex{1}\)

Якщо\(R\) (також написано\(\equiv\)) є співвідношенням еквівалентності,\(A,\) то всі R- класи не з'єднані з кожним інші, і\(A\) є їх союз.

Доказ

Візьміть два\(R\) -класи,\([p] \neq[q]\). Шукаючи протиріччя, припустимо, що вони не розмежовуються, тому

\[(\exists x) \quad x \in[p] \text{ and } x \in[q];\]

тобто,\(p \equiv x \equiv q\) а значить,\(p \equiv q .\) але потім, симетрією і перехідністю,

\[y \in[p] \Leftrightarrow y \equiv p \Leftrightarrow y \equiv q \Leftrightarrow y \in[q];\]

тобто,\([p]\) і\([q]\) складаються з однакових елементів\(y,\) всупереч припущенню\([q] \neq[q]\). Таким чином, дійсно, будь-які два (disfinctive)\(R\) -класи є неспільними.

Також за допомогою рефлексивності,

\[(\forall x \in A) \quad x \equiv x\]

тобто,\(x \in[x] .\) Таким чином кожен\(x \in A\) знаходиться в якомусь\(R\) -класі (а саме,\([x] ) ;\) in of\(A\) знаходиться в об'єднанні таких класів,

\[A \subseteq \bigcup_{x} R[x]\]

І навпаки,

\[(\forall x) \quad R[x] \subseteq A\]

так як

\[y \in R[x] \Rightarrow x R y \Rightarrow y R x \Rightarrow(y, x) \in R \Rightarrow y \in D_{R}=A\]

за визначенням. Таким чином\(A\) містить все\(R[x],\) звідси їх союз, і так

\[A=\bigcup_{x} R[x] . \square\]