Xreferat.com » Рефераты по математике » Размерность конечных упорядоченных множеств

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ

УНИВЕРСИТЕТ

МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА АЛГЕБРЫ И ГЕОМЕТРИИ


Выпускная квалификационная работа


РАЗМЕРНОСТЬ КОНЕЧНЫХ УПОРЯДОЧЕННЫХ МНОЖЕСТВ


Выполнила студентка V курса

математического факультета

Артемьева Е.П.

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


Научный руководитель:

доктор ф.-м. наук, профессор

Вечтомов Е.М.

/подпись/

Размерность конечных упорядоченных множествРецензент:

кандидат ф.-м. наук, доцент

Чермных В.В.


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


Допущен к защите в ГАК

Размерность конечных упорядоченных множествЗав. кафедрой Вечтомов Е.М.

(подпись)

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


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

(подпись)

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


Киров, 2003г.

Содержание


Введение

§1.Основные понятия

§2.Определение размерности упорядоченного множества

§3.Свойства размерности конечных упорядоченных множеств

Литература

Введение


Теория множеств служит фундаментом современной математики.

Порядковая структура входит в список основных (ещё алгебраическая и топологическая) математических структур, которые изучает теоретико-множественная математика.

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

Язык упорядоченных множеств и решёток широко применяется в математике (алгебра, логика, теория множеств, общая топология, графы) и является основой одного из важнейших типов математического мышления.

Дипломная работа состоит из трёх параграфов: «Основные понятия», «Определение размерности упорядоченных множеств», «Свойства размерности конечных упорядоченных множеств».

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

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

В третьем параграфе указаны 6 основных свойств размерности конечных упорядоченных множеств и приведены их доказательства. Некоторые из них оформлены в виде теорем.

§1.Основные понятия


Упорядоченным множеством называется пара <A, ≤ >, где А – непустое множество, а ≤ - бинарное отношение на А, называемое отношением порядка, которое (для " a,b,cОA)

рефлексивно: аЈа

транзитивно: аЈв и вЈс Ю аЈс

антисимметрично: аЈв и вЈа Ю а=в

Основными примерами упорядоченных множеств являются:

<R, ≤ > -множество всех действительных чисел с обычным отношением порядка и непустое подмножество;

<B(X), Н > - множество всех подмножеств данного множества X с отношением включения и непустое подмножество;

<N, / > - множество всех натуральных чисел с отношением делит и непустое подмножество;

множество всех лучей, лежащих на одной прямой, и отношением включения.

Пусть А – упорядоченное множество с отношением порядка Ј. Элементы а, в О А называются сравнимыми, если а Ј в или в Ј а.

Упорядоченное множество А, в котором любые 2 элемента сравнимы, называется цепью, а соответствующий порядок Ј - линейным.

Если в упорядоченном множестве А любые два различных элемента несравнимы, то множество А называется антицепью.

Элемент аОА называется наибольшим, если x Ј а для" xОА. Понятие наименьшего элемента определяется аналогичным образом. Если наибольший и наименьший элементы существуют, то они единственны. Наибольший элемент обычно обозначают – 1, а наименьший – 0.

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

Упорядоченное множество называется конечным, если конечно множество его элементов. Конечное упорядоченное множество <A, ≤ > удобно изображать в виде графа, который можно построить следующим образом:

элементы множества А изображаются точками;

точки а и в соединяются ребром – идущим вверх отрезком, не обязательно вертикальным, если а<в и между ними нет других элементов из А;

при этом все минимальные элементы А располагаются на одной горизонтали и образуют – первый уровень;

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

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

Заметим, что если а<в, то из точки а по ребрам, двигаясь вверх, можно добраться до точки в. Полученный граф назовем стандартным графом (диаграммой Хассе) упорядоченного множества А. Изоморфные упорядоченные множества имеют одинаковые стандартные графы, а неизоморфные – различные.

Приведем графы упорядоченных 4-х элементных множеств.

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


Следует обратить внимание на то, что из любой точки стандартного графа конечного упорядоченного множества можно по рёбрам спуститься на первый уровень, побывав на всех промежуточных уровнях. Т.е. среди стандартных графов не может быть такого, например, графа:

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


А должен быть такой

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


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


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


Шириной А называется наибольшее из чисел элементов антицепей в А. Ширина А будет не меньше числа элементов любого уровня этого графа.


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

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

Пусть В – непустое подмножество упорядоченного множества А. Элемент аОА называется верхней гранью для В, если вЈа для всех вОВ. Точной верхней гранью В называется наименьший элемент множества всех верхних граней В в А, его обозначают sup B. Точная нижняя грань определяется аналогичным образом и обозначается inf B.

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

Любая конечная решётка обладает наибольшим и наименьшим элементами. Среди графов 5-ти элементных множеств, только пять решёток.

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


В нашей дипломной работе пойдёт речь ещё и прямом произведении конечных упорядоченных множествах. Поэтому объясним, что это такое.

Пусть <A,≤> и <В,≤> - конечные упорядоченные множества с одинаковым порядком, тогда их прямым произведением Размерность конечных упорядоченных множеств называется конечное упорядоченное множество Размерность конечных упорядоченных множеств, элементы которого – это всевозможные пары, состоящие из двух компонент,1-ая компонента принадлежит множеству А, а вторая – В. Порядок на Размерность конечных упорядоченных множеств определяется следующим образом:


(a,b)≤(c,d)Ы(a≤c и b≤d).


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


§2.Определение размерности упорядоченного множества


Напомним, что такое цепь на примере диаграммы Хассе для конечного упорядоченного множества <A,Ј>. Здесь порядок Ј будет линейным.

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


Примером антицепи может служить множество:

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

Нелинейный порядок Ј на конечном упорядоченном множестве А можно доупорядочить до различных линейных порядков на А.

Например, нелинейный порядок на А

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


можно доупорядочить до следующих линейных порядков:

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

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

Теорема 1. Любой нелинейный порядок ≤ на конечном упорядоченном множестве А можно продолжить до линейных порядков, дающих в пересечении исходный порядок ≤.


Доказательство:

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

Возьмём произвольное конечное упорядоченное множество А с нелинейным порядком Ј.

Рассмотрим 2 его произвольных элемента а и b.

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

Размерность конечных упорядоченных множествЕсли при этом элемент xЈ а, а элемент y і b, то Размерность конечных упорядоченных множеств.

В нашем примере b и с несравнимы. Доопределим Размерность конечных упорядоченных множеств. При этом, а Ј b и c Ј e, значит, Размерность конечных упорядоченных множеств.

Если <A,Размерность конечных упорядоченных множеств> - всё ещё не цепь, то, беря новую пару несравнимых элементов, аналогично доопределяем до “большего” порядка на А.

Через несколько таких шагов получим линейный порядок на 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 )).

Эта перестановка задаёт свой линейный порядок на А, наряду с естественным числовым порядком, пересечение которых и определяет перестановочно упорядоченное множество < A, Размерность конечных упорядоченных множеств >.

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


При этом, аРазмерность конечных упорядоченных множествв Ы а<в и в данной перестановке n-ой степени число а встречается раньше числа в.

Конечные упорядоченные множества размерности 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) для любых конечных упорядоченного множества В и его непустого подмножества А.


Доказательство:


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


Пусть < B, ≤ >- конечное упорядоченное множество размерности n. Имеем, Размерность конечных упорядоченных множеств для линейных порядков Јi на В. На подмножестве А рассмотрим индуцированный порядок Размерность конечных упорядоченных множеств из В, т.е. ограничение отношения Ј на А.

Рассмотрим ограничения линейных порядков Јi на А – они также линейны и в пересечении дадут порядок Размерность конечных упорядоченных множеств.

Значит, по определению размерности упорядоченного множества размерность <A, Размерность конечных упорядоченных множеств> не превосходит n.

Ч.т.д.


Свойство размерности дизъюнктивного объединения: Пусть А и В – конечные упорядоченные множества и X=AРазмерность конечных упорядоченных множествB. Тогда d(X)=max(d(A), d(B)), если хотя бы одно из множеств А или В не является цепью, и d(X)=2, если А и В – цепи.


Доказательство:


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

Пусть <A, Ј> и <B, Размерность конечных упорядоченных множеств> - конечные упорядоченные множества.

Порядок на А Размерность конечных упорядоченных множествдля линейных порядков Ј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)<(c, d) Ы (a < c и b Ј d) или (a Ј c и b < d).


Определим m линейных порядков на Размерность конечных упорядоченных множеств по первой компоненте:

(a, b)<i(c, d) Ы a<i c или (a=c и b<1 d) для i=1,…,m. (*)


Аналогично определим n линейных порядков на Размерность конечных упорядоченных множеств по второй компоненте:

(a, b)<j(c, d) Ы b<j d или (b=d и a<1 c) для j=1,…,n. (**)


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

(a, b)<(c, d)Ы(a<ic и bЈj d ) или (aЈI c и b<j d) (***)

для i=1,…,m и для j=1,…,n.


Для завершения доказательства достаточно показать, что имеет место равенство:


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

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

Требуется доказать, что для любых (a,b) и (c,d) из Размерность конечных упорядоченных множеств:

(a, b)<(c, d) Ы(a, b)<i(c, d) и (a, b)<j(c, d).

Для " (a,b) и (c,d)

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: