Отношение упорядоченности

Отношение эквивалентности

Бинарное отношение r, заданное на множестве М, называется отношением эквивалентности или просто эквивалентностью, если оно рефлексивно, транзитивно и симметрично. Для обозначения этого отношения чаще используется запись a ~ b без указания r.

Значение этого отношения заключается в том, что с помощью него множество разбивается в объединение попарно непересекающихся подмножеств (классов эквивалентности).

Пусть «~» – эквивалентность на множестве М. Подмножество К_а Í М, состоящее из всех элементов М, эквивалентных элементу а Î М, называется классом эквивалентности элемента а по отношению «~», т.е. К_а ={ х: х ~ а, где а, х Î М }.

Утверждения:

1) Два класса эквивалентности множества М либо совпадают, либо не пересекаются.

2) Любой элемент множества М попадает в один и только один класс эквивалентности. Поэтому множество М разбивается на попарно непересекающиеся классы эквивалентных между собой элементов.

Множество всех классов эквивалентности для М по отношению «~» называется фактор–множеством и обозначается М /~. А процесс разбиения М на классы эквивалентности называется факторизацией.

Примеры:

1) Отношение равенства на любом множестве является эквивалентностью. Соответствующее ему разбиение на классы есть объединение всех одноэлементных подмножеств данного множества.

2) На множестве всех целых чисел рассмотрим отношение r, согласно которому (x, y)Î r, если х и у имеют одинаковые знаки. Ясно, что это отношение рефлексивно, транзитивно и симметрично, следовательно, r – эквивалентность. Тогда соответствующая факторизация множества ℤ /~=ℤ^‑∪ℤ⁺∪{0}, т.к. число 0 эквивалентно только себе.

Бинарное отношение, заданное на множестве М и обладающее свойствами рефлексивности, транзитивности и антисимметричности, называется отношением частичной упорядоченности или просто упорядоченностью. Множество М в этом случае называется упорядоченным. Упорядоченность называется строгой, если отношение не рефлексивно. Упорядоченность называется линейной, если для любых элементов а, b Î М => либо (a, b)Î r, либо (b, a)Î r. Множество М в этом случае называется линейно–упорядоченным или цепью.

Для обозначения отношения упорядоченности обычно используют знаки £ (или <), ³ (или >). При этом a £ b равнозначно b ³ a, и запись a < b означает, что a £ b и a ¹ b. Если a < b, то говорят, что а предшествует b (находится перед b), а b следует за а (находится после а). Т.о., для любых двух элементов цепи обязательно должно выполняться одно из двух: либо a £ b, либо b £ a.

Примеры:

1) На множестве М ={ a, b, c } рассмотрим отношение R ={(a, a); (a, b); (b, b); (c, b); (c, c)}. Это отношение рефлексивно, транзитивно и антисимметрично. Ввиду этого R является отношением частичной упорядоченности и М – частично упорядоченное множество (ч.у.м.). Линейно упорядоченным это множество не является, т.к. например, ни пара (a, c), ни пара (c, a) отношению R не принадлежит.

2) Множество натуральных чисел линейно упорядочено отношением £.

Утверждение: если множество М упорядочено или линейно–упорядочено, то и каждое его подмножество упорядочено тем же отношением.

Линейно–упорядоченное множество называется вполне упорядоченным, если у каждого его непустого и ограниченного снизу подмножества есть нижняя грань. Иными словами, упорядоченное множество является вполне упорядоченным, если любое его непустое подмножество имеет первый элемент. Элементы вполне упорядоченного множества носят название трансфинитов или трансфинитных чисел.

Примеры:

1) Ряд натуральных чисел является вполне упорядоченным, т.к. в любом его непустом подмножестве есть первый элемент (нижняя грань).

2) Множество целых чисел не является вполне упорядоченным в «естественном порядке», т.к. в нем самом нет первого элемента. Однако, его можно вполне упорядочить, если расположить его элементы, например так: 0, 1, -1, 2, -2, 3, -3,… или так: 1, 2, 3,…, 0, -1, -2, -3,…, где положительные числа предшествуют всем остальным.

Сечением вполне упорядоченного множества называется всякое его разбиение на два непустых непересекающихся подмножества А и В таких, что для любых элементов а А и b В следует, что а < b. Тогда множество А называется левым (или нижним) классом, а В – правым (или верхним) классом.

Свойство полноты в терминах сечений можно определить так: пусть дано произвольное сечение упорядоченного множества М = А ∪ В и А ∩ В =Æ и А, В ¹Æ, и для любых элементов аА и bВ следует, что а <b. Тогда существует элемент хМ такой, что a £ х и х £ b для любых элементов аА и bВ.

Например, свойство полноты по отношению £ имеется в каждом из множеств: ℕ, ℤ, ℝ. Но его нет в ℚ, т.к. имеется сечение ℚ на классы: А ={ x Îℚ: x £0 или х ²<2 } и B =ℚ A, где в А нет верхней грани, а в В нет нижней грани. Однако, если присоединить к В вещественное число Ö `2, то в А появится верхняя грань.

Центральной теоремой об упорядоченных множествах считается теорема Цермело (1904г.). Согласно этой теореме всякое множество можно вполне упорядочить. Эта теорема является следствием так называемой «аксиомы выбора», которая также была сформулирована Цермело (нем. матем. 1871–1953). Суть аксиомы заключается в следующем: если дано бесконечное множество бесконечных множеств, то из каждого множества можно выбрать по одному элементу, не указывая заранее закона выбора. Важность вполне упорядоченных множеств состоит в возможности применения метода индукции в случае любых вполне упорядоченных множеств.

Дата добавления: 2014-01-14