АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Отношение эквивалентности. Теорема о разбиении множества отношением эквивалентности на классы

Читайте также:
  1. I. IIонятие, виды и соотношение источников МЧП.
  2. IX. Отношение к личности
  3. IX.6. Взаимоотношение науки и техники
  4. S-M-N-теорема, приклади її використання
  5. V2: Дуализм свойств микрочастиц. Соотношение неопределенностей Гейзенберга
  6. А. Базовое системное соотношение.
  7. Абстрактные классы и чистые виртуальные функции. Виртуальные деструкторы. Дружественные функции. Дружественные классы.
  8. Б. Наследственное правоотношение
  9. Б. Наследственное правоотношение
  10. Б. Системное соотношение с измененным основным аргументом.
  11. Б1 1.Системы линейных алгебраических уравнений (СЛУ). Теорема Кроникера-Капелли. Общее решение СЛУ.
  12. Базисный минор и ранг матрицы. Теорема о базисном миноре

Определение 1. Бинарное отношение на множестве А называется отношением эквивалентности, если - рефлексивно, симметрично и транзитивно.

Определение 2. Пусть -отношение эквивалентности на множестве А. Множество называется классом эквивалентности с представителем а или смежным классом А по . И обозначается а\ .

Множество всех классов эквивалентности называется фактор - множеством и обозначается А\ .

Определение 3. Пусть Ø. Разбиением множества А на классы называется совокупность его непустых подмножеств множества А, объединение которых совпадает с самим множеством А, а пересечение любых двух различных из них пусто. Другими словами совокупность из S подмножеств множества А является разбиением множества А, если выполняются следующие условия:

1) каждое подмножество из S непусто;

2) объединение всех подмножеств из S совпадает с самим множеством А;

3) пересечение любых двух различных подмножеств из S равно пустому множеству.

Теорема 1. Если на непустом множестве А задано отношение эквивалентности , то А разбивается отношением на непересекающиеся классы, причем эти классы имеют вид а\ , где

Доказательство: Пусть а\ = Необходимо показать, что:

1) Ø.

2)

3) из Ø следует, что

1) Действительно, так как - отношение эквивалентности, то - рефлексивно, а, значит, . Следовательно, , то есть Ø.

2) Так как . С другой стороны,

Отсюда,

3) Предположим, что Ø. Пусть, например, , тогда, по определению класса эквивалентности,

Покажем, что Пусть Так как в силу симметричности , то в силу транзитивности , . Следовательно, . В силу произвольности выбора х, получаем:

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

Из и

Из (1) и (2) Получили противоречие с предположением, о том, что

Итак, множество А является объединением непустых непересекающихся классов, вида а\ . Что и требовалось доказать.

Замечание. Пусть - отношение эквивалентности на непустом множестве А. Тогда по теореме 1 множество А разлагается на непересекающиеся классы эквивалентности по отношению с представителем а.

Пример: Дано множество: A={1,2,3,4}, на котором задано отношение эквивалентности ={(1,1);(2,2);(3,3);(4,4);(2,4);(4,2)}. Построить разбиение множества А на непересекающиеся классы, соответствующее оношению эквивалентности .

Решение: A1={1}; A2={2,4}; A3={4}. A/ ={A1, A2, A3}.

Теорема 2. Пусть Если - разбиение непустого множества А на непересекающиеся классы, то S соответствует отношение эквивалентности на множестве А, причем

Доказательство. Пусть разбиение непустого множества А на непересекающиеся классы. Тогда, 1) Ø, 2) Ø

Определим на множестве А бинарное отношение по правилу: Другими словами, элементы a и b находятся в отношении тогда и только тогда, когда они принадлежат одному и тому же классу

1. Так как S - разбиение А, то и так как элемент a принадлежит одному классу , то по определению , пара , то есть - рефлексивно на А.

2. Пусть . Тогда, по определению , a и b принадлежат одному и тому же классу . Следовательно, и элементы b и a принадлежат одному и тому же классу . По определению имеем: , то есть -симметрично на А.

3. Пусть и . Значит, по определению , а и b принадлежат одному и тому же классу Аt и b и с принадлежат одному и тому же классу Аk. Так как b Аt и b Аk, то Аt= Аk, следовательно, а и с принадлежат одному и тому же классу и, значит, (а, с) . Итак, - -транзитивно на А.

Следовательно, - отношение эквивалентности на А.

Так как каждый класс эквивалентности по отношению эквивалентности состоит из тех и только тех элементов из А, которые находятся в отношении , то классы эквивалентности совпадают с классами из S. Но множество всех классов эквивалентности есть Что и требовалось доказать.

Замечание. В силу теорем 1 и 2, между множеством всех отношений эквивалентности на множестве А и множеством всех разбиений множества А на непересекающиеся классы существует взаимно однозначное соответствие. Следовательно, эквиваленций на конечном множестве А существует столько, сколько существует разбиений множества А.

Пример. Подсчитать, сколько отношений эквивалентности существует на множестве А={1,2,3}. Выписать отношения эквивалентности на А и соответствующие им разбиения.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.015 сек.)