Лексикографический порядок. Порядок по Парето
Основные определения
Определение 1.1. Пусть A – некоторое множество. Рассмотрим декартово произведение 
и некоторое его подмножество 
. Тогда 
называется бинарным отношением на множестве A.
Говорят, что элемент 
находится в отношении с элементом 
, если упорядоченная пара 
. Этот факт также записывают в виде 
.
Примеры. 1) Пусть 
. Определим бинарное отношение на множестве R следующим образом: 
, 
.
2) Пусть A – множество студентов потока, тогда – множество упорядоченных пар студентов. Рассмотрим , определяемое следующим образом: 
студенты x и y учатся в одной группе.
Рассмотрим ряд определений, связанных с понятием бинарного отношения.
Определение 1.2. Пусть , 
, т. е. отношение не выполняется ни для одной пары элементов множества A . Тогда отношение называется пустым .
Пример. Пусть 
, тогда 
. Рассмотрим отношение 
. Очевидно, что .
Определение 1.3. Пусть 
. Тогда отношение 
называется полным.
Определение 1.4. Пусть . Рассмотрим бинарное отношение 
. Бинарное отношение 
называется дополнительным к бинарному отношению .
Пример. Рассмотрим предыдущий пример, где A – множество студентов потока и бинарное отношение определяется так: студенты x и y учатся в одной группе. Тогда 
студенты x и y учатся в разных группах.
Определение 1.5. Пусть . Рассмотрим бинарное отношение 
, определяемое следующим образом: 
. Бинарное отношение 
называется противоположным бинарному отношению .
|
|
|
Примеры. 1) Пусть . Пусть , . Тогда 
.
2) Пусть A – множество студентов потока и бинарное отношение определяется так: студенты x и y учатся в одной группе. Тогда, очевидно, 
.
Свойства бинарных отношений. Отношение эквивалентности. Отношения порядка
Рассмотрим бинарное отношение на множестве A .
1. Рефлексивность. Бинарное отношение называется рефлексивным, если выполняется 
, для всех .
2. Симметричность. Бинарное отношение называется симметричным, если 
, для всех 
.
3. Транзитивность.Бинарное отношение называется транзитивным,
если 
, для всех 
.
Примеры. 1) Пусть . Рассмотрим бинарное отношение на множестве R, определяемое следующим образом: 
. Тогда обладает свойством рефлексивности, поскольку 
для всех 
. Бинарное отношение не обладает свойством симметричности, поскольку из неравенства 
не следует неравенство 
. Бинарное отношение обладает свойством транзитивности, поскольку из неравенств 
следует 
.
2) Пусть A – множество всех людей на Земле. Рассмотрим бинарное отношение на множестве A, определяемое следующим образом: человек x является братом или сестрой человека y (т. е . x и y имеют хотя бы одного общего родителя). Тогда , очевидно, рефлексивно, симметрично, но не транзитивно.
|
|
|
Определение 2.1. Бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности называется отношением эквивалентности.
Примеры. 1) Пусть . Рассмотрим бинарное отношение на множестве R, определяемое следующим образом: 
. Тогда является отношением эквивалентности. Действительно, рефлексивно, поскольку 
для всех . Бинарное отношение , очевидно, также симметрично и транзитивно.
2) Пусть A – множество студентов потока. Рассмотрим бинарное отношение 
на множестве A, определяемое следующим образом: студенты x и y учатся в одной группе. Тогда является отношением эквивалентности. Действительно, рефлексивность означает, что каждый студент учится сам с собой в одной группе. Симметричность означает, что если студент x учится в одной группе со студентом y, то и студент y учится в одной группе со студентом x. Транзитивность означает, что если студент x учится в одной группе со студентом y, а студент y учится в одной группе со студентом z, то студент x учится в одной группе со студентом z.
Отношение эквивалентности часто обозначают знаком 
.
Определение 2.2. Рассмотрим множество A и – отношение эквивалентности на множестве A . Пусть 
– подмножество множества A, определяемое следующим образом: 
. Тогда множество называется классом эквивалентности элемента x, порожденным отношением эквивалентности .
|
|
|
Свойства классов эквивалентности
1. Классы эквивалентности элементов множества не пусты. Действительно, класс эквивалентности множества x содержит элемент x: 
.
2. Пусть 
. Тогда 
.
Доказательство. Пусть 
. Это значит, что 
. Но , значит 
. Из транзитивности отношения следует, что 
. Значит, 
. Следовательно, 
.
Пусть теперь . Это значит, что . Поскольку , имеем . Из симметричности отношения следует, что 
, а тогда по транзитивности отношения получим, что . Это значит, что . Следовательно, 
.
Если и , то 
.
3. Если 
, то 
.
Доказательство. Предположим, что утверждение неверно. Это значит, что найдется 
, принадлежащий как классу эквивалентности , так и классу эквивалентности 
. Тогда и . Из симметричности и транзитивности отношения следует, что . Тогда по свойству 2 , что противоречит условию. Полученное противоречие доказывает справедливость утверждения.
Определение 2.3. Рассмотрим множество A . Пусть 
, 
. Множество 
называется разбиением множества A, если оно удовлетворяет условиям:
|
|
|
1) 
,
2) 
, при 
.
Примеры. 1) Множества четных чисел и нечетных чисел составляют разбиение множества целых чисел.
2) Множество всех людей живущих на Земле можно представить в виде разбиения на подмножества, состоящих из людей определенного года рождения.
Теорема 2.1. Классы эквивалентности множества A составляют разбиение множества A .
Доказательство. Рассмотрим множество 
– классов эквивалентности множества A, порожденных некоторым отношением эквивалентности. Докажем, что множество является разбиением множества A .
1) Докажем, что . Пусть 
и 
, . Очевидно, что , , следовательно, 
.
Пусть . Тогда найдется такой класс эквивалентности (ошибка - нужно убрать индекс у мал. а), что
. Значит, 
, и тогда 
.
Если и , то .
2) Условие при следует из свойства 3 классов эквивалентности. Теорема доказана.
Определение 2.4. Рассмотрим множество A и 
– отношение эквивалентности на A. Пусть 
– классы эквивалентности, порожденные отношением 
. Множество называется фактор-множеством множества A по отношению эквивалентности , и обозначается A│~.
Примеры. 1) Пусть A – множество студентов потока. Рассмотрим бинарное отношение на множестве A, определяемое следующим образом: студенты x и y учатся в одной группе. Тогда, как было установлено выше, отношение является отношением эквивалентности. При этом элементами фактор-множества A│Δ, порожденного отношением , являются группы данного потока.
2) Рассмотрим множество целых чисел Z и введем на этом множестве бинарное отношение : разность 
является четным числом. Отношение , очевидно, является отношением эквивалентности. Фактор-множество Z│Δ состоит из двух элементов – множества четных чисел и множества нечетных чисел.
Продолжим изучение свойств бинарных отношений.
4. Бинарное отношение на множестве A называется антисимметричным, если из условия 
следует, что 
.
Пример. Пусть . Рассмотрим бинарное отношение на множестве R, определяемое следующим образом: . Тогда бинарное отношение антисимметрично. Действительно, 
.
5. Бинарное отношение на множестве A называется асимметричным, если из условия следует, что 
, т. е. 
– неверно.
Пример. Пусть . Рассмотрим бинарное отношение на множестве 
, определяемое следующим образом: . Тогда бинарное отношение aсимметрично. Действительно, если 
, то, очевидно, что 
– неверно.
6. Бинарное отношение на множестве A называется антирефлексивным, если не существует такого элемента , что .
Пример. В предыдущем примере бинарное отношение , очевидно, антирефлексивно.
Определение 2.5. Бинарное отношение, обладающее свойствами рефлексивности, антисимметричности и транзитивности называется отношением нестрогого порядка.
Примеры. 1) Пусть . Рассмотрим бинарное отношение на множестве , определяемое следующим образом: . Тогда, очевидно, бинарное отношение является отношением нестрогого порядка.
2) Пусть A – множество всех подмножеств множества 
. Введем бинарное отношение на множестве A: 
. Докажем, что – отношение нестрогого порядка. Действительно, для любого множества X справедливо 
, следовательно, бинарное отношение рефлексивно. Если 
, то, 
, следовательно, бинарное отношение антисимметрично. И, наконец, если 
и 
, то, очевидно, 
, следовательно, бинарное отношение транзитивно.
Определение 2.6. Бинарное отношение, обладающее свойствами антирефлексивности и транзитивности называется отношением строгого порядка.
Примеры. 1) Пусть . Рассмотрим бинарное отношение на множестве : . Тогда, очевидно, бинарное отношение является отношением строгого порядка.
2) Пусть A – множество всех людей на Земле. Определим бинарное отношение на множестве A : человек x является потомком человека y. Тогда бинарное отношение является отношением строгого порядка. Действительно, никакой человек не может быть собственным потомком, это означает, что бинарное отношение антирефлексивно. Если человек x является потомком человека y, а человек y является потомком человека z, то x является также потомком z. Это означает, что бинарное отношение транзитивно.
Замечание. Отношение строгого порядка обладает свойством асимметричности. Докажем это утверждение. Рассмотрим множество A и отношение строгого порядка на этом множестве. Предположим, что не обладает свойством асимметричности. Это означает, что в множестве A найдутся такие элементы x и y, что 
и 
. Тогда по транзитивности получим, что 
, а это противоречит антирефлексивности . Полученное противоречие доказывает, что сделанное предположение неверно, следовательно, асимметрично.
Определение 2. 7. Множество, на котором задано отношение порядка (строгого или нестрогого) называется частично упорядоченным.
В частично упорядоченном множестве могут существовать пары элементов, не связанные отношением порядка.
Примеры. 1) Пусть 
. Введем на множестве 
бинарное отношение : 
. Тогда – отношение нестрогого порядка на . Следовательно, множество является частично упорядоченным. При этом в множестве имеются элементы, не находящиеся в отношении , например, 
и 
.
2) Пусть A – множество всех подмножеств множества . Введем бинарное отношение на множестве A: . Выше было доказано, что – отношение нестрогого порядка. Таким образом, множество A частично упорядочено. Очевидно, что в множестве A содержатся подмножества, не находящиеся в отношении .
Определение 2.8. Множество A называется совершенно упорядоченным (или линейно упорядоченным), если на нем задано отношение порядка, причем любые два элемента этого множества связаны этим отношением.
Примеры. 1) Множестводействительных чисел R с введенным на нем отношением нестрогого порядка : является, очевидно, совершенно упорядоченным.
2) Рассмотрим конечное множество 
, состоящее из различных элементов. На множестве A всегда можно ввести такое отношение порядка, что множество A будет совершенно упорядоченным. Например, если 
, то с бинарным отношением 
, являющимся строгом порядком, множество A будет совершенно упорядоченным.
Лексикографический порядок. Порядок по Парето
Рассмотрим два специальных вида отношений порядка, имеющие большое прикладное значение: лексикографический порядок и порядок по Парето.
Лексикографический порядок
Определение 3.1. Пусть A – множество с введенным на нем отношением строгого порядка . Рассмотрим множество S – подмножество n-кратного декартова произведения множества A на себя: 
. Введем на множестве S отношение порядка p L следующим образом:
пусть 
, тогда 
и 
.
Положим a p L b 
.
Тогда бинарное отношение p L на множестве S называется лексикографическим порядком.
Если a p L b , то говорят, что a лексикографически предшествует b , а b лексикографически следует за a.
Замечание. Из определения следует, что лексикографический порядок на множестве S основан на отношении строгого порядка на множестве A .
Лексикографический порядок является строгим, это следует из того, что бинарное отношение – строгий порядок. При этом множество S , очевидно, совершенно упорядочено.
Примеры. 1) Пусть 
– множество цифр. Введем на множестве A отношение строгого порядка естественным образом: одна цифра предшествует другой, если соответствующее ей число меньше числа, соответствующего другой цифре. Положим 
. Тогда все числа от 0 до 999 можно представить в виде элементов множества 
, считая, что двузначные числа начинаются с цифры 0, а однозначные с двух нулей. Тогда естественный порядок трехзначных чисел соответствует лексикографическому порядку на множестве S.
2) Пусть A – множество букв алфавита английского языка с добавлением буквы “пробел”, предшествующей букве А. Рассмотрим множество английских слов в некотором англо-русском словаре. Пусть n – длина самого длинного английского слова в словаре. Дополним каждое слово длины меньшей, чем n, пробелами в начале слова, так, чтобы длина слова стала равна n . Пусть S – множество английских слов в словаре с учетом их дополнений пробелами. Тогда все элементы множества S расположены в лексикографическом порядке, основанном на порядке букв в алфавите.
Порядок по Парето
Определение 3.2. Введем на множестве 
бинарное отношение следующим образом: пусть 
, тогда и . Положим a pP b 
. Тогда бинарное отношение pP на множестве называется порядком по Парето. Если ap P b , то говорят, что a предшествует b по Парето, а b следует за a по Парето.
Очевидно, что порядок по Парето строгий. При этом множество не является совершенно упорядоченным. Действительно, существуют точки в не сравнимые между собой по Парето. Например, при точки 
и 
не сравнимы по Парето.
Дата добавления: 2021-03-18; просмотров: 347; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!