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

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 минимальный.

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

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

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

2) если и , то ;

3) если и , то .

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

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

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

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

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

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

Множество .

Множество .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

$\backslash vartriangleright$ Пусть $M$ - множество всех действительнозначных функций, определенных на отрезке $$, то есть функций вида

f \colon \to \mathbb{R}

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

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

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

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

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

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

a < b, \qquad a=b, \qquad b

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке $$ (при условии

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

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

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

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

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

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

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

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

Примечания

Литература

• Александров П. С. Введение в теорию множеств и общую топологию. - М.: «НАУКА», 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. В математике: совокупность элементов, объединенных........
Толковый словарь Ожегова