Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

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

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

Узнайте стоимость индивидуальной работы

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


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

Тип Реферат
Предмет Математика
Просмотров
287
Размер файла
117 б
Поделиться

Ознакомительный фрагмент работы:

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

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

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

УНИВЕРСИТЕТ

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

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

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

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

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

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

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

/подпись/

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

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

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

/подпись/

Рецензент:

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

Чермных В.В.

/подпись/

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

Зав. кафедрой Вечтомов Е.М.

(подпись)

2003г.

Декан факультета Варанкина В.И.

(подпись)

2003г.

Киров, 2003г.

Содержание

Введение. 3

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

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

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

Литература. 22

Введение

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

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

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

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

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

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

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

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

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

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

1. рефлексивно: а£а

2. транзитивно: а£в и в£с Þ а£с

3. антисимметрично: а£в и в£а Þ а=в

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть В – непустое подмножество упорядоченного множества А. Элемент аÎА называется верхней гранью для В, если в£а для всех вÎВ. Точной верхней гранью В называется наименьший элемент множества всех верхних граней В в А, его обозначают supB. Точная нижняя грань определяется аналогичным образом и обозначается infB.

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

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

Если бы мы доопределили ba, тогда получили бы другой линейный порядок, содержащий исходный порядок £. В пересечении и í линейных порядков элементы 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=AB. Тогда 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<jd или (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) из не умоляя общности, будем считать, что

(a, b)<(c, d) (a<I c и b£j d) или (a£I c и b<j d) для i=1,…,m идля j=1,…,n.

Отсюда вследствие того, что x£y выполняется тогда и только тогда, когда x<y или x=y, следует равносильность:

Û(a<Ic и b<jd) или (a<Ic и b=d) или (a=c и b<jd)

для 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=A1A2 … 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.


Нет нужной работы в каталоге?

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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Математика
История
Экономика
icon
142645
рейтинг
icon
3069
работ сдано
icon
1329
отзывов
avatar
Математика
Физика
История
icon
140338
рейтинг
icon
5849
работ сдано
icon
2647
отзывов
avatar
Химия
Экономика
Биология
icon
94648
рейтинг
icon
2019
работ сдано
icon
1266
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
52 911 оценок star star star star star
среднее 4.9 из 5
игу
работа выполнена качественно, а самое главное быстро. всё требования были выполнены
star star star star star
ФЭК
Прекрасная Татьяна, выполнила все быстро, профессионально и раньше срока!!! Очень рекомендую 👌
star star star star star
Санкт-Петербургский государственный архитектурно-строительный университет
Выполнено быстро, качественно, преподаватель оценил по высшему баллу. Рекомендую.
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

Сделать 15 вариант из методички

Решение задач, Математический анализ

Срок сдачи к 5 июня

только что

Моделирование бизнес-процессов операторов связи

Другое, Проектирование и эксплуатация систем связи

Срок сдачи к 17 июня

только что

Написать реферат

Реферат, Физика

Срок сдачи к 29 мая

только что
только что

Написать реферат с 70 процентами антиплагиата. Требования указала в файле.

Реферат, Юридическая аргументация

Срок сдачи к 28 мая

только что

Анализ главного героя одного из сериалов на выбор

Контрольная, Психоанализ

Срок сдачи к 31 мая

1 минуту назад

Современные концепции управления персоналом

Курсовая, Основы управления персоналом

Срок сдачи к 10 июня

1 минуту назад

решить задачу

Решение задач, Бухгалтерский учет в страховых организациях

Срок сдачи к 29 мая

1 минуту назад
1 минуту назад

Расчетно-аналитическая работа

Другое, Диджитализация, финтех и инновации в финансовых институтах

Срок сдачи к 9 июня

1 минуту назад

Решить задачи

Решение задач, Статистика

Срок сдачи к 29 мая

2 минуты назад

Тема Патриотическое воспитание школьников в учебно-воспитательном...

Курсовая, Педагогика и психология

Срок сдачи к 2 июня

2 минуты назад

написать реферат

Реферат, «Реконструкция зданий, сооружений и застройки»

Срок сдачи к 31 мая

2 минуты назад

Стилизовать текст

Другое, История русского литературного языка

Срок сдачи к 27 мая

2 минуты назад

4 задачи

Курсовая, Внутризаводские и электротехнические комплексы и системы

Срок сдачи к 7 июня

3 минуты назад

Часть работы уже написана, есть содержание, 1 и 2 главы

Диплом, государственное и муниципальное управление

Срок сдачи к 6 июня

3 минуты назад

Написание курсовой работы строго по методтички

Курсовая, анализ финансово-хозяйственной деятельности

Срок сдачи к 13 июня

3 минуты назад
3 минуты назад
planes planes
Закажи индивидуальную работу за 1 минуту!

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

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно