Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Упорядоченные множества

Упорядоченные множества


Множество вместе с заданным на нем отношением порядка называют упорядоченным множеством.


Отношение порядка будем, как правило, обозначать [math]\leqslant[/math] (или значками [math]\preccurlyeq,\,\sqsubseteq[/math] и т.п., похожими на [math]\leqslant[/math]). При этом следует понимать, что даже на некотором множестве [math]S \subseteq \mathbb{R}[/math] рассматриваться может любое отношение порядка, а не только естественный числовой порядок. Множество [math]M[/math] с заданным на нем отношением порядка [math]\leqslant[/math] будем записывать как пару [math](M,\leqslant)[/math]. Записывая [math]x\leqslant y[/math], мы будем говорить, что элемент [math]x[/math] не больше элемента [math]y[/math].


Каждому отношению порядка [math]\leqslant[/math] на множестве [math]M[/math] можно сопоставить следующие отношения.


1. Отношение, которое будем обозначать [math]<[/math], получается из исходного отношения порядка [math]\leqslant[/math] выбрасыванием всех элементов диагонали [math]\operatorname{id}M[/math], т.е. [math]x<y[/math] для любых [math]x,y\in M[/math] тогда и только тогда, когда [math]x\leqslant y[/math] и [math]x\ne y[/math]. Записывая [math]x<y[/math], мы будем говорить, что элемент [math]x[/math] строго меньше элемента [math]y[/math]. Из определения следует, что отношение [math]<[/math] есть иррефлексивное, антисимметричное и транзитивное бинарное отношение на множестве [math]M[/math], т.е. оно является отношением строгого порядка.


Двойственный порядок


2. Двойственный порядок. Это бинарное отношение на множестве [math]M[/math], называемое также и отношением, двойственным к отношению порядка [math]\leqslant[/math], определяется как бинарное отношение на множестве [math]M[/math], обратное к отношению [math]\leqslant[/math]. Его обозначают [math]\geqslant[/math]. Тогда для любых [math]x,y[/math] условие [math]x\geqslant y[/math] равносильно тому, что [math]y\leqslant x[/math]. Можно без труда доказать, что отношение [math]\geqslant[/math] тоже является отношением порядка.


Записывая [math]x\geqslant y[/math], мы будем говорить, что элемент [math]x[/math] не меньше элемента [math]y[/math]. Отношение строгого порядка, ассоциированное с [math]\geqslant[/math], договоримся обозначать [math]>[/math], говоря при этом, что элемент [math]x[/math] строго больше элемента [math]y[/math], если [math]x\geqslant y[/math] и [math]x\ne y[/math].


Отношение доминирования


3. Отношение доминирования. Для двух элементов [math]x[/math] и [math]y[/math], по определению, [math]x\triangleleft y[/math] тогда и только тогда, когда [math]x[/math] строго меньше [math]y[/math] и не существует такого элемента [math]z[/math], что [math]x<z<y[/math]. Отношение [math]\triangleleft[/math] называют отношением доминирования (или просто доминированием), ассоциированным с отношением порядка [math]\leqslant[/math]. Если имеет место [math]x\triangleleft y[/math], то говорят, что элемент [math]y[/math] доминирует над элементом [math]x[/math].


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




Пример 1.15. а. Рассмотрим множество действительных чисел с естественным числовым порядком. Пусть [math]a<c[/math]. Известно, что для любых [math]a[/math] и [math]c[/math] найдется такое [math]b[/math], что [math]a<b<c[/math], т.е. это отношение порядка на множестве действительных чисел является плотным. Поэтому отношение доминирования будет пустым.


По той же причине будет пустым отношение доминирования, ассоциированное с естественным числовым порядком на множестве рациональных чисел. Но на множестве целых чисел (опять-таки с естественным числовым порядком) отношение доминирования не пусто. Так, [math]1\triangleleft2, -5\triangleleft-4[/math], но, конечно, неверно, что [math]1\triangleleft3[/math], поскольку между единицей и тройкой существует "промежуточный" элемент — двойка.


б. На множестве всех подмножеств трехэлементного множества [math]\{a,b,c\}[/math], где в качестве отношения порядка взято отношение теоретико-множественного включения [math]\subseteq[/math], подмножество [math]\{a,b\}[/math] доминирует над подмножествами [math]\{a\}[/math] и [math]\{b\}[/math], но не доминирует над пустым множеством. В свою очередь, все множество [math]\{a,b,c\}[/math] доминирует над любым своим двухэлементным подмножеством, но не доминирует над одноэлементным и над пустым.


в. По отношению делимости на множестве натуральных чисел 15 доминирует над 3 и 5, но 20 не доминирует над 5, так как существует „промежуточный" элемент — 10, делитель 20, который делится на 5, но не равен ни 20, ни 5.




Упорядоченное подмножество


Рассмотрим упорядоченное множество [math](M,\leqslant)[/math] и его произвольное непустое подмножество [math]B\subseteq M[/math]. Упорядоченное множество [math](B,\leqslant\big|_{B})[/math], где [math]\leqslant\big|_{B}[/math] — ограничение отношения [math]\leqslant[/math] на подмножество [math]B[/math], называют упорядоченным подмножеством упорядоченного множества [math](M,\leqslant)[/math].


Таким образом, можно переносить отношения порядка на непустые подмножества исходного упорядоченного множества. Как правило, вместо [math]\leqslant\big|_{B}[/math] будем писать просто [math]\leqslant[/math] (если ясно, о каком подмножестве [math]B[/math] идет речь). Порядок [math]\leqslant\big|_{B}[/math] на подмножестве [math]B[/math] называют также порядком, индуцированным исходным порядком [math]\leqslant[/math] на всем множестве [math]A[/math]. Часто прибегают к такому выражению: "рассмотрим подмножество [math]B[/math] упорядоченного множества [math](M,\leqslant)[/math] с индуцированным порядком", понимая под этим порядок [math]\leqslant\big|_{B}[/math].


Элементы [math]x[/math] и [math]y[/math] упорядоченного множества [math](M,\leqslant)[/math] называют сравнимыми по отношению порядка [math]\leqslant[/math], если [math]x\leqslant y[/math] или [math]y\leqslant x[/math]. В противном случае элементы [math]x[/math] и [math]y[/math] называются несравнимыми.


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


Замечание 1.5. Обратим внимание на то, что термину "упорядоченное множество" (в смысле приведенного определения) отвечает термин "частично упорядоченное множество", а то, что мы называем линейно упорядоченным множеством, называется просто упорядоченным множеством. Терминология этого выпуска более принята в алгебраической литературе и литературе по дискретной математике. Употребление термина "частично упорядоченное множество" мотивировано желанием подчеркнуть, что в общем случае в упорядоченном множестве существуют не сравнимые элементы.


Пример 1.16. а. Отношение естественного числового порядка на множестве [math]\mathbb{R}[/math] действительных чисел является отношением линейного порядка, поскольку для любых двух чисел [math]a,b[/math] имеет место или неравенство [math]a\leqslant b[/math], или неравенство [math]b\leqslant a[/math].


б. Отношение делимости (см. пример 1.13.г) на множестве [math]\mathbb{N}[/math] и отношение включения [math]\subseteq[/math] на [math]\mathval{B}(A)[/math] (см. пример 1.13,д) не являются линейными порядками, за исключением случая, когда [math]A[/math] — одноэлементное множество.




Наибольший, наименьший и максимальный, минимальный элементы множества


Пусть [math](A,\leqslant)[/math] — упорядоченное множество. Элемент [math]a\in A[/math] называют наибольшим элементом множества [math]A[/math], если для всех [math]x\in A[/math] выполняется неравенство [math]x\leqslant a[/math].


Элемент [math]b[/math] называют максимальным элементом множества [math]A[/math], если для всякого [math]x\in A[/math] имеет место одно из двух: или [math]x\leqslant b[/math], или [math]x[/math] и [math]b[/math] не сравнимы.


Аналогично определяются наименьший и минимальный элементы упорядоченного множества, а именно: наименьший элемент упорядоченного множества [math]A[/math] — это такой его элемент [math]a[/math], что [math]a\leqslant x[/math] для каждого [math]x\in A[/math], а минимальный элемент — это такой элемент [math]b\in A[/math], что для любого [math]x\in A[/math] элементы [math]b[/math] и [math]x[/math] не сравнимы или [math]b\leqslant x[/math].


Покажем, что наибольший (наименьший) элемент множества, если он существует, является единственным. Действительно, полагая, что [math]a[/math] и [math]a'[/math] — наибольшие элементы [math]A[/math] по отношению порядка [math]\leqslant[/math], получаем, что для всякого [math]x\in A[/math] выполняется [math]x\leqslant a[/math] и [math]x\leqslant a'[/math]. В частности, [math]a'\leqslant a[/math] и [math]a\leqslant a'[/math], откуда ввиду антисимметричности любого отношения порядка следует, что [math]a=a'[/math]. Аналогично доказывается единственность наименьшего элемента.


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


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


Пример 1.17. Рассмотрим множество точек плоскости с некоторой фиксированной прямоугольной декартовой системой координат. Координаты каждой точки плоскости задаются упорядоченной парой [math](x,y)[/math] действительных чисел. Отношение порядка на множестве точек плоскости определим следующим образом: [math](a,b)\leqslant (c,d)[/math], если и только если [math]a\leqslant c[/math] и [math]b\leqslant d[/math]. Рассмотрим множество точек треугольника [math]OAB[/math] (рис. 1.11, а). Точка с координатами [math](0;0)[/math] является наименьшим элементом этого множества. Максимальными элементами являются все точки, лежащие на стороне [math]AB[/math]. Наибольшего элемента нет.


Множества точек треугольника, прямоугольника и трапеции



Верхняя и нижняя грань множества


Пусть [math](A,\leqslant)[/math] — упорядоченное множество и [math]B\subseteq A[/math]. Элемент [math]a\in A[/math] называется верхней (соответственно нижней) гранью множества [math]B[/math], если для всех элементов [math]x\in B[/math] имеет место [math]x\leqslant a[/math] (соответственно [math]x\geqslant a[/math]).


Наименьший элемент множества всех верхних граней (соответственно наибольший элемент множества всех нижних граней) множества [math]B[/math] называют точной верхней гранью [math]B[/math] (соответственно точной нижней гранью [math]B[/math]) и обозначают [math]\sup B~ (\inf B)[/math].


Множество всех верхних (нижних) граней множества [math]B[/math] называют верхним (нижним) конусом [math]B[/math] и обозначают [math]B^{\triangle}[/math] (соответственно [math]B^{\triangledown}[/math]).


В отличие от наибольшего и наименьшего элементов множества [math]B[/math] элементы [math]\sup B[/math] и [math]\inf B[/math] не обязаны принадлежать множеству [math]B[/math]. Точная верхняя (нижняя) грань множества существует не всегда.


Пример 1.18. а. Рассмотрим множество [math]D[/math] точек прямоугольника [math]OABC[/math] (рис. 1.11, б) с заданным в примере 1.17 отношением порядка. Точка [math]O[/math] является точной нижней гранью, а точка [math]B[/math]— точной верхней гранью этого множества. Обе точки принадлежат множеству.


Если рассмотреть множество [math]F[/math] (рис. 1.11, в) с тем же отношением порядка, то увидим, что точная нижняя грань (точка [math]O[/math]) и точная верхняя грань (точка [math]E[/math]) множества [math]F[/math] существуют, но не принадлежат множеству.


б. На числовой прямой с "выколотой" точкой [math]b[/math] для полуинтервала [math][a;b)[/math] множество верхних граней есть [math](b;+\infty)[/math], но точной верхней грани нет.




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


Упорядоченное множество [math](M,\leqslant)[/math] называют вполне упорядоченным, если его любое непустое подмножество имеет наименьший элемент.


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


Можно показать, что справедлив принцип двойственности для упорядоченных множеств. Пусть [math](M,\leqslant)[/math] — произвольное упорядоченное множество. Тогда любое утверждение, доказанное для порядка [math]\leqslant[/math], останется справедливым для двойственного порядка [math]\geqslant[/math], если в нем:


1) порядок [math]\leqslant[/math] заменить на порядок [math]\geqslant[/math] и наоборот;
2) наименьший (минимальный) элемент заменить наибольшим (максимальным) элементом и наоборот;
3) [math]\inf[/math] заменить на [math]\sup[/math] и наоборот.

Например, если для некоторого [math]a\in M[/math] и для [math]B\subseteq M[/math] мы доказали, что [math]a=\sup B[/math] при заданном отношении порядка, то для двойственного порядка [math]a=\inf B[/math].


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




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


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


Конечное упорядоченное множество можно графически изобразить в виде так называемой диаграммы Хассе. На этой Диаграмме элементы множества изображаются кружочками. При этом если элемент [math]b[/math] доминирует над элементом [math]a[/math], то кружочек, изображающий элемент [math]b[/math], располагается выше кружочка, изображающего элемент [math]a[/math], и соединяется с ним прямой линией. Иногда для большей наглядности из [math]a[/math] в [math]b[/math] ведут стрелку. На рис. 1.12 изображены диаграммы Хассе для упорядоченных множеств делителей чисел 2, 6, 30 и 36 по рассмотренному выше отношению делимости (см. пример 1.13,г).


Диаграммы Хассе для упорядоченных множеств делителей чисел 2, 6, 30 и 36

Диаграмма Хассе для упорядоченного множества всех подмножеств трехэлементного множества {a,b,c} по отношению включения

На рис. 1.13 приведена диаграмма Хассе для упорядоченного множества всех подмножеств трехэлементного множества [math]\{a,b,c\}[/math] по отношению включения (см. пример 1.13.д).


Последовательность [math]\{x_i\}_{i\in\mathbb{N}}[/math] элементов упорядоченного множества называют неубывающей, если для каждого [math]i\in\mathbb{N}[/math] справедливо неравенство [math]x_i\leqslant x_{i+1}[/math].


Элемент а упорядоченного множества [math](M,\leqslant)[/math] называют точной верхней гранью последовательности [math]\{x_i\}_{i\in\mathbb{N}}[/math] если он есть точная верхняя грань множества всех членов последовательности. Другими словами, точная верхняя грань последовательности есть точная верхняя грань области ее значений как функции натурального аргумента.




Точная нижняя грань последовательности


Двойственно определяется точная нижняя грань последовательности.


Упорядоченное множество [math](M,\leqslant)[/math] называют индуктивным, если:


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

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


Определение 1.5. Пусть [math](M_1,\leqslant)[/math] и [math](M_2,\preccurlyeq)[/math] — индуктивные упорядоченные множества. Отображение [math]f\colon M_1\to M_2[/math] одного индуктивного упорядоченного множества в другое называют непрерывным, если для любой неубывающей последовательности [math]a_1,\ldots,a_n,\ldots[/math] элементов множества [math]M_1[/math] образ ее точной верхней грани равен точной верхней грани последовательности образов [math]f(a_1),\ldots,f(a_n),\ldots[/math], т.е. справедливо равенство


[math]f(\sup a_n)=\sup f(a_n).[/math]

Определение 1.6. Отображение [math]f\colon M_1\to M_2[/math] упорядоченных множеств [math](M_1,\leqslant)[/math] и [math](M_2,\preccurlyeq)[/math] называют монотонным, если для любых [math]a,b\in M_1[/math] из [math]a\leqslantb[/math] следует [math]f(a)\preccurlyeq f(b)[/math].


Теорема 1.6. Всякое непрерывное отображение одного индуктивного упорядоченного множества в другое монотонно.


Пусть [math]f[/math] — непрерывное отображение индуктивного упорядоченного множества [math](M_1,\leqslant)[/math] в индуктивное упорядоченное множество [math](M_2, \preccurlyeq)[/math]. Пусть [math]a,b\in M_1[/math] и [math]a\leqslant b[/math]. Образуем последовательность [math]\{x_i\}_{n\in\mathbb{N}}[/math], где [math]x_1=a[/math], а [math]x_n=b,~ n\geqslant2[/math]. Эта последовательность неубывающая. Для нее [math]\sup x_n=\sup\{a,b\}=b[/math]. В силу непрерывности отображения [math]f[/math]


[math]f(b)=f(\sup x_n)= f(\sup\{a,b\})= \sup\{f(a),f(b)\}.[/math]

откуда следует, что [math]f(a)\preccurlyeq f(b)[/math].




Заметим, что функция [math]f\colon \mathbb{R}\to \mathbb{R}[/math], непрерывная в смысле определений математического анализа, не обязана быть монотонным отображением упорядоченных множеств [math]\mathbb{R}[/math] с естественным числовым порядком, т.е. приведенное выше определение 1.5 непрерывности не вполне аналогично определению непрерывности в анализе . Например, рассмотрим непрерывное в смысле определений математического анализа отображение [math]y=-x[/math] числовой прямой с естественным числовым порядком на себя. Это отображение не является монотонным в смысле данного выше определения 1.6, поскольку, например, [math]0\leqslant1[/math], однако неравенство [math]f(0)=0\leqslant f(1)=-1[/math] не выполняется.


В общем случае монотонное в смысле определения 1.6 отображение не является непрерывным в смысле определения 1.5. Приведем пример, показывающий, что утверждение, обратное теореме 1.6, неверно.


Пример 1.19. Рассмотрим множество всех точек отрезка [math][0;1][/math] числовой прямой с порядком, индуцированным естественным числовым порядком. Это множество индуктивно: его наименьший элемент — 0, а любая неубывающая последовательность элементов ограничена сверху и по признаку Вейерштрасса имеет предел, который и будет ее точной верхней гранью. Любая кусочно-непрерывная (но не непрерывная!) и монотонная в смысле обычных определений из курса математического анализа функция, отображающая этот отрезок на любой отрезок с порядком, индуцированным естественным числовым порядком, дает пример монотонного в смысле определения 1.6, но не непрерывного в смысле определения 1.5 отображения между индуктивными частично упорядоченными множествами. Например, пусть функция [math]f[/math] имеет вид


[math]f=\begin{cases}0,\!5x,&\text{if}\quad 0 \leqslant x<0,\!5\,;\\ 0,\!5+0,\!5x,&\text{if}\quad 0,\!5\leqslant x\leqslant1.\end{cases}[/math]

Это отображение монотонно. Для последовательности [math]\{x_n\}= \left\{ \frac{n}{2n+ 1}\right\}[/math], точная верхняя грань равна [math]0,\!5[/math]. Точная верхняя грань последовательности [math]\{f(x_n)\}[/math] равна [math]0,\!25[/math], a [math]f(\sup x_n)=f(0,\!5)=0,\!75[/math]. Следовательно, отображение не является непрерывным в смысле определения 1.5.




Не следует путать отображение, монотонное в смысле определения 1.6, с монотонными функциями из курса математического анализа. Функция [math]f\colon\mathbb{R}\to\mathbb{R}[/math] будет монотонной в смысле определения 1.6 тогда и только тогда, когда она является неубывающей.


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved