Сервер Методического Обеспечения вгуэс

Вид материала

Реферат

Содержание 3. Проверка выполняется для всех трех аксиом. а) делится на 3 Классом эквивалентности

Подобный материал:

• Дипломная работа студента 545 группы, 334.18kb.
• Т. Н. Коржавина Принципы организации службы научного и методического обеспечения колледжа, 47.35kb.
• «sql*net», 239.02kb.
• Генезис развития теории и методики программно-методического обеспечения обучения, 145.89kb.
• Прозрачный прокси сервер на базе squid, ipfw и Freebsd, 8.5kb.
• Доклад «Три кита школьного образования: стандарты, учебники, егэ», 116.02kb.
• Справка по результатам самоаттестации методического объединения учителей русского языка, 447.26kb.
• Большой Сервер Недвижимости 31. 05. 2008: программа, 1328.13kb.
• Т. Г. Римская научный редактор, к и. н., доцент, директор филиала вгуэс в г. Находке, 2476.8kb.
• Владивосток: Изд-во вгуэс, 2005., 1071.2kb.

.

Значит, .

1. §6. Отношение эквивалентности

2. Определение 1

Отношение называется отношением эквивалентности, если выполняются три аксиомы:

а) для любого  – рефлексивность;

б) для любых  – симметричность;

в) для любых  – транзитивность.

1. Пример 1

определяется условием: делится на 3. Проверка выполняется для всех трех аксиом.

а) делится на 3, следовательно, .

б) Пусть , то есть делится на 3, значит, и также делится на 3, значит, .

в) Пусть , , следовательно, делится на 3 и делится на 3, тогда тоже делится на 3, то есть .

1. Пример 2

Пусть определяется следующим условием: делится на 3. Данное отношение не является отношением эквивалентности, так как нарушается уже первая аксиома – рефлексивность, так как не для любого делится на 3. Достаточно взять . Отметим кстати, что остальные две аксиомы – симметричность и транзитивность – выполняются. Проверьте это самостоятельно.

1. Пример 3

определяется условием .

а) Так как для любого , значит, .

б) Пусть , то есть , значит, , то есть . Симметричность выполняется.

в) Пусть и , значит, и , следовательно, , поэтому . Транзитивность выполняется.

1. Пример 4

Пусть  – множество мужчин, определяется условием  – брат y. Если договориться, что мужчина сам себе является братом, то является отношением эквивалентности, так как симметричность и транзитивность выполняется очевидным образом.

Если договорится для отношения эквивалентности вместо писать ~ , то аксиомы этого отношения перепишутся более простым и обычным образом:

а) для любого ~ ;

б) для любых ~ ~ ;

в) для любых ~ ~ ~ .

1. Задача

Докажите, что эти условия равносильны следующим отношениям:

а) ;

б) ;

в) .

1. Определение 2

Пусть задана система множеств , тогда:

а) ;

б) .

Очевидно, что объединение и пересечение конечного числа множеств, например, n, является частным случаем этих определений, когда индексное множество .

1. Определение 3

Система множеств называется разбиением множества , если

а) ;

б) для любых .

Другими словами, различные множества из системы не пересекаются.

1. Определение 4

Пусть  – отношение эквивалентности на . Классом эквивалентности, порожденным элементом , называется множество .

1. Теорема 5

Если  – отношение эквивалентности на , то множество классов эквивалентности образуют разбиение .

• Доказательство

Докажем вначале . Так как для любого , то включение очевидно. Возьмем . Так как , то , значит , то есть , значит и . Пусть , значит существует , то есть и . По транзитивности . Теперь докажем, что . Возьмем . Если же . Таким образом, .

Итак, мы доказали, что любое отношение эквивалентности на множестве порождает естественным образом разбиение на классы эквивалентности. Оказывается, имеет место и обратное утверждение.

1. Теорема 6

Пусть система множеств образует разбиение множества . Отношение существует такое , что является отношением эквивалентности на . Причем элементы разбиения являются классом эквивалентности.

• Доказательство

Проверим выполнение всех трех аксиом – рефлексивности, симметричности, транзитивности.

Рефлексивность. Пусть , тогда для некоторого . Тогда можно записать: , то есть .

Симметричность. Пусть , то есть существует , такой, что , тогда и , значит, .

Транзитивность. Пусть и , значит, существуют такие и , что и , но тогда , то есть . По определению разбиения , значит, , то есть .

Теорема доказана.