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$$