Читайте также:
|
1. Если X ={ 1,2,3,4,5 }, то множество {{ 1,2 }, { 3 }, { 4,5 }} будет его разбиением.
2. Если X – множество студентов университета, то разбиениями будут множество факультетов или множество студенческих групп.
Утверждение 1.6. Всякое разбиение множества X определяет на X отношение эквивалентности r тогда и только тогда, когда из < x, y > Î r следует, что x, y принадлежат одному подмножеству разбиения.
Доказательство. Всякое разбиение, согласно определению, задает отношение принадлежности к подмножеству разбиения. Следовательно, остается доказать, что это отношение есть эквивалентность.
1) Рефлексивность: < x, x > Î r, так как x принадлежит какому-то одному подмножеству.
2) Симметричность: пусть x, y принадлежат одному подмножеству, тогда из
< x, y > Î r следует, что y, x принадлежат этому же подмножеству, т.е. < y, x > Î r.
3) Транзитивность: Пусть < x, y > Î r, тогда x, y Î Xt, и пусть < y, z > Î r, тогда
y, z Î Xs. Так как y Î Xt и y Î Xs, то Xt = Xs, тогда z Î Xt, следовательно, < x, z> Î r.
Утверждение 1.7. Всякое отношение эквивалентности r определяет разбиение множества X на классы эквивалентности относительно этого отношения.
Доказательство. Согласно утверждению 1.5, каждый элемент x принадлежит некоторому классу эквивалентности [ x ] относительно r. Покажем, что любые два класса либо не пересекаются, либо совпадают. Действительно, пусть z принадлежит разным классам, то есть z Î [ x ] и z Î [ y ], тогда < x, z > Î r и < y, z > Î r, то есть [ x ] = [ z ], [ y ] = [ z ]. Следовательно, [ x ] = [ y ], так как они состоят из одних и тех же элементов.
Фактор-множествомX/r множества X по отношению эквивалентности r называетсясовокупность классов эквивалентности элементов этого множества
1.5. Отношение частичного порядка
Ø Упорядоченные множества
Ø Точная верхняя и точная нижняя грани упорядоченных множеств
Ø Диаграммы Хассе
Ø Изоморфизм множеств
Ø Классы бинарных отношений, не являющиеся эквивалентностью или частичным порядком
Упорядоченные множества
Отношением частичного порядка на множестве C называется бинарное отношение £ (предшествует), являющееся одновременно рефлексивным, антисимметричным и транзитивным на этом множестве. Множество C, на котором задано отношение порядка £, записывается как пара (C, £).
Дата добавления: 2015-07-20; просмотров: 45 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Доказательство.Так как r – рефлексивно, то <x, x> Î r и по определению класса эквивалентности [x], x Î [x]. | | | Пример 1.23 |