§6. Булевы алгебры

Материал из Википедии - свободной энциклопедии

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

В качестве абстрактного примера можно привести совокупность подмножеств множества из трёх элементов $\{ x, y, z\}$ (булеан данного множества), упорядоченную по отношению включения.

Определение и примеры

Порядком , или частичным порядком , на множестве $M$ называется бинарное отношение $\varphi$ на $M$ (определяемое некоторым множеством $R_{\varphi} \subset M \times M$ ), удовлетворяющее следующим условиям :

Рефлексивность : $\forall a \; (a \varphi a)$
Транзитивность : $\forall a, b, c \; (a \varphi b) \wedge (b \varphi c) \Rightarrow a \varphi c$
Антисимметричность : $\forall a, b \; (a \varphi b) \wedge (b \varphi a) \Rightarrow a = b$

Множество $M$ , на котором задано отношение частичного порядка, называется частично упорядоченным . Если быть совсем точным , то частично упорядоченным множеством называется пара $\langle M, \varphi \rangle$ , где $M$ - множество, а $\varphi$ - отношение частичного порядка на $M$ .

Терминология и обозначения

Отношение частичного порядка обычно обозначают символом $\leqslant$ , по аналогии с отношением «меньше либо равно» на множестве действительных чисел . При этом, если $a \leqslant b$ , то говорят, что элемент $a$ не превосходит $b$ , или что $a$ подчинён $b$ .

Если $a \leqslant b$ и $a \neq b$ , то пишут $a < b$ , и говорят, что $a$ меньше $b$ , или что $a$ строго подчинен $b$ .

Иногда, чтобы отличить произвольный порядок на некотором множестве от известного отношения «меньше либо равно» на множестве действительных чисел, вместо $\leqslant$ и $<$ используют специальные символы $\preccurlyeq$ и $\prec$ соответственно.

Строгий и нестрогий порядок

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

$\forall a \; \neg (a \varphi a)$

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

Если $\leqslant$ - нестрогий порядок на множестве $M$ , то отношение $<$ , определяемое как:

$a < b \; \overset{\mathrm{def}}{\Longleftrightarrow} \; (a \leqslant b) \wedge (a \neq b)$

является строгим порядком на $M$ . Обратно, если $<$ - строгий порядок, то отношение $\leqslant$ , определенное как

$a \leqslant b \; \overset{\mathrm{def}}{\Longleftrightarrow} \; (a < b) \vee (a = b)$

является нестрогим порядком.

Поэтому всё равно - задать на множестве нестрогий порядок, или строгий порядок. В результате получится одна и та же структура. Разница только в терминологии и обозначениях.

Примеры

Верхнее и нижнее множество

Специальные типы частично упорядоченных множеств

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

Пусть $\langle M, \leqslant\rangle$ - частично упорядоченное множество. Если в $M$ любые два элемента сравнимы, то множество $M$ называется линейно упорядоченным . Линейно упорядоченное множество также называют совершенно упорядоченным , или просто, упорядоченным множеством . Таким образом, в линейно упорядоченном множестве для любых двух элементов $a$ и $b$ имеет место одно и только одно из соотношений: либо $a, либо a=b, либо b .$

Также всякое линейно упорядоченное подмножество частично упорядоченного множества называют цепью , то есть цепь в частично упорядоченном множестве $\langle M, \leqslant \rangle$ - такое его подмножество, в котором любые два элемента сравнимы.

Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке (при условии $a), булеан \mathcal{P}(M) (при |M|\geqslant 2), натуральные числа с отношением делимости - не являются линейно упорядоченными.$

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

Вполне упорядоченные множества

Линейно упорядоченное множество называется вполне упорядоченным , если каждое его непустое подмножество имеет наименьший элемент . Такой порядок на множестве называется полным порядком , в контексте, где его невозможно спутать с полным порядком в смысле .

Классический пример вполне упорядоченного множества - множество натуральных чисел $\mathbb{N}$ . Утверждение о том, что любое непустое подмножество $\mathbb{N}$ содержит наименьший элемент, равносильно принципу математической индукции . В качестве примера линейно упорядоченного, но не вполне упорядоченного множества можно привести множество неотрицательных чисел, упорядоченное естественным образом $\mathbb{R}_{+} = \{ x: x \geqslant 0\}$ . Действительно, его подмножество $\{x: x > 1\}$ не имеет наименьшего элемента.

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

Полное частично упорядоченное множество - частично упорядоченное множество, у которого есть дно - единственный элемент, который предшествует любому другому элементу и у каждого направленного подмножества которого есть точная верхняя граница . Полные частично упорядоченные множества применяются в λ-исчислении и информатике , в частности, на них вводится топология Скотта , на основе которой строится непротиворечивая модель λ-исчисления и денотационная семантика . Специальным случаем полного частично упорядоченного множества является полная решётка - если любое подмножество, не обязательно направленное, имеет точную верхнюю грань, то оно оказывается полной решёткой.

Упорядоченное множество $M$ тогда и только тогда является полным частично упорядоченным, когда каждая функция $f \colon M\rightarrow M$ , монотонная относительно порядка ( $a \leqslant b \Rightarrow f(a) \leqslant f(b)$ ) обладает хотя бы одной неподвижной точкой : $\exists _{x \in M} f(x)=x$ .

Любое множество $M$ можно превратить в полное частично упорядоченное выделением дна $\bot$ и определением порядка $\leqslant$ как $\bot \leqslant m$ и $m \leqslant m$ для всех элементов $m$ множества $M$ .

Теоремы о частично упорядоченных множествах

К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа и лемма Куратовского - Цорна . Каждая из этих теорем эквивалентна аксиоме выбора .

В теории категорий

Каждое частично упорядоченное множество (и каждый предпорядок) можно рассматривать как категорию , в которой каждое множество морфизмов $\mathrm{Hom}(A,B)$ состоит не более чем из одного элемента. Например, эту категорию можно определить так: $\mathrm{Hom}(A,B)=\{(A,B)\}$ , если A ≤ B (и пустое множество в противном случае); правило композиции морфизмов: (y , z )∘(x , y ) = (x , z ). Каждая категория-предпорядок эквивалентна частично упорядоченному множеству.

Напишите отзыв о статье "Частично упорядоченное множество"

Примечания

Литература

Александров П. С. Введение в теорию множеств и общую топологию. - М .: Наука , 1977. - 368 с.
Барендрегт, Хенк. Ламбда-исчисление. Его синтаксис и семантика = The Lambda Calculus. Its syntax and semantics. - М .: Мир , 1985. - 606 с. - 4800 экз.
Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. - 7-е изд. - М .: Физматлит , 2004. - 572 с. - ISBN 5-9221-0266-4 .
Хаусдорф Ф. Теория множеств. - 4-е изд. - М .: УРСС , 2007. - 304 с. - ISBN 978-5-382-00127-2 .
Гуров С.И. Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры. - 2-е изд. - М .: Либроком , 2013. - 352 с. - ISBN 978-5-397-03899-7 .

См. также

Отрывок, характеризующий Частично упорядоченное множество

Подбитый зверь под Бородиным лежал там где то, где его оставил отбежавший охотник; но жив ли, силен ли он был, или он только притаился, охотник не знал этого. Вдруг послышался стон этого зверя.
Стон этого раненого зверя, французской армии, обличивший ее погибель, была присылка Лористона в лагерь Кутузова с просьбой о мире.
Наполеон с своей уверенностью в том, что не то хорошо, что хорошо, а то хорошо, что ему пришло в голову, написал Кутузову слова, первые пришедшие ему в голову и не имеющие никакого смысла. Он писал:

«Monsieur le prince Koutouzov, – писал он, – j"envoie pres de vous un de mes aides de camps generaux pour vous entretenir de plusieurs objets interessants. Je desire que Votre Altesse ajoute foi a ce qu"il lui dira, surtout lorsqu"il exprimera les sentiments d"estime et de particuliere consideration que j"ai depuis longtemps pour sa personne… Cette lettre n"etant a autre fin, je prie Dieu, Monsieur le prince Koutouzov, qu"il vous ait en sa sainte et digne garde,
Moscou, le 3 Octobre, 1812. Signe:
Napoleon».
[Князь Кутузов, посылаю к вам одного из моих генерал адъютантов для переговоров с вами о многих важных предметах. Прошу Вашу Светлость верить всему, что он вам скажет, особенно когда, станет выражать вам чувствования уважения и особенного почтения, питаемые мною к вам с давнего времени. Засим молю бога о сохранении вас под своим священным кровом.
Москва, 3 октября, 1812.
Наполеон. ]

«Je serais maudit par la posterite si l"on me regardait comme le premier moteur d"un accommodement quelconque. Tel est l"esprit actuel de ma nation», [Я бы был проклят, если бы на меня смотрели как на первого зачинщика какой бы то ни было сделки; такова воля нашего народа. ] – отвечал Кутузов и продолжал употреблять все свои силы на то, чтобы удерживать войска от наступления.
В месяц грабежа французского войска в Москве и спокойной стоянки русского войска под Тарутиным совершилось изменение в отношении силы обоих войск (духа и численности), вследствие которого преимущество силы оказалось на стороне русских. Несмотря на то, что положение французского войска и его численность были неизвестны русским, как скоро изменилось отношение, необходимость наступления тотчас же выразилась в бесчисленном количестве признаков. Признаками этими были: и присылка Лористона, и изобилие провианта в Тарутине, и сведения, приходившие со всех сторон о бездействии и беспорядке французов, и комплектование наших полков рекрутами, и хорошая погода, и продолжительный отдых русских солдат, и обыкновенно возникающее в войсках вследствие отдыха нетерпение исполнять то дело, для которого все собраны, и любопытство о том, что делалось во французской армии, так давно потерянной из виду, и смелость, с которою теперь шныряли русские аванпосты около стоявших в Тарутине французов, и известия о легких победах над французами мужиков и партизанов, и зависть, возбуждаемая этим, и чувство мести, лежавшее в душе каждого человека до тех пор, пока французы были в Москве, и (главное) неясное, но возникшее в душе каждого солдата сознание того, что отношение силы изменилось теперь и преимущество находится на нашей стороне. Существенное отношение сил изменилось, и наступление стало необходимым. И тотчас же, так же верно, как начинают бить и играть в часах куранты, когда стрелка совершила полный круг, в высших сферах, соответственно существенному изменению сил, отразилось усиленное движение, шипение и игра курантов.

Русская армия управлялась Кутузовым с его штабом и государем из Петербурга. В Петербурге, еще до получения известия об оставлении Москвы, был составлен подробный план всей войны и прислан Кутузову для руководства. Несмотря на то, что план этот был составлен в предположении того, что Москва еще в наших руках, план этот был одобрен штабом и принят к исполнению. Кутузов писал только, что дальние диверсии всегда трудно исполнимы. И для разрешения встречавшихся трудностей присылались новые наставления и лица, долженствовавшие следить за его действиями и доносить о них.
Кроме того, теперь в русской армии преобразовался весь штаб. Замещались места убитого Багратиона и обиженного, удалившегося Барклая. Весьма серьезно обдумывали, что будет лучше: А. поместить на место Б., а Б. на место Д., или, напротив, Д. на место А. и т. д., как будто что нибудь, кроме удовольствия А. и Б., могло зависеть от этого.
В штабе армии, по случаю враждебности Кутузова с своим начальником штаба, Бенигсеном, и присутствия доверенных лиц государя и этих перемещений, шла более, чем обыкновенно, сложная игра партий: А. подкапывался под Б., Д. под С. и т. д., во всех возможных перемещениях и сочетаниях. При всех этих подкапываниях предметом интриг большей частью было то военное дело, которым думали руководить все эти люди; но это военное дело шло независимо от них, именно так, как оно должно было идти, то есть никогда не совпадая с тем, что придумывали люди, а вытекая из сущности отношения масс. Все эти придумыванья, скрещиваясь, перепутываясь, представляли в высших сферах только верное отражение того, что должно было совершиться.
«Князь Михаил Иларионович! – писал государь от 2 го октября в письме, полученном после Тарутинского сражения. – С 2 го сентября Москва в руках неприятельских. Последние ваши рапорты от 20 го; и в течение всего сего времени не только что ничего не предпринято для действия противу неприятеля и освобождения первопрестольной столицы, но даже, по последним рапортам вашим, вы еще отступили назад. Серпухов уже занят отрядом неприятельским, и Тула, с знаменитым и столь для армии необходимым своим заводом, в опасности. По рапортам от генерала Винцингероде вижу я, что неприятельский 10000 й корпус подвигается по Петербургской дороге. Другой, в нескольких тысячах, также подается к Дмитрову. Третий подвинулся вперед по Владимирской дороге. Четвертый, довольно значительный, стоит между Рузою и Можайском. Наполеон же сам по 25 е число находился в Москве. По всем сим сведениям, когда неприятель сильными отрядами раздробил свои силы, когда Наполеон еще в Москве сам, с своею гвардией, возможно ли, чтобы силы неприятельские, находящиеся перед вами, были значительны и не позволяли вам действовать наступательно? С вероятностию, напротив того, должно полагать, что он вас преследует отрядами или, по крайней мере, корпусом, гораздо слабее армии, вам вверенной. Казалось, что, пользуясь сими обстоятельствами, могли бы вы с выгодою атаковать неприятеля слабее вас и истребить оного или, по меньшей мере, заставя его отступить, сохранить в наших руках знатную часть губерний, ныне неприятелем занимаемых, и тем самым отвратить опасность от Тулы и прочих внутренних наших городов. На вашей ответственности останется, если неприятель в состоянии будет отрядить значительный корпус на Петербург для угрожания сей столице, в которой не могло остаться много войска, ибо с вверенною вам армиею, действуя с решительностию и деятельностию, вы имеете все средства отвратить сие новое несчастие. Вспомните, что вы еще обязаны ответом оскорбленному отечеству в потере Москвы. Вы имели опыты моей готовности вас награждать. Сия готовность не ослабнет во мне, но я и Россия вправе ожидать с вашей стороны всего усердия, твердости и успехов, которые ум ваш, воинские таланты ваши и храбрость войск, вами предводительствуемых, нам предвещают».
Но в то время как письмо это, доказывающее то, что существенное отношение сил уже отражалось и в Петербурге, было в дороге, Кутузов не мог уже удержать командуемую им армию от наступления, и сражение уже было дано.
2 го октября казак Шаповалов, находясь в разъезде, убил из ружья одного и подстрелил другого зайца. Гоняясь за подстреленным зайцем, Шаповалов забрел далеко в лес и наткнулся на левый фланг армии Мюрата, стоящий без всяких предосторожностей. Казак, смеясь, рассказал товарищам, как он чуть не попался французам. Хорунжий, услыхав этот рассказ, сообщил его командиру.
Казака призвали, расспросили; казачьи командиры хотели воспользоваться этим случаем, чтобы отбить лошадей, но один из начальников, знакомый с высшими чинами армии, сообщил этот факт штабному генералу. В последнее время в штабе армии положение было в высшей степени натянутое. Ермолов, за несколько дней перед этим, придя к Бенигсену, умолял его употребить свое влияние на главнокомандующего, для того чтобы сделано было наступление.
– Ежели бы я не знал вас, я подумал бы, что вы не хотите того, о чем вы просите. Стоит мне посоветовать одно, чтобы светлейший наверное сделал противоположное, – отвечал Бенигсен.
Известие казаков, подтвержденное посланными разъездами, доказало окончательную зрелость события. Натянутая струна соскочила, и зашипели часы, и заиграли куранты. Несмотря на всю свою мнимую власть, на свой ум, опытность, знание людей, Кутузов, приняв во внимание записку Бенигсена, посылавшего лично донесения государю, выражаемое всеми генералами одно и то же желание, предполагаемое им желание государя и сведение казаков, уже не мог удержать неизбежного движения и отдал приказание на то, что он считал бесполезным и вредным, – благословил совершившийся факт.

Записка, поданная Бенигсеном о необходимости наступления, и сведения казаков о незакрытом левом фланге французов были только последние признаки необходимости отдать приказание о наступлении, и наступление было назначено на 5 е октября.
4 го октября утром Кутузов подписал диспозицию. Толь прочел ее Ермолову, предлагая ему заняться дальнейшими распоряжениями.
– Хорошо, хорошо, мне теперь некогда, – сказал Ермолов и вышел из избы. Диспозиция, составленная Толем, была очень хорошая. Так же, как и в аустерлицкой диспозиции, было написано, хотя и не по немецки:
«Die erste Colonne marschiert [Первая колонна идет (нем.) ] туда то и туда то, die zweite Colonne marschiert [вторая колонна идет (нем.) ] туда то и туда то» и т. д. И все эти колонны на бумаге приходили в назначенное время в свое место и уничтожали неприятеля. Все было, как и во всех диспозициях, прекрасно придумано, и, как и по всем диспозициям, ни одна колонна не пришла в свое время и на свое место.
Когда диспозиция была готова в должном количестве экземпляров, был призван офицер и послан к Ермолову, чтобы передать ему бумаги для исполнения. Молодой кавалергардский офицер, ординарец Кутузова, довольный важностью данного ему поручения, отправился на квартиру Ермолова.
– Уехали, – отвечал денщик Ермолова. Кавалергардский офицер пошел к генералу, у которого часто бывал Ермолов.
– Нет, и генерала нет.
Кавалергардский офицер, сев верхом, поехал к другому.
– Нет, уехали.
«Как бы мне не отвечать за промедление! Вот досада!» – думал офицер. Он объездил весь лагерь. Кто говорил, что видели, как Ермолов проехал с другими генералами куда то, кто говорил, что он, верно, опять дома. Офицер, не обедая, искал до шести часов вечера. Нигде Ермолова не было и никто не знал, где он был. Офицер наскоро перекусил у товарища и поехал опять в авангард к Милорадовичу. Милорадовича не было тоже дома, но тут ему сказали, что Милорадович на балу у генерала Кикина, что, должно быть, и Ермолов там.
– Да где же это?
– А вон, в Ечкине, – сказал казачий офицер, указывая на далекий помещичий дом.
– Да как же там, за цепью?
– Выслали два полка наших в цепь, там нынче такой кутеж идет, беда! Две музыки, три хора песенников.
Офицер поехал за цепь к Ечкину. Издалека еще, подъезжая к дому, он услыхал дружные, веселые звуки плясовой солдатской песни.
«Во олузя а ах… во олузях!..» – с присвистом и с торбаном слышалось ему, изредка заглушаемое криком голосов. Офицеру и весело стало на душе от этих звуков, но вместе с тем и страшно за то, что он виноват, так долго не передав важного, порученного ему приказания. Был уже девятый час. Он слез с лошади и вошел на крыльцо и в переднюю большого, сохранившегося в целости помещичьего дома, находившегося между русских и французов. В буфетной и в передней суетились лакеи с винами и яствами. Под окнами стояли песенники. Офицера ввели в дверь, и он увидал вдруг всех вместе важнейших генералов армии, в том числе и большую, заметную фигуру Ермолова. Все генералы были в расстегнутых сюртуках, с красными, оживленными лицами и громко смеялись, стоя полукругом. В середине залы красивый невысокий генерал с красным лицом бойко и ловко выделывал трепака.
– Ха, ха, ха! Ай да Николай Иванович! ха, ха, ха!..
Офицер чувствовал, что, входя в эту минуту с важным приказанием, он делается вдвойне виноват, и он хотел подождать; но один из генералов увидал его и, узнав, зачем он, сказал Ермолову. Ермолов с нахмуренным лицом вышел к офицеру и, выслушав, взял от него бумагу, ничего не сказав ему.
– Ты думаешь, это нечаянно он уехал? – сказал в этот вечер штабный товарищ кавалергардскому офицеру про Ермолова. – Это штуки, это все нарочно. Коновницына подкатить. Посмотри, завтра каша какая будет!

На другой день, рано утром, дряхлый Кутузов встал, помолился богу, оделся и с неприятным сознанием того, что он должен руководить сражением, которого он не одобрял, сел в коляску и выехал из Леташевки, в пяти верстах позади Тарутина, к тому месту, где должны были быть собраны наступающие колонны. Кутузов ехал, засыпая и просыпаясь и прислушиваясь, нет ли справа выстрелов, не начиналось ли дело? Но все еще было тихо. Только начинался рассвет сырого и пасмурного осеннего дня. Подъезжая к Тарутину, Кутузов заметил кавалеристов, ведших на водопой лошадей через дорогу, по которой ехала коляска. Кутузов присмотрелся к ним, остановил коляску и спросил, какого полка? Кавалеристы были из той колонны, которая должна была быть уже далеко впереди в засаде. «Ошибка, может быть», – подумал старый главнокомандующий. Но, проехав еще дальше, Кутузов увидал пехотные полки, ружья в козлах, солдат за кашей и с дровами, в подштанниках. Позвали офицера. Офицер доложил, что никакого приказания о выступлении не было.

Бинарное отношениена множестве А называется антисимметричным если:

(а,в А) а ф в в ф а

Бинарное отношение на множестве А называется рефлексивным если:

Бинарное отношение на множестве А называется транзитивным если:

(a,в,cA) aв вc > а с

Отношение делимости (нацело) на множестве натуральных чисел N антисимметрично. В самом деле, если ав, ва, то существуют натуральные q 1 ,qN, такие, что а=вq 1 , в=аq откуда а=аq 1 q, то есть q 1 q=1. Но,

q 1 ,qN,следовательно q 1 =q=1, откуда следует, что а = в.

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

Множество А с заданным на нем отношением частичного порядка? называют частично упорядоченным множеством и обозначают < А; ? >.

В дальнейшем для удобства будем пользоваться сокращением ЧУМ, обозначающим частично упорядоченное множество.

< N, ? > ? обычное нестрогое неравенство чисел (в школьном смысле). Нужно доказать транзитивность, рефлексивность и антисимметричность этого отношения?.

a) a ? a ,(2 ? 2) - рефлексивность,

b) если а? в, в? с, то a ? c, (3 ? 4, 4 ? 5 > 3 ? 5) - транзитивность,

c) если a ? в, в? a, то a=в, (3 ? 3, 3 ? 3 > 3=3) - антисимметричность.

Из этого следует, что < N, ? > - ЧУМ.

a) Отношение делимости на множестве натуральных чисел N рефлексивно, т.к всякое число кратно самому себе, т.е т.к для любого аN всегда a = a 1 (1N), это, по смыслу отношение, имеем а а. Следовательно, рефлексивно.

б) Если первое число делится нацело на второе(т.е кратное второму), а второе кратно третьему, то первое кратно третьему, значит отношение транзитивно, т.е. если а в, в с, a,в,cN. Значит, существуют такие q,qN, что

Обозначим: q = qqN. Имеем

где qN, т.е. а с - по определению. Следовательно, отношение транзитивно.

в) Антисимметричность отношения следует из того, что два натуральных числа, кратных друг другу, равны между собой, т.е. если ав, ва, то существуют такие q 1 ,qN, что

то есть q 1 q=1. Но, q 1 ,qN,следовательно q 1 =q=1, откуда следует, что а = в. Следовательно антисимметрично.

Поэтому есть частичный порядок и, стало быть, < N, > - ЧУМ(частично упорядоченным множеством).

Элементы a,в ЧУМа А называются несравнимыми и записываются

если a ? в и в? а.

Элементы a,в ЧУМа А называются сравнимыми если a ? в или в? а.

Частичный порядок? на A называется линейным, а само ЧУМ линейно - упорядоченным или цепью, если любые два элемента из А сравнимы, т.е. для любых a,в A, либо a ? в, либо в? a.

< N, ? >, - являются цепью. Однако <В(М) ; > ,где В(М) - множество всех подмножеств множества М или В(М) называется булеаном на множестве М, не является цепью, т.к. не для любых двух подмножеств множество М одно является подмножеством другого.

Пусть < А, ? > - произвольный ЧУМ.

Элемент mA называется минимальным, если для любого x A из того, что x ? m следует x = m.

Смысл этого понятия в том, что А не содержит элементов строго меньших этого элемента m. Говорят, что х строго меньше m и записывают х < m, если x ? m, но притом x ? m. Аналогично определяется максимальный элемент этого ЧУМ. Ясно, что если m, m- разные минимальные (максимальные) элементы ЧУМ, то m || m.

В теории частично упорядоченных множеств условие a ? в иногда читают так: элемент а содержится в элементе в или элемент в содержит элемент а.

Каждый элемент конечного ЧУМа содержит минимальный элемент и содержится в максимальном элементе этого ЧУМа.

Доказательство:

Пусть а - произвольный элемент конечного ЧУМа S. Если а - минимальный элемент, то в силу рефлексивности, лемма доказана. Если А не минимален, то найдется элемент а такой, что

Если а минимален, то всё доказано. Если же элемент ане является минимальным, то для некоторого а получим

Если а минимален, то из (1), (2), благодаря транзитивности, заключаем, что а содержит минимальный элемент а. Если же а не минимален, то

Таким образом, на некотором n - ом шаге рассуждений процесс оборвется, что равносильно тому, что элемент а минимален. При этом

а< а<< а< а< а

За счет транзитивности отсюда следует, что элемент а содержит минимальный элемент а. Аналогично, элемент а содержится в максимальном элементе. Лемма доказана.

Следствие.

Конечное ЧУМ содержит, по меньшей мере, один минимальный элемент.

Сейчас мы введем важное для дальнейшего изложения понятие диаграммы конечного ЧУМа S.

Вначале берем все минимальные элементы m, m, m в S. Согласно следствию такие найдутся. Затем в частично упорядоченном множестве

S = S {m, m, m},

которые, как и S , является конечным, берем минимальные элементы, и рассматриваем множество

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

Далее отыскиваем минимальные элементы ЧУМа, изображаем их точками “третьего ряда” и соединяем точками “второго ряда” указанным выше способом. Продолжаем процесс до тех пор, пока не будут исчерпаны все элементы данного ЧУМа S. Процесс конечен в силу конечности множества S. Полученную совокупность точек и отрезков называют диаграммой ЧУМа S. При этом a < в тогда и только тогда, когда от “точки” а можно перейти к “точки” в по некоторой “восходящей” ломаной. В силу этого обстоятельства, любое конечное ЧУМ можно отождествить с его диаграммой.

Здесь задано диаграммой ЧУМ

S = {m, m, },в которой m< , m< , m< m< , m< m< , m< .

Элемент m называется наименьшим элементом ЧУМа, если для любого x A всегда m ? x.

Понятно, что наименьший элемент является минимальным, но обратное не верно: не всякий минимальный элемент является наименьшим. Наименьший элемент (если такой имеется) только один. Аналогично определяется наибольший элемент.

Это ЧУМ, элементы которого попарно несравнимы. Такие частично упорядоченные множества называются антицепями.

Эта цепь с наименьшим и наибольшим элементом. Где 0 - наименьший элемент, а 1 - наибольший элемент.

Пусть М - подмножество частичного упорядоченного множества А. Элемент а A называют нижней гранью множества М, если а? х для любого x М.

Наибольшая из всех нижних граней множества М, если она существует, называется точной нижней гранью множества М и обозначают inf M.

Пусть < А, ? > - произвольный ЧУМ. Элемент сA называется точной нижней гранью элементов a,в A, если с = inf{a,в}.

Замечание 1.

Не во всяком ЧУМ для любых двух элементов существует точная нижняя грань.

Покажем это на примере.

Для {a;c},{d;e} нет нижней грани,

inf{a;в}=d, inf{в;c}=e.

Приведем пример ЧУМ, у которого для любых элементов существует точная нижняя грань.

inf{a;в}=d, inf{a;d}=d, inf{a;0}=0, inf{a;c}=0, inf{a;e}=0,

inf{в;c}=e, inf{в;e}=e, inf{в;d}=d,

inf{c;e}=c, inf{c;0}=0, inf{c;d}=0,

inf{d;e}=0, inf{d;0}=0,

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

Пример 10.

Приведем пример ЧУМ, которое не является полурешеткой.

Пусть < N, ? > - линейно - упорядоченное множество натуральных чисел и e,eN. На множестве N=N{ e ,e} определим бинарное отношение? , пологая что x ? y, если x,y N, где x ? y, или если x N, y { e ,e}. Также считаем по определению: e ? e ,e? e.

Диаграмма этого ЧУМ следующая:

Любое натуральное число n ? e и n ? e, но в N нет наибольшего элемента, следовательно, N - ЧУМ, но не полурешетка.

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

Для этого введем некоторые дополнительные алгебраические понятия. Как известно, полугруппой называется непустое множество с заданной на нем ассоциативной бинарной алгебраической операцией.

Произвольную полугруппу обычно обозначают S (semigroup).

Определение. Элемент eS называется идемпотентом, если

e= e, то есть e · e = e.

Пример 11.

Полугруппа < N; · > ? обладает единственным идемпотентом 1.

Полугруппа < Z; + > ? обладает единственным идемпотентом 0.

Полугруппа < N; + > ? не имеет идемпотента, т.к. 0N.

Для любого непустого множества X, как обычно, через обозначается множество всех подмножеств множества X - булеан множества X. Полугруппа <В;> - такова, что каждый ее элемент идемпотентен.

Полугруппа называется идемпотентной полугруппой или связкой, если каждый ее элемент является идемпотентным. Таким образом, примерами связки является всякий булеан относительно объединения.

Пример 12.

Пусть X - произвольное множество.

B- множество всех подмножеств множества Х.

B- называется булеаном на множестве Х.

Если Х = {1,2,3} , то

B = {O,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}.

Так как пересечение двух подмножеств множества Х вновь является подмножеством в Х, то имеем группоид < В;> , более того, это полугруппа и даже связка, так как

А В и А= АА =А.

Точно также, имеем связку <; В > .

Коммутативная связка называется полурешеткой.

Пример 13.

Пусть Х = {1,2,3}, построим диаграмму < В; >.

Приведем примеры ЧУМ, но не полурешетки.

Пример 14.

ЧУМ с двумя нижними гранями е и d , которые между собой не сравнимы: е||d. Следовательно, inf{a;с} не существует.

Пример 15.

ЧУМ с двумя нижними гранями с и d, которые между собой несравнимы: с||d. Следовательно, inf{a;в} не существует.

Приведем примеры полурешеток.

Пример 16.

Диаграмма:

inf{a;в}=в, inf{a;с}=с, inf{a;d}=d,

inf{в;c}=d, inf{в;d}=d,

Пример 17.

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

inf{a;в}=в, inf{a;с}=с, inf{в;c}=с.

Теорема 1.

Пусть ~~- полурешетка. Тогда ~~коммутативная связка, где~~~~

aв = inf {a,в} (*).

Доказательство:

Нужно доказать, что в ~~выполняются следующие тождества:~~

(1) x y = y x

(2) (x y) z = x (y z)

1) Согласно равенству(*)

x y = inf (x,y) = inf (y,x) = y x

2) Обозначим а = (x y) z, в = x (y z)

Докажем, что а = в.

Для этого достаточно доказать, что

в? а (5) (в силу антисимметричности)

Обозначим

с = x y , d = y z

По смыслу, а точная нижняя грань между с и z

а? с, а? z , c ? x,

следовательно, в силу транзитивности a ? x.

Аналогично, а? y, т.е. а - общая нижняя грань для y и z. А d - их точная нижняя грань.

Следовательно, a ? d, но в = inf {x,d}.

Из неравенства a ? x , a ? d следует, что а - некоторая общая нижняя грань для х и d, а в - их точная нижняя грань, следовательно,

а? в (4) доказано.

Аналогично доказывается (5).

Из (4) и (5) , в виду антисимметричности, заключаем, что а = в.

Этим мы доказали ассоциативность операции ().

3) Имеем x х = inf {x,x} = x.

Равенство выполняется за счет рефлексивности: х? х.

Т.о. построенная алгебра ~~будет коммутативной идемпотентной полугруппой, т.е. коммутативной связкой.~~

Теорема 2.

Пусть ~~- коммутативная идемпотентная полугруппа, тогда бинарное отношение? на S, определяемое равенство~~

? = {(a,в) S?S | a·в = а},

является частичным порядком. При этом ЧУМ ~~является полурешеткой.~~

Доказательство:

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

По условию ~~удовлетворяет трем тождествам:~~

(1) х= х

(2) х·y = y·x

(3) (x·y)·z = x·(y·z)

Тогда х·х = х= х - в силу (1). Поэтому х? х.

2) антисимметричность? .

Пусть х? у и у? х, тогда по определению,

(4) х·у = х

(5) у·х = у

отсюда, благодаря коммутативности, имеем х = у.

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

Пусть х? у и у? z тогда, по определению,

(6) х·у = х

(7) у·z = у

Имеем x·z = (x·y)·z x·(y·z) х·у х

Итак, x·z = x, то есть х? z.

Таким образом, имеем ЧУМ ~~. Остается показать, что для любых (а, в)S существует inf{а,в}.~~

Берем произвольные а,в S и докажем, что элемент с = а·в является inf{а,в}, т.е с = inf{а,в}.

В самом деле,

с·а = (а·в)·а а·(а·в) (а·а)·в а·в = с,

Аналогично, с·в = (а·в)·в а·(в·в) а·в = с,

Итак, с - общая нижняя грань {а,в}.

Докажем ее точность.

Пусть d - некоторая общая нижняя грань для а и в:

(8) d ? a

(9) d ? в

(10) d·a = d

(11) d·в = d

d·c = d·(а·в) (d·а)·в d·в d,

d·c = d, следовательно, d ? c.

Вывод: с = inf{a,в}.

Доказанные теоремы 1 и 2 позволяют смотреть на полурешетки с двух точек зрения: как на ЧУМ, и как на алгебре (идемпотентные коммутативные полугруппы).

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

В качестве абстрактного примера можно привести совокупность подмножеств множества из трех элементов $\{ x, y, z\}$ , упорядоченное по отношению включения.

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

Определение и примеры

Порядком , или частичным порядком , на множестве $M$ называется бинарное отношение $\varphi$ на $M$ (определяемое некоторым множеством $R_{\varphi} \subset M \times M$ ), удовлетворяющее следующим условиям :

Рефлексивность : $\forall a \; (a \varphi a)$

Транзитивность : $\forall a, b, c \; (a \varphi b) \wedge (b \varphi c) \Rightarrow a \varphi c$

Антисимметричность : $\forall a, b \; (a \varphi b) \wedge (b \varphi a) \Rightarrow a = b$

Множество $M$ , на котором задано отношение частичного порядка, называется частично упорядоченным (англ. partially ordered set, poset ). Если быть совсем точным , то частично упорядоченным множеством называется пара $\langle M, \varphi \rangle$ , где $M$ - множество, а $\varphi$ - отношение частичного порядка на $M$ .

Терминология и обозначения

Отношение частичного порядка обычно обозначают символом $\leqslant$ , по аналогии с отношением «меньше либо равно» на множестве действительных чисел. При этом, если $a \leqslant b$ , то говорят, что элемент $a$ не превосходит $b$ , или что $a$ подчинен $b$ .

Если $a \leqslant b$ и $a \neq b$ , то пишут $a < b$ , и говорят, что $a$ меньше $b$ , или что $a$ строго подчинен $b$ .

Иногда, чтобы отличить произвольный порядок на некотором множестве от известного отношения «меньше либо равно» на множестве действительных чисел, вместо $\leqslant$ и $<$ используют специальные символы $\preccurlyeq$ и $\prec$ соответственно.

Строгий и нестрогий порядок

Отношение, удовлетворяющее условиям рефлексивности, транзитивности и антисимметричности, также называют нестрогим , или рефлексивным порядком . Если условие рефлексивности заменить на условие антирефлексивности :
$\forall a \; \neg (a \varphi a)$
то получим определение строгого , или антирефлексивного порядка .

Если $\leqslant$ - нестрогий порядок на множестве $M$ , то отношение $<$ , определяемое как:
$a < b \; \overset{\mathrm{def}}{\Longleftrightarrow} \; (a \leqslant b) \wedge (a \neq b)$
является строгим порядком на $M$ . Обратно, если $<$ - строгий порядок, то отношение $\leqslant$ , определенное как
$a \leqslant b \; \overset{\mathrm{def}}{\Longleftrightarrow} \; (a < b) \vee (a = b)$
является нестрогим порядком.

Поэтому все равно - задать на множестве нестрогий порядок, или строгий порядок. В результате получится одна и та же структура. Разница только в терминологии и обозначениях.

Примеры

$\vartriangleright$ Как уже указывалось выше, множество действительных чисел $\mathbb{R}$ частично упорядочено по отношению «меньше либо равно» $\leqslant$ .

$\vartriangleright$ Пусть $M$ - множество всех действительнозначных функций, определенных на отрезке , то есть функций вида
f \colon \to \mathbb{R}

Введем отношение порядка $\leqslant$ на $M$ следующим образом. Мы скажем, что $f \leqslant g$ , если для всех $x \in$ выполнено неравенство $f(x) \leqslant g(x)$ . Очевидно, введенное отношение в самом деле является отношение частичного порядка.

$\vartriangleright$ Пусть $M$ - некоторое множество. Множество $\mathcal{P}(M)$ всех подмножеств $M$ (так называемый булеан), частично упорядочено по включению $M \subseteq N$ .

$\vartriangleright$ Множество всех натуральных чисел $\mathbb{N}$ частично упорядочено по отношению делимости $m \mid n$ .

Связанные определения

Несравнимые элементы

Если $a$ и $b$ - действительные числа, то имет место одно и только из соотношений:
a < b, \qquad a=b, \qquad b

В случае, если $a$ и $b$ - элементы произвольного частично упорядоченного множества, то существует четвёртая логическая возможность: не выполнено ни одно из указанных трех соотношений. В этом случае элементы $a$ и $b$ называются несравнимыми . Например, если $M$ - множество действительнозначных функций на отрезке , то элементы $f(x) = x$ и $g(x) = 1-x$ будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина «частично упорядоченное множество» .

Минимальный/максимальный и наименьший/наибольший элементы

Основные статьи : Максимум (математика) , Минимум (математика)

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

Элемент $a \in M$ называется минимальным (англ. minimal element ), если не существует элемента $b < a$ . Другими словами, $a$ - минимальный элемент, если для любого элемента $b \in M$ либо $b>a$ , либо $b=a$ , либо $b$ и $a$ несравнимы. Элемент $a$ называется наименьшим (англ. least element, lower bound (opp. upper bound) ), если для любого элемента $b \in M$ имеет место неравенство $b \geqslant a$ . Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент $a$ может и не быть наименьшим, если существуют элементы $b$ , не сравнимые с $a$ .

Очевидно, что если в множестве существует наименьший элемент, то он единственен. А вот минимальных элементов может быть несколько. В качестве примера рассмотрим множество $\mathbb{N}\setminus \{ 1 \} = \{ 2, 3, \ldots \}$ натуральных чисел без единицы, упорядоченное по отношению делимости $\mid$ . Здесь минимальными элементами будут простые числа, а вот наименьшего элемента не существует.

Аналогично вводятся понятия максимального (англ. maximal element ) и наибольшего (англ. greatest element ) элементов.

Верхние и нижние грани

Пусть $A$ - подмножество частично упорядоченного множества $\langle M, \leqslant\rangle$ . Элемент $u \in M$ называется верхней гранью (англ. upper bound ) $A$ , если любой элемент $a \in A$ не превосходит $u$ . Аналогично вводится понятие нижней грани (англ. lower bound ) множества $A$ .

Любой элемент, больший, чем некоторая верхняя грань $A$ , также будет верхней гранью $A$ . А любой элемент, меньший, чем некоторая нижняя грань $A$ , также будет нижней гранью $A$ . Эти соображения ведут к введению понятий наименьшей верхней грани (англ. least upper bound ) и наибольшей нижней грани (англ. greatest lower bound ).

Специальные типы частично упорядоченных множеств

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

Основная статья : Линейно упорядоченное множество

Пусть $\langle M, \leqslant\rangle$ - частично упорядоченное множество. Если в $M$ любые два элемента сравнимы, то множество $M$ называется линейно упорядоченным (англ. linearly ordered set ). Линейно упорядоченное множество также называют совершенно упорядоченным (англ. totally ordered set ), или просто, упорядоченным множеством . Таким образом, в линейно упорядоченном множество для любых двух элементов $a$ и $b$ имеет место одно и только одно из соотношений: либо $a, либо a=b, либо b .$

Также всякое линейно упорядоченное подмножество частично упорядоченного множества называют цепью (англ. chain ), то есть цепь в частично упорядоченном множестве $\langle M, \leqslant \rangle$ - такое его подмножество, в котором любые два элемента сравнимы.

Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке (при условии $a), булеан \mathcal{P}(M) (при |M|\geqslant 2), натуральные числа с отношением делимости - не являются линейно упорядоченными.$

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

Вполне упорядоченные множества

Основная статья : Вполне упорядоченное множество

Линейно упорядоченное множество называется вполне упорядоченным (англ. well-ordered ), если каждое его непустое подмножество имеет наименьший элемент . Соответственно, порядок на множестве называется полным порядком (англ. well-order ).

Классический пример вполне упорядоченного множества - множество натуральных чисел $\mathbb{N}$ . Утверждение о том, что любое непустое подмножество $\mathbb{N}$ содержит наименьший элемент, равносильно принципу математической индукции. В качестве примера линейно упорядоченного, но не вполне упорядоченного множества можно привести множество неотрицательных чисел $\mathbb{R}_{+} = \{ x: x \geqslant 0\}$ . Действительно, его подмножество $\{x: x > 1\}$ не имеет наименьшего элемента.

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

Теоремы о частично упорядоченных множествах

К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа и лемма Куратовского-Цорна . Эти утверждения эквивалентны между собой и существенно опираются на так называемую аксиому выбора (в действительности, эквивалентны аксиоме выбора).

Примечания

Литература

Александров П. С. Введение в теорию множеств и общую топологию. - М.: «НАУКА», 1977. - 368 с.

Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. - 7-е изд. - М.: «ФИЗМАТЛИТ», 2004. - 572 с. - ISBN 5-9221-0266-4

Хаусдорф Ф. Теория множеств. - 4-е изд. - М.: УРСС, 2007. - 304 с. - ISBN 978-5-382-00127-2

См. также

Решетка

Порядковое число

Предпорядок

cs:Uspořádaná množinaeo:Partordohu:Részbenrendezett halmazko:부분순서 nl:Partiële orde oc:Relacion d"òrdre ro:Relaţie de ordine sl:Relacija urejenostizh:偏序关系

Уведомление : Предварительной основой данной статьи была аналогичная статья в http://ru.wikipedia.org , на условиях CC-BY-SA, http://creativecommons.org/licenses/by-sa/3.0 , которая в дальнейшем изменялась, исправлялась и редактировалась.

Множество М, в котором введено отношение порядка, т. е. для некоторых пар элементов х, у установлено абстрактное отношение х должно следовать х, введенным выше (тогда его называют строгим порядком), отношение связано следующим образом: или
Примеры. 1. Мн-во действительных чисел с обычным упорядочением; означает, что число положительно. В этом случае для любой пары элементов либо у, либо
Мн-во всех матриц с действительными элементами; означает, что для всех но . Очевидно, что существуют «несравнимые» матрицы , для которых ни ни
Мн-во всех непрерывных ф-ций на отрезке означает, что для всех но
В этом случае также существуют пары для которых ни ни
Понятие частичной упорядоченности важно в сочетании с алгебраическими структурами (напр., абелевой группой), или алгебраическими и топологическими (в теории частично упорядоченных линейных пространств). Частичная упорядоченность в киберн. системах часто имеет характер иерархического подчинения. Простейшей моделью такого подчинения является отношение подчинения между гранями симплекса: означает, что грань х является собственной гранью грани у.
Если М - Ч. у. м. с порядком то положив а -К b в том и только том случае, когда определим на М новый порядок. Возникающее при этом Ч. у. двойственным (или дуальным) к М. Для всякого высказывания о Ч. у. м. существует двойственное высказывание, получаемое заменой символа Напр., нижний конус подмн-ва А в Ч. у. м. М определяется условием а для всех а верхний конус условием: для всех Элемент максимальным, если или минимальным, если а. Элемент а в Ч. у. наибольшим (или единицей), если а для всех . Двойственным образом определяется наименьший элемент (или нуль). Конечно, всякий наибольший (наименьший) элемент максимален (минимален), но не наоборот. Если среди элементов нижнего конуса отличных от а, существует наибольший элемент b, то говорят, что а покрывает b (или что b непосредственно предшествует а, или а непосредственно следует за b). Если Ч. у. м. М имеет «0» и «1», то ряд где покрывает наз. композиционным рядом.
В исследовании Ч. у. м. и их применений чрезвычайно полезен принцип двойственности: если справедлива какая-либо теорема о Ч. у. сформулированная в общелогических терминах и терминах порядка, то справедлива и двойственная ей теорема.
Если для любых элементов х и у из Ч. у. м. М имеет место одно и только одно из трех утверждений: то множество М наз. линейно упорядоченным (или совершенно упорядоченным, а также цепью). Всякий минимальный (максимальный) элемент линейно упорядоченного мн-ва является наименьшим (наибольшим). Вообще говоря, подмножества линейно упорядоченного мн-ва не имеют миним. элементов; напр., во мн-ве упорядоченном обычным отношением «меньше», часть не имеет миним. элемента. Если каждая часть М имеет миним. элемент, М. наз. вполне упорядоченным множеством. Напр., мн-во натуральных чисел вполне упорядочено, а мн-во Z всех целых чисел - нет. По теореме Цермело (1904), любое мн-во может быть вполне упорядочено, т. е. в нем можно ввести отношение порядка, обладающее описанным выше свойством. Ч. у. изоморфными, если существует такое биективное отображение что из следует Если М частично упорядочено, то для любого подмножество отрезком М. Для двух вполне упорядоченных мн-в М и N можно показать, что либо М изоморфно отрезку N, либо - отрезку М: если верно то и другое, то М изоморфно N. Изоморфизм есть эквивалентности отношение между вполне упорядоченными мн-вами; классы эквивалентности наз. ординальными (порядковыми) числами. обозначает ординальное число, соответствующее М. Для ординальных чисел вводится отношение если М изоморфно отрезку N, но не N. Конечное ординальное число есть класс эквивалентности, содержащий отрезок натурального ряда , с

естественным упорядочением. Наименьшее бесконечное ординальное число со есть класс, содержащий весь натуральный ряд с естественным упорядочением. Порядковые числа важны как средство доказательства по методу трансфинитной индукции, который является естественным обобщением обычного метода полной индукции. Пусть требуется доказать предложение Р (а), формулировка которого содержит произвольное ординальное число а. Принцип трансфинитной индукции состоит в том, что если верно Р (1) и из справедливости для следует справедливость Р (а), то Р (а) верно для всех а. Этот принцип можно доказать как теорему в рамках аксиоматической теории Применение его требует предварительного полного упорядочения мн-ва объектов, для которых доказывается предложение, что приводит к их трансфинитной нумерации; такое упорядочение возможно в силу аксиомы выбора Цермело. С помощью трансфинитной индукции доказывается ряд важных теорем математики, напр., теорема Хана-Банаха в функциональном анализе. Важным является также построение различных матем. объектов с помощью трансфинитной индукции. Применение трансфинитной индукции часто заменяется подходом, основанным на теореме Цорна. Пусть М - Ч. у. м., X; если и для всех , то у наз. мажорантой X. Если всякое линейно упорядоченное подмножество имеет мажоранту, М наз. индуктивным. Теорема Цорна о том, что всякое индуктивное упорядоченное мн-во обладает по крайней мере одним максимальным элементом, широко применяется в алгебре, функциональном анализе и др. областях математики. Наглядное представление об этой теореме дает упорядочение подмножеств данного мн-ва «по вложению» означает .
Доказательства с помощью теоремы Цорна состоят в том, что ищется макс. подмножество данного мн-ва М, обладающее некоторым свойством, а затем доказывается, что предположение приводит к противоречию; отсюда заключают, что требуемым свойством обладает все мн-во М.
Лит.: Alexandroff P. Diskrete Raume. «Математический сборник», 1937, т. 2, в. 3; Канторович Л. В., Вулих Б. 3., Пинскер А. Г. Функциональный анализ в полуупорядоченных пространствах. М.- Л., 1950 [библиогр. с. 543-546]; Курош А. Г. Лекции по общей алгебре. М., 1962 [библиогр. с. 383-387]; Скорняков Л. А. Элементы теории структур. М., 1970 [библиогр. с. 145]; Риге Ж. Бинарные отношения, замыкания, соответствия Галуа. В кн.; Кибернетический сборник, в. 7. М., 1963; Бурбаки Н. Начала математики, ч. 1. Основные структуры анализа, кн. 2. Теория множеств. Пер. с франц. М., 1965. А. В. Гладкий.

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

обладает хотя бы одним минимальным во множестве
элементом.
2) Условие обрыва убывающих цепей . Всякая строго убывающая цепь элементов
частично упорядоченного множества
обрывается на конечном месте. Другими словами, для всякой убывающей цепи
существует такой индекс, при котором эта цепь стабилизируется, т.е.
.
3) Условие индуктивности. Все элементы частично упорядоченного множества
обладают некоторым свойством, если этим свойством обладают все минимальные элементы этого множества (если они существуют) и если из справедливости свойствадля всех элементов, строго предшествующих некоторому элементу, может быть выведена справедливость этого свойства для самого элемента.
Теорема 1: Условия минимальности, обрыва убывающих цепей и индуктивности - эквивалентны между собой.
Доказательство: 1) Сначала покажем, что из условия минимальности вытекает условие индуктивности. Действительно, пусть частично упорядоченное множество
удовлетворяет условию минимальности и пусть в нем для некоторого свойствавыполняются посылки условия индуктивности. Если при этом во множестве
существуют элементы, которые не обладают свойством, то пустьбудет одним из минимальных среди таких элементов (существование такого элементаобеспечивается условием минимальности). Элементне может быть минимальным во всем множестве
, что следует из посылки условия индуктивности, а так как все элементы, строго предшествующие элементу, свойствомуже обладают, то по условию индуктивности и элементобязан обладать этим свойством. Мы пришли к противоречию.
2) Покажем, что из условия индуктивности вытекает условие обрыва убывающих цепей. Пусть частично упорядоченное множество
удовлетворяет условию индуктивности. Применим это условие к следующему свойству: элементобладает свойством, если всякая строго убывающая цепь элементов, начинающаяся элементом, обрывается на конечном месте. Этим свойством обладают, очевидно, все минимальные элементы множества
, если они существуют. С другой стороны, пусть все элементы, строго предшествующие элементу, обладают свойством. Это значит, что все убывающие цепи, начинающиеся с элементов, строго предшествующих элементу, обрываются на конечном месте, но тогда и всякая строго убывающая цепь, начинающаяся элементом, обрывается. Из условия индуктивности следует, что свойствомобладают все элементы множества
, т.е. во множестве
обрывается всякая строго убывающая цепь.
3) Из условия обрыва убывающих цепей вытекает условие минимальности. Предположим, что частично упорядоченное множество
условию минимальности не удовлетворяет, пусть найдется его непустое подмножество
, которое не имеет минимальных элементов. Пользуясь аксиомой выбора (см. далее) отметим по одному элементу в каждом непустом подмножестве из множества
, а затем построим последовательность элементов
следующим образом. В качествевыберем элемент, отмеченный в подмножестве
. Если элемент, уже выбран и
, то в качестве следующего элемента
берем элемент, отмеченный в непустом (т.к.
не имеет минимальных элементов) множестве элементов из
, строго предшествующих. Построенная последовательность является бесконечной строго убывающей цепью. Значит, множество
не удовлетворяет условию обрыва убывающих цепей. Теорема доказана.
Определение 3: Частично упорядоченное множество называется структурой или решёткой , если в нем любое двухэлементное подмножество имеет точную верхнюю границу
и точную нижнюю границу
. Точная верхняя граница
для элементовиобладает свойствами:
, и
причем
, если- любая другая верхняя граница этих элементов. Аналогично определяется точная нижняя граница.
Определение 4: Решетка называется дистрибутивной , если операции
и
связаны дистрибутивными законами, т.е. выполнены соотношения:
Замечание: Указанные соотношения называются двойственными. Отметим, что в решетке одно из этих соотношений является следствием другого.
Определение 5: Нулем и единицей решетки называются его наименьший и наибольший элементы, если они существуют.
Определение 6: В решетке можно определить следующим образом дополнение: является дополнением для(а- дополнением для), если одновременно
и
.
Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй.
Отметим, что теория решеток и теория булевых алгебр – это самостоятельные разделы алгебры.
Определение 8: Линейно упорядоченное множество, удовлетворяющее условию минимальности (а значит и двум другим условиям, эквивалентным с ним), называется вполне упорядоченным .
Примером вполне упорядоченного множества служит множество натуральных чисел с естественным порядком. Всякое подмножество вполне упорядоченного множества само вполне упорядочено. Из определения вполне упорядоченного множества следует, что оно обладает единственным минимальным элементом.
Во вполне упорядоченном множестве для всякого элемента существует элемент, непосредственно следующий за. Элементможет не иметь, однако, непосредственно предшествующего элемента; в этом случае он называйсяпредельным элементом .
При изучении бесконечных множеств часто приходится пользоваться следующей аксиомой, которую называют аксиомой выбора.
Аксиома: Если дано множество
, то существует функция, сопоставляющая каждому непустому подмножеству
определенный элемент
этого подмножества.
Другими словами, функция отмечает по одному элементу в каждом из непустых подмножеств множества
.
Вопрос о логических основах этой аксиомы и о законности ее использования относится к числу самых трудных и спорных вопросов обоснования теории множеств. Многие из теорем, доказанные с помощью аксиомы выбора совершенно противоречили наглядности. Поэтому один из видных математиков XX века Бертран Рассел так высказался об этой аксиоме: «Сначала она кажется очевидной; но чем больше вдумываешься в нее, тем более странными кажутся выводы из этой аксиомы; под конец же перестаешь понимать, что же она означает».
Имеется целый ряд утверждений, каждое из которых эквивалентно аксиоме выбора. Например, следующие теоремы.
Теорема Цериело: Всякое множество можно вполне упорядочить.
Теорема Хауздорфа: Всякая цепь частично упорядоченного множества содержится в некоторой максимальной цепи.