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

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

Версия 18:45, 23 марта 2009

Пример построения 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 &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

Зачем всё это: с решёткой пор. идеалов связано много комбинат. задач.