7.3: Класи еквівалентності
- Page ID
- 65486
Як було зазначено в розділі 7.2, відношення еквівалентності на множині\(A\) - це відношення з певною комбінацією властивостей (рефлексивних, симетричних і перехідних), які дозволяють сортувати елементи множини за певними класами. Це робиться за допомогою певних підмножин\(A\), які пов'язані з елементами множини\(A\). Це буде проілюстровано наступним прикладом. Дозволяти\(A = \{a, b, c, d, e\}\), і\(R\) нехай відношення на множині\(A\) визначено наступним чином:
\(a\ R\ a\)\(b\ R\ b\)\(c\ R\ c\)\(d\ R\ d\)\(e\ R\ e\)
\(a\ R\ b\)\(b\ R\ a\)\(b\ R\ e\)\(e\ R\ b\)
\(a\ R\ e\)\(e\ R\ a\)\(c\ R\ d\)\(d\ R\ c\)
Для кожного\(y \in A\) визначте\(R[y]\) підмножину\(A\) наступним чином:
\(R[y] = \{x \in A\ |\ x\ R\ y\}.\)
Тобто\(R[y]\) складається з тих елементів в\(A\) таких, що\(x\ R\ y\). Наприклад, використовуючи\(y = a\), ми бачимо\(a\ R\ a\), що\(b\ R\ a\), і\(e\ R\ a\), і так\(R[a] = \{a, b, e\}\).
- Визначити\(R[b]\),\(R[c]\),\(R[d]\) і\(R[e]\).
- Намалюйте орієнтований граф для відношення\(R\) і поясніть,\(R\) чому відношення еквівалентності на\(A\).
- Які з множин\(R[a]\)\(R[b]\),\(R[c]\),,\(R[d]\)\(R[e]\) і рівні?
- Які з наборів\(R[a]\),\(R[b]\),\(R[c]\),\(R[d]\) і\(R[e]\) розмежовуються?
Як ми побачимо в цьому розділі, відносини між цими множинами характерні для співвідношення еквівалентності. Наступний приклад покаже, наскільки різним це може бути для відношення, яке не є співвідношенням еквівалентності.
Дозволяти\(A = \{a, b, c, d\}\), і\(S\) нехай відношення на множині\(A\) визначено наступним чином:
\(b\ S\ b\)\(c\ S\ c\)\(d\ S\ d\)\(e\ S\ e\)
\(a\ S\ b\)\(a\ S\ d\)\(b\ S\ c\)
\(c\ S\ d\)\(d\ S\ c\)
5. Намалюйте диграф, який представляє відношення\(S\) на\(A\). Поясніть\(S\), чому не є відношення еквівалентності на\(A\).
Для кожного\(y \in A\) визначте\(S[y]\) підмножину\(A\) наступним чином:
\(S[y] = \{x \in A\ |\ x\ S\ y\} = \{x \in A\ |\ (x, y) \in S\}.\)
Наприклад, використовуючи\(y = b\), ми бачимо, що\(S[b] = \{a, b\}\) з\((a, b) \in S\) і\((b, b) \in S\). Крім того, ми бачимо, що\(S[a] = \emptyset\) оскільки немає х 2 А такий, що.x; a/ 2 S.
6. Визначити\(S[c]\),\(S[d]\), і\(S[e]\).
7. Які з множин\(S[a]\),\(S[b]\)\(S[c]\),\(S[d]\),,\(S[e]\) і рівні?
8. Які з наборів\(S[b]\),\(S[c]\),\(S[d]\), і\(S[e]\) розмежовуються?
Важливим співвідношенням еквівалентності, яке ми вивчили, є конгруентність\(n\) по модулю на цілих числах. Ми також можемо визначити підмножини цілих чисел на основі конгруентності по модулю\(n\). Ми проілюструємо це конгруентністю по модулю 3. Наприклад, ми можемо визначити,\(C[0]\) щоб бути множиною всіх цілих чисел a, які є конгруентними до 0 по модулю 3. Тобто,
\(C[0] = \{a \in \mathbb{Z}\ |\ a \equiv 0\text{ (mod 3)}\}.\)
Оскільки ціле число\(a\) збігається з 0 по модулю 3, якщо ділить лише 3\(a\), ми можемо використовувати метод реєстру, щоб вказати цей набір наступним чином:
\(C[0] = \{..., -9, -6, -3, 0, 3, 6, 9, ...\}.\)
- Використовуйте метод реєстру, щоб вказати кожен з наступних множин:
(a) Набір\(C[1]\) всіх цілих чисел\(a\), які збігаються з 1 по модулю 3. Тобто\(C[1] = \{a \in \mathbb{Z}\ |\ a \equiv 1 \text{ (mod 3)}\}.\)
(b) множина всіх цілих чисел\(a\), які є конгруентними 2 по модулю 3.\(C[2]\) Тобто\(C[2] = \{a \in \mathbb{Z}\ |\ a \equiv 2 \text{ (mod 3)}\}.\)
(c) множина всіх цілих чисел\(a\), які є конгруентними 3 по модулю 3.\(C[3]\) Тобто,\(C[3] = \{a \in \mathbb{Z}\ |\ a \equiv 3 \text{ (mod 3)}\}.\) - Тепер розглянемо три набори,\(C[0]\),\(C[1]\), і\(C[2]\).
(а) Визначте перетин будь-яких двох з цих множин. Тобто визначити,\(C[0] \cap C[1]\)\(C[0] \cap C[2]\), і\(C[1] \cap C[2]\).
(б) Нехай\(n = 734\). Що таке залишок при\(n\) діленні на 3? Який із трьох наборів, якщо такий є, містить\(n = 734\)?
(c) Повторіть частину (2b) для\(n = 79\) і для\(n = -79\).
(d) Як ви думаєте, що\(C[0] \cup C[1] \cup C[2] = \mathbb{Z}\) Поясніть.
(e) Чи є\(C[3]\) множина дорівнює одній з множин\(C[0]\)\(C[1]\), або\(C[2]\)?
(f) Ми також можемо визначити\(C[4] = \{a \in \mathbb{Z}\ |\ a \equiv 4 \text{ (mod 3)}\}\). Чи дорівнює цей набір будь-якому з попередніх наборів, які ми вивчили в цій частині? Поясніть.
Визначення класу еквівалентності
Ми вказали, що відношення еквівалентності на множині - це відношення з певною комбінацією властивостей (рефлексивних, симетричних і перехідних), які дозволяють сортувати елементи множини за певними класами. Ми бачили, що це відбувається в попередньому перегляді діяльності. Тепер ми можемо проілюструвати конкретно, що це означає. Наприклад, у Preview Activity\(\PageIndex{2}\) ми використовували співвідношення еквівалентності конгруентності по модулю 3\(\mathbb{Z}\) для побудови наступних трьох наборів:
\[\begin{array} {rcl} {C[0]} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 0\text{ (mod 3)}\},} \\ {C[1]} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 1\text{ (mod 3)}\},\text{ and}} \\ {C[2]} &= & {\{a \in \mathbb{Z}\ |\ a \equiv 2\text{ (mod 3)}\}.} \end{array}\]
Основні результати, які ми хочемо використовувати зараз, - це Теорема 3.31 та Слідство 3.32 на сторінці 150. Цей наслідок говорить нам, що для будь-якого\(a \in \mathbb{Z}\),\(a\) відповідає точно одному з цілих чисел 0, 1 або 2. Отже, ціле число\(a\) має бути конгруентним 0, 1 або 2, і воно не може бути конгруентним двом з цих чисел. Таким чином
- Для кожного\(a \in \mathbb{Z}\),\(a \in C[0]\),\(a \in C[1]\), або\(a \in C[2]\); і
- \(C[0] \cap C[1] = \emptyset\),\(C[0] \cap C[2] = \emptyset\), і\(C[1] \cap C[2] = \emptyset\).
Це означає, що відношення конгруентності по модулю 3 сортує цілі числа на три різні множини або класи, і що кожна пара цих множин не має спільних елементів. Отже, якщо ми використовуємо прямокутник для представлення\(\mathbb{Z}\), ми можемо розділити цей прямокутник на три менші прямокутники\(C[0]\)\(C[1]\), відповідні,\(C[2]\) і ми могли б уявити цю ситуацію наступним чином:
Цілі числа
| \(C[0]\)складається з усіх цілих чисел із залишком 0 при діленні на 3 | \(C[1]\)складається з усіх цілих чисел із залишком 1 при діленні на 3 | \(C[2]\)складається з усіх цілих чисел із залишком 2 при діленні на 3 |
Кожне ціле число знаходиться рівно в одному з трьох множин (C [0]\)\(C[1]\), або\(C[2]\), і два цілих числа збігаються по модулю 3 тоді і тільки тоді, коли вони знаходяться в одному множині. Ми побачимо, що подібним чином, якщо\(n\) є будь-яке натуральне число, то відношення конгруентності по модулю\(n\) може бути використано для сортування цілих чисел по\(n\) класах. Ми також побачимо, що загалом, якщо у нас є відношення еквівалентності\(R\) на множині\(A\), ми можемо сортувати елементи множини\(A\) в класи аналогічним чином.
\(\sim\)Дозволяти відношення еквівалентності на непорожній множині\(A\). Для кожного\(a \in A\) класу еквівалентності\(a\)\(\sim\) визначається підмножина\(A\), позначається [\(a\)], що складається з усіх елементів,\(A\) які еквівалентні\(a\). Тобто,
\([a] = \{x \in A\ |\ x \sim a\}.\)
Ми читаємо [\(a\)] як «клас еквівалентності\(a\)" або як «дужка»\(a\).
Нотатки
- Ми використовуємо позначення [\(a\)], коли використовується лише одне відношення еквівалентності. Якщо існує більше одного відношення еквівалентності, то нам потрібно розрізняти класи еквівалентності для кожного відношення. Ми часто використовуємо щось на\([a]_{\sim}\) кшталт, або якщо\(R\) це ім'я відношення, ми можемо використовувати\(R[a]\) або\([a]_R\) для класу еквівалентності визначеного по\(R\). У будь-якому випадку завжди пам'ятайте, що коли ми працюємо з будь-яким співвідношенням еквівалентності на множині A if\(a \in A\), то клас еквівалентності [\(a\)] є підмножиною\(A\).
- Ми знаємо, що кожне ціле число має клас еквівалентності для співвідношення еквівалентності конгруентності по модулю 3. Але, як ми бачили, насправді є тільки три різних класи еквівалентності. Використовуючи позначення з визначення, вони:
\([0] = \{a \in \mathbb{Z}\ |\ a \equiv 0 \text{ (mod 3)}\},\)
\([1] = \{a \in \mathbb{Z}\ |\ a \equiv 1 \text{ (mod 3)}\},\) і
\([2] = \{a \in \mathbb{Z}\ |\ a \equiv 2 \text{ (mod 3)}\}.\)
Не використовуючи термінологію в той час, ми фактично визначили класи еквівалентності відношення еквівалентності\(R\) в Preview Activity\(\PageIndex{1}\). Які різні класи еквівалентності для цього відношення еквівалентності?
- Відповідь
-
Додайте сюди тексти. Не видаляйте цей текст спочатку.
Класи конгруентності по модулю\(n\) та конгруентності
У Preview Activity\(\PageIndex{2}\) ми використовували позначення\(C[k]\) для набору всіх цілих чисел, які збігаються з\(k\) модулем 3. Ми могли б використовувати подібне позначення для класів еквівалентності, і це було б цілком прийнятно. Однак позначення [\(a\)], ймовірно, є найпоширенішим позначенням для класу еквівалентності\(a\). Тепер ми будемо використовувати цю саму позначення, коли мова йде про конгруентність по модулю,\(n\) коли розглядається лише одне співвідношення конгруентності.
Нехай\(n \in \mathbb{N}\). Конгруентність по модулю\(n\) є відношення еквівалентності на\(\mathbb{Z}\). Так для того\(a \in \mathbb{Z}\),
\([a] = \{x \in \mathbb{Z}\ |\ x \equiv a \text{ (mod \(n\))}\}.\)
У цьому випадку [\(a\)] називається класом конгруентності по\(a\) модулю\(n\).
Ми бачили, що конгруентність по модулю 3 ділить цілі числа на три різних класи конгруентності. Кожен клас конгруентності складається з цілих чисел з однаковим залишком при діленні на 3. Аналогічним чином, якщо ми використовуємо конгруентність по модулю 2, ми просто ділимо цілі числа на два класи. Один клас буде складатися з усіх цілих чисел, які мають залишок 0 при діленні на 2, а інший клас буде складатися з усіх цілих чисел, які мають залишок 1 при діленні на 2. Тобто конгруентність по модулю 2 просто ділить цілі числа на парні і непарні цілі числа.
Визначте всі відмінні класи конгруентності для співвідношення еквівалентності конгруентності по модулю 4 на цілі числа. Вкажіть кожен клас конгруентності за допомогою методу реєстру.
- Відповідь
-
Додайте сюди тексти. Не видаляйте цей текст спочатку.
Властивості класів еквівалентності
Як ми бачили, в Preview Activity\(\PageIndex{1}\) відношення R було співвідношенням еквівалентності. Для цієї активності попереднього перегляду ми використовували для\(R[y]\) позначення класу еквівалентності\(y \in A\), і ми спостерігали, що ці класи еквівалентності були або рівними, або неспільними.
Однак у Preview Activity\(\PageIndex{1}\) відношення не\(S\) було співвідношенням еквівалентності, і тому ми не використовуємо термін «клас еквівалентності» для цього відношення. Слід зазначити, однак, що набори не\(S[y]\) були рівними і не були розрізненими. Це демонструє одне з головних відмінностей між співвідношеннями еквівалентності та відносинами, які не є співвідношеннями еквівалентності.
У теоремі 7.14 ми доведемо,\(\sim\) що якщо відношення еквівалентності на множині\(A\), то ми можемо «сортувати» елементи\(A\) в різні класи еквівалентності. Властивості класів еквівалентності, які ми доведемо, такі: (1) Кожен елемент A знаходиться у власному класі еквівалентності; (2) два елементи еквівалентні тоді і лише тоді, коли їх класи еквівалентності рівні; і (3) два класи еквівалентності або однакові, або вони нез'єднані.
\(A\)Дозволяти бути непорожній набір і нехай\(\sim\) відношення еквівалентності на множині\(A\). Потім,
- Для кожного\(a \in A\),\(a \in [a]\).
- Для кожного\(a, b \in A\),\(a \sim b\) якщо і тільки якщо\([a] = [b]\),
- Для кожного\(a, b \in A\),\([a] = [b]\) або\([a] \cap [b] = \emptyset\).
- Доказ
-
Дозвольте A бути непорожнім набором і припустити, що\(\sim\) це відношення еквівалентності на\(A\). Щоб довести першу частину теореми, давайте\(a \in A\). Оскільки\(\sim\) це відношення еквівалентності на\(A\), воно є рефлексивним на\(A\). Таким чином\(a \sim a\), і можна зробити висновок, що\(a \in [a]\).
Друга частина цієї теореми є біумовним твердженням. Доведемо це шляхом доведення двох умовних тверджень. Ми спочатку доведемо, що якщо\(a \sim b\), то\([a] = [b]\). Так давайте\(a, b \in A\) і припустимо, що\(a \sim b\). Ми зараз доведемо, що два\([a]\) набори\([b]\) і рівні. Ми зробимо це, доводячи, що кожен є підмножиною іншого.
По-перше, припустимо, що\(x \in [a]\). Потім, за визначенням,\(x \sim a\). Оскільки ми припустили\(a \sim b\), що, ми можемо використовувати перехідну властивість\(\sim\) зробити висновок\(x \sim b\), що, і це означає, що\(x \in [b]\). Це доводить це\([a] \subseteq [b]\).
Тепер ми припускаємо, що\(y \in [b]\). Це означає\(y \sim b\), що, а значить і симетричною властивістю, що\(b \sim y\). Знову ж таки, ми припускаємо, що\(a \sim b\). Отже, ми маємо
\(a \sim b\)і\(b \sim y\).
Ми використовуємо перехідну властивість, щоб зробити висновок, що\(a \sim y\) і потім, використовуючи симетричну властивість, робимо висновок, що\(y \sim a\). Це доводить це\(y \in [a]\) і, отже, що\([b] \subseteq [a]\). Це означає, що можна зробити висновок, що якщо\(a \sim b\), то\([a] = [b]\).
Треба зараз довести, що якщо\([a] = [b]\), то\(a \sim b\). Нехай\(a, b \in A\) і припустимо, що\([a] = [b]\). Використовуючи першу частину теореми, ми знаємо, що\(a \in [a]\) і оскільки дві множини рівні, це говорить нам про це\(a \in [b]\). Звідси за визначенням\([b]\), ми робимо висновок, що\(a \sim b\). На цьому доказ другої частини теореми завершено.
Для третьої частини теореми давайте\(a, b \in A\). Так як ця частина теореми є диз'юнкцією, розглянемо два випадки: Або
\([a] \cap [b] = \emptyset\)або\([a] \cap [b] \ne \emptyset\).
У разі коли\([a] \cap [b] = \emptyset\), перша частина диз'юнкції вірна, а значить і доводити нічого. Таким чином, ми припускаємо, що\([a] \cap [b] \ne \emptyset\); і покаже, що\([a] = [b]\). Так як\([a] \cap [b] \ne \emptyset\), є елемент\(x\) в\(A\) такому, що
\(a \in [a] \cap [b]\).
Це означає, що\(x \in [a]\) і\(x \in [b]\). Отже,\(x \in a\) і\(x \in b\), і так ми можемо використовувати першу частину теореми, щоб зробити висновок, що\([x] = [a]\) і\([x] = [b]\). Отже\([a] = [b]\), і ми довели, що\([a] = [b]\) або\([a] \cap [b] = \emptyset\).
Теорема 7.14 дає первинні властивості класів еквівалентності. Наслідки цих властивостей будуть вивчені у вправах. Наступна таблиця повторює властивості в теоремі 7.14 і дає словесний опис кожного з них.
| Формальна заява з теореми 7.14 | Словесний опис |
|---|---|
| Для кожного\(a \in A\),\(a \in [a]\). | Кожен елемент\(A\) знаходиться у власному класі еквівалентності. |
| Для кожного\(a, b \in A\),\(a \sim b\) якщо і тільки якщо\([a] = [b]\). | Два елементи\(A\) еквівалентні тоді і тільки тоді, коли їх класи еквівалентності рівні. |
| Для кожного\(a, b \in A\),\([a] = [b]\) або\([a] \cap [b] = \emptyset\) | Будь-які два класи еквівалентності або рівні, або вони неспільні. Це означає, що якщо два класи еквівалентності не є розрізненими, то вони повинні бути рівними. |
\(f: \mathbb{R} \to \mathbb{R}\)Дозволяти визначатися\(f(x) = x^2 - 4\) для кожного\(x \in \mathbb{R}\). \(\sim\)Визначте відношення\(\mathbb{R}\) наступним чином:
Для\(a, b \in \mathbb{R}\),\(a \sim b\) якщо і тільки якщо\(f(a) = f(b)\).
У вправі (6) розділу 7.2 ми довели, що\(\sim\) це відношення еквівалентності на\(\mathbb{R}\). Отже, кожне дійсне число має клас еквівалентності. Для цього співвідношення еквівалентності,
- Визначте класи еквівалентності 5, -5, 10, -10\(\pi\), і\(-\pi\).
- Визначте клас еквівалентності 0.
- Якщо\(a \in \mathbb{R}\), скористайтеся методом roster, щоб вказати елементи класу еквівалентності\([a]\).
- Відповідь
-
Додайте сюди тексти. Не видаляйте цей текст спочатку.
Результати теореми 7.14 узгоджуються з усіма співвідношеннями еквівалентності, вивченими в попередній діяльності та в ході перевірок. Оскільки ця теорема застосовується до всіх співвідношень еквівалентності, вона застосовується до відношення конгруентності\(n\) по модулю на цілі числа. Через важливість цього співвідношення еквівалентності ці результати для конгруентності по модулю n наведені в наступному слідстві.
Нехай\(n \in \mathbb{N}\). Для кожного\(a \in \mathbb{Z}\), нехай\([a]\) представляють клас конгруентності по\(a\) модулю\(n\).
- Для кожного\(a \in \mathbb{Z}\),\(a \in [a]\).
- Для кожного\(a, b \in \mathbb{Z}\),\(a \equiv b\) (мод\(n\)) якщо і тільки якщо\([a] = [b]\).
- Для кожного\(a, b \in \mathbb{Z}\),\([a] = [b]\) або\([a] \cap [b] = \emptyset\).
Для співвідношення еквівалентності конгруентності по модулю\(n\), Теорема 3.31 і Слідство 3.32 говорять нам, що кожне ціле число є конгруентним до його залишку при діленні на\(n\), і що кожне ціле число є конгруентним по модулю\(n\) точно одному з цілих чисел\(0, 1, 2, ..., n - 1\). Це означає, що кожне ціле число знаходиться саме в одному з класів конгруентності\([0], [1], [2], ..., [n - 1]\). Отже, наслідок 7.16 дає нам наступний результат:
Нехай\(n \in \mathbb{N}\). Для кожного\(a \in \mathbb{Z}\), нехай\([a]\) представляють клас конгруентності по\(a\) модулю\(n\).
- \(\mathbb{Z} = [0] \cup [1] \cup [2] \cup \cdot\cdot\cdot \cup [n - 1]\)
- Для\(j, k \in \{0, 1, 2, ..., n -1\}\), якщо\(j \ne k\), то\([j] \cap [k] = \emptyset\).
Розділи та співвідношення еквівалентності
Розділ множини\(A\) - це сукупність підмножин\(A\), які «розбивають» множину на\(A\) нез'єднані підмножини. Технічно кожна пара різних підмножин у збірці повинна бути нез'єднаною. Потім ми говоримо, що колекція підмножин попарно розмежовується. Введемо наступне формальне визначення.
\(A\)Дозволяти бути непорожнім набором, і нехай\(\mathcal{C}\) буде колекція підмножин\(A\). Колекція підмножин\(\mathcal{C}\) є розділом за\(A\) умови, що
- Для кожного\(V \in \mathcal{C}\),\(V \ne \emptyset\).
- Для кожного\(x \in A\) існує\(V \in \mathcal{C}\) таке, що\(x \in V\).
- Для кожного\(V, W \in \mathcal{C}\),\(V = W\) або\(V \cap W = \emptyset\).
Існує тісний зв'язок між розділами та класами еквівалентності, оскільки класи еквівалентності відношення еквівалентності утворюють розділ базової множини, як буде доведено в теоремі 7.18. Доказ цієї теореми спирається на результати в теоремі 7.14.
\(\sim\)Дозволяти відношення еквівалентності на непорожній множині\(A\). Тоді\(\mathcal{C}\) колекція всіх класів еквівалентності,\(\sim\) що визначається, є розділом множини\(A\).
- Доказ
-
\(\sim\)Дозволяти відношення еквівалентності на непорожній множині\(A\), і нехай\(\mathcal{C}\) буде колекція всіх класів еквівалентності, визначених\(\sim\). Тобто,
\(\mathcal{C} = \{[a]\ |\ a \in A\}\).
Ми будемо використовувати теорему 7.14, щоб довести, що\(\mathcal{C}\) це розділ\(A\).
Частина (1) теореми 7.14 стверджує, що для кожного\(a \in A\),\(a \in [a]\). З точки зору класів еквівалентності це означає, що кожен клас еквівалентності є непорожнім, оскільки кожен елемент\(A\) знаходиться у своєму класі еквівалентності. Отже\(\mathcal{C}\), колекція всіх класів еквівалентності, що визначається\(\sim\), задовольняє першим двом умовам визначення розділу.
Тепер ми повинні показати, що\(\mathcal{C}\) колекція всіх класів еквівалентності визначається\(\sim\) задовольняє третій умові для того, щоб бути розділом. Тобто нам потрібно показати, що будь-які два класи еквівалентності або рівні, або є неспільними. Однак це саме результат у частині (3) теореми 7.14.
Отже, доведено, що колекція C всіх класів еквівалентності, що визначається,\(\sim\) є розділом множини A.
Примітка: Теорема 7.18 показала нам,\(\sim\) що якщо відношення еквівалентності на непорожній множині\(A\), то колекція класів еквівалентності визначається\(\sim\) формою поділу множини\(A\).
Цей процес можна повернути назад. Це означає, що за допомогою розділу\(\mathcal{C}\) непорожньої\(A\) множини ми можемо визначити відношення еквівалентності, класи еквівалентності\(A\) яких є саме підмножинами\(A\), що утворюють розділ. Це буде вивчено у Вправі (12).
- Дозволяти\(A = \{a, b, c, d, e\}\) і\(\sim\) нехай відношення на\(A\) що представлено орієнтованим графом на малюнку 7.4.
Довести, що\(\sim\) є відношення еквівалентності на множині\(A\), і визначити всі класи еквівалентності, визначені цим співвідношенням еквівалентності. - Нехай\(A = \{a, b, c, d, e, f\}\), і припустимо, що\(\sim\) це відношення еквівалентності на\(A\). Також припустимо, що відомо, що
\(a \sim b\)\(a \nsim c\)\(e \sim f\)
\(a \sim d\)\(a \nsim f\)\(e \nsim c\)
намалюйте повний орієнтований граф для співвідношення еквівалентності\(\sim\) на множині\(A\), а потім визначте всі класи еквівалентності для цього співвідношення еквівалентності. - Нехай\(A = \{0, 1, 2, 3, ..., 999, 1000\}\). Визначте відношення\(R\) на\(A\) наступним чином:
Для\(x, y \in A\),\(x\ R\ y\) якщо і тільки якщо\(x\) і\(y\) мають однакову кількість цифр.Довести, що\(R\) є відношення еквівалентності на множині\(A\) і визначити всі різні класи еквівалентності, визначені\(R\).
- Визначте всі класи конгруентності для співвідношення конгруентності по модулю 5 на множині цілих чисел.
- Нехай\(\mathbb{Z}_9 = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}\).
(а)\(\sim\) Визначте відношення\(\mathbb{Z}_9\) наступним чином: для всіх\(a, b \in \mathbb{Z}_9\),\(a \sim b\) якщо і тільки якщо\(a^2 \equiv b^2\) (мод 9). Довести, що\(\sim\) є відношення еквівалентності на\(\mathbb{Z}_9\) і визначити всі різні класи еквівалентності цього відношення еквівалентності.
(б)\(\approx\) Визначте відношення\(\mathbb{Z}_9\) наступним чином: Для всіх\(a, b \in \mathbb{Z}_9\),\(a \approx b\) якщо і тільки якщо\(a^3 \equiv b^3\) (мод 9). Довести, що\(\approx\) є відношення еквівалентності на\(\mathbb{Z}_9\) і визначити всі різні класи еквівалентності цього відношення еквівалентності. - \(\sim\)Визначте відношення\(\mathbb{Q}\) наступним чином: Для\(a, b \in \mathbb{Q}\),\(a \sim b\) якщо і тільки якщо\(a - b \in \mathbb{Z}\). У процесі перевірки 7.9 розділу 7.2 ми показали, що відношення\(\sim\) є співвідношенням еквівалентності на\(\mathbb{Q}\). Також див. вправу (9) у розділі 7.2.
(а) Доведіть, що\([\dfrac{5}{7} = \{m + \dfrac{5}{7}\ |\ m \in \mathbb{Z}\}\).
(б) Якщо\(a \in \mathbb{Z}\), то який клас еквівалентності\(a\)?
(c) Якщо\(a \in \mathbb{Z}\), довести, що існує біекція від\([a]\) до\([\dfrac{5}{7}]\). - \(\sim\)Визначте відношення\(\mathbb{R}\) наступним чином:
Для\(x, y \in \mathbb{R}\),\(x \sim y\) якщо і тільки якщо\(x - y \in \mathbb{Q}\).
(а) Доведіть, що\(\sim\) це відношення еквівалентності на\(\mathbb{R}\).
(b) Перерахуйте чотири різних дійсних числа, які знаходяться в класі еквівалентності\(\sqrt{2}\).
(c) Якщо\(a \in \mathbb{Q}\), що таке клас еквівалентності\(a\)?
(d) Доведіть, що\([\sqrt{2}] = \{r + \sqrt{2}\ |\ r \in \mathbb{Q}\}\).
(е) Якщо\(a \in \mathbb{Q}\), довести, що існує біекція від\([a]\) до\([\sqrt{2}]\). - Визначте відношення\(\sim\) за\(\mathbb{Z}\) наступним чином: Для\(a, b \in \mathbb{Z}\),\(a \sim b\) якщо і тільки якщо\((2a + 3b \equiv 0\) (мод 5). \(\sim\)Відношення - це відношення еквівалентності на\(\mathbb{Z}\). (Див. Вправа (13) у розділі 7.2). Визначте всі різні класи еквівалентності для цього відношення еквівалентності.
- Нехай\(A = \mathbb{Z} \times (\mathbb{Z} - \{0\})\). Тобто,\(A = \{(a, b) \in \mathbb{Z} \times \mathbb{Z}\ |\ b \ne 0\}\). \(\approx\)Визначте відношення\(A\) наступним чином:
Для\((a, b), (c, d) \in A\),\((a, b) \approx (c, d)\) якщо і тільки якщо\(ad = bc\).
(а) Доведіть, що\(\approx\) це відношення еквівалентності на\(A\).
(б) Чому необхідно було включити обмеження, яке\(b \ne 0\) у визначенні множини\(A\)?
(c) Визначити рівняння, яке дає відношення між\(a\) і\(b\) якщо\((a, b) \in A\) і\((a, b) \approx (2, 3)\).
(d) Визначте принаймні чотири різні елементи в [(2, 3)], клас еквівалентності (2, 3).
(e) Використовуйте поняття конструктора набору для опису [(2, 3)], клас еквівалентності (2, 3). - Для\((a, b) (c, d) \in \mathbb{R} \times \mathbb{R}\), визначити,\((a, b) \sim (c, d)\) якщо і тільки якщо\(a^2 + b^2 = c^2 + d^2\). У вправі (15) розділу 7.2 ми довели, що\(\sim\) це відношення еквівалентності на\(\mathbb{R} \times \mathbb{R}\).
(a) Визначити клас еквівалентності (0, 0).
(b) Використовуйте позначення конструктора множин (і не використовуйте символ\(\sim\)), щоб описати клас еквівалентності (2, 3), а потім дати геометричний опис цього класу еквівалентності.
(c) Дати геометричний опис типового класу еквівалентності для цього співвідношення еквівалентності.
(г) Нехай\(\mathbb{R}^{\ast} = \{x \in \mathbb{R}\ |\ x \ge 0\}\). Довести, що існує один до одного відповідність (bijection) між\(\mathbb{R}^{\ast}\) і множиною всіх класів еквівалентності для цього відношення еквівалентності. - \(A\)Дозволяти бути непорожній набір і нехай\(\sim\) відношення еквівалентності на\(A\). Доведіть кожне з наступного:
(а) Для кожного\(a, b \in A\),\(a \nsim b\) якщо і тільки якщо\([a] \cap [b] = \emptyset\).
(б) Для кожного\(a, b \in A\), якщо\([a] \ne [b]\), то\([a] \cap [b] = \emptyset\).
(c) Для кожного\(a, b \in A\), якщо\([a] \cap [b] \ne \emptyset\) тоді\([a] = [b]\).
Дослідження та діяльність - Розділ визначає відношення еквівалентності. Нехай\(A = \{a, b, c, d, e\}\) і нехай\(\mathcal{C} = \{\{a, b, c\}, \{d, e\}\}\).
(а) Поясніть, чому\(\mathcal{C}\) це розділ\(A\).
\(\sim\)Визначте відношення\(A\) наступним чином: Для\(x, y \in A\),\(x \sim y\) якщо і тільки в тому випадку, якщо існує безліч\(U\) в\(\mathcal{C}\) такому, що\(x \in U\) і\(y \in U\).
(b) Доведіть, що\(\sim\) це відношення еквівалентності на множині\(A\), а потім визначити всі класи еквівалентності для\(\sim\). Як порівнюється колекція всіх класів еквівалентності\(\mathcal{C}\)?
Те, що ми зробили для конкретного розділу в Part (12b), можна зробити для будь-якого розділу набору. Таким чином, щоб узагальнити Частина (12b), ми дозволяємо\(A\) бути непорожній набір і нехай\(\mathcal{C}\) бути розділ\(A\). Потім ми\(\sim\) визначаємо відношення\(A\) наступним чином:
Для\(x, y \in A\),\(x \sim y\) якщо і тільки якщо існує безліч\(U\) в\(\mathcal{C}\) такому, що\(x \in U\) і\(y \in U\).
(c) Доведіть, що\(\sim\) це відношення еквівалентності на множині\(A\).
(г) Нехай\(a \in A\) і нехай\(U \in \mathcal{C}\) таке\(a \in U\). Доведіть це\([a] = U\). - Відносини еквівалентності на множині матриць. Наступні вправи вимагають знання елементарної лінійної алгебри. Ми дозволимо\(\mathcal{M}_{n,n} (\mathbb{R}\) бути множиною всіх\(n\)\(n\) матриць з дійсними числовими записами.
(а)\(\sim\) Визначте відношення\(\mathcal{M}_{n,n} (\mathbb{R}\) наступним чином: Для всіх\(A, B \in \mathcal{M}_{n,n} (\mathbb{R}\),\(A \sim B\) якщо і тільки якщо існує обернена матриця\(P\) в\(\mathcal{M}_{n,n} (\mathbb{R}\) такому, що\(B = PAP^{-1}\). Чи\(\sim\) є відношення еквівалентності на\(\mathcal{M}_{n,n} (\mathbb{R}\)? Обгрунтуйте свій висновок.
(b) Визначити відношення\(R\)\(\mathcal{M}_{n,n} (\mathbb{R}\) наступним чином: Для всіх\(A, B \in \mathcal{M}_{n,n} (\mathbb{R}\),\(A\ R\ B\) якщо і тільки якщо det (\(A\)) = det (\(B\)). Чи\(R\) є відношення еквівалентності на\(\mathcal{M}_{n,n} (\mathbb{R}\)? Обгрунтуйте свій висновок.
(c)\(\sim\) Дозволяти відношення еквівалентності на\(\mathbb{R}\). \(\approx\)Визначте відношення\(\mathcal{M}_{n,n} (\mathbb{R}\) наступним чином: Для всіх\(A, B \in \mathcal{M}_{n,n} (\mathbb{R}\),\(A \approx B\) якщо і тільки якщо det (\(A\)) det ()\(\sim\) det (\(B\)). Чи\(\approx\) є відношення еквівалентності на\(\mathcal{M}_{n,n} (\mathbb{R}\)? Обгрунтуйте свій висновок.
- Відповідь
-
Додайте сюди тексти. Не видаляйте цей текст спочатку.