Спирина, М.С. Дискретная математика

полного На множестве М задано отношение частичного порядка, если сравнимы все не все элементы этого множества. Множество Л/, на котором установлено отношение частичного полного порядка, называет­ ся ------------- упорядоченным. вполне Отношение нестрогого порядка должно удовлетворять трем ус­ ловиям: • рефлективности, т.е. xRx\ • антисимметричности, т.е. если xRy и yRx, то х =у\ • транзитивности, т.е. если xRy, a yRz, то xRz. Отношение нестрогого порядка является объединением отно­ шения строгого порядка и отношения тождественности. Каждому отношению порядка R на множестве М можно поставить в соот­ ветствие обратное отношение порядка Например, отношения «больше» и «меньше» на множестве действительных чисел. Для связного отношения порядка R на множестве М существует ему противоположное R, причем, если R — отношение нестрогого порядка, то R — отношение строгого порядка, и наоборот. Во множестве R отношение нестрогого порядка < противоположно отношению строгого порядка >. Отношение порядка дает возможность сравнивать между собой различные элементы множества М. Пусть М — упорядоченное множество с отношением строгого порядка <. Об упорядоченной паре х < у говорят, что элемент х предшествует элементу у. Пусть М — вполне упорядоченное множество. Тогда, если для элемента х не нашлось предшествующего, то он называется минимальным: т.е. не существует элементов у, «меньших», чем х. Символически это записывается так: 3 у G М у < х и у ^ х На множестве N натуральных чисел выполняются лишь свой­ ства антисимметричности и транзитивности. Поэтому на нем ус­ тановлено отношение полного порядка: для любой пары нату­ ральных чисел единица является предшествующим числом, т.е. минимальным. Можно доказать, что конечное вполне упорядо­ ченное множество содержит единственный минимальный элемент. Например, на множествах чисел Z, Q, R отношения < и > есть отношения нестрогого полного порядка, а отношения < и > есть отношения строгого полного порядка. Отношение с есть отноше­ ние нестрогого частичного порядка на множестве 2м (булеан). Всякий частичный порядок на конечном множестве может быть доведен до полного. То есть существует такое отношение полного порядка, для которого заданное отношение частичного порядка является подмножеством. 44