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

При данном отношении справедливы аксиомы: 1) рефлексивности, 2) антисимметричности; 3) транзитивности.

Отношение нестрогого порядка задает некоторый способ сравнения элементов на рассматриваемом множестве таким образом, что для каждого его элемента х пара (х, х)также принадлежит отношению. Данные отношения обычно обозначают символом £, так как на числовых множествах нестрогий порядок может быть задан предикатом «х меньше или равен у». Если х £ у, то говорят, что х подчинен у либо х не превосходит у.

Определение. Множества, на которых введено отношение нестрогого (частичного) порядка, называют частично упорядоченными. Частичный порядок на X называется линейным, если все пары элементов из X сравнимы, т.е. для любых х, уÎ X можно выяснить (х £ у) либо(у £ х).

Пусть Х — частично упорядоченное множество. Наименьшим называют элемент аÎХ, который подчинен (не превосходит) всех остальных элементов X, т.е."хÎ X (х £ а). Наибольшим называют элемент аÎХ, которому подчинены все остальные элементы из X — "хÎ X (х £ а).Обозначаются наименьший и наибольший элементы как minХ и mахХ.

У линейно упорядоченного множества любое подмножество также является линейно упорядоченным.

Пример 4. Рассмотрим в качестве исходного множество натуральных чисел N. Зададим на нем два варианта отношения нестрогого порядка с помощью предикатов:

1) Р(х, у) = «х £ у» ,

2) Р(х, у)= «х делится без остатка на у».

Оба отношения удовлетворяют аксиомам рефлексивности, антисимметричности и транзитивности.

Первое отношение задает на N линейный порядок, поскольку оно определено для всех пар натуральных чисел. Наименьший элемент minХ= 1, наибольшего не существует.

Второе отношение не обеспечивает на N линейный порядок, поскольку существуют пары несравнимых натуральных чисел. Например, (2, 3), (4, 5) и т.д. Наименьшего и наибольшего элементов нет.








Дата добавления: 2015-10-05; просмотров: 1068; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


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

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2021 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.014 сек.