СППМ/ЧУМ, 02 лекция (от 23 марта)
Материал из eSyr's wiki.
| (1 промежуточная версия не показана) | |||
| Строка 1: | Строка 1: | ||
| + | * '''Аудиозапись:''' http://esyr.org/lections/audio/am_2009_summer/am_soc_09_03_23.ogg | ||
| + | |||
Пример построения J(P) | Пример построения J(P) | ||
| Строка 267: | Строка 269: | ||
Зачем всё это: с решёткой пор. идеалов связано много комбинат. задач. | Зачем всё это: с решёткой пор. идеалов связано много комбинат. задач. | ||
| + | |||
| + | {{СППМ}} | ||
| + | {{Lection-stub}} | ||
Текущая версия
Пример построения J(P)
d / \ a c | b
I ⊂ P: x ∈ I, y ≤ x ⇒ y ∈ I
- ∅ — идеал
- Идеал, порожд. a:
<a> <b> = J(b)
\ /
∅
* Идеал, порожд. a и b:
<a,b>
/ \
<a> <b> = J(b)
\ /
∅
- c:
<a,b> <c>
/ \ /
<a> <b> = J(b)
\ /
∅
- Объед. идеалов c и a,b:
<a,c>
/ \
<a,b> <c>
/ \ /
<a> <b> = J(b)
\ /
∅
- Объед. идеалов d:
<d>
|
<a,c>
/ \
<a,b> <c>
/ \ /
<a> <b> = J(b)
\ /
∅
Операции над множествами.
Далее нам потр. ЧУМ спец. вида:
x_2 / \ x_1 x_3
Это Z_3. Их наз. заборами или зигзагами.
x_1 x_3 \ / x_2
Это Z_3^d.
y_2 y_4 / \ / y_1 y_3
Z_4
Одеу опрер. мы уже знаем — вщятие двойств. Дмаграмма Х. получ. перевёрнутая.
Вторая операция: добавление наиб. или наим. элемента. Будем обозн. P^.
Третья операция — прямая сумма, P+Q. Если у нас есть два ЧУМ, P и Q, с непересек. носителями: <P, ≤_P>, <Q, ≤_q>, то P ∪ Q наз. множеством объед., а порядок задан след. образом: x ≤ y ⇔ x ≤_P y || x ≤_Q y.
Частично мы делаем вот для чего: обычно все ЧУМ необозримы, и какая-то их классиф., нет её. Например, попытка разл. ЧУМ в прямую сумму и рассм. компоннты. Наск. она удачна, увидим позже.
Вторая операция — порядковая сумма, P +O Q. Это тоже ЧУМ с носителем, порядок опред. след. образом: x ≤ y, если либо x ≤_P y || x ≤_Q y || (x ∈ P && x ∈ Q). Операция некоммут., но ассоц.
Что на ур. диаграмм Х.: надо построить ДХ P, сверху постр. Q, и все макс. эл. P соед. с мин. эл. Q.
Z_4 +O Z_3:
x_2 / \ < вот здесь можно разрезать x_1 x_3 | >< | < вот здесь можно разрезать y_2 y_4 / \ / < здесь — нельзя. y_1 y_3
Лубое ЧУМ. разл. в множ. упор. или неуп. элементоа.
Лексикограф. сумма: <P, ≤_P>, причём с каж. эл-том P связано ЧУМ <Q_p, ≤_p>. Сейчас будет подстановка: ∑_p Q_p. Его элементы — пары (p,q), а порядок — след. образом: (p, q) ≤ (p', q') ⇔ (p <_P p') || ((p = p') && (q ≤_p q'))
На уровне диагграмм Х.: надо нарис. P, откинуть все линии, вместо каждого эл-та нарис. Q, и соед. элементы макс. и мин. элементы.
b u w y / \ \ / | .z a c v x P Q_a Q_b Q_c
by
|
bx
/ | \
/ | \
au av cz
\ /
aw
Призведения
Прямое произведение P × Q есть упорядоч. мн-во с носителем P × Q, порядок задаётся след. образом: (p, q) ≤ (p', q') ⇔ p ≤_P p' && q ≤_Q q'. На ур. диагр. Х. вместо каждого элемента из P ставим Q и соед. соотв. элементы.
< Пример Z_3 × Z_4 >
P × Q ~= Q × P. Однако диагр. Х. будут совершенно непохожи.
Важна след. теорема: каждый частич. порядок вложим в произв. соотв. цепей: P ⊂-> C_1 × ... × C_k.
По поводу прямой суммы: 1 озн. один элмент, если есть P+Q, то есть и nP. Что такое n1? Антицепь из n элементов. А что такое 1 +O 1 +O ... +O 1? n-элем. цепь.
Z_3 вкл. в 2 × 2, Z_4 вкл. в 2 × 3/
Интересное мн-во S_3:
d e f |\/ \/| |/\ /\| a b c
S_3 вкл. 2^3
Теорема Оре: любое подх. мн-во вкл. в подх. произв. цепей. Минимальное k наз. мультипликативной размерностью. У Z_3 и Z_4 она равна 2, у S_3 — 3.
Прямое произведение. Если P×Q ~= P×R ⇒ Q ~= R.
P^n ~= Q^n ⇒ P ~= Q.
Степень. Есть два ЧУМ, <P, ≤_P>, <Q, ≤_Q>, P^Q — множество всех изотонных отобр. из Q в P: {f: Q → P | f — изотонная}, порядок: f ≤ g: ∀_Q x: f(x) ≤_P q(x)
Для д. Х. нет простого алгоритма. для примера лектор построит Z_4^{Z_3}:
< пример >
2 ×' 3:
bz / \ by az / \ / bz ay \ / ax
Что известно про степень:
- P^Q ~= P^R ⇒ Q ~= R
- P^Q ~= R^Q. Гарри ... предп, что из этого следует, что P ~=R. Док. нет до сих пор, хотя для многих ЧУМ это справедливо.
Что здесь следует сказать: для этих операций (больше опер. вводиться не будет) +, ×, ↑ действ. законы коммут., ассоц., дистриб., как в обыкн. алгебре.
- P × (Q + R) ~= P×Q+P×R
- P^{Q × R} ~= (P^Q)^R
Кроме того:
- 1^P ~= 1
- 2^n ~= (n + 1)
2^n — множ. всех ф-ций из n в 2. Если считать, что 2 = [0,1], то в каждой ф-ции будет 0..01...1, всего в векторе n элементов, и их количество n+1. Расположены они друг над другом, отсюда (n + 1).
n^P — множество функций перевода из Р в n-элементную цепь.
- n^P ~= (2^{n-1})^P ~= 2^{n-1 × P}
Д/З: 3^{3}
Понятие решётки. Можно вывести из понятия ЧУМ, ЧУМ специального вида, решёточно-упорядоч.
В ЧУМ у нас были опр. верхнего и нижнего конусы: A_δ, A^∇, A⊂P, это ЧУМ, наслед. исх. порядок. Может так статься, что у верхнего конуса найдётся наим. элемент, тогда он наз. sup A, а в нижнем может оказ. макс. элемент, inf A. Решёточноу упор. мн-во такое, что любая пара элементов имеет inf и sup. Кдассический пример:
d / \ | | / \ | c | | / \ | a b
Понятно, что это не реш., так как конус для a и b не им. sup. A^δ = {c,d}
Булева алгебра: P(A)
...
Полная решётка — inf/sup суш. у любого подмн-ва.
Другой подход к решётке: <L, |_|, П>. Эти операции подч. законам коммутативности: a |_| b = b |_| a (аналогич. для пересеч.); ассоциативности: a П (b П c) = (a П b) П c; jvybgjntynyjcnb x |_| x = x; полгощения x |_| (x П y) = x.
Любое решёточно упор. множество есть решётка и наоборот. a |_| b = sup {a,b}, a П b = inf {a, b}.
Очень редкий случай в математике. Когда объект описан и как модель, и как алгебра. Такая двойственность порождает очень богатую теорию.
Цепи, булевы алгебры, произв. есть решётки.
Решётки:
| | | /\
| | \/
|
/\ | /\ \/ /\ | \ /|\ | \/ \ / \|/
Везде, где будет присут. такое ЧУМ:
|X|
и гомеоморфное ему, то это уже не решётка.
Есть ЧУМ P. Вопрос: можно ли его достр. до решётки? Ответ можно, и на это отв. теорема Мак Нила (?): P может быть вложено в полую решётку L. Это предст. интерес, когда P беск.
Пример: достр. до решётки. Ввежём операции (X ⊂ P):
- X^^δ = G(x)
- X^^∇ = L(x)
Утв., что P*(P) есть решётка.
(пример)
Добавились замыкания Мак Нила. Конструкция, которую предложил Додекинд для постр. действ. чисел сечениями, может быть продолжена для любых ЧУМ. Поэтому это замык. наз. Додекинда-Мак Нила.
Понятие дистр. решётки: та же решётка плюс вып. закон дистрибутивности:
- (a |_| b) П c = (a П c) |_| ( b П c)
Было время, когда Додекинд и другие великие думали, что вообще все решётки дистриб.
Дистриб решётки интересны вот почему: оказывается, решётка порядоквых идеалов есть дистрибутивная решётка. Док-во: объед. пордяк. идеалов есть пордяк. идеал (sup), пересеч. тоже (inf), это алгебра, а алгебра дистриб. Такая констр. наз. кольцо множеств. (не путать с алгебр. кольцом). Если есть опер. дополнния, то поле множеств.
Лектор говорил, что эл-ты, непоср. след. за 0, наз. атомами. В решётке атомов 2, в цепи — 1. В дистр. решётках, в булевых алгебрах понятие атома имеет центр. роль, если мы знаем атомы, знаем всё. В теории дистр. решёток центральную роль игр. не атомы, тут центр. роль решают неразложимые в объед. элементы.
Элемент наз. неразлож. в объед, если из a = b |_| c ⇐ a = b || a = c
В рассм. в начале лекции примере <c> неразложим.
Множество всех неразлож. эл-тов L будем обозн. I_{rr}(L).
Важность этих элементов: любой элемент: x = |_| a, a ∈ I_rr(x), I_rr(x) = I_rr(L) ∩ X^∇.
Любой элемент может предст. как объед. неразложимых, в нём содерж.
Пусть есть ЧУМ P. Множество пор. идеалов J(P) есть дистриб. решётка. А если взять Irr(J(P)), то что это такое? Irr(J(P)) ~= P. Доказательство: в дистр. решётке какой эл-т неразложим? Только собст., порожд. одним элементом.
Изоморфизм φ(x) = x^∇ ставит в соотв. элементу его главный идеал.
Мы взяли ЧУМ, взяли множ. идеалов, взяли разлож и получили то, что было. А если назад: J(Irr(L)), будет ли это то, что было? Да, если L конеч-дистр.
Этот факт в случае, если L конеч. и дистриб., наз. фактом о конеч. дистр. решётках, ФТКДР.
Теперь переходим к самому интересному. Есть ЧУМ, по нему можно постр. решётку пор. идеалов. Нас будет интиер. вопрос выч. элементов этой решётки. |J(P)| = j(P). Основными действ. элементами будут явл. след. множества:
- Z_k
- Забор с соед. кр. элементами. Малая корона — s_n
- Двудольное ЧУМ, по n элементов, где верх. связ. со всеми ниж, кроме своего индекса: a_i < b_i, i ≠ j. Это наз. большая корона — S_n.
s_n, S_n — 2n-эл множества, n>3.
Для n ≥ 3, k ≥ 0 вводится двудольный граф из 2(n+k) элементов, где верхние эл. соед. с нижними n, начиная с i+k+1, циклически. Обобщённая корона.
Почему именно они? Они держат проблему. известно было, что если взять забор из n элементов, построить решётку пор. ид., и посчитать число их, то |J(Z_n)| = F_(n+2) (n+2 число Фиббоначи)
В комбин. есть число Люка: L_n = F_{n+1}+F_{n-1}
Д.З.: j(s_n) = L_{2n}
j(S_n) = 2^{n+1} + n - 1
Зачем всё это: с решёткой пор. идеалов связано много комбинат. задач.
| Математические методы решения биометрических задач | 1 2 |
|---|---|
| Некоторые проблемы теории ЧУМ | 1 2 3 |
| Систематизация терминологии | 1 2 |
