Лексикографический порядок. Порядок по Парето
Основные определения
Определение 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!