что такое упорядоченное множество
Упорядоченные множества
Вводя операции надмножествами, мы не учитывали, что сами множества могут иметь свою внутреннюю структуру, т. е. мы считали, что все элементы множества равноправны. Однако в математике такие «чистые» множества представляют мало интереса, и гораздо чаще изучаются множества, между элементами которых существуют те или иные отношения. Одним из важнейших отношений между элементами множества является отношение порядка.
Отношение порядка есть не что иное, как правило, устанавливающее порядок «следования» элементов множества.
Пусть А — некоторое множество, Множество А называется упорядоченным множеством, если для любых его двух элементов а, b установлено одно из следующих отношений порядка:
либо а ≤ b (а не превосходит b),
либо b ≤ а (b не превосходит а),
обладающих следующими свойствами:
1)рефлексивность:
любой элемент не превосходит самого себя;
2) антисимметричность:
если а не превосходит b, а b не превосходит а, то элементы а и b совпадают;
3) транзитивность:
если а не превосходит b, a b не превосходит с, то а не превосходит с.
Пустое множество условились считать упорядоченным. В сформулированном выше определении упорядоченного множества, элементами которого могут быть объекты любой природы, знак ≤ читается «не превосходит». Привычное чтение и смысл этот знак (как знак «меньше или равно») приобретает в случае, когда элементы множества А — числа.
Два множества, составленные из одних и тех же элементов, но с разными отношениями порядка, считаются различными упорядоченными множествами.
Одно и то же множество можно упорядочить различными способами, получая тем самым различные упорядоченные множества.
Пример
Рассмотрим множество, элементами которого являются различные выпуклые многоугольники: треугольник, четырехугольник, пятиугольник, шестиугольник и т. д. Один способ образования упорядоченного множества из данного неупорядоченного множества может, например, состоять в том, что в качестве первого элемента упорядоченного множества мы берем треугольник, в качестве второго — четырехугольник, третьего — пятиугольник и т. д., т. е. упорядочиваем множество в порядке возрастания числа внутренних углов многоугольников. Множество многоугольников может быть упорядочено и другим способом, например перечислением многоугольников в порядке возрастания площадей, когда в качестве первого выбирается многоугольник, имеющий наименьшую площадь, в качестве второго — многоугольник с площадью, не превышающей площадь всех остальных, кроме уже выбранного, и т. д.
Упорядоченные (конечные или счетные) множества часто записывают, располагая их элементы в заданном порядке в круглых скобках.
Пример
Записи (1; 2; 3) и (2; 1; 3) представляют различные конечные упорядоченные множества, которые можно получить из одного и того же множества <1; 2; 3>, упорядочивая его двумя различными способами.
Для записи счетного упорядоченного множества необходимо указать первый элемент упорядоченного множества и указать порядок (правило) расположения последующих элементов.
Упорядоченные множества
Каждому отношению порядка на множестве можно сопоставить следующие отношения.
Двойственный порядок
Отношение доминирования
Из определения следует, что отношение доминирования иррефлексивно, антисимметрично, но не транзитивно. Оно может быть и пусто. Например, легко видеть, что пустым будет отношение доминирования, если исходный порядок является плотным бинарным отношением на соответствующем множестве.
в. По отношению делимости на множестве натуральных чисел 15 доминирует над 3 и 5, но 20 не доминирует над 5, так как существует „промежуточный» элемент — 10, делитель 20, который делится на 5, но не равен ни 20, ни 5.
Упорядоченное подмножество
Упорядоченное множество, все элементы которого попарно сравнимы, называют линейно упорядоченным, а соответствующее отношение — отношением линейного порядка (или просто линейным порядком). Бели индуцированный порядок на подмножестве упорядоченного множества является линейным, то это линейно упорядоченное подмножество называют цепью. Любое подмножество попарно не сравнимых элементов данного упорядоченного множества называют антицепью.
Замечание 1.5. Обратим внимание на то, что термину «упорядоченное множество» (в смысле приведенного определения) отвечает термин «частично упорядоченное множество», а то, что мы называем линейно упорядоченным множеством, называется просто упорядоченным множеством. Терминология этого выпуска более принята в алгебраической литературе и литературе по дискретной математике. Употребление термина «частично упорядоченное множество» мотивировано желанием подчеркнуть, что в общем случае в упорядоченном множестве существуют не сравнимые элементы.
б. Отношение делимости (см. пример 1.13.г) на множестве и отношение включения на (см. пример 1.13,д) не являются линейными порядками, за исключением случая, когда — одноэлементное множество.
Наибольший, наименьший и максимальный, минимальный элементы множества
Замечание 1.6. Поскольку на одном и том же множестве могут быть определены разные отношения порядка (например, на множестве натуральных чисел — естественный числовой порядок и отношение делимости), то, когда это необходимо, мы будем говорить о наибольших, наименьших (соответственно максимальных и минимальных) элементах по данному отношению порядка, уточняя тем самым, о каком отношении порядка идет речь.
Следующие примеры показывают, что максимальных (минимальных) элементов может быть сколько угодно. Но заметим, что если у множества есть наибольший (соответственно наименьший) элемент, то он является единственным максимальным (соответственно минимальным) элементом данного множества.
Верхняя и нижняя грань множества
Множество всех верхних (нижних) граней множества называют верхним (нижним) конусом и обозначают (соответственно ).
Пример 1.18. а. Рассмотрим множество точек прямоугольника (рис. 1.11, б) с заданным в примере 1.17 отношением порядка. Точка является точной нижней гранью, а точка — точной верхней гранью этого множества. Обе точки принадлежат множеству.
Если рассмотреть множество (рис. 1.11, в) с тем же отношением порядка, то увидим, что точная нижняя грань (точка ) и точная верхняя грань (точка ) множества существуют, но не принадлежат множеству.
Вполне упорядоченные множества
Множество натуральных чисел с отношением естественного числового порядка вполне упорядоченное. Множество целых чисел не вполне упорядоченное, поскольку оно не имеет наименьшего элемента. Аналогично множества рациональных и действительных чисел не являются вполне упорядоченными.
Говорят также и о взаимно двойственных определениях: если в любом определении, связанном с упорядоченным множеством, произвести взаимные замены согласно принципу двойственности, то получится новое определение, называемое двойственным к исходному. Так, определение наибольшего (максимального) элемента множества двойственно к определению наименьшего (минимального) элемента, и наоборот. Часто употребляют оборот речи: «двойственным образом…» (или «двойственно…»), понимая под этим переход к утверждению или определению, которое двойственно к исходному.
Способы наглядного представления упорядоченных множеств
Рассмотрим теперь некоторые способы наглядного представления упорядоченных множеств.
На рис. 1.13 приведена диаграмма Хассе для упорядоченного множества всех подмножеств трехэлементного множества по отношению включения (см. пример 1.13.д).
Элемент а упорядоченного множества называют точной верхней гранью последовательности если он есть точная верхняя грань множества всех членов последовательности. Другими словами, точная верхняя грань последовательности есть точная верхняя грань области ее значений как функции натурального аргумента.
Точная нижняя грань последовательности
Двойственно определяется точная нижняя грань последовательности.
Упорядоченное множество называют индуктивным, если:
Например, множество всех подмножеств некоторого множества по отношению включения будет индуктивным. Наименьший элемент — пустое множество, а точной верхней гранью произвольной неубывающей последовательности множеств будет объединение всех членов этой последовательности (наименьшее по включению множество, содержащее в качестве подмножества любой член последовательности).
Теорема 1.6. Всякое непрерывное отображение одного индуктивного упорядоченного множества в другое монотонно.
В общем случае монотонное в смысле определения 1.6 отображение не является непрерывным в смысле определения 1.5. Приведем пример, показывающий, что утверждение, обратное теореме 1.6, неверно.
Пример 1.19. Рассмотрим множество всех точек отрезка числовой прямой с порядком, индуцированным естественным числовым порядком. Это множество индуктивно: его наименьший элемент — 0, а любая неубывающая последовательность элементов ограничена сверху и по признаку Вейерштрасса имеет предел, который и будет ее точной верхней гранью. Любая кусочно-непрерывная (но не непрерывная!) и монотонная в смысле обычных определений из курса математического анализа функция, отображающая этот отрезок на любой отрезок с порядком, индуцированным естественным числовым порядком, дает пример монотонного в смысле определения 1.6, но не непрерывного в смысле определения 1.5 отображения между индуктивными частично упорядоченными множествами. Например, пусть функция имеет вид
Не следует путать отображение, монотонное в смысле определения 1.6, с монотонными функциями из курса математического анализа. Функция будет монотонной в смысле определения 1.6 тогда и только тогда, когда она является неубывающей.
Для приложений особенно важны непрерывные отображения индуктивного упорядоченного множества в себя.
Упорядоченное множество
 | Список значений слова или словосочетания со ссылками на соответствующие статьи. Если вы попали сюда из другой статьи Википедии, пожалуйста, вернитесь и уточните ссылку так, чтобы она указывала на статью. |
Полезное
Смотреть что такое «Упорядоченное множество» в других словарях:
УПОРЯДОЧЕННОЕ МНОЖЕСТВО — множество, на к ром задано отношение порядка. См. также Линейно упорядоченное множество, Частично упорядоченное множество … Математическая энциклопедия
упорядоченное множество — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN ordered set … Справочник технического переводчика
Частично упорядоченное множество — У этого термина существуют и другие значения, см. Упорядоченное множество. Подмножества
Вполне упорядоченное множество — У этого термина существуют и другие значения, см. Упорядоченное множество. Вполне упорядоченное множество линейно упорядоченное множество M такое, что в любом его непустом подмножестве есть минимальный элемент, другими словами это… … Википедия
ЛИНЕЙНО УПОРЯДОЧЕННОЕ МНОЖЕСТВО, — цепь, частично упорядоченное множество, в к ром для любых двух элементов аи bимеет место или Подмножество Л. у. м. само является Л. у. м. Всякий максимальный (минимальный) элемент Л. у. м. оказывается наибольшим (наименьшим). Важнейший частный… … Математическая энциклопедия
частично упорядоченное множество — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN partially ordered set … Справочник технического переводчика
ЧАСТИЧНО УПОРЯДОЧЕННОЕ МНОЖЕСТВО — непустое множество, на к ром зафиксирован нек рый порядок. Ч. у. м. является примером модели. Примеры Ч. у. м.: 1) множество натуральных чисел с обычным порядком; 2) множество натуральных чисел, где означает, что аделит b; 3) множество всех… … Математическая энциклопедия
Частично упорядоченное множество — (матем.) см. Упорядоченные и частично упорядоченные множества … Большая советская энциклопедия
Упорядоченные и частично упорядоченные множества
Полезное
Смотреть что такое «Упорядоченные и частично упорядоченные множества» в других словарях:
Упорядоченные и частично упорядоченные множества — В математике частично упорядоченным множеством называется множество, на котором определено отношение частичного порядка. Неформально можно сказать, что это отношение вводит некую иерархию элементов множества, выстраивает зависимости между ними,… … Википедия
Частично упорядоченное множество — У этого термина существуют и другие значения, см. Упорядоченное множество. Подмножества
Частично упорядоченное множество — (матем.) см. Упорядоченные и частично упорядоченные множества … Большая советская энциклопедия
ЧАСТИЧНО УПОРЯДОЧЕННАЯ ГРУППА — группа G, на к рой задано отношение частичного порядка такое, что для любых а, b, х, у из G неравенство влечет за собой Множество Ч. у. г., называемое положительным конусом, или целой частью, группы G, обладает свойствами: 1) 2) 3) для любых… … Математическая энциклопедия
РЕШЕТКА — с т р у к т у р а, частично упорядоченное множество, в к ром каждое двухэлементное подмножество имеет как точную верхнюю, так и точную нижнюю грани. Отсюда вытекает существование этих граней для всякого непустого конечного подмножества. П р и м е … Математическая энциклопедия
Трансфинитные числа — (от Транс… и лат. finitus ограниченный) обобщённые порядковые числа. Определение Т. ч. опирается на понятие вполне упорядоченного множества (см. Упорядоченные и частично упорядоченные множества). Каждое конечное множество можно сделать… … Большая советская энциклопедия
Непрерывность по Скотту — в математике свойство функций над частично упорядоченными множествами, выражающееся в сохранении точной верхней грани относительно отношения частичного порядка. Топология Скотта структура над полной решёткой или, в более общем случае, над полным… … Википедия
Теорема Шпильрайна — Теорема Шпильрайна одна из центральных теорем теории упорядоченных множеств, впервые сформулированная и доказанная польским математиком Эдвардом Шпильрайном в 1930 году. Содержание 1 Формулировка 2 Доказательство … Википедия
ПОРЯДКА ОТНОШЕНИЕ — бинарное (двуместное, двучленное) отношение, обладающее свойствами иррефлек сивности (см. Рефлексивность) и транзитивности (из чего следует также его антисимметричность, см. Симметричность). П. о. упорядочивает элементы множества, на к ром оно… … Философская энциклопедия
Множеств теория — учение об общих свойствах множеств, преимущественно бесконечных. Понятие множества, или совокупности, принадлежит к числу простейших математических понятий; оно не определяется, но может быть пояснено при помощи примеров. Так, можно… … Большая советская энциклопедия