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

Главная » Частично упорядоченное множество. Теоремы о частично упорядоченных множествах.

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

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

1) для любого ;

2) если и , то ;

3) если и , то .

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

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

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

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

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

Пустое множество .

Множество .

Множество .

Заметим, что эти множества упорядочены относительно отношения принадлежности (). Нетрудно догадаться, как для такого отношения порядка выглядит вполне упорядоченное множество из трех элементов:

Е множество получается объединением предыдущих множеств.

Определение . Построенные таким образом множества называются натуральными числами.

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

Михаил Раскин

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

Виктор Викторов

Основные понятия, операции над множествами, тождества, свойства дополнения, правило Де Моргана, свойства симметрической разности; отображение (функция), факторотображение, отношение эквивалентности, парадокс брадобрея; упорядоченные множества, минимальный, наименьший, максимальный и наибольший элементы в упорядоченном множестве, мажоранта и миноранта; аксиома выбора, вполне упорядоченное множество.

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

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

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

Порядком , или частичным порядком , на множестве называется бинарное отношение на (определяемое некоторым множеством ), удовлетворяющее следующим условиям :

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

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

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

Если и , то пишут , и говорят, что меньше , или что строго подчинен .

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

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

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

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

Если — нестрогий порядок на множестве , то отношение , определяемое как:

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

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

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

Примеры

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

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

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

Если и — действительные числа, то имеет место только одно из следующих соотношений:

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

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

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

Элемент называется минимальным (англ. minimal element ), если не существует элемента . Другими словами, — минимальный элемент, если для любого элемента либо , либо , либо и несравнимы. Элемент называется наименьшим (англ. least element, lower bound (opp. upper bound) ), если для любого элемента имеет место неравенство . Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент может и не быть наименьшим, если существуют элементы , не сравнимые с .

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

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

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

Пусть — подмножество частично упорядоченного множества . Элемент называется верхней гранью (англ. upper bound ) , если любой элемент не превосходит . Аналогично вводится понятие нижней грани (англ. lower bound ) множества .

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

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

Для элемента частично упорядоченного множества верхним множеством (англ. upper set, upset ) называется множество всех элементов, которым предшествует ().

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

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

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

В качестве абстрактного примера можно привести совокупность подмножеств множества из трех элементов \{ 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 , которая в дальнейшем изменялась, исправлялась и редактировалась.

множество Рс заданным на нем бинарньш отношением, удовлетворяющим условиям: 4) в любом непустом подмножестве ~ существует такой элемент а, что для всех; таким образом В. у. м.- линейно упорядоченное множество, удовлетворяющее условию минимальности. Понятие В. у. м. было введено Г. Кантором . Примером В. у. м. служит естественным образом упорядоченное множество натуральных чисел. С другой стороны, отрезок действительных чисел с естественным порядком не является В. у. м. Любое подмножество В. у. м. само вполне упорядоченное. Декартово произведение конечного числа В. у. м. вполне упорядочено отношением лексикографического порядка. Линейно упорядоченное множество является вполне упорядоченным тогда и только тогда, когда оно не содержит подмножества, антиизоморфного (см. Антиизоморфизм частично -упорядоченных множеств) множеству натуральных чисел. Наименьший элемент В. у. м. Рназ. нулем (и обозначается 0). Для любого элемента множество наз. начальным отрезком множества Р. Для всякого элемента а, не являющегося наибольшим в Р, существует элемент, непосредственно следующий за ним; его принято обозначать a+1. Элемент В. у. м., не имеющий непосредственно предшествующего, называется предельным. Теорема о сравнении. Для любых двух В. у. м. P1 и P2 имеет место одна и только одна из следующих ситуаций: 1) Р 1 изоморфно Р 2 ,2) Р 1 изоморфно некоторому начальному отрезку множества Р 2 ,3) Р 2 изоморфно начальному отрезку множества P1. Принимая в числе аксиом теории множеств выбора аксиому, можно доказать, что на всяком непустом множестве можно ввести отношение порядка, превращающее его во В. у. м. (т. е. всякое непустое множество можно вполне упорядочить). Эта теорема, называемая теоремой Цермело, на самом деле эквивалентна аксиоме выбора. Теорема Цермело и теорема о сравнении служат основанием для сравнения множеств по их мощности. Порядковые типы В. у. м. наз. трансфинитами, или трансфинитными числами. Лит.: Cantor G., «Math. Ann.», 1883, Bd 21, S. 51-8; Александров П. С., Введение в общую теорию множеств и функций, М.-Л., 1948; ХаусдорфФ., Теория множеств, пер. с нем., М.-Л., 1937; Бурбаки Н., Теория множеств, пер. с франц., М., 1965; Куратовский К., Мостовский А., Теория множеств, пер с англ., М., 1970. Б. А. Ефимов, Т. С. Фофанова.

Смотреть значение Вполне Упорядоченное Множество в других словарях

Множество — масса
уймища
бездна
пропасть
тьма
тьма-тьмущая
тьма тем
куча
воз
вагон
прорва
гибель
сила
Словарь синонимов

Вполне — нареч. полно, сполна, без недостатка, без обмера. Меряй вполне. | Избыточно, в довольстве, в достатке. Они живут вполне. | Все без остатка, сполна, совсем, вовсе, вдосталь………
Толковый словарь Даля

Множество — множить и пр. см. многий.
Толковый словарь Даля

Множество — множества, ср. (книжн.). 1. только ед. Неопределенно большое количество, число чего-н. рабочих. фактов. Я слышал в жизни множество отличнейших певцов. Некрасов. 2. Совокупность……..
Толковый словарь Ушакова

Вполне Нареч. — 1. Полностью, совершенно, всецело.
Толковый словарь Ефремовой

Не Вполне Нареч. Разг. — 1. Не в полной мере.
Толковый словарь Ефремовой

Вполне — нареч. Совершенно, очень, в полной мере. удовлетвориться объяснением. достойный человек. Пускай я радости вкушаю не вполне. Пушкин.
Толковый словарь Ушакова

Вполне — нареч. Совершенно, полностью, в полной мере. В. доволен. В. готов. В. определённый ответ. В. достаточно.
Толковый словарь Кузнецова

Множество — -а; ср.
1. Очень большое количество, число кого-, чего-л. М. народа. М. фактов. Вырастить м. цветов. Доказательства представлены во множестве. Великое м. примеров (очень……..
Толковый словарь Кузнецова

Достижимое Множество — Возможный ожидаемый доход и стандартные пары отклонений всех портфелей, которые можно составить из данного набора активов.
Экономический словарь

Достижимое Множество (feasible Set (или Opportunity Set)) — множество портфелей, которые можно сформировать из ценных бумаг, рассматриваемых инвестором.
Экономический словарь

Множество — совокупность элементов, параметров, объединенных по какому-либо
признаку
Экономический словарь

Множество Допустимых Решений — область, в пределах которой может быть произведен
выбор решений, ограниченный поставленными целями и имеющимися ресурсами.
Экономический словарь

Универсальное Множество — , в математике — МНОЖЕСТВО, содержащее все элементы с определенным свойством. Так же называют гипотетическое множество, которое должно включать в себя все возможные……..
Научно-технический энциклопедический словарь

Множество — в математике, см. Множеств теория.

Несчетное Множество — понятие теории множеств; бесконечное множество,мощность которого больше, чем мощность счетного множества. Напр.,множество всех действительных чисел — несчетное множество.
Большой энциклопедический словарь

Пустое Множество — понятие теории множеств; пустое множество — множество,не содержащее ни одного элемента; обозначается? или 0. Понятие пустоемножество (подобно понятию «нуль») возникает……..
Большой энциклопедический словарь

Счетное Множество — понятие теории множеств; счетное множество -бесконечное множество, элементы которого возможно занумероватьнатуральными числами. Множество всех рациональных чисел……..
Большой энциклопедический словарь

Несколько Или Множество Необходимых Причин — каузальная схема, которая предусматривает, по крайней мере, две причины для объяснения происходящего.
Социологический словарь

Несколько Или Множество Удовлетворительных Причин — каузальная схема, которая срабатывает в случае, если при отсутствии всякой предварительной информации ситуация предоставляет возможность самых различных интерпретаций,……..
Социологический словарь

Класс, Множество (в Логике И Математике) — — конечная или бесконечная совокупность объектов, выделенная по общему для них признаку (свойству или отношению), мыслимая как нечто целое. Объекты, составляющие К.,……..
Философский словарь

Нечеткое Множество — — множество с нечеткими границами, когда переход от принадлежности элементов множеству к непринадлежности их множеству происходит постепенно, нерезко. В классической……..
Философский словарь

Нормальное Множество — см.: Противоречие в явном определении.
Философский словарь

ВПОЛНЕ — ВПОЛНЕ, нареч. Совершенно, полностью. В. доволен.
Толковый словарь Ожегова

МНОЖЕСТВО — МНОЖЕСТВО, -а, ср. 1. Очень большое количество, число кого-чего-н. М. людей. М. случаев. Всяких запасов во множестве. 2. В математике: совокупность элементов, объединенных……..
Толковый словарь Ожегова

Поделиться:

Оставьте комментарий

одиннадцать + семь =