Визначення 16. розбиття множини на класи називається поділ на непересічні, але в сумі вичерпні його підмножини.
Зазвичай доводиться мати справу з розбивками, побудованими на базі тієї чи іншої ознаки, за яким елементи безлічі об'єднуються в класи. Наприклад, безліч всіх студентів розбивається на підмножини студентів різних курсів. Ознаки, за якими розбивається безліч, можуть бути самими різними. Але такі ознаки не цілком довільні. Припустимо, наприклад, що ми хочемо розбити безліч студентів економічного факультету за наступним ознакою: студент Іванов потрапляє в один клас із студентом Петровим, якщо і тільки якщо він вчиться в університеті на рік більше Петрова. Ясно, що ніякого розбиття таким шляхом отримати не можна. Якщо Іванов потрапив в один клас з Петровим, то Петров вчиться на рік менше Іванова, значить, він не може потрапити в один клас з Івановим на нашу ознакою. Він не може навіть потрапити в один клас з самим собою! Наведений приклад підказує умови, яким повинен задовольняти будь-яка ознака розбиття деякої множини на класи. Нижче ці умови наведені без доведення їхньої необхідності та достатності.
Нехай M - деякий безліч і нехай деякі з пар x. y цієї множини є "зазначеними". При цьому x. y і y. x - дві, взагалі кажучи, різні пари. Якщо x. y - "відзначена" пара, то ми будемо говорити, що елемент x пов'язаний з y ставленням # 981 ;. Наприклад, якщо мати на увазі розбиття студентів на курси, то означає: "студент x вчиться на одному курсі зі студентом y". дане відношення # 981; називається відношенням еквівалентності, якщо воно має такі властивості:
1) рефлексивність x ≈ x;
2) симетричність, якщо x ≈ y. то y ≈ x;
3) транзитивність, якщо x ≈ y. y ≈ z. то x ≈ z.
Як уже згадувалося, для того щоб по даному відношенню можна було розбити безліч на непересічні класи, необхідно і достатньо, щоб це відношення було ставленням еквівалентності.
Приклад розбиття універсальної множини на чотири класи еквівалентності
Визначення 17. Подрібнення розбиття. якщо і - два різних розбиття множини U. то ми отримаємо нове розбиття, розглядаючи систему всіх підмножин виду A i ∩ B j. Це нове розбиття називається подрібненням двох початкових розбиття.
Ще один приклад подрібнення розбиття показаний на малюнку 5
Для будь-якого кінцевого безлічі X позначимо n (X) число елементів у ньому.
Теорема 3 (про число елементів в об'єднанні множин).
n (A ∪ B) = n (A) + n (B) - n (A ∩ B)
Доведення. Неважко бачити, що справедливі формули
n (A) = n (A ∩ B) + n (A ∩ B # 175; ). n (B) = n (B ∩ A) + n (B ∩ A # 175; ).
Тоді n (A) + n (B) = n (A ∩ B) + n (A ∩ B) # 175; + N (B ∩ A) + n (B ∩ A # 175; ). Або перепишемо цю формулу n (A) + n (B) - n (A ∩ B) = n (A ∩ B) + n (A ∩ B # 175; ) + N (B ∩ A # 175; ). Далі, безлічі
A ∩ B. A ∩ B # 175 ;. A # 175; ∩ B попарно не перетинаються. Отже, утворюють розбиття множини A ∪ B.
Тоді n (A ∪ B) = n (A ∩ B # 175; ) + N (A # 175; ∩ B) + n (A ∩ B).
З огляду на попередню формулу, отримуємо потрібну нам співвідношення.