Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества.

Другим важным бинарным отношением, часто встречающимся в математике, является отношение порядка.

Определение 1.Бинарное отношение Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru на множестве Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru Ø называется отношением порядка, если оно антисимметрично транзитивно.

Например, отношение «<» является отношением порядка на множестве N.

Определение 2.Отношение порядка Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru на множестве А называется нестрогим,отношением порядка, если оно рефлексивно.

Например, отношение « Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru » является нестрогим отношением порядка на множестве N.

Определение 3.Отношение порядка Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru на множестве А называется строгим отношением порядка, если оно антирефлексивно.

Например, отношение «<» - отношение строгого порядка на множестве N.

Определение 3 эквивалентно следующему определению:

Определение 3'.Бинарное отношение Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru на множестве Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru Ø называется отношением строгого порядка, если Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru антирефлексивно и транзитивно.

Покажем, что из антирефлексивности и транзитивности Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru на А следует антисимметричность Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru на А.

Допустим, Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru и Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru тогда, в силу транзитивности Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru , Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru , что невозможно, так как Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru - антирефлексивно. Значит, либо Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru , либо Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru то есть, Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru - антисимметрично.

Определение 4.Бинарное отношение Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru на множестве Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru Ø называется отношением предпорядка,если оно рефлексивно и транзитивно на А.

Определение 5.Отношение порядка Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru на множестве А называется линейным,если оно связанно.

Определение 6. Пусть Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru - отношение порядка на непустом множестве А. Тогда пара <А, Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru > называется упорядоченным множеством. Если Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru -линейный порядок, то <А, Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru > называется линейным упорядоченным множеством.

Определение 7.Пусть <А, Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru >-упорядоченное множество .Элемент а из А называется наименьшим (наибольшим)в А, если Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru для любого элемента x из А, отличного от Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru .

Определение 8.Пусть <А, Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru > - упорядоченное множество. Элемент Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru из А называется минимальным (максимальным),в А, если выполняется условие: для любого x из а, если Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru , то x = a.

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

Пример 1:пусть Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru Ø,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. Рассмотрим на множестве Р(М) бинарное отношение « Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru ». Это бинарное отношение рефлексивно, антисимметрично, транзитивно. Значит, оно является отношением нестрогого порядка. Отношение « Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru » не является связанным на Р(М). Например: {1} Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru {2}, но {1} Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru {2} и {2} Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru {1}. Пара Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru является упорядоченным множеством, но не является линейно упорядоченным множеством. Здесь имеем единственный максимальный (он же наибольший) элемент {1,2,3} и единственный минимальный(он же наименьший) элемент Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru Ø. Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru

 
  Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru

Пример 2. К={ Ø,{1},{2},{3},{1,2},{1,3},{2,3}}. <K, Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru > - упорядоченное множество. В К наибольшего элемента нет, но в К три максимальных элемента {1,2},{1,3},{2,3}. В К единственный минимальный (он же наименьший элемент).

 
  Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru

Определение 9.Линейно упорядоченное множество <A, Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru > называется вполне упорядоченным множеством,если каждое непустое подмножество множества А имеет наименьший элемент.

Пример 3.Если «<» - есть обычное отношение «меньше» на множестве N, то <N,< > является вполне упорядоченным множеством.

Пример 4.<R,< > - линейно упорядоченное множество, но не вполне упорядоченное множество. Отношение порядка и предпорядка. Линейный порядок. Упорядоченные множества. Наибольший (наименьший), максимальный (минимальный) элементы упорядоченного множества. - student2.ru

Наши рекомендации