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

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

• Диктофонная запись: http://esyr.org/lections/audio/am_2009_summer/am_soc_09_03_16.ogg

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

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

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

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

Если у нас есть подмн-во дек. произв. двух совп. мн-в, то оно явл. отношением:

ρ ⊂ A × B
A = B
ρ ∈ A2

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

Любое подмножество квдарата это отношение. Два объекта нах. в отн. ρ, если эта пара принадл. ρ

a ρ b <=> ()a, b ∈ ρ

Некоторые отношения:

• ∇ A ≠ ∅ — gjkyjt jnyjitybt? dsgjky/ lkz dct[/
• δ x ρ x — диагональное отношение
• (R) δ ≤ P <=> x ρ X — рефлексивное отношение
• (AR) δ ∪ ρ = ∅ — антирефлексивное отношение

Двойственное отношение к ρ: ρ^d: b ρ^d a <=> a ρ b

• Симметричность: ρ = ρ^d
• Антисимметричность? ρ ∪ ρ^d = δ a ρ b & b ρ a => a = b
• Транзитивность: ф ?крщж И ? и ?крщж с =Ю ф ?крщж с

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

δ ∈ ~ &siin; ∇

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

A ≠ ∅ P(A) ∈ X, Y, ... X,Y &isin

a ≤ b или b ≤ a => a ~ b, a ~/~ b

x ∈ [a, b] = a ≤ x & x ≤ b

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

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

P =

— упорядоченные множества — пара множества и отношения на нём. δ — и отношение, и порядок. Множество, упор. δ нах. тривиально упорядоченным. Существуют ли такие объекты (упорядоч. мн-ва)? Да, сущ., на любом мн-ве можно ввести порядок. Важным случае порядка явл. цепь, или ЧУМ, когда любые два элемента сравнимы. ЧУМ различают:

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

Примеры: <Z, ≤>, <N, |>. Второй пример — не цепь. <R, ≤>, (P(A), ⊂) На мн-ве может быть задан один порядок, может другой, может оказаться, что один есть подмножество другого. Тогда второй порядок есть продолжение первого: ≤_1, ≤_2: ≤_1 &; &le Пробелма, вокруг которой мы будем ходить: любой порядок может быть продолжен до линейного. Тривилаьный порядок может быть продолжен до любого. <ε(A), ⊂> — множество, упорядоч. по разбиению. Пусть у нас есть мн-во, её классы эквив. есть некое разбиение. Если есть вторая эквив., классы эжквив. явл. разб. данного разбиения, то одна вклад. в другую. Что такое рисовать ЧУМ: мы будем пользоваться диаграммой Хасса(?). Если a ρ 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 ≤ b, b ≤ 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, ≤>
Если есть q ⊂ P, то оно обр. <Q, ≤|Q>, ≤|Q — сущение порядка.

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

В ЧУм выд. особый элемент:

1. u ∈ P наз. максимальным, если: u ≤ x => u = x — нет содерж. его, за ним никто не следует
2. min: x ≤ => u=x
3. наиб: x ≤ u
4. наим: u ≤ x

Ясно, что наиб. эл-то есть макс., но не наоб.: макс. может быть много, наиб. всегда один.

Пример: если у нас Bⁿ, f ∈ M(n). α явл. нижней единицей, если f(α) = 1, ∀β ≤ α: f(&beta) = 0. Тогда все нижнике единицы будут минимальными.

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

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

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

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

Рассмотрим <L, ≤>, постр разб из A и B, A+B=L, причём так, что любой из A ≤ лююой из 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 ≤ ω(P)

• max_k w_k — число Шпернера
• max_k w_k = ω(P) — свойство Ш.

[править] Изотонные отобр. Порядковые идеалы.

Пусть есть <P, ≤>. Пусть A ⊂ P

Верхний конус: A^Δ = {x∈P|∀_A a a ≤ x}

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

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

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

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

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

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

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

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

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

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

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

<P(A), ⊂>

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

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

J_0(P) ⊂ J(P) ⊂ P(P), и лектор утв., что P =~ J_0(P) и φ — изоморфизм.

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

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