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

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

Версия от 18:42, 23 марта 2009; ESyr01 (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Пример построения J(P)

 d
/ \
a  c
   |
   b

I ⊂ P: x ∈ I, y ≤ x ⇒ y ∈ I

  • ∅ — идеал
  • Идеал, порожд. a:
<a>   = 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, с непересек. носителями:

, <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 &times ... × C_k. По поводу прямой суммы: 1 озн. один элмент, если есть P+Q, то есть и nP. Что такое n1? Антицепь из n элементов. А что такое 1 +O 1 +O ... +O 1? n-элем. цепь. Z_3 вкл. в 2 &times 2, Z_4 вкл. в 2 &times 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 &times' 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 Зачем всё это: с решёткой пор. идеалов связано много комбинат. задач.


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.

Личные инструменты
Разделы