СППМ/ЧУМ, 01 лекция (от 16 марта)
Материал из eSyr's wiki.
(Новая: Сергей Исаевич Блтжайшие 3 пн мы будем заниматься ЧУМ. Так случилось, что в учебной программе этой тем...) |
|||
| Строка 1: | Строка 1: | ||
| - | + | <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 пн мы будем заниматься ЧУМ. Так случилось, что в учебной программе этой теме почти ничего не посвящено, у нас этим мало занимаются, и литературы практически нет. А повод, для чего курс затеян, это понятие размерночти ЧУМ, с этим вообще труба, на русском языке про это вообще ничего нет, всё это статьях или англоязычных книжках. С другой стороны, тематика чрезвычайно интересная, тут много оставшихся нерешёнными проблем, на них лектор будет указывть, и это та область, которая близка к элемент. теории чисел, когда формулировки проблем, теорем формулируются легко, а доказательства очен сложны. Например, как теорема Ферама. | Блтжайшие 3 пн мы будем заниматься ЧУМ. Так случилось, что в учебной программе этой теме почти ничего не посвящено, у нас этим мало занимаются, и литературы практически нет. А повод, для чего курс затеян, это понятие размерночти ЧУМ, с этим вообще труба, на русском языке про это вообще ничего нет, всё это статьях или англоязычных книжках. С другой стороны, тематика чрезвычайно интересная, тут много оставшихся нерешёнными проблем, на них лектор будет указывть, и это та область, которая близка к элемент. теории чисел, когда формулировки проблем, теорем формулируются легко, а доказательства очен сложны. Например, как теорема Ферама. | ||
Версия 18:36, 23 марта 2009
 |
 |
 |
 |
 |
Блтжайшие 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 =— упорядоченные множества — пара множества и отношения на нём. δ — и отношение, и порядок. Множество, упор. δ нах. тривиально упорядоченным. Существуют ли такие объекты (упорядоч. мн-ва)? Да, сущ., на любом мн-ве можно ввести порядок. Важным случае порядка явл. цепь, или ЧУМ, когда любые два элемента сравнимы. ЧУМ различают:
- конеч. или бесконечные
- Бесконечные, но любой интервал конечен — локально конечные — пример: цепь целых чисел
| 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 — сущение порядка.
Есть цепи как подмн-ва. уже показан пример лок. конеч. мн-ва, где есть цепь любого размера.
В ЧУм выд. особый элемент:
- u ∈ P наз. максимальным, если: u ≤ x => u = x — нет содерж. его, за ним никто не следует
- min: x ≤ => u=x
- наиб: x ≤ u
- наим: u ≤ x
Ясно, что наиб. эл-то есть макс., но не наоб.: макс. может быть много, наиб. всегда один.
Пример: если у нас Bn, 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) и φ — изоморфизм.
Каждому эл-ту соотв. идеал и только один. Это биекция. Следовательно, это отобр.
Т. о. мы уходим от ЧУМ к множеству подмн-в, а с ним мы можем работать.
| Математические методы решения биометрических задач | 1 2 |
|---|---|
| Некоторые проблемы теории ЧУМ | 1 2 3 |
| Систематизация терминологии | 1 2 |
