Отношения строгого и нестрогого порядка

Определение. Отношения R на множестве X называется отношением строгого порядка, если оно транзитивно и асимметрично.

Кроме отношений «x > y» или «x < y» отношения строгого порядка являются такие, как « следует за » (или предшествует ), «выше», «длиннее», «короче» и др.

Определение. Отношение R на множестве X называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно.

Помимо отношений «x y», «x y» к этому типу отношений принадлежат такие, как: «не выше», «не длиннее», «быть делителем на множестве N» и др.

Множество X с заданным на нём отношением порядка (строгого или нестрогого) называется упорядоченным множеством. Множество N натуральных чисел можно упорядочить с помощью отношения «меньше» и с помощью отношения «кратно», однако одно из них отношения строгого порядка, а второе – нестрогого. Графы нестрогих отношений «быть кратным» и «x y» отличаются друг от друга. На рис. 4.21 показаны графы отношений «число x кратно числу y» и «x y» на множестве

«x y» «x y»

Рис.4.21

Как видно из рисунка, граф отношений «x y» несвязный в отличие от графа «x y». Про такие отношения, как «x y» (связный граф) говорят, что оно линейно упорядочивает множество X и называется отношениями линейного порядка.

Поиск по сайту: