Что называется порядком множества
Что называется порядком множества
Здесь на первый план выступает как раз то, что мы до сих пор принципиально оставляли в стороне, а именно, вопрос о том, как имеющиеся в множествах одинаковой мощности отношения порядка различают эти множества. Ведь те взаимно однозначные отображения самого общего вида, которые мы до сих пор допускали, нарушали все эти отношения — вспомните хотя бы только об отображении квадрата на отрезок! Я бы хотел особенно подчеркнуть значение именно этого второго раздела учения о множествах; ведь не может же это учение иметь своей целью устранить посредством введения новых, более общих понятий те различия, которые с давних пор вошли в обиход математики; скорее, наоборот, это учение может и должно служить тому, чтобы с помощью общих понятий познать эти различия в их самой глубокой сущности.
Порядковые типы счетных множеств.
Теперь наша цель заключается в том, чтобы проиллюстрировать на определенных, общеизвестных примерах понятие различных возможных расположений элементов множества в определенном порядке. Если начинать со счетных множеств, то мы уже знаем три совершенно разные примера расположения элементов в таких множествах, столь различные между собой, что равенство их мощностей составляло, как мы видели, особую и ни в каком случае не самоочевидную теорему; это следующие множества:
1) множество натуральных чисел;
2) множество всех (отрицательных и положительных) целых чисел;
3) множество всех рациональных чисел и множество всех алгебраических чисел.
Расположение элементов во всех этих трех множествах имеет одно общее свойство, в силу которого оно называется линейным порядком в множестве. Это свойство состоит в следующем: из каждых двух элементов какой-нибудь один всегда предшествует другому, т. е., выражаясь алгебраически, всегда известно, какой элемент меньше и какой больше, и, далее, если из трех элементов а, b, с элемент а предшествует элементу b, а элемент b — элементу с, то всегда а предшествует элементу с (если 
, то 
Но, с другой стороны, в рассмотренных примерах имеют место такие характерные различия: в первом множестве существует первый элемент (нуль), который предшествует всем остальным, но нет последнего элемента, который следовал бы за всеми другими; во втором множестве нет ни первого, ни последнего элемента. Но в обоих этих множествах есть то общее, что за всяким элементом непосредственно следует определенный ближайший элемент, и всякому элементу непосредственно предшествует определенный другой элемент.
В противоположность этому у третьего множества между каждыми двумя элементами всегда есть, как мы уже видели выше, бесконечно много других элементов; такое свойство множества мы обозначали термином «всюду плотное множество», так что, в частности, среди всех рациональных или алгебраических чисел, лежащих между а и b, если не считать самих этих чисел, нет ни наименьшего, ни наибольшего числа. Таким образом, способы расположения элементов в этих трех множествах, т. е. их порядковые типы, различны между собой, хотя сами множества имеют одинаковые мощности. С этим можно связать — и это действительно делают представители теории множеств — вопрос о всех вообще возможных порядковых типах счетных множеств.
Непрерывность континуума. Перейдем теперь к рассмотрению множеств мощности континуума; здесь нам известно одно множество с имеющимся в нем линейным порядком, а именно, континуум 
всех действительных чисел. Но наряду с ним в двумерном и многомерных случаях мы имеем примеры множеств 
с расположением элементов, отличным от того, который мы назвали «линейным». Так, в случае множества 
для того чтобы определить взаимное расположение двух точек, небходимы уже не одно, а два соотношения типа неравенств.
Здесь наиболее важно проанализировать понятие непрерывности одномерного континуума; открытие того, что это понятие действительно основано только лишь на простых свойствах порядка, свойственного множеству 
является первой замечательной заслугой учения о множествах в деле выяснения основных математических понятий, а именно, оказывается, что все свойства непрерывности континуума проистекают из того, что последний представляет собой линейно упорядоченное множество со следующими двумя свойствами:
1. Если разделить множество на какие-либо две части А, В, но таким образом, чтобы, всякий элемент принадлежал какой-либо одной из этих частей и чтобы все элементы, входящие в часть А, предшествовали всем элементам части В, то в таком случае либо А имеет последний элемент, либо В имеет первый элемент.
Вспоминая дедекиндово определение иррациональных чисел 
мы можем выразить это свойство еще так: всякое «сечение» в нашем множестве производится одним из его элементов.
2. Между любыми двумя элементами множества имеется бесконечно много других элементов.
Этим вторым свойством обладают не только континуум 
но и счетное множество всех рациональных чисел; первое же свойство указывает на существенное различие между этими упорядоченными множествами. Всякое линейно упорядоченное множество, обладающее обоими этими свойствами, в учении о множествах называют непрерывным по той причине, что для него действительно можно доказать все теоремы, которые имеют место для континуума в силу его непрерывности.
Я хочу указать еще на то, что эти свойства непрерывности можно формулировать также несколько иначе, а именно, исходя из так называемых «основных» рядов Кантора. Основным рядом называют такую счетную последовательность 
элементов данного множества, что в самом множестве либо 
либо 
Некоторый элемент а множества называют предельным элементом основного ряда, если — в первом случае — в основном ряду всегда найдутся элементы, большие всякого элемента, лежащего в данном множестве до а, но вовсе нет элементов, бблыпих хотя бы одного элемента, расположенного после 
аналогично определяют предельный элемент во втором случае. Если множество обладает тем свойством, что всякому входящему в его состав основному ряду соответствует в нем предельный элемент, то множество называют замкнутым-, если же, наоборот, всякий элемент множества является предельным элементом некоторого основного ряда, выделенного из него, то множество называют плотным. Непрерывность множеств, имеющих мощность континуума, состоит, существенным об» разом, в соединении обоих этих свойств.
Попутно я хочу здесь напомнить, что при беседе о дифференциальном и интегральном исчислениях мы говорили, еще и о другом континууме — о континууме
Веронезе, который возникает из обыкновенного континуума посредством присоединения актуально бесконечно малых величин. Хотя таким путем получается тоже линейно упорядоченное множество, но тем не менее этот континуум обладает, конечно, совершенно иным типом расположения, чем обычный континуум 
теорема о том, что всякий основной ряд имеет предельный элемент, здесь уже места не имеет.
Полный порядок
В математике частично упорядоченным множеством называется множество, на котором определено отношение частичного порядка. Неформально можно сказать, что это отношение вводит некую иерархию элементов множества, выстраивает зависимости между ними, показывает, какой элемент множества «больше», а какой «меньше». При этом такое отношение вовсе не обязано быть отношением линейного порядка, т.е. не все элементы «сравнимы».
Содержание
Формальное определение
Пары элементов, для которых не выполняется ни 
, ни 
, называются несравнимыми. В линейно упорядоченных множествах таких пар нет.
Примеры
Минимальный и наименьший элементы множества
В отличие от линейно упорядоченных множеств, для частично упорядоченных множеств различают понятия минимального и наименьшего элементов. Наименьшим элементом множества называется элемент, меньший всех остальных элементов. Минимальным элементом называется элемент, меньше которого во множестве нет. Наименьших элементов во множестве может быть не более одного, в то время как минимальных может быть много. Легко показать, что если во множестве есть наименьший элемент, он является и единственным минимальным. Если же минимальных элементов несколько, то все они несравнимы.
Аналогично вводятся понятия максимального и наибольшего элементов.
Пример 1. Для множества подмножеств <x, y, z> с отношением 
, изображённого на рисунке, единственным наименьшим и минимальным элементом является 
. Для множества непустых подмножеств наимешьшего нет, а минимальными будут <x>, <y>, <z>.
Пример 2. Для натуральных чисел с отношением делимости, единственным наименьшим и минимальным элементом является 1. Для натуральных чисел, больших 1, с тем же порядком, наименьшего элемента нет, а минимальными являются простые числа, т.к. они не делятся ни на какие другие элементы.
Строгий и нестрогий порядки
Иногда описанный здесь порядок называется нестрогим (или рефлексивным). В противовес ему существует понятие строгого (или иррефлексивного) частичного порядка — это отношение, удовлетворяющее только последним двум из приведённого списка аксиом.
Если R является нестрогим порядком, то 
— это соответствующий ему строгий порядок. Подобным образом и нестрогий порядок ставится в соответствие строгому.
Литература
Полезное
Смотреть что такое «Полный порядок» в других словарях:
Полный порядок — Разг. Экспрес. Благополучный результат, исход начатого дела, мероприятия. Ну, полный порядок. В райкоме комсомола провели беседу. У ребят исключительная тяга к высшему образованию. Сказал бы лучше к городской жизни, сумрачно проговори Чернов (Ю.… … Фразеологический словарь русского литературного языка
ПОРЯДОК — порядка, м. 1. только ед. Состояние благоустройства и налаженности, систематичность, правильность в расположении чего–н., в ходе дел; противоп. беспорядок. «Привести в порядок впечатления.» Тургенев. В комнате полный порядок. Восстановить порядок … Толковый словарь Ушакова
полный — • полный абсурд • полный анализ • полный беспорядок • полный восторг • полный достаток • полный дурак • полный застой • полный идиот • полный комфорт • полный крах • полный мрак • полный невежда • полный нейтралитет • полный отдых • полный отказ… … Словарь русской идиоматики
порядок — сущ., м., употр. очень часто Морфология: (нет) чего? порядка, чему? порядку, (вижу) что? порядок, чем? порядком, о чём? о порядке; мн. что? порядки, (нет) чего? порядков, чему? порядкам, (вижу) что? порядки, чем? порядками, о чём? о порядках … … Толковый словарь Дмитриева
порядок — дка; м. 1. только ед. Правильное, отлаженное, организованное состояние; благообразный внешний вид. Образцовый п. Полный п. в делах. Поддерживать п. в комнате. Навести п. на столе. Привести в п. потрёпанную книгу. Во всём царит п. Нарушать,… … Энциклопедический словарь
порядок — I см. порядок; в функц. сказ. 1) разг. сниж. Хорошо; так, как нужно, как требуется; нормально. У тебя всё готово? Порядок! Видел свою дочь? С ней полный порядок. 2) В исправном, надлежащем, благополучном состоянии. Всё в порядке. Все документы в… … Словарь многих выражений
порядок — • абсолютный порядок • безупречный порядок • жесткий порядок • изумительный порядок • исключительный порядок • настоящий порядок • образцовый порядок • полный порядок … Словарь русской идиоматики
Полный Пэ (студия) — Логотип «полного Пэ» Гвардейская переводчицкая имени Клима Чугункина артель «полный Пэ» творческий проект Дмитрия Пучкова (Гоблина), в рамках которого Дмитрий Пучков переводит кинофильмы с английского языка на русский. Переводы, именуемые… … Википедия
Порядок Спорыньевые или Клавицепсовые (Саvicipitales) — Спорыньевые образуют перитеции в хорошо развитых стромах, состоящих только из гиф гриба. Стромы обычно мясистые, светло или яркоокрашенные, у некоторых представителей порядка темные. Их форма разнообразна, от распростертых но субстрату… … Биологическая энциклопедия
Упорядоченные множества
Каждому отношению порядка на множестве можно сопоставить следующие отношения.
Двойственный порядок
Отношение доминирования
Из определения следует, что отношение доминирования иррефлексивно, антисимметрично, но не транзитивно. Оно может быть и пусто. Например, легко видеть, что пустым будет отношение доминирования, если исходный порядок является плотным бинарным отношением на соответствующем множестве.
в. По отношению делимости на множестве натуральных чисел 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 тогда и только тогда, когда она является неубывающей.
Для приложений особенно важны непрерывные отображения индуктивного упорядоченного множества в себя.
Упорядоченные множества
Вводя операции надмножествами, мы не учитывали, что сами множества могут иметь свою внутреннюю структуру, т. е. мы считали, что все элементы множества равноправны. Однако в математике такие «чистые» множества представляют мало интереса, и гораздо чаще изучаются множества, между элементами которых существуют те или иные отношения. Одним из важнейших отношений между элементами множества является отношение порядка.
Отношение порядка есть не что иное, как правило, устанавливающее порядок «следования» элементов множества.
Пусть А — некоторое множество, Множество А называется упорядоченным множеством, если для любых его двух элементов а, b установлено одно из следующих отношений порядка:
либо а ≤ b (а не превосходит b),
либо b ≤ а (b не превосходит а),
обладающих следующими свойствами:
1)рефлексивность:
любой элемент не превосходит самого себя;
2) антисимметричность:
если а не превосходит b, а b не превосходит а, то элементы а и b совпадают;
3) транзитивность:
если а не превосходит b, a b не превосходит с, то а не превосходит с.
Пустое множество условились считать упорядоченным. В сформулированном выше определении упорядоченного множества, элементами которого могут быть объекты любой природы, знак ≤ читается «не превосходит». Привычное чтение и смысл этот знак (как знак «меньше или равно») приобретает в случае, когда элементы множества А — числа.
Два множества, составленные из одних и тех же элементов, но с разными отношениями порядка, считаются различными упорядоченными множествами.
Одно и то же множество можно упорядочить различными способами, получая тем самым различные упорядоченные множества.
Пример
Рассмотрим множество, элементами которого являются различные выпуклые многоугольники: треугольник, четырехугольник, пятиугольник, шестиугольник и т. д. Один способ образования упорядоченного множества из данного неупорядоченного множества может, например, состоять в том, что в качестве первого элемента упорядоченного множества мы берем треугольник, в качестве второго — четырехугольник, третьего — пятиугольник и т. д., т. е. упорядочиваем множество в порядке возрастания числа внутренних углов многоугольников. Множество многоугольников может быть упорядочено и другим способом, например перечислением многоугольников в порядке возрастания площадей, когда в качестве первого выбирается многоугольник, имеющий наименьшую площадь, в качестве второго — многоугольник с площадью, не превышающей площадь всех остальных, кроме уже выбранного, и т. д.
Упорядоченные (конечные или счетные) множества часто записывают, располагая их элементы в заданном порядке в круглых скобках.
Пример
Записи (1; 2; 3) и (2; 1; 3) представляют различные конечные упорядоченные множества, которые можно получить из одного и того же множества <1; 2; 3>, упорядочивая его двумя различными способами.
Для записи счетного упорядоченного множества необходимо указать первый элемент упорядоченного множества и указать порядок (правило) расположения последующих элементов.
Частичный порядок
В математике частично упорядоченным множеством называется множество, на котором определено отношение частичного порядка. Неформально можно сказать, что это отношение вводит некую иерархию элементов множества, выстраивает зависимости между ними, показывает, какой элемент множества «больше», а какой «меньше». При этом такое отношение вовсе не обязано быть отношением линейного порядка, т.е. не все элементы «сравнимы».
Содержание
Формальное определение
Пары элементов, для которых не выполняется ни , ни , называются несравнимыми. В линейно упорядоченных множествах таких пар нет.
Примеры
Минимальный и наименьший элементы множества
В отличие от линейно упорядоченных множеств, для частично упорядоченных множеств различают понятия минимального и наименьшего элементов. Наименьшим элементом множества называется элемент, меньший всех остальных элементов. Минимальным элементом называется элемент, меньше которого во множестве нет. Наименьших элементов во множестве может быть не более одного, в то время как минимальных может быть много. Легко показать, что если во множестве есть наименьший элемент, он является и единственным минимальным. Если же минимальных элементов несколько, то все они несравнимы.
Аналогично вводятся понятия максимального и наибольшего элементов.
Пример 1. Для множества подмножеств <x, y, z> с отношением , изображённого на рисунке, единственным наименьшим и минимальным элементом является . Для множества непустых подмножеств наимешьшего нет, а минимальными будут <x>, <y>, <z>.
Пример 2. Для натуральных чисел с отношением делимости, единственным наименьшим и минимальным элементом является 1. Для натуральных чисел, больших 1, с тем же порядком, наименьшего элемента нет, а минимальными являются простые числа, т.к. они не делятся ни на какие другие элементы.
Строгий и нестрогий порядки
Иногда описанный здесь порядок называется нестрогим (или рефлексивным). В противовес ему существует понятие строгого (или иррефлексивного) частичного порядка — это отношение, удовлетворяющее только последним двум из приведённого списка аксиом.
Если R является нестрогим порядком, то — это соответствующий ему строгий порядок. Подобным образом и нестрогий порядок ставится в соответствие строгому.
Литература
Полезное
Смотреть что такое «Частичный порядок» в других словарях:
частичный порядок — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN partial order … Справочник технического переводчика
ЧАСТИЧНЫЙ ПОРЯДОК — см. Порядок … Математическая энциклопедия
Порядок Спорыньевые или Клавицепсовые (Саvicipitales) — Спорыньевые образуют перитеции в хорошо развитых стромах, состоящих только из гиф гриба. Стромы обычно мясистые, светло или яркоокрашенные, у некоторых представителей порядка темные. Их форма разнообразна, от распростертых но субстрату… … Биологическая энциклопедия
Порядок оплаты заказа — порядок расчетов, производимых туроператором со средством размещения, который включает полный или частичный авансовый платеж (предоплату); при этом окончательный расчет за предоставленные услуги производится по факту оказания данных услуг … Лексикон туриста
Полный порядок — В математике частично упорядоченным множеством называется множество, на котором определено отношение частичного порядка. Неформально можно сказать, что это отношение вводит некую иерархию элементов множества, выстраивает зависимости между ними,… … Википедия
Полный или частичный аванс — порядок оплаты, при котором туроператор перечисляет на счет средства размещения авансовый платеж за услуги, которые будут оказаны клиентам после получения аванса; аванс может составлять полную сумму стоимости услуг (полный аванс) или неполную… … Лексикон туриста
Упорядоченные и частично упорядоченные множества — (математичексие) множества, в которых каким либо способом установлен порядок следования их элементов или, соответственно, частичный порядок. Понятия порядка и частичного порядка следования элементов определяются следующим образом. Говорят … Большая советская энциклопедия
Теорема Шпильрайна — Теорема Шпильрайна одна из центральных теорем теории упорядоченных множеств, впервые сформулированная и доказанная польским математиком Эдвардом Шпильрайном в 1930 году. Содержание 1 Формулировка 2 Доказательство … Википедия
Упорядоченные и частично упорядоченные множества — В математике частично упорядоченным множеством называется множество, на котором определено отношение частичного порядка. Неформально можно сказать, что это отношение вводит некую иерархию элементов множества, выстраивает зависимости между ними,… … Википедия
ДОУПОРЯДОЧИВАЕМАЯ ГРУППА — группа, всякий частичный порядок в к рой может быть продолжен до линейного (см. Упорядочиваемая группа). Д. г. наз. также О* группами. Существует следующий критерий доупорядочиваемости группы. Пусть S(g) минимальная инвариантная подполугруппа… … Математическая энциклопедия