Отношение частичного порядка. Свойства отношений на множестве. Отношения строгого порядка

Свойства отношений:

1) рефлексивность;

2)симметричность;

3)транзитивность.

4)связанность.

Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: х Rх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.

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

Существуют отношения, не обладающие свойством рефлексивности, например, отношение перпендикулярности отрезков: ab, ba (нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе). Поэтому на графе данного отношения нет ни одной петли.

Не обладает свойством рефлексивности и отношение «длиннее» для отрезков, «больше на 2» для натуральных чисел и др.

Отношение R на множестве Х называется антирефлексивным , если для любого элемента из множества Х всегда ложно х Rх: .

Существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Примером такого отношения может служить отношение «точка х симметрична точке у относительно прямой l », заданное на множестве точек плоскости. Действительно, все точки прямой l симметричны сами себе, а точки, не лежащие на прямой l, себе не симметричны.

Отношение R на множестве Х называется симметричным , если выполняется условие: из того, что элемент х находится в отношении с элементом y , следует, что и элемент y находится в отношении R с элементом х: xRyyRx .

Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y , граф содержит стрелку, идущую от y к х (рис. 35).

Примерами симметричных отношений могут быть следующие: отношение «параллельности» отрезков, отношение «перпендикулярности» отрезков, отношение «равенства» отрезков, отношение подобия треугольников, отношение «равенства» дробей и др.

Существуют отношения, которые не обладают свойством симметричности.

Действительно, если отрезок х длиннее отрезка у , то отрезок у не может быть длиннее отрезка х . Граф этого отношения обладает особенностью: стрелка, соединяющая вершины, направлена только в одну сторону.

Отношение R называют антисимметричным , если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.

Кроме отношения «длиннее» на множестве отрезков существуют и другие антисимметричные отношения. Например, отношение «больше» для чисел (если х больше у , то у не может быть больше х ), отношение «больше на» и др.

Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.

Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z , следует, что элемент х находится в отношении R с элементом z : xRy и yRz xRz.

Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z , содержит стрелку, идущую от х к z.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b , отрезок b длиннее отрезка с , то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а= b, b=с)(а=с).

Существуют отношения, которые не обладают свойством транзитивности. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b , а отрезок b перпендикулярен отрезку с , то отрезки а и с не перпендикулярны!

Существует еще одно свойство отношений, которое называется свойством связанности, а отношение, обладающее им, называют связанным.

Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y , либо элемент y находится в отношении R с элементом х . С помощью символов это можно записать так: xy xRy или yRx.

Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y , либо y>x.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y , что ни число х не является делителем числа y , ни число y не является делителем числа х (числа 17 и 11 , 3 и 10 и т.д.).

Рассмотрим несколько примеров. На множестве Х={1, 2, 4, 8, 12} задано отношение «число х кратно числу y ». Построим граф данного отношения и сформулируем его свойства.

Про отношение равенства дробей говорят, оно является отношением эквивалентности.

Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойством рефлексивности, симметричности и транзитивности.

Примерами отношений эквивалентности могут служить: отношения равенства геометрических фигур, отношение параллельности прямых (при условии, что совпадающие прямые считаются параллельными).

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {; }, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х , т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества - классы эквивалентности.

Так, мы установили, что отношению равенства на множестве
Х ={ ;; ; ; ; } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?

Во-первых, эквивалентный - это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {; ; }, неразличимы с точки зрения отношения равенства, и дробь может быть заменена другой, например . И эта замена не изменит результата вычислений.

Во-вторых, поскольку в классе эквивалентности оказываются элементы, неразличимые с точки зрения некоторого отношения, то считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. класса эквивалентности по одному представителю позволяет вместо всех элементов множества изучать совокупность представителей из классов эквивалентности. Например, отношение эквивалентности «иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольников и т.д. свойства, присущие некоторому классу, рассматриваются на одном его представителе.

В-третьих, разбиение множества на классы с помощью отношения эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то общее, что имеют параллельные прямые между собой.

Другим важным видом отношений являются отношения порядка. Рассмотрим задачу.На множестве Х ={3, 4, 5, 6, 7, 8, 9, 10 } задано отношение «иметь один и тот же остаток при делении на 3 ». Это отношение порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9 ). Во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 4, 7, 10 ). В третий попадут все числа, при делении которых на 3 в остатке получается 2 (это числа 5, 8 ). Действительно, полученные множества не пересекаются и их объединение совпадает с множеством Х . Следовательно, отношение «иметь один и тот же остаток при делении на 3 », заданное на множестве Х , является отношением эквивалентности.

Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».

Отношение R на множестве Х называется отношением строгого порядка , если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х< y ».

Если же отношение обладает свойствами рефлексивности, антисимметричности и транзитивности, то такое оно будет являться отношением нестрогого порядка . Например, отношение «х y ».

Примерами отношения порядка могут служить: отношение «меньше» на множестве натуральных чисел, отношение «короче» на множестве отрезков. Если отношение порядка обладает еще и свойством связанности, то говорят, что оно является отношением линейного порядка . Например, отношение «меньше» на множестве натуральных чисел.

Множество Х называется упорядоченным, если на нем задано отношение порядка.

Например, множество Х= {2, 8, 12, 32 } можно упорядочить при помощи отношения «меньше» (рис. 41), а можно это сделать при помощи отношения «кратно» (рис. 42). Но, являясь отношением порядка, отношения «меньше» и «кратно» упорядочивают множество натуральных чисел по-разному. Отношение «меньше» позволяет сравнивать два любых числа из множества Х , а отношение «кратно» таким свойством не обладает. Так, пара чисел 8 и 12 отношением «кратно» не связана: нельзя сказать, что 8 кратно 12 либо 12 кратно 8.

Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.

2) отношение на множестве Х называется отношением строго порядка , если оно антисимметрично и транзитивно. Отношение называется антисимметричным , если из того, что а находится в отношении с в не следует, что в находится в отношении с а (а, в ∈ Х, а R в → в R а) R – находиться в отношении. Отношение называется транзитивным , если для любых элементов а, в, с из того, что а R в и в R с → что а R с, а, в, с ∈ Х. Например: отношение «больше, меньше». Множество, на котором задано отношение строгого порядка, называется упорядоченным множеством.

3) отношение на множестве Х называется отношением не строгого порядка , если оно рефлексивно, ассиметрично и транзитивно. Например: отношение ≥ ≤. Если отношение порядка обладает свойством связности, то говорят, что оно является отношением линейного порядка . Отношение называется связанным на множестве Х, если для любых элементов х и у выполняется условие: из того, что х ≠ у следует, что х R у или у R х. Если на множестве задано отношение линейного порядка, то оно линейно упорядочивает данное множество.

5. Множество действительных чисел. Его свойства . К расширению множества рациональных чисел привела необходимость измерения длин отрезков, площадей и т.д. В основе любого измерения лежит один и тот же принцип: измеряемый объект сравнивается с эталоном (предметом или явлением), величина которого имеет численное значение, равное 1, но не всегда единичный отрезок вкладывается в измеряемом объекте. Поэтому при измерении делают 2 допущения, которые в математике определились как аксиомы: 1) Единичный эталон можно разделить на любое число равных между собой долей или частей. 2) Выбранным эталоном можно измерять любой как угодно большой объект. Для отрезков эти аксиомы сформулировал Архимед: Как бы ни был мал отрезок АВ и как бы ни был велик отрезок СД, существует такое натуральное число N, что N*AB>CD, если в измеряемом отрезке CD уложилось равное число отрезков АВ, то длина отрезка CD выражается натуральным числом. Если в измеряемом отрезке CD отрезок АВ укладывается неравное число раз, то АВ разбиваем на 10 одинаковых отрезков, называемых десятой долей эталонов. При необходимости десятая доля может разбиваться на 10 равных частей и т.д. Если в отрезок CD укладывается равное число 10, 100 и т.д. долей отрезков АВ, то длина отрезка CD выражается рациональным числом. Однако не всегда длина отрезка может выражаться натуральным или рациональным числом. Существуют несоизмеримые отрезки, т.е. отрезки, длина которых не выражается рациональным числом. (теоремы смотри вопрос 32)

Числа, которые могут быть представлены в виде бесконечных десятичных непериодических дробей называется иррациональными. Объединение множества рациональных чисел и множества иррациональных чисел есть множество действительных чисел ().

Свойства множества действительных чисел . 1). Множество точек числовой оси равномощно множеству действительных чисел.

0 М 1 Возьмем на отрезке от 0 до 1 любую точку М,

Д проведем полуокружность с центром в

Середине этого отрезка и радиусом

К О С равным половине его. Проведем перпендикуляр из М до пересечения с полукругом. Получим Д. Эта точка единственная, так как полукруг и прямая пересекаются только в одной точке. Из середины данного отрезка через Д проведем прямую до пересечения с числовой осью. Получим К, которая определяется единственным образом, так как де прямые пересекаются только в одной точке. Выбирая другую произвольную точку на заданном отрезке и повторяя весь процесс получим, что любой точке отрезка от0 до 1 соответствует единственная точка числовой прямой. Рассуждая в обратном порядке можно показать, что любой точке числовой прямой также соответствует единственная точка от 0 до 1. Если произвольная точка Е принадлежит числовой прямой, то через точки М и Е можно провести только одну прямую, которая пересечет полуокружность. Из полуокружности можно опустить перпендикуляр на заданный отрезок. Таким образом, между точками отрезка от 0 до 1 и точками числовой прямой устанавливается взаимно одинаковое отображение, т.е. они равномощны.

2) множество действительных чисел не является счетным, т.е. оно не равно множеству натуральных чисел.

3). Множество действительных чисел является непрерывным множеством. Непрерывность множества действительных чисел состоит в том, что между любыми двумя действительными числами находится бесконечное множество только действительных чисел

6. Разбиение множества на классы. Примеры классификации. Отношение эквивалентности, его свойства. Взаимосвязь отношения эквивалентности с разбиением множества на классы. Рассмотрим на примере. Пусть задано множество М (множество выпуклых многоугольников), образуем все подмножества данного множества: А 1 – множество треугольников; А2 – множество четырехугольников; А3 – множество пятиугольников; Ак – множество к-угольников. Множество М считается разбитым на классы, если выполняются следующие условия:

1. каждое подмножество А не пусто
2. пересечения любых двух подмножеств является пустым множеством
3. объединение всех подмножеств есть данное множество М

Разбиение множества на классы называется классификацией .

Отношение на множестве Х называется эквивалентным , если оно рефлексивно, симметрично и транзитивно. Отношение называется рефлексивным , если любой элемент из множества Х находится в отношении сам с собой а ∈ Х, а R а (R – находиться в отношении). Отношение называется симметричным , если для любых двух элементов множества Х (а и в) из того, что а находится в отношении с в, будет следовать, что в находится в отношении с а (а, в ∈ Х, а R в → в R а). Отношение называется транзитивным , если для любых элементов а, в, с из того, что а R в и в R с → что а R с, а, в, с ∈ Х. На графе отношения эквивалентности есть петли, взаимно обратные стрелки и треугольные стрелки. Отношение эквивалентности, и только оно, связано с разбиением множества на классы. Это утверждение можно сформулировать в виде теоремы : Если на множестве Х задано отношение эквивалентности, то это отношение разбивает множество Х на классы, и наоборот, если множество Х разбито на классы, то на заданном множестве выполняется отношение эквивалентности. Например. Пусть задано отношение – жить в одном доме. Покажем, что множество жильцов в доме будет разбито на классы. А каждый класс, это отдельная квартира. Для данного разделения будут выполняться все необходимые условия разбиения множества на классы: а) каждый класс не пуст, т.к. в каждой квартире хотя бы 1 человек, но прописан, б) классы не пересекаются (1 человек не прописан в двух разных квартирах), в) объединение всех классов, т.е. жильцов каждой квартиры, и составляет множество жильцов дома.

18 . Теоретико-множественный подход к построению теории целых неотрицательных чисел. Отношения равенства, больше (меньше). Два множества А и В называются эквивалентными или равномощными, если между ними можно установить взаимнооднозначное соответствие, т.е., если каждому элементу множества А ставится в соответствие единственный элемент множества В и наоборот. Мощность или кардинальное число – это такое свойство, которое присуще любому множеству В, равномощному множеству А и не присуще ни какому другому множеству не равномощному множеству А. А~В n (А)=а – это мощность. Отношение равномощности является отношением эквивалентности, т.е. для него выполняются свойства рефлексивности, симметричности и транзитивности. Отношение равномощности разбивает множество всех множеств на классы эквивалентности. Для определения понятия натурального числа и нуля рассмотрим разбиение всех конечных множеств.

Пусть М это множество всех конечных множеств. М=К 0 Ка Кв, где Ко – это класс пустых множеств, Ка – это множество, содержащее равномощные множества а 1, а 2 , а 3 и т.д., Кв – это множество. Содержащее равномощные множества в 1 , в 2 , в 3 и т.д. Множество М может содержать и другие подмножества К различной природы, которые состоят из равномощных множеств. У каждого класса эквивалентности К есть общее то, что они состоят из одинакового количества элементов, других общих свойств нет. Целое неотрицательное число с теоретико-множественной точки зрения, есть общее свойство класса конечных равномощных множеств. Натуральное число есть общее свойство класса не пустых конечных равномощных множеств. Каждому классу приписывается кардинальное число (мощность). Классу пустое множество приписывается координальное число 0. Классу состоящему из множеств, имеющих 1 элемент приписывается число1. Классу, состоящему из множеств, имеющих 2 элемента приписывается число 2. (n(К 0)=0, n(К 1)=1, n(К 2)=2, n(Ка)=а).

Отношение равенства . Целые неотрицательные числа а и в называются равными, если множества А и В, численность которых они выражают, равномощны (А; n(А)=а, n(В)=в, А ~ В n(А)=n(В) а=в).

Теорема : отношение равенства во множестве целых неотрицательных чисел является отношением эквивалентности. Доказательство . Докажем, что отношение равенства обладает свойствами симметричности, транзитивности и рефлексивности.

Т.к. свойства рефлексивности, симметричности, транзитивности выполняются, то отношение равенства является отношением эквивалентности.

Отношение меньше . Целое неотрицательное число а<в, если множество А равномощно собственному подмножеству В 1 множества В. а<в; n(А)=а; n(В)=в; В 1 В n(В 1)

Теорема: отношение меньше во множестве целых неотрицательных чисел является отношением строго порядка. Доказательство: Докажем, что отношение меньше обладает свойствами анти симметричности и транзитивности.

С 2 С 1 С 2 ~В 1 С 2 ~А n(А)=n(С 2) n(С 2)

А В С 1 С

В 1 С 2

19 . Сложение и вычитание в количественной теории целых неотрицательных чисел. Их свойства . Суммой двух целых неотрицательных чисел а и в называется целое неотрицательное число с, которое является мощностью объединения двух непересекающихся множеств А и В, мощности которых соответственно равны а и в. а+в=с, n(С)=n(АUВ), n(АUВ)=n(А)+n(В).

Свойства сложения . 1. Сложение во множестве целых неотрицательных чисел всегда существует и определяется единственным образом. Докажем, что сумма всегда существует. Рассмотрим А и В, такие, что их пересечение пустое множество и число элементов А есть а, а мощность В есть – в. найдем объединение А и В. Так как объединение двух непересекающихся множеств всегда существует, а значит существует и сумма, а из определения суммы следует, что сложение всегда существует.

Докажем, что сумма определяется единственным образом. Существует С 1 и С 2 – неотрицательные целые числа. С 1 =а+в и С 2 =а+в. Сумма чисел а и в не зависит от того, какие множества А и В мы выбрали из класса равномощных множеств, а следовательно и объединение А и В, взятых из класса равномощных множеств не зависит от выбора множеств А и В, т.к мощности в каждом классе одинаковы, то С 1 =С 2 .

2. Каммутотивность сложения. Для любых целых неотрицательных чисел а и в выполняется свойство а+в=в+а. Из теории множеств знаем, что для АUВ=ВUА. Если равны множества, равны их численные значения. n(АUВ)=n(ВUА). Из теории множеств знаем, что мощность объединения равна сумме мощностей. N(А)+n(В)=n(В)+n(А).

3. Свойство ассоциативности. Для любых чисел а, в, с выполняется свойство: а+(в+с)=(а+в)+с. Из теории множеств известно, что для объединения множеств выполняется свойство ассоциативности: АU(ВUС)=(АUВ)UС, если равны множества, то равны их численные значения, n(АU(ВUС))=n((АUВ)UС). Из теории множеств известно, что мощность объединения равна сумме мощностей этих множеств, n(А)+n(ВUС)=n(АUВ)+n(С) n(А)+(n(В)+n(С))=(n(А)+n(В))+n(С) а+(в+с)=(а+в)+с.

Разностью целых неотрицательных чисел а и в называется целое неотрицательное число с, которое является мощностью дополнения множества В до множества А, таких, что В принадлежит А, n(А)=а, n(В)=в.

Свойства разности . 1. Для того чтобы разность целых неотрицательных чисел существовала, необходимо и достаточно, чтобы а было больше или равно в.

Докажем : 1) достаточное условие существования разности. Дано: а - в = с, доказать: а в. По определению разности следует, что существует дополнение множества В до множества А, и это дополнение имеет мощность, которую можно найти из равенства, известного из теории множеств.

n () = n(А)-n(В). Из того, что В является подмножеством А следует, что число элементов в В меньше числа элементов А. n (В)в; В входит в А; n(В)

2). Необходимое условие. Дано а в. доказать существование разности (а-в). Если а>в, по определению отношения «меньше» существует множество А 1 , такое что А 1 входит в А и А 1 ~В. Составим разность А и А 1. Эта разность всегда существует (А- А 1 =С) , а следовательно существует С, которое является этой разностью. Из этих условий следует, что С является дополнением А 1 до А. С = 1А Мощность С есть мощность дополнения А 1 до А. n (С)=n( 1А)=n(А)-n(А 1) , так как А 1 ~ В, то n(А 1)=n(В), следовательно n(С)=n(А)-n(В), следовательно с=а-в.

2. Разность целых неотрицательных чисел находится единственным образом, так как разность есть мощность дополнения подмножеств до множества, а дополнение определяется единственным образом, то и разность целых неотрицательных чисел определяется единственным образом.

3. Для вычитания не выполняются свойства коммутативности и ассоциативности.

4. Вычитание суммы из числа. а-(в+с)=(а-в)-с. Из теории множеств известно А\(ВUС)=(А\В)\С, причем В Ì А; С Ì А; ВUСÌА.

n (А\(ВUС))=n((А\В)\С)

n(А)-n(ВUС)=n(А\В)-n(С)

n(А)-(n(В)+n(С))=(n(А)-n(В))-n(С)

а-(в+с)=(а-в)-с.

5. Вычитание числа из разности (а-в)-с=(а-с)-в. Доказательство основывается на свойстве разности множеств (А\В)\С=(А\С)\В.

6. Вычитание числа из суммы (а+в)-с=(а-с)+в. Доказательство опирается на свойство множеств (АUВ)\С=(А\С) UВ.

Отключите adBlock!
очень нужно

Отношение эквивалентности. Связь отношения эквивалентности с разбиением множества на классы

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

Пример. Рассмотрим отношение «х однокурсник у » на множестве студентов педфака. Оно обладает свойствами:

1) рефлексивности, т.к. каждый студент является однокурсником самому себе;

2) симметричности, т.к. если студент х у , то и студент у является однокурсником студента х ;

3) транзитивности, т.к. если студент х - однокурсник у , а студент у – однокурсник z , то студент х будет однокурсником студента z .

Таким образом, данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, а значит, является отношением эквивалентности. При этом множество студентов педфака можно разбить на подмножества, состоящие из студентов, обучающихся на одном курсе. Получаем 5 подмножеств.

Отношением эквивалентности являются также, например, отношение параллельности прямых, отношение равенства фигур. Каждое такое отношение связано с разбиением множества на классы.

Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).

Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х , порождает разбиение этого множества на классы, то оно является отношением эквивалентности.

Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?

Построим граф данного отношения: (самостоятельно)

Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х 1 = {3; 6}, Х 2 = {1; 4; 7}, Х 3 = {2; 5; 8}.

Считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу.

В начальном курсе математики также встречаются отношения эквивалентности, например, «выражения х и у имеют одинаковые числовые значения», «фигура х равна фигуре у ».

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

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

Примеры отношений строгого порядка: «больше» на множестве натуральных чисел, «выше» на множестве людей и др.

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

Примеры отношений нестрогого порядка: «не больше» на множестве действительных чисел, «быть делителем» на множестве натуральных чисел и др.

Определение. Множество Х называют упорядоченным, если на нем задано отношение порядка.

Пример . На множестве Х = {1; 2; 3; 4; 5} заданы два отношения: «х £ у » и «х – делитель у ».

Оба эти отношения обладают свойствами рефлексивности, антисимметричности и транзитивности (постройте графы и проверьте свойства самостоятельно), т.е. являются отношением нестрогого порядка. Но первое отношение обладает свойством связности, а второе – нет.

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

В начальной школе изучаются многие отношения порядка. Уже в первом классе водятся отношение «меньше», «больше» на множестве натуральных чисел, «короче», «длиннее» на множестве отрезков и др.

Контрольные вопросы

1. Дайте определение бинарного отношения на множестве Х .

2. Как записать утверждение о том, что элементы х и у находятся в отношении R ?

3. Перечислите способы задания отношений.

4. Сформулируйте свойства, которыми могут обладать отношения. Как данные свойства отражаются на графе?

5. Какими свойствами должно обладать отношение, чтобы оно являлось отношением эквивалентности?

6. Как отношение эквивалентности связано с разбиением множества на классы?

7. Какими свойствами должно обладать отношение, чтобы оно являлось отношением порядка?

Слово «порядок» часто применяют в самых различных вопросах. Офицер дает команду: «По порядку номеров рассчитайся», арифметические действия выполняются в определенном порядке, спортсмены становятся по росту, существует порядок выполнения операций при изготовлении детали, порядок слов в предложении.

Что же общего во всех случаях, когда говорится о порядке? В том, что в слово «порядок» вкладывается такой смысл: оно означает, какой элемент того или иного множества за каким следует (или какой элемент какому предшествует).

Отношение «х следует за у » транзитивно: если «х следует за у » и «у следует за z », то «x следует за z ». Кроме того, это отношение должно быть антисимметричным: для двух различных х и у , если х следует за у , то у не следует за х .

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

Выясним особенности графа и графика отношений строгого порядка.

Рассмотрим пример. На множестве X = {5, 7, 10, 15, 12} задано отношение R : «х < у ». Зададим это отношение перечислением пар
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Построим его граф. Мы видим, что граф данного отношения не имеет петель. На графе нет двойных стрелок. Если из х идет стрелка в у , а из у – в z , то из х идет стрелка в z (рис. 8).

Построенный граф позволяет расположить элементы множества X в таком порядке:

{5, 7, 10, 12, 15}.

На рис.6 (§ 6 этой главы) графы VII, VIII – это графы отношений строгого порядка.

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

Отношению «меньше» в множестве действительных чисел противоположно отношение «не меньше». Оно уже не является отношением строгого порядка. Дело в том, при х = у , выполняются отношения х ³ у и у ³ х , т.е. отношение «не меньше» обладает рефлексивностью.

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

Такие отношения являются объединениями отношения строгого порядка с отношением тождества.

Рассмотрим отношение «не больше» (£) для множества

X = {5, 7, 10, 15, 12}. Построим его граф (рис. 9).

Граф отношения нестрогого порядка, в отличие от графа отношения строгого порядка, в каждой вершине имеет петли.

На рис. 6 (§ 6 этой главы) графы V, VI – это графы отношений нестрогого порядка.

Упорядоченные множества

Множество может оказаться упорядоченным (говорят также полностью упорядоченным) некоторым отношением порядка, другое же неупорядоченным или частично упорядоченным таким отношением.

Определение. Множество X называют упорядоченным некоторым отношением порядка R , если для любых двух элементов х, у из Х :

(х , у ) Î R или (у, х ) Î R .

Если R – отношение строгого порядка, то множество Х упорядочено этим отношением при условии: если х , у любые два неравных элемента множества Х , то (х , у ) Î R или (у, х ) Î R , или любые два элемента х, у множества Х равны.

Из школьного курса математики известно, что числовые множества N , Z , Q , R упорядочены отношением «меньше» (<).

Множество подмножеств некоторого множества не упорядочено введением отношения включения (Í), или строгого включения (Ì) в указанном выше смысле, т.к. существуют подмножества ни одно из которых не включается в другое. В этом случае говорят, что данное множество частично упорядочено отношением Í (или Ì).

Рассмотрим множество X = {1, 2, 3, 4, 5, 6} и в нем два отношения «меньше» и «делится на». Легко проверить, что оба эти отношения являются отношениями порядка. Граф отношения «меньше» можно изобразить в виде луча.

Граф отношения «делится на» можно изобразить лишь на плоскости.

Кроме того, на графе второго отношения есть вершины, не соединенные стрелкой. Например, нет стрелки, соединяющей числа 4 и 5 (рис. 10).

Первое отношение «х < у » называется линейным. Вообще, если отношение порядка R (строгого и нестрогого) на множестве X обладает свойством: для любых х , у Î Х либо хRy , либо yRx , то его называют отношением линейного порядка, а множество X – линейно упорядоченным множеством.

Если множество X конечно, и состоит из n элементов, то линейное упорядочивание Х сводится к нумерации его элементов числами 1,2,3, ..., n .

Линейно упорядоченные множества обладают рядом свойств:

1°. Пусть а, в, с – элементы множества X , упорядоченного отношением R . Если известно, что aRв и вRс , то говорят, что элемент в лежит между элементами а и с .

2°. Множество X , линейно упорядоченное отношением R , называется дискретным, если между любыми двумя его элементами лежит лишь конечное множество элементов этого множества.

3°. Линейно упорядоченное множество называется плотным, если для любых двух различных элементов этого множества существует элемент множества, лежащий между ними.

План лекции №14 Классификация бинарных отношений

1. Классификация антисимметричных отношений
2. Классификация рефлексивных отношений
2.1. Отношения квазипорядка
2.2. Отношения нестрогого частичного порядка
2.3. Отношения нестрого упорядочения
2.4. Нестрогий качественный порядок
2.5. Нестрогий слабый порядок
2.6. Нестрогий порядок
3. Двойственность отношений строгого и нестрогого порядка
4. Обзор свойств различных видов отношений

Классификация антисимметричных отношений

Структура графов ациклических отношений

Структура графов отношений качественного порядка

Структура графов отношений слабого порядка

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

Строгим порядком (строгим предпочтением, сильным порядком, строгим линейным порядком) называется антирефлексивное, транзитивное, слабосвязное бинарное отношение (12).

Строгий порядок является частным случаем слабого порядка (строгого частичного предпочтения) с дополни-тельным условием слабосвязности.

Пример: Отношение "строго меньше" на множестве целых чисел.

Классификация рефлексивных отношений

Отношения квазипорядка

Эти бинарные отношения позволяют сравнивать элементы некоторого множества, но не по сходству, а путем расположения элементов групп в некотором порядке, т.е. путем частичного упорядочивания.

Квазипорядком (нестрогим частичным предпочтением) называется рефлексивное и транзитивное бинарное отношение (3).

Пример: "быть братом" (Иван-Петр, Андрей-Анна)

Свойства квазипорядков

1. Пересечение квазипорядков остается квазипорядком.
2. Симметричная часть квазипорядка обладает свойствами рефлексивности, симметричности и транзитивности и поэтому является отношением эквивалентности. R с = R / R инв
3. С помощью этого пересечения можно выделить группы эквивалентных между собой вариантов, тогда между выделенными группами может быть установлено отношение нестрогого частичного порядка, порожденное исходным отношением.
4. Асимметричная часть квазипорядка является транзитивным и антирефлексивным отношением = качественный порядок.

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

Отношением нестрогого частичного порядка (4) называется отношение, имеющее свойства рефлексивности, антисимметричности и транзитивности.

Нестрогий частичный порядок является антисимметричным квазипорядком

Пример: отношение "быть частью", определенное для множеств (и их подмножеств)

Свойства нестрогих частичных порядков

1. Пересечение нестрогих частичных порядков остается нестрогим частичным порядком.
2. Симметричная часть нестрогого частичного порядка является диагональю.
3. Асимметричная часть нестрогого частичного порядка является (строгим) качественным порядком.
4. В теории интеллектуальных систем важную роль играют частично упорядоченные множества – домены вместе с определенными на них отношениями нестрогого частичного порядка.
5. Частично упорядоченные множества с дополнительным свойством существования у каждой пары элементов верхней и нижней граней называются решетками. Частным случаем решеток являются булевы алгебры.

Отношения нестрогого упорядочения

Нестрогим упорядочением называется рефлексивное отношение, обладающее свойством слабосвязности (5).

Нестрогое упорядочение можно определить также как полносвязное отношение.

Отношение нестрогого упорядочения можно представить как результат объединения некоторых отношений толерантности и доминирования.

Свойства отношений нестрогого частичного упорядочения

1. Пересечение и объединение полносвязных отношений остается полносвязным отношением.
2. Симметричная часть нестрогого частичного упорядочения является толерантностью.
3. Асимметричная часть нестрогого частичного упорядочения является доминированием.
4. Для полносвязных отношений необходимым условием транзитивности является негатранзитивность отношения.
5. Для полносвязных отношений свойство транзитивности является достаточным условием негатранзитивности отношения.

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

Бинарное отношение R называется нестрогим качественным порядком, если оно негатранзитивно и полносвязно (6).

Нестрогий качественный порядок является негатранзитивным нестрогим упорядочиванием.

Отношение нестрогого качественного порядка можно представить как результат объединения некоторых отношений толерантности и качественного порядка.

Свойства отношений нестрогого качественного порядка

1. Симметричная часть нестрогого качественного порядка является толерантностью. НТ?
2. Асимметричная часть нестрогого качественного порядка транзитивна, поэтому является отношением качественного порядка.
3. Таким образом, отношение нестрогого качественного порядка можно представить как результат объединения отношений толерантности и качественного порядка, порожденных исходным отношением.
4. Двойственное отношение обладает свойствами асимметричности и транзитивности поэтому является отношением качественного порядка.

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

Нестрогим слабым порядком называется полносвязное транзитивное и негатранзитивное отношение (7).

Нестрогим слабым порядком называется полносвязное транзитивное отношение.

Нестрогим слабым порядком называется транзитивное нестрогое упорядочение.

Свойства отношений нестрогого слабого порядка

1. Симметричная часть нестрогого слабого порядка является эквивалентностью.
2. Асимметричная часть R ас нестрогого слабого порядка транзитивна, поэтому является отношением качественного порядка.
3. Таким образом, отношение нестрогого слабого порядка можно представить как результат объединения отношений эквивалентности и слабого порядка, порожденных исходным отношением.
4. Нестрогий слабый порядок можно представить в виде множества частично упорядоченных слоев, каждый из которых является классом эквивалентности.

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

Нестрогим порядком (нестрогим линейным порядком) называется антисимметричное, транзитивное, полносвязное бинарное отношение (8).

Нестрогим порядком называется антисимметричный нестрогий слабый порядок.

Нестрогим порядком называется антисимметричное нестрогое упорядочение.

Свойства отношений нестрогого линейного порядка

1. Симметричная часть нестрогого порядка является диагональю.
2. Асимметричная часть R ас нестрогого порядка транзитивна и слабосвязна, поэтому является отношением строгого порядка.
3. Двойственное отношение обладает свойствами асимметричности, негатранзитивности и слабосвязности поэтому является отношением строгого порядка. Кроме того оно совпадает с R ас.
4. Таким образом, отношение нестрогого порядка можно представить как результат объединения диагонали и строгого порядка, порожденных исходным отношением.

Двойственность отношений строгого и нестрогого порядка

Обзор свойств различных видов отношений