Упорядоченные множества

Множество может оказаться упорядоченным (говорят также полностью упорядоченным) некоторым отношением порядка, другое же неупорядоченным или частично упорядоченным таким отношением.

Определение. Множество X называют упорядоченным некоторым отношением порядка R, если для любых двух элементов х, у из Х:

(х, у) Î R или (у, х) Î R.

Если R – отношение строгого порядка, то множество Х упорядочено этим отношением при условии: если х, у любые два неравных элемента множества Х, то (х, у) Î R или (у, х) Î R, или любые два элемента х, у множества Х равны.

Из школьного курса математики известно, что числовые множества N, Z, Q, R упорядочены отношением «меньше» (<).

Множество подмножеств некоторого множества не упорядочено введением отношения включения (Í), или строгого включения (Ì) в указанном выше смысле, т.к. существуют подмножества ни одно из которых не включается в другое. В этом случае говорят, что данное множество частично упорядочено отношением Í (или Ì).

Рассмотрим множество X = {1, 2, 3, 4, 5, 6} и в нем два отношения «меньше» и «делится на». Легко проверить, что оба эти отношения являются отношениями порядка. Граф отношения «меньше» можно изобразить в виде луча.

1 2 3 4 5 6

Граф отношения «делится на» можно изобразить лишь на плоскости.

Кроме того, на графе второго отношения есть вершины, не соединенные стрелкой. Например, нет стрелки, соединяющей числа 4 и 5 (рис. 10).

Первое отношение «х < у» называется линейным. Вообще, если отношение порядка R (строгого и нестрогого) на множестве X обладает свойством: для любых х, у Î Х либо хRy, либо yRx, то его называют отношением линейного порядка, а множество X – линейно упорядоченным множеством.

Если множество X конечно, и состоит из n элементов, то линейное упорядочивание Х сводится к нумерации его элементов числами 1,2,3,..., n.

Линейно упорядоченные множества обладают рядом свойств:

1°. Пусть а, в, с – элементы множества X, упорядоченного отношением R. Если известно, что aRв и вRс, то говорят, что элемент в лежит между элементами а и с.

2°. Множество X, линейно упорядоченное отношением R, называется дискретным, если между любыми двумя его элементами лежит лишь конечное множество элементов этого множества.

3°. Линейно упорядоченное множество называется плотным, если для любых двух различных элементов этого множества существует элемент множества, лежащий между ними.

Дата добавления: 2015-07-18