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

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

Для обозначения отношения упорядоченности обычно используют знаки  (или ),  (или ). При этом 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) Множество натуральных чисел линейно упорядочено отношением .

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

Пусть А  М и М – упорядоченное множество. Элемент хМ называется верхней (нижней) границей множества А, если для  аА => а ≤ х ( х ≤ а ). Множество А в этом случае называется ограниченным сверху (снизу). Естественно, что А может иметь не одну верхнюю (нижнюю) границу, а множество верхних (нижних) границ. Тогда наименьшая из верхних границ А называется верхней гранью множества А и обозначается sup(А) – супремум. Аналогично, наибольшая из нижних границ множества А называется нижней гранью А и обозначается inf(А) – инфимум. (Иначе говоря, верхняя грань А есть нижняя граница множества всех верхних границ А, а нижняя грань А есть верхняя граница множества всех нижних границ А.)

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

Примеры:

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). Суть аксиомы заключается в следующем: если дано бесконечное множество бесконечных множеств, то из каждого множества можно выбрать по одному элементу, не указывая заранее закона выбора. Важность вполне упорядоченных множеств состоит в возможности применения метода индукции в случае любых вполне упорядоченных множеств.