МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Вятський державний гуманітарний
УНІВЕРСИТЕТ
МАТЕМАТИЧНИЙ ФАКУЛЬТЕТ
Кафедра алгебри та геометрії
Випускна кваліфікаційна робота
РОЗМІРНІСТЬ скінчена впорядкована множина
Виконала студентка V курсу
математичного факультету
Артем'єва Є.П.
/ Підпис /
Науковий керівник:
доктор ф.-м. наук, професор
Вечтомов Є.М.
/ Підпис /
Рецензент:
кандидат ф.-м. наук, доцент
Чермний В.В.
/ Підпис /
Допущений до захисту в ГАК
Зав. кафедрою Вечтомов Є.М.
(Підпис)
2003р.
Декан факультету Варанкіна В.І.
(Підпис)
2003р.
Кіров, 2003р.
Зміст
\ T "Заголовок 2; 2; Заголовок 3; 3" Введення. 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-х елементних множин.

Слід звернути увагу на те, що з будь-якої точки стандартного графа кінцевого впорядкованої множини можна по ребрах спуститися на перший рівень, побувавши на всіх проміжних рівнях. Тобто серед стандартних графів не може бути такого, наприклад, графа:


А повинен бути такий

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

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

Зауваження: число елементів будь-якого кінцевого впорядкованої множини не перевершує твори його довжини на ширину.
Нехай В - непорожня підмножина впорядкованої множини А. Елемент аÎА називається верхньою межею для В, якщо в £ а для всіх вÎВ. Точної верхньою межею В називається найменший елемент множини всіх верхніх граней У в А, його позначають 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 лінійних порядків , Щоб у перетині вони дали безліч А В.
Перший лінійний порядок на А У визначимо наступним чином:
£ ₁ ... .
Тобто ми взяли перший лінійний порядок на А і приписали до нього праворуч перший лінійний порядок на В.
Другий лінійний порядок на А У   отримаємо, взявши з безлічі А лінійний порядок £ _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 _<i c і 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 _<I c і b ^<j d) або (a _<I c і b = d) або (a = c і b ^<j d)
для 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 = A ₁ A ₂ ... A _n = . (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-ку таким чином:
на місце першого компоненти 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.