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

Last updated
Save as PDF

Page ID: 53177

\( \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}}\)

Template:MathJaxZach

Відношення ідентичності на множині є рефлексивним, симетричним та перехідним. Відносини\(R\), які мають всі три з цих властивостей, дуже поширені.

Визначення\(\PageIndex{1}\): Equivalence relation

Відношення\(R \subseteq A^2\), яке є рефлексивним, симетричним та перехідним, називається співвідношенням еквівалентності. Елементи\(x\) і\(y\) з\(A\), як кажуть,\(R\) рівнозначні, якщо\(Rxy\).

Відносини еквівалентності породжують поняття класу еквівалентності. Співвідношення еквівалентності «розбиває» домен на різні розділи. Усередині кожного розділу всі об'єкти пов'язані один з одним; і жодні об'єкти з різних розділів не пов'язані один з одним. Іноді корисно просто говорити про ці розділи безпосередньо. З цією метою ми введемо визначення:

Визначення\(\PageIndex{2}\)

\(R \subseteq A^2\)Дозволяти відношення еквівалентності. Для кожного\(x \in A\) класу еквівалентності\(x\) in\(A\) є множиною\(\equivrep{x}{R} = \Setabs{y \in A}{Rxy}\). Частка від\(A\) under\(R\) - це\(\equivclass{A}{R} = \Setabs{\equivrep{x}{R}}{x \in A}\), тобто множина цих класів еквівалентності.

Наступний результат підтверджує визначення класу еквівалентності, доводячи, що класи еквівалентності дійсно є розділами\(A\):

Пропозиція\(\PageIndex{1}\)

Якщо\(R \subseteq A^2\) відношення еквівалентності, то\(Rxy\) iff\(\equivrep{x}{R} = \equivrep{y}{R}\).

Доказ. Для напрямку зліва направо, припустимо\(Rxy\), і нехай\(z \in \equivrep{x}{R}\). За визначенням, тоді,\(Rxz\). Оскільки\(R\) це відношення еквівалентності,\(Ryz\). (Написання цього: як\(Rxy\) і\(R\) є симетричним у нас є\(Ryx\), і як\(Rxz\) і\(R\) є перехідним у нас є\(Ryz\).) Отже\(z \in \equivrep{y}{R}\). узагальнюючи,\(\equivrep{x}{R} \subseteq \equivrep{y}{R}\). Але точно так же,\(\equivrep{y}{R} \subseteq \equivrep{x}{R}\). Отже\(\equivrep{x}{R} = \equivrep{y}{R}\), по розширеності.

Для напрямку справа наліво, припустимо\(\equivrep{x}{R} = \equivrep{y}{R}\). Так як\(R\) є рефлексивним\(Ryy\), так\(y \in \equivrep{y}{R}\). При цьому також\(y \in \equivrep{x}{R}\) припущенням, що\(\equivrep{x}{R} = \equivrep{y}{R}\). Отже\(Rxy\). ◻

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

Приємний приклад співвідношення еквівалентності походить від модульної арифметики. Для будь-якого\(a\), і\(b\)\(n \in \Nat\), скажіть, що\(a \equiv_n b\) якщо ділення\(a\) на\(n\) дає залишок\(b\). (Дещо більш символічно:\(a \equiv_n b\) іф\((\exists k \in \Nat)a - b = kn\).) Тепер,\(\equiv_n\) це відношення еквівалентності, для будь-якого\(n\). І є точно\(n\) різні класи еквівалентності генеруються\(\equiv_n\); тобто\(\equivclass{\Nat}{\equiv_n}\) має\(n\) елементи. Це: множина чисел, що ділиться на\(n\) без залишку, тобто\(\equivrep{0}{\equiv_n}\); множина чисел, ділиться на\(n\) залишок\(1\), тобто\(\equivrep{1}{\equiv_n}\);...; і множина чисел, ділиться на \(n\)з залишком\(n-1\), т\(\equivrep{n-1}{\equiv_n}\). Е.

Проблема\(\PageIndex{1}\)

Покажіть, що\(\equiv_n\) це відношення еквівалентності, для будь-якого\(n \in \Nat\), і що\(\equivclass{\Nat}{\equiv_n}\) має саме\(n\) члени.