Вполне упорядоченное множество действительные числа. Частично упорядоченное множество

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

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

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

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

И. В. Ященко Парадоксы теории множеств

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

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

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

1) a Ј a для любого a О M ;

2) если a Ј b и b Ј c , то a Ј c ;

3) если a Ј b и b Ј a , то a = b .

Отношением порядка являются, например, обычное сравнение чисел на прямой (Ј ), вложенность множеств (Н ), отношение "делит" (a | b a делит b ).

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

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

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

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

0 ° . Пустое множество Ж .

1 ° . Множество {Ж }.

2 ° . Множество {Ж , {Ж }}.

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

3 ° . {Ж , {Ж }, {Ж ,{Ж }}}.

..............................................

n ° . {Ж , {Ж }, {Ж ,{Ж }}, ...,(n - 2) ° , (n - 1) ° } – n -е множество получается объединением предыдущих n - 1 множеств.

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

Все эти множества составляют множество натуральных чисел N . Подумайте, почему для существования этого множества необходима аксиома бесконечности (см. аксиому бесконечности). Элемент множества M называется наименьшим , если он меньше любого другого элемента M . Можно также определить минимальный элемент M : это такой элемент, меньше которого в множестве M нет. Важно, что в случае, когда M не является линейно упорядоченным, понятия наименьшего и минимального элементов различны. В частности, наименьших элементов всегда не более одного, а для минимальных это не так. На рис. 4 каждый из элементов a 15 и a 51 минимальный.

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

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