7.3: Перегородки

Теореми 7.42 і 7.43 означають,\(\sim\) що якщо відношення еквівалентності на множині\(A\), то\(\sim\)\(A\) розпадається на попарно неспільні «шматки», де кожен шматок є деяким\([a]\) для\(a\in A\). Як ви, напевно, вже помітили, відносини еквівалентності тісно пов'язані з наступним поняттям.

Визначення 7.51. \(\Omega\)Колекція підмножин\(A\) множини називається розділом,\(A\) якщо елементи\(\Omega\) задовольняють:

1. Кожен\(X\in \Omega\) непорожній,
2. Для всіх\(X,Y\in\Omega\),\(X\cap Y=\emptyset\) коли\(X\neq Y\), і
3. \(\displaystyle \bigcup_{X\in\Omega}X=A\).

Тобто елементи є попарно непорожніми множинами, і їх об'єднання - це все\(A\).\(\Omega\) Кожен\(X\in \Omega\) називається блоком розділу.

Приклад 7.52. Розглянемо співвідношення еквівалентності\(\sim\) на множині,\(P\) описаному в прикладі 7.45. Нагадаємо, що класи еквівалентності відповідають колекціям індивідів з однаковим прізвищем. Оскільки кожен клас еквівалентності непорожній і кожен житель міста належить рівно до одного класу еквівалентності, колекція класів еквівалентності утворює розділ\(P\). Тобто це перегородка\(P\),\(P/\mathord\sim\) де блоки перегородки відповідають множинам мешканців з однойменною прізвищем.

Приклад 7.53. Кожен з наведених нижче є прикладом розділу множини, наведеного в дужках.

1. Демократична, республіканська, незалежна, партія зелених, лібертаріанська тощо (набір зареєстрованих виборців)
2. Першокурсник, другокурсник, молодший, старший (набір старшокласників)
3. Евенс, коефіцієнти (набір цілих чисел)
4. Раціональні, ірраціональні (множина дійсних чисел)

Приклад 7.54. Нехай\(A=\{a,b,c,d,e,f\}\) і\(\Omega=\{\{a\}, \{b,c,d\}, \{e,f\}\}\). Оскільки елементи попарно нероз'єднані непорожні підмножини\(A\) таких, що їх об'єднання є все\(A\),\(\Omega\) є розділом,\(A\) що складається з трьох блоків.\(\Omega\)

Завдання 7.55. Розглянемо набір\(A\) з прикладу 7.54.

1. Знайдіть перегородку,\(A\) що складається з чотирьох блоків.
2. Знайти колекцію підмножин\(A\), які не утворюють розділ. Подивіться, скільки способів ви можете запобігти тому, щоб ваша збірка була розділом.

Завдання 7.56. Для кожного з перерахованих нижче, знайдіть розділ\(\mathbb{Z}\) з заданими властивостями.

1. Розділ\(\mathbb{Z}\), який складається з скінченно багатьох блоків, де кожен з блоків нескінченний.
2. Розділ\(\mathbb{Z}\), який складається з нескінченно багатьох блоків, де кожен з блоків є кінцевим.
3. Розділ\(\mathbb{Z}\), який складається з нескінченно багатьох блоків, де кожен з блоків нескінченний.

Завдання 7.57. Для кожного співвідношення в задачі 7.34 визначте, чи утворює відповідна колекція множин родичів розділ заданої множини.

Проблема 7.58. Чи можемо ми розділити порожній набір? Якщо так, опишіть розділ. Якщо ні, поясніть, чому.

Наступна теорема викладає половину тісного зв'язку між розділами і співвідношеннями еквівалентності. Теорема 7.73 дає другу половину.

Проблема 7.59. Якщо\(\sim\) є співвідношенням еквівалентності на непорожній\(A\) множині, то\(A/\mathord\sim\) утворюється розділ\(A\).

Завдання 7.60. У попередній теоремі, чому ми\(A\) вимагали бути непорожніми?

Завдання 7.61. Розглянемо співвідношення еквівалентності\[\sim\ =\{(1,1),(1,2),(2,1), (2,2),(3,3),(4,4),(4,5),(5,4),(5,5),(6,6),(5,6),(6,5),(4,6),(6,4)\}\] на множині\(A=\{1,2,3,4,5,6\}\). Знайдіть розділ, який визначається за допомогою\(Rel(\sim)\).

Виявляється, ми можемо змінити ситуацію, а також. Тобто, за заданим розділом, ми можемо сформувати відношення еквівалентності таким чином, щоб класи еквівалентності відповідали блокам розділу. Перш ніж довести це, нам потрібно визначення.

Визначення 7.62. \(A\)Дозволяти множина і\(\Omega\) будь-яка колекція підмножин\(A\) (не обов'язково розділ). Визначте відношення\(R_{\Omega}\) на\(A\) via,\(aR_{\Omega}b\) якщо існує\(X\in \Omega\), що містить обидва\(a\) і\(b\). Це відношення називається\(A\) відношенням на асоційованих до\(\Omega\).

Іншими словами, два елементи пов'язані саме тоді, коли вони знаходяться в одній підмножині.

Завдання 7.63. Нехай\(A=\{a,b,c,d,e,f\}\) і нехай\(\Omega=\{\{a,c\},\{b,c\},\{d,f\}\}\). Перерахуйте впорядковані пари\(R_{\Omega}\) і намалюйте відповідний диграф.

Завдання 7.64. \(\Omega\)Дозволяти\(A\) і бути, як у прикладі 7.54. Перерахуйте впорядковані пари\(R_{\Omega}\) і намалюйте відповідний диграф.

Завдання 7.65. Розглянемо задачу 7.24. Знайдіть відношення на\(A\) асоційованому до\(Rel(\sim)\) та порівняйте з тим, що ви отримали\(R\) в Задачі 7.24.

Завдання 7.66. Наведіть приклад множини\(A\) і збірки\(\Omega\) з\(\mathcal{P}(A)\) таких, щоб відношення\(R_{\Omega}\) не було рефлексивним.

Завдання 7.67. Нехай\(A=\{1,2,3,4,5,6\}\) і\(\Omega=\{\{1,3,4\},\{2,4\},\{3,4\},\{6\}\}\).

1. Чи\(\Omega\) є перегородкою\(A\)?
2. Знайдіть\(R_{\Omega}\), перерахувавши впорядковані пари або намалювавши диграф.
3. Чи\(R_{\Omega}\) є відношення еквівалентності?
4. Знайти\(Rel(R_\Omega)\) (тобто колекцію підмножин\(A\) визначених по\(R_{\Omega}\)). Як пов'язані\(\Omega\) і\(Rel(R_\Omega)\) пов'язані?

Теорема 7.68. If\(\Omega\) є сукупністю підмножин непорожньої\(A\) множини (не обов'язково розділ) такий, що\[\bigcup_{X\in\Omega}X=A,\] потім\(R_{\Omega}\) є рефлексивним.

Завдання 7.69. Чи потрібно\(A\) вимагати бути непорожнім у теоремі 7.68?

Теорема 7.70. Якщо\(\Omega\) є сукупністю підмножин\(A\) множини (не обов'язково розділ), то\(R_{\Omega}\) є симетричною.

Теорема 7.71. Якщо\(\Omega\) є сукупністю підмножин множини\(A\) (необов'язково розділ) такий, що елементи попарно нез'єднані, то\(R_{\Omega}\) є перехідним.\(\Omega\)

Завдання 7.72. Чому ми не\(A\) вимагали бути непорожніми в теоремах 7.70 та 7.71?

Нагадаємо, що теорема 7.59 говорить про те, що класи еквівалентності для відношення на непорожній\(A\) множині визначає поділ\(A\). Наступна теорема говорить нам, що кожен розділ множини дає відношення еквівалентності, де класи еквівалентності відповідають блокам розділу. Цей результат є наслідком теорем 7.68, 7.70 та 7.71.

Теорема 7.73. Якщо\(\Omega\) є розділом множини\(A\), то\(R_{\Omega}\) це відношення еквівалентності.

Разом теореми 7.59 та 7.73 говорять нам, що співвідношення еквівалентності та розділи - це два різні способи перегляду одного і того ж.

Слідство 7.74. Якщо відношення на\(R\) непорожній множині\(A\) таке, що колекція множини родичів щодо\(R\) є розділом\(A\), то\(R\) це відношення еквівалентності.

Проблема 7.75. Нехай\(A=\{\circ, \triangle, \blacktriangle, \square, \blacksquare, \bigstar \}\). Складіть розділ\(\Omega\) на,\(A\) а потім намалюйте диграф, відповідний\(R_{\Omega}\).