Таблицы Брадиса

Пусть отношение эквивалентности на М.

Пусть отношение эквивалентности на М.

Элементы математики в задачах - Г. А. Мерзон

Определение 4. Пусть-- отношение эквивалентности на М, а є

є М. Множество Ыа = {х є М | а ~ х} называется классом эквивалент­ности элемента а.

Ш Обязательно разберите определение на простом примере. Напри­мер, пусть множество М — это множество учеников школы, а а ~ Ь, если ученики а и Ь учатся в одном классе. Тогда Ыа — это все одно­классники а (включая самого а).

Задача 5. Докажите, что для любого отношения эквивалентности классы эквивалентности либо не пересекаются, либо совпадают.

Докажите, что каждое отношение эквивалентности на М задаёт разбиение множества М на непересекающиеся классы эквивалент­ности.

Ш Это одна из самых важных задач в листочке.

Решение. Предположим, что два класса эквивалентности Ыа и Ыь пе­ресекаются, то есть существует с, принадлежащее обоим классам (см. рисунок). Докажем, что эти классы эквивалентности совпадают. Для

N

 

N

 

 

этого достаточно доказать, что Ыа с ЫЬ и ЫЬ с Ыа. Докажем первое включение. Для любого элемента d е Ыа верно, что d ~ а (на самом деле а ~ d, но отношение эквивалентности симметрично!) и а ~ с, а значит, по транзитивности d ~ с, но мы знаем, что с ~ Ь, а значит, опять применяя транзитивность, получаем, что d ~ Ь, то есть d еЫЬ.

& Можно также воспользоваться такой леммой: если а е ЫЬ, то

На С Щ.

Определение 5. Пусть-- отношение эквивалентности на М. Мно­жество классов эквивалентности называется фактормножеством и обозначается М/

Это определение еще труднее понимается школьниками. Вернем­ся к примеру, который мы разбирали в комментарии к определе­нию 4. Каждый класс эквивалентности — это ученики из одного клас­са, значит, фактормножество — это множество классов в этой школе.