Редактирование: СППМ/ЧУМ, 01 лекция (от 16 марта)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Сергей Исаевич

Блтжайшие 3 пн мы будем заниматься ЧУМ. Так случилось, что в учебной программе этой теме почти ничего не посвящено, у нас этим мало занимаются, и литературы практически нет. А повод, для чего курс затеян, это понятие размерночти ЧУМ, с этим вообще труба, на русском языке про это вообще ничего нет, всё это статьях или англоязычных книжках. С другой стороны, тематика чрезвычайно интересная, тут много оставшихся нерешёнными проблем, на них лектор будет указывть, и это та область, которая близка к элемент. теории чисел, когда формулировки проблем, теорем формулируются легко, а доказательства очен сложны. Например, как теорема Ферама.

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

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

Постепенно известного (517 группе) будет все меньше и местно, а неизвестного всё больше и больше.

Если у нас есть подмн-во дек. произв. двух совп. мн-в, то оно явл. отношением:
 &rho; &sub; A &times; B
 A = B
 &rho; &isin; A2

какие бывают общие отношения: &nabla; — отношение общее.

Любое подмножество квдарата это отношение. Два объекта нах. в отн. &rho;, если эта пара принадл. &rho;
 a &rho; b <=> ()a, b &isin; &rho;

Некоторые отношения:
* &nabla; A &ne; &empty; — gjkyjt jnyjitybt? dsgjky/ lkz dct[/
* &delta; x &rho; x — диагональное отношение
* (R) &delta; &le; P <=> x &rho; X — рефлексивное отношение
* (AR) &delta; &cup; &rho; = &empty; — антирефлексивное отношение

Двойственное отношение к &rho;: &rho;^d: b &rho;^d a <=> a &rho; b
* Симметричность: &rho; = &rho;^d
* Антисимметричность? &rho; &cup; &rho;^d = &delta; a &rho; b & b &rho; a => a = b
* Транзитивность: ф ?крщж И ? и ?крщж с =Ю ф ?крщж с

Если отношение RST, то это отношение эквивалентности: &epsilon(A). Наименьш. эквив — диагональ, наибольшая — аморфность, когда все эквив. друг другу.

&delta; &isin; ~ &siin; &nabla;

R, AS, T — порядки, обозн. их как &le;.

A &ne; &empty;
P(A) &isin; X, Y, ...
X,Y &isin

a &le; b или b &le; a => a ~ b, a ~/~ b

x &isin; [a, b] = a &le; x & x &le; b

a содержится b, а предшествует b, b покрывает a.

a < b — a строго содерж. в b.

'''P''' = <P, &le;> — упорядоченные множества — пара множества и отношения на нём.

&delta; — и отношение, и порядок. Множество, упор. &delta; нах. тривиально упорядоченным.

Существуют ли такие объекты (упорядоч. мн-ва)? Да, сущ., на любом мн-ве можно ввести порядок.

Важным случае порядка явл. цепь, или ЧУМ, когда любые два элемента сравнимы.

ЧУМ различают:
* конеч. или бесконечные
** Бесконечные, но любой интервал конечен — локально конечные — пример: цепь целых чисел

Примеры: <'''Z''', &le;>, <'''N''', |>. Второй пример — не цепь. <'''R''', &le;>, ('''P'''(A), &sub;)

На мн-ве может быть задан один порядок, может другой, может оказаться, что один есть подмножество другого. Тогда второй порядок есть продолжение первого:
 &le;_1, &le;_2: &le;_1 &; &le

Пробелма, вокруг которой мы будем ходить: любой порядок может быть продолжен до линейного.

Тривилаьный порядок может быть продолжен до любого.

<&epsilon;(A), &sub;> — множество, упорядоч. по разбиению.

Пусть у нас есть мн-во, её классы эквив. есть некое разбиение. Если есть вторая эквив., классы эжквив. явл. разб. данного разбиения, то одна вклад. в другую.

Что такое рисовать ЧУМ: мы будем пользоваться диаграммой Хасса(?). Если a &rho; b, то рисовать стрелку мз b в a. Но тогда надо ещё пририсовать петли. Но так никто не делает, полиз. диагр. Хасса: никто не рисует петель, b рис. выше a, и не рис. транзитивность. Тогда получается, что 4-элементная цепь это вот:

graph {
  3 -- 2 -- 1 -- 0
 }
Это цепь '''4'''. Вообще цепь из n элементов есть '''n'''.

Диагр. вкл. трёх мн-в:
 digraph {
   label 0 "{}"
   label 7 "{a,b,c}"

0 -- 1 -- 3 -- 7
   0 -- 4 -- 6 -- 7
   0 -- 2 -- 6
   2 -- 3
   1 -- 5 -- 7
   5 -- 6
 }
'''2'''^3

Множество из одного элемента — один порядок.

Множество из 2 элементов — три порядка. a ~/~ b, a &le; b, b &le; a

Задача: сколько существует неизоморфных диаграмм Хасса. Число диагр. — H(n)

u(3) = 19
 H(3) = 5
 l(3) = 6

{a, b, c}

Rfrbt tcnm gjhzlrb^ gthdsq — тривиально упорядоченное множество. Второй — цепь. 
 graph { 1 2 3 }
 graph { 1 -- 2 -- 3 }
 graph { 1 -- 2 3 -- 2}
 graph { 2 -- 1 3 -- 2}

А для 4?

Интересно число H(n). Лектор наричует табличку для первых n:

{|
 !n
 |1||2||3||4||5||6||7
 |-
 !H(n)
 |1||2||5||16||63||318||2045
 |-
 !u(n)
 |1||3||19||219||4231||130023||6129856
 |}

Вопрос номер 1: сколько существует H(n)? Формулы нет до сих пор и вряд ли она существует. Однако, есть асимптотики: ln H(n) ~ ((n^2)/4) ln 2. Но не слишком тут преуспели.

Понятно, почему n^2/4: можно представить диаграмму в виде таблицы, симметричность — пополам, транзитивность — ещё пополам.

Не успели мы сделать и шаг, уже столкнулись с проблеммой.

Диаграммы Хасса строят и для беск. мн-в, если понятно, как они выглядят. Например, бесконечная цепь.

Другой пример:
 graph {
   1 -- 2
   1 -- 11 -- 2
   1 -- 21 -- 22 -- 2
   1 -- 31 -- 32 -- 33 -- 2
 }

У ЧУМ ест. обр. опр. подмн-во:
 <P, &le;>
 Если есть q &sub; P, то оно обр. <Q, &le;|Q>, &le;|Q — сущение порядка.

Есть цепи как подмн-ва. уже показан пример лок. конеч. мн-ва, где есть цепь любого размера.

В ЧУм выд. особый элемент: 
# u &isin; P наз. максимальным, если: u &le; x => u = x — нет содерж. его, за ним никто не следует
# min: x &le; => u=x
# наиб: x &le; u
# наим: u &le; x
Ясно, что наиб. эл-то есть макс., но не наоб.: макс. может быть много, наиб. всегда один.

Пример: если у нас Bn, f &isin; M(n). &alpha; явл. нижней единицей, если f(&alpha;) = 1, &forall;&beta; &le; &alpha;: f(&beta) = 0. Тогда все нижнике единицы будут минимальными.

Другой пример — <'''N''', |>

Лектор обр. внимание на цепь. Цепь явл. максимальной, если она явл. цепью в данном мн-ве и при добавл. любого эл-та цепью быть пересатёт.  Другой термин — насыщенная.

Если сущ. макс. эл-т., то порядок. наз. ограниченным.

По поводу скачков: множество макс. элементов — max(P)

Рассмотрим <L, &le;>, постр разб из A и B, A+B=L, причём так, что любой из A &le; лююой из B.

Если в A есть наиб., а в B наим., то это скачок. Для всех цепей разб. есть скачки. Если в A есть наиб., а в B нет наим., или наоборот, то это додекиндово(?) сечение. Третий вариант — когда ни там, ни там нет гранич. элементов — щель. Пример: множество действ. чисел с выкинутым одним значением.

Цепь наз. непр., если все её сеч. додекиндовы. С этим откр. дядюшки Додекинда мы ещё встретимся.

Какие сущ. способы: есть множ. рац. чисел (это, естеств., цепь), какие есть способы его дополнения?
* Метрический, по Коши. Число есть множество.
* По порядку, по Додекинду. 
Эти дополнения совпадают. Чрезвычайно редкий случай.

Здесь метрики не вводим никакой.

Попр. доказать теорему: в ЧУМ каждый элемент содер. мин. и содерж. в макс.

Для конеч. цепей: Если он max, то проблем нет, если нет, то сущ. элемент, который его содерж., и так далее до макс. Если будут u_1...u_k, которые есть неупл. цепь, то будем запис. это как [u_1 ... u_k]

Если имеется в ЧУМ мин. элемент, то эл., след. за min, наз. атомом. В конеч. ЧУМ они всегда сущ., в беск. — не факт.

вот мы построим диагр. Хасса для <N, |>, попр. постр. <N_0, |>, допуская, что 0|0, где он быдет нах.: выше всех. Тогда получилось огр. конеч. ЧУМ, единицей явл. 0, а нулём — едиинца, а атомы — простые числа.

Далее. След. хар-ки.

Если мы возьмём конеч. ЧУМ, и найдём в нём цепь макс. длины. Число эл-тов в ней наз. высотой ЧУМ: h('''P''').

Понятие антицепей: в антицепи любая пара эл-тов не сравнима (в цепи любая пара — сравнима). Ели мы возьмём антицепь, такую, что число эл-тов в ней будет больше, чем число эл-тов в любой другой, то это будет ширина ЧУМ: w('''P''').

Если в мн-ве все макс. цепи один. длины, то множество наз. градуированным (пример — '''2'''^3). сразу же появл. ранговая функция, каждый эл-т имеет свой ранг. Это сколько от него вниз до нулевого. Нулевой имеет нулевой ранг, атомы — первый и так далее.

Рангвое мн-во подразделяется на слои, эл-ты один. ранга. Число элементов ранга k будем обозн. шириной ранга w_k. Очевидно, что любой слой — антицепь. Обратное неверно.

Пример:
 \/ /|
  \ |/
   \/
max_k w_k &le; &omega;(P)
* max_k w_k — число Шпернера
* max_k w_k = &omega;(P) — свойство Ш.

== Изотонные отобр. Порядковые идеалы. ==

Пусть есть <P, &le;>. Пусть A &sub; P

Верхний конус: A^&Delta; = {x&isin;P|&forall;_A a a &le; x}

Двойственно опр. нижний конус: A^&Nabla; = {x&isin;P|&forall;_A a x &le; a}

Если A сост. из одного эл-та, то пишут так: a^&Delta;, a^&Nabla;

Пусть есть <P_1, &le;_1>, <P_2, &le;_2>. Посмотрим отображение: &phi;: P_1 &le; P_2. Хочется рассм. такие &phi;, которые сохр. порядок, так что если a &le;_1 b, то &phi;(a) &le;_2 &phi;(b). Такие отобр. наз. изотонными, сохр. порядок. Если в обр. стороны, то это обр. изотонные. А если наоборот: a &le;_1 b, то &phi;(b) &le;_2 &phi;(a), то антиизотонные.

Если &phi; — биекция, явл. и изотонным и обр. изот., то это изоморфизм.

Зачем обр. изотонность: можно отобр. 2^3 в соотв. с мощностью, то оно не будет обр. изот.

Далее, важное понятие — идеал. Пусть имеется ЧУМ <P, &le;>, I &sub; P, I есть идеал (полуидеал, ...). Если x &isin; I, y &le; X => y &isin; I. Если какой-то эл-т принадлежит идеалу, то прин. и все, к-рые его покрывают. (аналог вверх — фильтр)

Вложенье — инъективное изотонное отобр.

Покажем, что идеалы сущ.: нижний конус — идеал. a^&Nabla; = J(a)

Какие могут быть ещё идеалы: вохьмём антицепь a_1 ... a_k. Возьмём нижние конуса и объединим — будет идеал: J(a_1 ... a_k) = &cup; a^&Nabla;

J(a) — главный идеал, J(a_1 ... a_k) — конеч. порожд. В конеч. ЧУм др. нет.

J(P) — множество всех идеалов ЧУМ. J_0(P) — множество всех главных идеалов. J_0(P) &sub; J(P).

<P(A), &sub;>

Теорема. Любое ЧУМ может быть вложено в множество подмн-в A.

Набросок. док-ва: нетрудно показать, что &phi;(x) = x^&Nabla; есть мономорфизм в множество J(P) и изоморфизм в J_0(P).

J_0(P) &sub; J(P) &sub; '''P'''(P), и лектор утв., что P =~ J_0(P) и &phi; — изоморфизм.

Каждому эл-ту соотв. идеал и только один. Это биекция. Следовательно, это отобр.

Т. о. мы уходим от ЧУМ к множеству подмн-в, а с ним мы можем работать.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://libesyr.so/wiki/%D0%A1%D0%9F%D0%9F%D0%9C/%D0%A7%D0%A3%D0%9C%2C_01_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_16_%D0%BC%D0%B0%D1%80%D1%82%D0%B0%29

@@ Строка 1: / Строка 1: @@
-* '''Диктофонная запись:''' http://esyr.org/lections/audio/am_2009_summer/am_soc_09_03_16.ogg
+Сергей Исаевич
-<gallery perrow="5">
-Изображение:Soc 090316 desk 1.jpg
-Изображение:Soc 090316 desk 2.jpg
-Изображение:Soc 090316 desk 3.jpg
-Изображение:Soc 090316 desk 4.jpg
-Изображение:Soc 090316 desk 5.jpg
-</gallery>
 Блтжайшие 3 пн мы будем заниматься ЧУМ. Так случилось, что в учебной программе этой теме почти ничего не посвящено, у нас этим мало занимаются, и литературы практически нет. А повод, для чего курс затеян, это понятие размерночти ЧУМ, с этим вообще труба, на русском языке про это вообще ничего нет, всё это статьях или англоязычных книжках. С другой стороны, тематика чрезвычайно интересная, тут много оставшихся нерешёнными проблем, на них лектор будет указывть, и это та область, которая близка к элемент. теории чисел, когда формулировки проблем, теорем формулируются легко, а доказательства очен сложны. Например, как теорема Ферама.

Редактирование: СППМ/ЧУМ, 01 лекция (от 16 марта)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты