7.3: Відносини еквівалентності

Last updated
Save as PDF

Page ID: 64098

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Відношення на множині$A$ - це відношення еквівалентності, якщо воно є рефлексивним, симетричним та перехідним. Ми часто використовуємо позначення тильди$a\sim b$ для позначення відношення еквівалентності.

Приклад$\PageIndex{1}\label{eg:equivrel-01}$

Відносини в прикладах 7.2.4, 7.2.5 та 7.2.7 є співвідношеннями еквівалентності, як і в практичних вправах 7.2.2 та 7.2.6.

Приклад$\PageIndex{2}\label{eg:relmod4}$

Визначте відношення$\sim$$\mathbb{Z}$ на\[a\sim b \,\Leftrightarrow\, a\equiv b \mbox{ (mod~4)}. \nonumber\] перевірці, що$\sim$ є співвідношенням еквівалентності.

Відповідь

Нам потрібно перевірити три властивості:

Це очевидно$a\equiv a$ (мод 4), отже$a\sim a$. Відношення$\sim$ є рефлексивним.
Якщо$a\sim b$, то$a\equiv b$ (мод 4). Зрозуміло, що у нас теж є$b\equiv a$ (мод 4). Значить,$\sim$ симетрична.
Якщо$a\sim b$ і$b\sim c$, то\[a\equiv b \pmod{4}, \qquad\mbox{and}\qquad b\equiv c \pmod{4}. \nonumber\] випливає, що$a\equiv c$ (мод 4). Таким чином$a\sim c$. Це показує, що$\sim$ є перехідним.

Отже,$\sim$ це відношення еквівалентності.

вправа$\PageIndex{1}\label{he:relmod6}$

Визначте відношення$\sim$$\mathbb{Z}$ на\[a\sim b \,\Leftrightarrow\, a\equiv b \mbox{ (mod~6)}. \nonumber\] перевірці, що$\sim$ є співвідношенням еквівалентності.

вправа$\PageIndex{2}\label{he:relmodn}$

$n\geq2$Дозволяти натуральне число. Визначте відношення$\sim$$\mathbb{Z}$ на\[a\sim b \,\Leftrightarrow\, a\equiv b \mbox{ (mod~$n$)}. \nonumber\] перевірці, що$\sim$ є співвідношенням еквівалентності.

Придивіться до Прикладу 7.3.2. Всі цілі числа, що мають однаковий залишок при діленні на 4, пов'язані один з одним. Визначте\[\begin{array}{lclcr} {[0]} &=& \{n\in\mathbb{Z} \mid n\bmod 4 = 0 \} &=& 4\mathbb{Z}, \\ [3pt] {[1]} &=& \{n\in\mathbb{Z} \mid n\bmod 4 = 1 \} &=& 1+4\mathbb{Z}, \\ [3pt] {[2]} &=& \{n\in\mathbb{Z} \mid n\bmod 4 = 2 \} &=& 2+4\mathbb{Z}, \\ [3pt] {[3]} &=& \{n\in\mathbb{Z} \mid n\bmod 4 = 3 \} &=& 3+4\mathbb{Z}. \end{array} \nonumber\] множини Зрозуміло, що кожне ціле число належить рівно одному з цих чотирьох множин. Отже,\[\mathbb{Z} = [0] \cup [1] \cup [2] \cup [3]. \nonumber\] Ці чотири набори попарно нез'єднані, так$\mathbb{Z}$ це неспільний союз цих чотирьох наборів. Ми говоримо, що$\{[0], [1], [2], [3]\}$ це розділ$\mathbb{Z}$.

Визначення

$\{S_1,S_2,\ldots,S_n\}$Колекція непорожніх підмножин$S$ називається розділом,$S$ якщо підмножини попарно$S_1,S_2,\ldots,S_n$ нез'єднані ($S_i \cap S_j = \emptyset$всякий раз$i\neq j$), а\[S_1\cup S_2\cup \cdots \cup S_n = S. \nonumber\] підмножини$S_1,S_2,\ldots,S_n$ називаються частинами або складові частини перегородки.

Через транзитивності і симетрії всі елементи, пов'язані з нерухомим елементом, повинні бути пов'язані один з одним. Таким чином, якщо ми знаємо один елемент в групі, ми по суті знаємо всіх її «родичів».

Визначення: клас еквівалентності

$\sim$Дозволяти відношення еквівалентності на$A$. Множина\[[a] = \{ x\in A \mid x\sim a \}. \nonumber\] називається класом еквівалентності$a$.

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

У прикладі 7.2.4 кожен клас еквівалентності відношення$S$ складається з усіх трикутників, які схожі. Зауважте, що жоден трикутник не може належати до двох різних класів еквівалентності. Це означає, що класи еквівалентності попарно розмежовуються.

У тому ж прикладі кожен клас еквівалентності відношення$P$ складається з усіх ліній, які паралельні. Знову ж таки, зверніть увагу, що жодна лінія не може належати до двох різних класів еквівалентності. Таким чином, класи еквівалентності попарно розмежовуються.

Приклад$\PageIndex{4}\label{eg:equivmod4}$

Для відношення$\sim$ на$\mathbb{Z}$ визначеному$a\sim b\,\Leftrightarrow\, a\equiv b$ (mod 4), існує чотири класи еквівалентності$[0],[1],[2]$ і$[3]$, і$\{[0], [1], [2], [3]\}$ множина утворює розділ$\mathbb{Z}$. Тому\[\mathbb{Z} = [0]\cup[1]\cup[2]\cup[3], \nonumber\] і чотири складові$[0]$$[1]$,$[2]$ і$[3]$ попарно розмежовуються.

вправа$\PageIndex{3}\label{he:equivmod6}$

Які класи еквівалентності відношення$\sim$ у вправі 7.3.1?

вправа$\PageIndex{4}\label{he:equivmodn}$

Які класи еквівалентності відношення$\sim$ у вправі 7.3.2?

вправа$\PageIndex{5}\label{he:equivrel-01}$

Для кожного з співвідношень еквівалентності, згаданих у прикладі 7.3.1, визначте його класи еквівалентності.

Всі елементи в одному класі еквівалентності пов'язані один з одним. Тому елементи у$[a]$ всіх мають одну і ту ж властивість, якою$a$ користується, з точки зору відношення$\sim$. У прикладі 7.3.4 клас еквівалентності$[0]$ складається з елементів, кратних 4. Клас еквівалентності$[1]$ складається з елементів, які при поділенні на 4 залишають 1 як залишок, і аналогічно для класів еквівалентності$[2]$ і$[3]$. Через спільну зв'язок між елементами в класі еквівалентності всі$[a]$ ці елементи можуть бути представлені будь-яким членом в межах класу еквівалентності. Це дух, що стоїть за наступною теоремою.

Теорема$\PageIndex{1}\label{thm:equivclass}$

Якщо$\sim$ відношення еквівалентності на$A$, то$a\sim b \Leftrightarrow [a]=[b]$.

Доказ: Доказ залишаємо як вправу.

Класи еквівалентності можна розглядати як об'єкти з багатьма псевдонімами. Кожен елемент класу еквівалентності може служити його представником. Тому ми повинні проявляти особливу обережність, коли ми маємо справу з класами еквівалентності. Не обманюйте себе представниками, і вважайте два, очевидно, різні класи еквівалентності, коли насправді вони можуть бути ідентичними.

Приклад$\PageIndex{5}\label{eg:sameLN}$

Визначте$\sim$ на сукупності людей у спільноті відповідно до\[a\sim b \,\Leftrightarrow\, \mbox{$a$ and $b$ have the same last name}. \nonumber\] Ми бачили, що$\sim$ це відношення еквівалентності. Кожен клас еквівалентності складається з усіх осіб з однаковим прізвищем у громаді. Отже, наприклад, Джеймс Сміт, Люсі Сміт та Пітер Сміт належать до одного класу еквівалентності. Будь-який Сміт може служити його представником, тому ми можемо позначити його як, наприклад,$[$ Пітер Сміт$]$.

Приклад$\PageIndex{6}\label{eg:samedec}$

Визначити$\sim$ на$\mathbb{R}^+$ відповідно до\[x\sim y \,\Leftrightarrow\, x-y\in\mathbb{Z}. \nonumber\] Отже, два дійсних числа пов'язані тоді і тільки тоді, коли вони мають однакові десяткові частини. Легко перевірити, що$\sim$ це відношення еквівалентності, і кожен клас еквівалентності$[x]$ складається з усіх позитивних дійсних чисел, що мають ті ж десяткові частини, що і$x$ має. Зверніть увагу,\[\mathbb{R}^+ = \bigcup_{x\in(0,1]} [x], \nonumber\] що це означає, що класи еквівалентності$[x]$$x\in(0,1]$, де, утворюють розділ$\mathbb{R}$.

вправа$\PageIndex{6}\label{he:samedec2}$

Доведіть, що відношення$\sim$ в прикладі 7.3.6 дійсно відношення еквівалентності.

вправа$\PageIndex{7}\label{he:samedec3}$

Визначте$\sim$ на$\mathbb{R}$ відповідно до\[x\sim y \,\Leftrightarrow\, x-y\in\mathbb{Z}. \nonumber\] Show, що$\sim$ є класом еквівалентності. Правда чи брехня:$-2.14\in[5,14]$? Поясніть.

Що робить відносини еквівалентності настільки важливими є наступна фундаментальна теорема про відносини еквівалентності.

Теорема$\PageIndex{2}\label{thm:FTequiv}$: Fundamental Theorem on Equivalence Relation

З огляду на будь-яке відношення еквівалентності на непорожній$A$ множині, множина класів еквівалентності утворює розділ$A$. І навпаки, будь-який розділ$\{A_1,A_2,\ldots,A_n\}$ непорожнього множини на$A$ скінченну кількість непорожніх підмножин викликає відношення еквівалентності$\sim$ на$A$, де$a\sim b$ якщо і тільки якщо$a,b\in A_i$ для деяких$i$ (таким чином$a$ і$b$ належать до одного компонента).

Доказ

Зрозуміло, що$A$ це об'єднання класів еквівалентності індуковано$\sim$, тому залишається показати, що ці класи еквівалентності попарно неспільні. Припустимо$[a]\cap[b]\neq\emptyset$. Нехай$x\in [a]\cap[b]$. Потім$x\in[a]$ і$x\in[b]$. Маючи$x\in[a]$ засоби$x\sim a$, і$x\in[b]$ має на увазі, що$x\sim b$. Симетрія і транзитивність означають це$a\sim b$. Теорема 7.3.1 це запевняє$[a]=[b]$. Тому якщо$[a]\neq[b]$, то$[a]\cap[b] = \emptyset$. Це доводить, що класи еквівалентності утворюють розділ$A$.

$A = A_1\cup A_2\cup\cdots\cup A_n$Дозволяти бути розділом$A$, визначити відношення$\sim$ на$A$ відповідно\[x\sim y \,\Leftrightarrow\, x,y\in A_i \mbox{ for some $i$}. \nonumber\] випливає відразу з визначення$x\sim x$, що, тому відношення є рефлексивним. Зрозуміло також, що$x\sim y$ має на увазі$y\sim x$, отже, відношення симетричне. Нарешті, якщо$x\sim y$ і$y\sim z$, то$x,y\in A_i$ для деяких$i$, і$y,z\in A_j$ для деяких$j$. Оскільки$A_i$ s утворюють розділ$A$, елемент$y$ не може належати до двох компонентів. Це означає$i=j$, отже,$x,z\in A_i$. Це доводить, що$\sim$ є перехідним. Отже,$\sim$ є відношення еквівалентності.

Ідея теореми досить проста. Кожен клас еквівалентності складається з усіх «родичів» з однієї сім'ї, тому очевидно множина$A$ може бути розділена на сім'ї (класи еквівалентності). Ці сім'ї не мають спільних елементів (отже, попарно нез'єднаних), оскільки теорема 7.3.1 стверджує, що будь-які два класи еквівалентності, що поділяють деякі спільні елементи, повинні бути однаковими. Тому сім'ї утворюють перегородку з$A$. І навпаки, за умови розділу$\cal P$, ми могли б визначити відношення, яке пов'язує всі члени в одному компоненті. Це відношення виявляється співвідношенням еквівалентності, причому кожен компонент утворює клас еквівалентності. Це відношення еквівалентності називається відношенням еквівалентності, індукованим$\cal P$.

Приклад$\PageIndex{7}$

У прикладі 7.2.4 відношення$S$ є відношенням еквівалентності, а класи еквівалентності - множини подібних трикутників, які утворюють розділ множини${\cal T}$. Це означає, що будь-який трикутник належить до одного класу еквівалентності. Іншими словами, ми можемо класифікувати трикутники на площині відповідно до їх трьох внутрішніх кутів.

Відношення$P$ в тому ж прикладі також є співвідношенням еквівалентності. Його класи еквівалентності - це множини ліній, які паралельні. Кожна лінія на площині належить рівно одному класу еквівалентності. Отже, ми можемо класифікувати лінії на площині за їх нахилами.

Приклад$\PageIndex{8}\label{eg:equivrelat-06}$

Більше$\mathbb{Z}^*$, визначте\[R_3 = \{ (m,n) \mid m,n\in\mathbb{Z}^* \mbox{ and } mn > 0\}. \nonumber\] Це не важко перевірити, що$R_3$ це відношення еквівалентності. Існує всього два класи еквівалентності:$[1]$ і$[-1]$, де$[1]$ містяться всі натуральні числа, і$[-1]$ всі від'ємні цілі числа. Очевидно, що$\mathbb{Z}^*=[1]\cup[-1]$.

Приклад$\PageIndex{9}\label{eg:equivrelat-07}$

Для кожного визначте$b\in\mathbb{R}$,$L_b$ щоб бути лінією в$\mathbb{R}^2$ (яка також називається$xy$ -plane) з рівнянням$y=2x+b$. Тоді${\cal L} =\{L_b \mid b\in \mathbb{R}\}$ це перегородка$\mathbb{R}^2$ тому, що враховуючи будь-яку точку на$\mathbb{R}^2$, є лише одна пряма лінія з нахилом 2, яка може пройти через неї. Такий розділ викликає співвідношення еквівалентності,$\sim$ визначене\[(p,q) \sim (s,t) \Leftrightarrow \mbox{both $(p,q)$ and $(s,t)$ lie on $L_b$ for some $b$}. \nonumber\] Таким чином,$(p,q)\sim(s,t)$ якщо і тільки тоді, коли дві точки$(p,q)$ і$(s,t)$ лежать на одній прямій лінії нахилу 2. Це означає$\frac{q-t}{p-s}=2$. Тому ми можемо перевизначити визначення як\[(p,q) \sim (s,t) \Leftrightarrow q-t=2(p-s). \nonumber\] Наприклад,$(1,5)\sim (0,3)$. По суті,$[(1,5)]$ відповідає рядок$y=2x+3$ або$L_3$. Аналогічно$[(1,1.25)]$ відповідає рядок$y=2x-0.75$ або$L_{-0.75}$. Загалом,$L_b=[(0,b)]$.

вправа$\PageIndex{8}\label{he:equivrelat-02}$

Розглянемо розділ$\mathbb{R}^2$ ($xy$-plane),\[\mathbb{R}^2 = \bigcup_{b\in\mathbb{R}} L_b, \nonumber\] де$L_b$ знаходиться лінія, що задовольняє рівнянню$y=5x+b$. Визначте відношення еквівалентності, індуковане цим розділом.

Ми широко вивчали модульну арифметику. У вправі 7.3.2 ви вже довели наступний результат.

Теорема$\PageIndex{3}$

Для будь-якого натурального числа$n\geq2$ конгруентність відношення по модулю$n$ є співвідношенням еквівалентності на$\mathbb{Z}$

Тепер ми можемо надати більш суворе визначення$\mathbb{Z}_n$.

Визначення

$n\geq2$Дозволяти ціле число. Класи$[0], [1], \ldots, [n-1]$ еквівалентності конгруентності зв'язку по модулю$n$ називаються класами залишку по модулю$n$. Множина\[\mathbb{Z}_n = \big\{ [0], [1], \ldots, [n-1] \big\} \nonumber\] називається множиною класів залишку по модулю$n$.

Зауваження

Ми визначаємо дві операції$\oplus$ і$\odot$ на елементи$\mathbb{Z}_n$ відповідно до\[[a]\oplus[b] = [a+b], \qquad\mbox{and}\qquad [a]\odot[b] = [ab]. \nonumber\] Ми не будемо вдаватися в деталі, але ми хотіли б зауважити, що$\<\mathbb{Z}_n,\oplus,\odot\>$ утворює алгебраїчну структуру, яка називається кільцем. На практиці ми рідко пишемо,$\mathbb{Z}_n=\big\{[0],[1],\ldots,[n-1]\big\}$ тому що це занадто громіздко. Замість цього ми просто пишемо$\mathbb{Z}_n = \{0,1,2,\ldots,n-1\}$. Однак, що ми дійсно працюємо з в$\mathbb{Z}_n$ є залишкові класи представлені цілими числами 0 через$n-1$.

Матриця випадковості співвідношення еквівалентності демонструє гарний візерунок. І навпаки, вивчаючи матрицю випадковості відношення, ми можемо визначити, чи є відношення відношення еквівалентності.

Якщо ми можемо переставити рядки та стовпці матриці падіння так, що модифікована матриця випадковість може бути розділена на блоки підматриць, що містять повністю 1s або повністю 0s, таким чином, що 1-підматриці лежать на діагоналі, то базове відношення$R$ є співвідношенням еквівалентності. Ось причина. Оскільки записи в кожній 1-підматриці є всі 1s, це означає, що відповідні елементи пов'язані один з одним. Це поняття транзитивності. Очевидно, що кожен елемент пов'язаний з самим собою. Оскільки 1-підматриці лежать на діагоналі, матриця, звідси і відношення, симетрична. Це доводить, що основним відношенням є відношення еквівалентності. Кожен клас еквівалентності складається з усіх елементів, які відповідають рядку і стовпцям в одній 1-матриці.

Приклад$\PageIndex{10}\label{eg:equivrelat-08}$

Дозвольте$A=\{1,2,3,4,5\}$ і визначити відношення$R_1$$A$ по\[R_1 = \{ (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,4), (4,4), (5,4), (5,5) \}. \nonumber\] Це зрозуміло з матриці падіння (ми додаємо рядки, щоб зробити 0- і 1-підматриці більш видатними)\[\begin{array}{cc} & \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{array} & \left(\begin{array}{ccc|cc} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{array}\right) \end{array} \nonumber\], що$R_1$ є відношенням еквівалентності і що вона має два класи еквівалентності:$[1]=[2]=[3]=\{1,2,3\}$, і$[4]=[5]=\{4,5\}$, такий, що$A=[1]\cup[4]$.

Приклад$\PageIndex{11}\label{eg:equivrelat-09}$

Нехай$A=\{a,b,c,d\}$. Визначте відношення$R_2$$A$ по\[R_2 = \{(a,a), (a,c), (b,b), (b,d), (c,a), (c,c), (d,b), (d,d)\}. \nonumber\] Після перезапису матриці падіння стає\[\begin{array}{cc} & \begin{array}{cccc} a & b & c & d \end{array} \\ \begin{array}{c} a \\ b \\ c \\ d \end{array} & \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right) \end{array} \qquad\leadsto\qquad \begin{array}{cc} & \begin{array}{cccc} a & c & b & d \end{array} \\ \begin{array}{c} a \\ c \\ b \\ d \end{array} & \left( \begin{array}{cc|cc} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right) \end{array} \nonumber\] зрозуміло, що$R_2$ це відношення еквівалентності, з$[a]=[c]=\{a,c\}$, і$[b]=[d]=\{b,d\}$, таке що$A=[a]\cup[b]$.

вправа$\PageIndex{9}\label{he:equivrelat-03}$

Відомо, що відношення,$S$ визначене на$\{1,2,3,4,5,6\}$ множині, є\[\displaylines{ S = \{ (1,1), (1,4), (2,2), (2,5), (2,6), (3,3), \hskip1in \cr (4,1), (4,4), (5,2), (5,5), (5,6), (6,2), (6,5), (6,6) \}. \cr} \nonumber\] Show,$S$ тобто відношення еквівалентності, вивчаючи його матрицю падіння, і переписуючи її, якщо це необхідно. Визначте зміст його класів еквівалентності.

Приклад$\PageIndex{12}\label{eg:equivrelat-10}$

Знайдіть відношення еквівалентності,$R$ індуковане\[{\cal P} = \big\{ \{1\}, \{3\}, \{2,4,5,6\} \big\} \nonumber\] поділом$A=\{1,2,3,4,5,6\}$.

Відповідь: З двох класів одноелементної еквівалентності$\{1\}$ і$\{3\}$, ми знаходимо дві впорядковані пари$(1,1)$ і$(3,3)$ які належать$R$. З класу$\{2,4,5,6\}$ еквівалентності будь-яка пара елементів виробляє впорядковану пару, до якої належить$R$. Тому, в\[\begin{aligned} R &=& \{ (1,1), (3,3), (2,2), (2,4), (2,5), (2,6), (4,2), (4,4), (4,5), (4,6), \\ & & \quad (5,2), (5,4), (5,5), (5,6), (6,2), (6,4), (6,5), (6,6) \}. \end{aligned} \nonumber\] якості альтернативи, ми можемо побудувати матрицю падіння,\[\begin{array}{cc} & \begin{array}{cccccc} 1 & 3 & 2 & 4 & 5 & 6 \end{array} \\ \begin{array}{c} 1 \\ 3 \\ 2 \\ 4 \\ 5 \\ 6 \end{array} & \left( \begin{array}{c|c|cccc} 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{array} \right) \end{array} \nonumber\] з якої$R$ можна легко отримати впорядковані пари в.

вправа$\PageIndex{10}\label{he:equivrelat-04}$

Знайдіть відношення еквівалентності,$R$ викликане\[{\cal P} = \big\{ \{a,d\}, \{b,c,g\}, \{e,f\} \big\} \nonumber\] поділом,$A=\{a,b,c,d,e,f,g\}$ перерахувавши всі його впорядковані пари (метод реєстру).

Резюме Огляд

Відношення$R$ на множині$A$ - це відношення еквівалентності, якщо воно є рефлексивним, симетричним та перехідним.
Якщо$R$ відношення еквівалентності на множині$A$, його класи еквівалентності утворюють розділ$A$.
У кожному класі еквівалентності всі елементи пов'язані, і кожен елемент$A$ належить до одного класу еквівалентності.
Співвідношення$R$ визначає членство в кожному класі еквівалентності, і кожен елемент класу еквівалентності може бути використаний для представлення цього класу еквівалентності.
У певному сенсі, якщо ви знаєте один член в класі еквівалентності, ви також знаєте всі інші елементи класу еквівалентності, оскільки всі вони пов'язані відповідно до$R$.
І навпаки, враховуючи розділ$A$, ми можемо використовувати його для визначення відношення еквівалентності, оголосивши два елементи пов'язані, якщо вони належать одному компоненту в розділі.

Вправа$\PageIndex{1}\label{ex:equivrelat-01}$

Показати, що кожне з наступних відносин$\sim$ на$\mathbb{Z}$ є співвідношенням еквівалентності, і знайти його класи еквівалентності.

$m\sim n \,\Leftrightarrow\, |m-3|=|n-3|$
$m\sim n \,\Leftrightarrow\, m+n$є навіть

Вправа$\PageIndex{2}\label{ex:equivrel-02}$

$m\sim n \,\Leftrightarrow\, 3\mid(m+2n)$
$m\sim n \,\Leftrightarrow\, 5\mid(2m+3n)$

Вправа$\PageIndex{3}\label{ex:equivrel-03}$

$T$Дозволяти бути фіксованою підмножиною непорожнього множини$S$. Визначте відношення$\sim$$\wp(S)$ на\[X\sim Y \,\Leftrightarrow\, X\cap T = Y\cap T, \nonumber\] Show, що$\sim$ є співвідношенням еквівалентності. Зокрема, нехай$S=\{1,2,3,4\}$ і$T=\{1,3\}$.

Правда чи брехня:$\{1,2,4\}\sim\{1,4,5\}$?
Як щодо$\{1,2,4\}\sim\{1,3,4\}$?
Знайти$[\{1,5\}]$
Опишіть$[X]$ для будь-якого$X\in\wp(S)$.

Вправа$\PageIndex{4}\label{ex:equivrel-04}$

Для кожного з наступних відносин$\sim$ на$\mathbb{R}\times\mathbb{R}$, визначте, чи є це відношення еквівалентності. Для тих, що є, опишіть геометрично клас еквівалентності$[(a,b)]$.

$(x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, y_1-x_1^2=y_2-x_2^2$.
$(x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, (x_1-1)^2+y_1^2=(x_2-1)^2+y_2^2$

Вправа$\PageIndex{5}\label{ex:equivrel-05}$

$(x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, x_1+y_2=x_2+y_1$
$(x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, (x_1-x_2)(y_1-y_2)=0$

Вправа$\PageIndex{6}\label{ex:equivrel-06}$

$(x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, |x_1|+|y_1|=|x_2|+|y_2|$
$(x_1,y_1)\sim(x_2,y_2) \,\Leftrightarrow\, x_1y_1=x_2y_2$

Вправа$\PageIndex{7}\label{ex:equivrel-07}$

Визначте відношення$\sim$$\mathbb{Q}$ на\[x\sim y \,\Leftrightarrow\, 2(x-y)\in\mathbb{Z}. \nonumber\] Show, що$\sim$ є співвідношенням еквівалентності. Опишіть класи еквівалентності$[0]$ і$\big[\frac{1}{4}\big]$.

Вправа$\PageIndex{8}\label{ex:equivrel-08}$

Визначте відношення$\sim$$\mathbb{Q}$ на\[x\sim y \,\Leftrightarrow\, \frac{x-y}{2}\in\mathbb{Z}. \nonumber\] Show, що$\sim$ є співвідношенням еквівалентності. Опишіть класи еквівалентності$[0]$,$[1]$ і$\big[\frac{1}{2}\big]$.

Вправа$\PageIndex{9}\label{ex:equivrel-09}$

Розглянемо наступне відношення на$\{a,b,c,d,e\}$:\[\displaylines{ R = \{(a,a),(a,c),(a,e),(b,b),(b,d),(c,a),(c,c),(c,e), \cr (d,b),(d,d),(e,a),(e,c),(e,e)\}. \hskip0.7in \cr} \nonumber\] Покажіть, що це відношення еквівалентності, і опишіть його класи еквівалентності.

Відповідь: Використовуйте матричне представлення відношення.

Вправа$\PageIndex{10}\label{ex:equivrel-10}$

Кожна частина нижче дає перегородку$A=\{a,b,c,d,e,f,g\}$. Знайдіть відношення еквівалентності на$A$ індукованому розділом.

Відповідь

$\mathcal{P}_1 = \big\{\{a,b\},\{c,d\},\{e,f\},\{g\}\big\}$
$\mathcal{P}_2 = \big\{\{a,c,e,g\},\{b,d,f\}\big\}$
$\mathcal{P}_3 = \big\{\{a,b,d,e,f\},\{c,g\}\big\}$
$\mathcal{P}_4 = \big\{\{a,b,c,d,e,f,g\}\big\}$

Вправа$\PageIndex{11}\label{ex:equivrel-11}$

$\sim$Дозволяти відношення еквівалентності на$A$. Доведіть, що якщо$a\sim b$, то$[a]=[b]$.

Вправа$\PageIndex{12}\label{ex:equivrel-12}$

$\sim$Дозволяти відношення еквівалентності на$A$. Доведіть, що якщо$[a]=[b]$, то$a\sim b$.