МИНИСТЕРСТВООБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ВЯТСКИЙГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ
УНИВЕРСИТЕТ
МАТЕМАТИЧЕСКИЙФАКУЛЬТЕТ
КАФЕДРААЛГЕБРЫ И ГЕОМЕТРИИ
Выпускная квалификационная работа
РАЗМЕРНОСТЬКОНЕЧНЫХ УПОРЯДОЧЕННЫХ МНОЖЕСТВ
Выполниластудентка V курса
математическогофакультета
АртемьеваЕ.П.
/>/подпись/
Научныйруководитель:
докторф.-м. наук, профессор
ВечтомовЕ.М.
/подпись/
/>Рецензент:
кандидатф.-м. наук, доцент
ЧермныхВ.В.
/>/подпись/
Допущенк защите в ГАК
/>Зав. кафедрой ВечтомовЕ.М.
(подпись)
/>/>2003г.
/>Декан факультета ВаранкинаВ.И.
(подпись)
/>/>2003г.
Киров, 2003г.
Содержание
Введение. 3
§1.Основные понятия. 4
§2.Определение размерностиупорядоченного множества. 9
§3.Свойства размерности конечныхупорядоченных множеств. 14
Литература. 22
Введение
Теория множеств служитфундаментом современной математики.
Порядковая структура входит в список основных (ещёалгебраическая и топологическая) математических структур, которые изучаеттеоретико-множественная математика.
При написании этой дипломной работы мы задавались целью –изучить порядковую структуру и элементы алгебраической теории решёток,сформировать углублённое представление о размерности упорядоченных множеств,познакомиться со свойствами размерности конечных упорядоченных множеств,сформулировать новые свойства и доказать их.
Язык упорядоченных множеств и решёток широко применяетсяв математике (алгебра, логика, теория множеств, общая топология, графы) иявляется основой одного из важнейших типов математического мышления.
Дипломная работа состоит из трёх параграфов: «Основныепонятия», «Определение размерности упорядоченных множеств», «Свойстваразмерности конечных упорядоченных множеств».
В первом параграфе определяются основные понятия, скоторыми нужно ознакомиться для дальнейшей работы и устанавливаются связи междуними. Большое число примеров позволяет достаточно глубоко понять сутьрассматриваемых понятий.
Во втором параграфе рассматриваются только конечныемножества. И особое внимание уделяется на линейный и нелинейный порядок.Формулируется и доказывается теорема об их связи. На основе этого появляетсяпонятие размерности.
В третьем параграфе указаны 6 основных свойствразмерности конечных упорядоченных множеств и приведены их доказательства.Некоторые из них оформлены в виде теорем. §1.Основныепонятия
Упорядоченныммножествомназывается пара , где А – непустое множество, а ≤ — бинарное отношение на А, называемое отношением порядка,которое(для " a,b,cÎA)
1. рефлексивно: а£а
2. транзитивно: а£в и в£с Þ а£с
3. антисимметрично: а£в и в£а Þ а=в
Основными примерами упорядоченных множеств являются:
· R, ≤ > -множество всех действительных чисел собычным отношением порядка и непустое подмножество;
· B(X), Í > — множество всех подмножествданного множества X с отношениемвключения и непустое подмножество;
· N, / > — множество всех натуральныхчисел с отношением делит и непустое подмножество;
· множество всехлучей, лежащих на одной прямой, и отношением включения.
Пусть А – упорядоченноемножество с отношением порядка £. Элементы а, в Î А называются сравнимыми, если а £ в или в £ а.
Упорядоченное множествоА, в котором любые 2 элемента сравнимы, называется цепью, асоответствующий порядок £ — линейным.
Если в упорядоченноммножестве А любые два различных элемента несравнимы, то множество А называется антицепью.
Элемент аÎА называется наибольшим, если x £ а для" xÎА. Понятие наименьшего элементаопределяется аналогичным образом. Если наибольший и наименьший элементысуществуют, то они единственны. Наибольший элемент обычно обозначают – 1, анаименьший – 0.
Элемент множества А будетназываться максимальным, если в А нет элементов больших его. Аналогичнымобразом определяется понятие минимального элемента.
Упорядоченное множествоназывается конечным, если конечно множество его элементов. Конечноеупорядоченное множество удобно изображать в виде графа,который можно построить следующим образом:
Ø элементы множества А изображаютсяточками;
Ø точки а и в соединяются ребром– идущим вверх отрезком, не обязательно вертикальным, если а
Ø при этом все минимальные элементы Арасполагаются на одной горизонтали и образуют – первый уровень;
Ø выше находятся минимальные элементымножества А, из которого удалены точки первого уровня, они образуют второйуровень;
Ø еще выше идет третий уровень,состоящий из минимальных элементов множества, полученного удалением из Аэлементов второго и первого уровней, и т.д.
Заметим, что если астандартным графом (диаграммой Хассе) упорядоченногомножества А. Изоморфные упорядоченные множества имеют одинаковые стандартныеграфы, а неизоморфные – различные.
Приведем графыупорядоченных 4-х элементных множеств.
/>
Следует обратить вниманиена то, что из любой точки стандартного графа конечного упорядоченного множестваможно по рёбрам спуститься на первый уровень, побывав на всех промежуточныхуровнях. Т.е. среди стандартных графов не может быть такого, например, графа:
/>
А должен быть такой
/>
Длиной конечного упорядоченного множества Абудем называть наибольшее из чисел элементов цепей А. Видно, что длина А равначислу уровней его стандартного графа.
/>
Шириной А называется наибольшее из чиселэлементов антицепей в А. Ширина А будет не меньше числа элементов любогоуровня этого графа.
/>
Замечание: число элементов любого конечногоупорядоченного множества не превосходит произведения его длины на ширину.
Пусть В – непустоеподмножество упорядоченного множества А. Элемент аÎА называется верхней гранью для В,если в£а для всех вÎВ. Точной верхней гранью В называетсянаименьший элемент множества всех верхних граней В в А, его обозначают supB. Точная нижняя грань определяетсяаналогичным образом и обозначается infB.
Упорядоченное множество,в котором каждое двухэлементное множество обладает тачной верхней и точнойнижней гранью называется решёткой.
Любая конечная решёткаобладает наибольшим и наименьшим элементами. Среди графов 5-ти элементныхмножеств, только пять решёток.
/>
В нашей дипломной работе пойдёт речь ещё и прямом произведении конечных упорядоченных множествах.Поэтому объясним, что это такое.
Пусть и — конечные упорядоченные множества с одинаковым порядком,тогда их прямым произведением /> называетсяконечное упорядоченное множество />,элементы которого – это всевозможные пары, состоящие из двух компонент,1-аякомпонента принадлежит множеству А, а вторая – В. Порядок на /> определяется следующимобразом:
(a,b)≤(c,d)Û(a≤c и b≤d).
/>/>§2.Определение размерности упорядоченного множества
Напомним, что такое цепьна примере диаграммы Хассе для конечного упорядоченного множества . Здесь порядок £ будет линейным.
/>
Примером антицепи может служить множество:
/>
Нелинейный порядок £на конечном упорядоченном множестве А можно доупорядочить до различных линейныхпорядков на А.
Например, нелинейныйпорядок на А
/>
можнодоупорядочить до следующих линейных порядков:
/>
Длялюбого нелинейного порядка конечного упорядоченного множества будет справедливатеорема.
Теорема1. Любойнелинейный порядок ≤ на конечном упорядоченном множестве А можнопродолжить до линейных порядков, дающих в пересечении исходный порядок ≤.
Доказательство:
/>
Возьмём произвольноеконечное упорядоченное множество А с нелинейным порядком £.
Рассмотрим 2 егопроизвольных элемента а и b.
Если они несравнимы, тодоопределим /> (или можно взять/>).
/>Если приэтом элемент x£ а, а элемент y ³ b, то />.
В нашем примере b и снесравнимы. Доопределим />. Приэтом, а £ b и c £ e, значит, />.
Если > — всё ещё не цепь, то, беря новуюпару несравнимых элементов, аналогично доопределяем до “большего” порядка на А.
Через несколько такихшагов получим линейный порядок на A, содержащий исходный порядок £.
Если бы мыдоопределили b/>a, тогда получили бы другой линейныйпорядок, содержащий исходный порядок £. В пересечении /> и í линейных порядков элементы a и bокажутся несравнимыми.
Аналогичным образом можнополучить и другие линейные порядки, пересечение которых образует множество А.
Ч.т.д.
Из всего вышесказанного видно, что любой порядок наконечном упорядоченном множестве А является пересечением нескольких линейныхпорядков на А.
/>
Наименьшее число линейныхпорядков на А, дающих в пересечении данный порядок £, называется размерностью А. Иобозначается d(A).
/>
d(A)=2.
Корректность определения:каждое конечное упорядоченное множество имеет размерность. По определениюконечного упорядоченного множества в нём будет конечное число элементов. Алинейный порядок получается путём различных перестановок этих элементов. Есличисло элементов n, то числоперестановок будет />n! — конечное число. Из них выберемнаименьшее число линейных порядков, пересечение которых даст исходноемножество, и получим конечную размерность.
Цепи имеют размерность 1.Известно, что размерность всех множеств с количеством элементов n (где n£5), кроме цепей, равна 2.
Среди 6-элементных множеств существует только одно сразмерностью 3.
/>
Остальные 6-элементныемножества имеют размерность 2.
Дадим понятиеперестановочно упорядоченного множества.
Пусть имеется множествоА, состоящее из n элементов. А={1,2 ,3 ,…, n}. Рассмотрим некоторую перестановкуэтого множества. (Например, (2, 1, 4, 3, …, n, n-1 )).
Эта перестановка задаётсвой линейный порядок на А, наряду с естественным числовым порядком,пересечение которых и определяет перестановочно упорядоченноемножество >.
/>
При этом, а/>в Û а
Конечные упорядоченныемножества размерности 1 и 2 получаются с точностью до изоморфизма, какперестановочно упорядоченные множества.
Например, цепи Z: d(Z)=1
/>
соответствуетперестановка (1,2,3).
А множеству P: d(P)=2
/>
соответствуетперестановка (1,6,5,4,3,2).
Перестановочноупорядоченные множества, отличные от цепей, — это в точности упорядоченныемножества размерности 2.
Например, перестановка(5,3,1,2,6,4,7) задаёт упорядоченное множество размерности 2:
/>§3.Свойства размерности конечных упорядоченных множеств
Свойствомонотонности: АÍВ Þd(A) £d(B) для любых конечныхупорядоченного множества В и его непустого подмножества А.
Доказательство:
/>
Пусть - конечное упорядоченное множество размерности n. Имеем, /> длялинейных порядков £i наВ. На подмножестве А рассмотрим индуцированный порядок /> из В, т.е. ограничениеотношения £ на А.
Рассмотрим ограничениялинейных порядков £iнаА – они также линейны и в пересечении дадут порядок />.
Значит, по определениюразмерности упорядоченного множества размерность > не превосходит n.
Ч.т.д.
Свойство размерности дизъюнктивногообъединения:Пусть А и В – конечные упорядоченные множества и X=A/>B.Тогда d(X)=max(d(A), d(B)), если хотя бы одно из множеств А или В не являетсяцепью, и d(X)=2,если А и В – цепи.
Доказательство:
/>Дизъюнктивным объединением упорядоченных множеств А и В (А/>В) называетсяупорядоченное множество, состоящее из непересекающихся объединяемых множеств,на каждом из которых сохраняется свой порядок, а элементы из разных множествпопарно несравнимы.
Пусть и > — конечныеупорядоченные множества.
Порядокна А />для линейных порядков £i , а порядок на В /> длялинейных порядков />.
Пусть дляопределённости n³m и n³2.
Врезультате объединения А и В получается упорядоченное множество, состоящее извсех элементов А и всех элементов В. Значит, одному линейному порядку на А/>В соответствует двалинейных порядка: один для А £i и один для В />.Линейные порядки на А/>В должнысодержать все n линейных порядков £i и все m линейных порядков />, чтобы в пересечении онидали множество А/>В.
Первыйлинейный порядок на А/>Вопределимследующим образом:
£1 … />.
Т.е. мывзяли первый линейный порядок на А и приписали к нему справа первый линейныйпорядок на В.
Второйлинейный порядок на А/>В получим,взяв из множества А линейный порядок £2,а из множества В, если m³2, то линейный порядок />, если же m=1,то линейный порядок />. Носейчас линейный порядок из множества А поместим за линейным порядком измножества В, для того, чтобы элементы из разных множеств были попарнонесравнимы:
/> … £2, где j=1при m=1 и j=2 при m³2.
Аналогичнымобразом будем получать остальные линейные порядки на А/>В:
£i … /> при i£m
£i … /> при i>m.
Получим n линейных порядков, пересечение которых даёт множество А/>В. Т.е. />=n=max(d(A),d(B)).
Ч.т.д.
Теорема 2. Размерность прямого произведения двухконечных упорядоченных множеств А и В меньше либо равна сумме их размерностей:
/>.
Доказательство:
Дадим сначала несколькоопределений.
Пусть даны конечныеупорядоченные множества и , размерности которых соответственно равны m и n. Поэтому />, длянекоторых линейных порядков £iна А и /> длялинейных порядков на В.
Определим покоординатнопорядок на /> :
(a, b)
Определим m линейных порядков на /> по первой компоненте:
(a, b)
Аналогично определим n линейных порядков на /> по второй компоненте:
(a, b)d или(b=d и a
Исходя из этихопределений, порядок на /> можноопределить и следующим образом:
(a,b)
для i=1,…,m и для j=1,…,n.
Для завершениядоказательства достаточно показать, что имеет место равенство:
/>
Тогда по определениюразмерности конечного упорядоченного множества получим />.
Требуется доказать, чтодля любых (a,b) и (c,d) из />:
(a,b)
Для " (a,b) и (c,d) из /> не умоляяобщности, будем считать, что
(a, b) (a
Отсюда вследствие того,что x£y выполняется тогда и только тогда,когда x
Û(ac и bd) или (ac и b=d) или (a=c и bd)
для i=1,…,m и для j=1,…,n
/> /> />
для i=1,…,m и для j=1,…,n.
Эта система равносильнатому, что элементы (a,b) и (c,d) сравнимы как попервой, так и по второй компоненте. И порядок на /> равенпересечению его линейных порядков.
А т.к. размерность – этонаименьшее число линейных порядков, дающих в пересечении множество, то />.
Ч.т.д.
Теорема3. ЕслиА и В – не одноэлементные множества,причём А- решётка, а В –цепь, то размерность их прямого произведения на единицубольше размерности решётки:
/>.
Доказательство:
/>
/> (по теореме 2).
Покажем, что выполняетсяи />.
Возьмём любую цепь Z из множества цепей, пересечениекоторых образует решётку. Каждой такой цепи (а их /> ) во множестве цепей, пересечениекоторых образует множество/>, будет соответствовать своя цепь, все первые компонентыкоторой находятся в таком же соответствии, как и элементы цепи Z.
Но во множестве /> среди вторых компонент должны сохраняться исоотношения, которые присутствуют в цепи В. Значит, во множестве цепей,пересечение которых образует множество />, появится еще одна цепь.
Ч.т.д.
Теорема 4. /> /> решёткаX, размерности n.
Доказательство:
Возьмём n не одноэлементных цепей А1,А2,…, Аnи рассмотрим множество X=A1/> A2/> … />An=/>.(n-1) раз применяя теорему 3 получаем,что d(X)=n.
Ч.т.д.
Теорема5. Размерность множества всехподмножеств ß(M) множества М равна мощности множества М, т.е.
d(ß(M))=/>.
Доказательство:
1) Покажем, что ß(M) @/>, где D={0,1}.
/> — будем рассматривать, какмножество n-ок, состоящих из 0 и 1.
М={1,2,3,…,n}.
/>
2) Чтобы доказать, что ß(M) и /> изоморфны, нужноустановить взаимно однозначное соответствие.
Т.е. нужно показать, чтодля любого подмножества Xмножества М существует n-ка,состоящая из 0 и 1. И для любой n-кисуществует подмножество Yмножества М.
3) Выделим во множестве М подмножество X и составим по нему n-ку таким образом:
наместо 1-ой компоненты n-кипоставим 1, если первый элемент множества М входит и в его подмножество X;
и 0,если 1-ый элемент множества М не входит в подмножество X.
Аналогичным образомопределим все остальные компоненты n-ки.
Из нашего примера:
/>/>X (0,1,1,0,1,0…0)
n компонент
4) И, наоборот,возьмём произвольную n-ку.Например, (0,1,0,1,0…0). И поставим ей в соответствие подмножество Y множества М по тому же принципу:
если к-ая компонента равна 1, то к-ый элемент множества Мвходит в подмножество Y;
если же к-ая компонента равна 0, то к-ый элемент множества Мне входит в подмножество Y.
Из примера получаем подмножество Y={2,4}.
5) Т.о. из ß(M)@/> следует, что d(ß(M))=d(/>)/>n
Получили, что d(ß(M))=/>.
Ч.т.д.
Литература
1. Беран Л. Упорядоченные множества:Популярные лекции по математике. Вып. 55. – М.: Наука, 1981.
2. Биркгоф Г. Теория решёток. – М.:Наука, 1984.
3. Вечтомов Е. М. Теория решёток:учебно-методическая разработка спецкурса. – Киров: КГПИ, 1995.
4. Гретцер Г. Общая теория решёток. –М.: Мир, 1982.
5. Оре О. Теория графов. — М.: Наука,1980.