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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 11: Строка 11:
* ∅ — идеал
* ∅ — идеал
* Идеал, порожд. a:
* Идеал, порожд. a:
-
<a> &lt;b> = J(b)
+
&lt;a&gt; &lt;b&gt; = J(b)
\ /
\ /
&empty;
&empty;
-
* Идеал, порожд. a и b:
+
* Идеал, порожд. a и b:
-
<a,b>
+
&lt;a,b&gt;
/ \
/ \
-
<a> <b> = J(b)
+
&lt;a&gt; &lt;b&gt; = J(b)
\ /
\ /
&empty;
&empty;
* c:
* c:
-
<a,b> <c>
+
&lt;a,b&gt; &lt;c&gt;
/ \ /
/ \ /
-
<a> <b> = J(b)
+
&lt;a&gt; &lt;b&gt; = J(b)
\ /
\ /
&empty;
&empty;
* Объед. идеалов c и a,b:
* Объед. идеалов c и a,b:
-
<a,c>
+
&lt;a,c&gt;
/ \
/ \
-
<a,b> <c>
+
&lt;a,b&gt; &lt;c&gt;
/ \ /
/ \ /
-
<a> <b> = J(b)
+
&lt;a&gt; &lt;b&gt; = J(b)
\ /
\ /
&empty;
&empty;
* Объед. идеалов d:
* Объед. идеалов d:
-
<d>
+
&lt;d&gt;
|
|
-
<a,c>
+
&lt;a,c&gt;
/ \
/ \
-
<a,b> <c>
+
&lt;a,b&gt; &lt;c&gt;
/ \ /
/ \ /
-
<a> <b> = J(b)
+
&lt;a&gt; &lt;b&gt; = J(b)
\ /
\ /
&empty;
&empty;
Строка 69: Строка 69:
Вторая операция: добавление наиб. или наим. элемента. Будем обозн. P^.
Вторая операция: добавление наиб. или наим. элемента. Будем обозн. P^.
-
Третья операция — прямая сумма, P+Q. Если у нас есть два ЧУМ, P и Q, с непересек. носителями: <P, &le;_P>, <Q, &le;_q>, то P &cup; Q наз. множеством объед., а порядок задан след. образом: x &le; y &hArr; x &le;_P y || x &le;_Q y.
+
Третья операция — прямая сумма, P+Q. Если у нас есть два ЧУМ, P и Q, с непересек. носителями: &lt;P, &le;_P&gt;, &lt;Q, &le;_q&gt;, то P &cup; Q наз. множеством объед., а порядок задан след. образом: x &le; y &hArr; x &le;_P y || x &le;_Q y.
Частично мы делаем вот для чего: обычно все ЧУМ необозримы, и какая-то их классиф., нет её. Например, попытка разл. ЧУМ в прямую сумму и рассм. компоннты. Наск. она удачна, увидим позже.
Частично мы делаем вот для чего: обычно все ЧУМ необозримы, и какая-то их классиф., нет её. Например, попытка разл. ЧУМ в прямую сумму и рассм. компоннты. Наск. она удачна, увидим позже.
Строка 80: Строка 80:
x_2
x_2
-
/ \ < вот здесь можно разрезать
+
/ \ &lt; вот здесь можно разрезать
x_1 x_3
x_1 x_3
-
| >< | < вот здесь можно разрезать
+
| &gt;&lt; | &lt; вот здесь можно разрезать
y_2 y_4
y_2 y_4
-
/ \ / < здесь — нельзя.
+
/ \ / &lt; здесь — нельзя.
y_1 y_3
y_1 y_3
Лубое ЧУМ. разл. в множ. упор. или неуп. элементоа.
Лубое ЧУМ. разл. в множ. упор. или неуп. элементоа.
-
Лексикограф. сумма: <P, &le;_P>, причём с каж. эл-том P связано ЧУМ <Q_p, &le;_p>. Сейчас будет подстановка: &sum;_p Q_p. Его элементы — пары (p,q), а порядок — след. образом: (p, q) &le; (p', q') &hArr; (p <_P p') || ((p = p') && (q &le;_p q'))
+
Лексикограф. сумма: &lt;P, &le;_P&gt;, причём с каж. эл-том P связано ЧУМ &lt;Q_p, &le;_p&gt;. Сейчас будет подстановка: &sum;_p Q_p. Его элементы — пары (p,q), а порядок — след. образом: (p, q) &le; (p', q') &hArr; (p &lt;_P p') || ((p = p') && (q &le;_p q'))
На уровне диагграмм Х.: надо нарис. P, откинуть все линии, вместо каждого эл-та нарис. Q, и соед. элементы макс. и мин. элементы.
На уровне диагграмм Х.: надо нарис. P, откинуть все линии, вместо каждого эл-та нарис. Q, и соед. элементы макс. и мин. элементы.
Строка 112: Строка 112:
Прямое произведение P &times; Q есть упорядоч. мн-во с носителем P &times; Q, порядок задаётся след. образом: (p, q) &le; (p', q') &hArr; p &le;_P p' && q &le;_Q q'. На ур. диагр. Х. вместо каждого элемента из P ставим Q и соед. соотв. элементы.
Прямое произведение P &times; Q есть упорядоч. мн-во с носителем P &times; Q, порядок задаётся след. образом: (p, q) &le; (p', q') &hArr; p &le;_P p' && q &le;_Q q'. На ур. диагр. Х. вместо каждого элемента из P ставим Q и соед. соотв. элементы.
-
< Пример Z_3 &times; Z_4 >
+
&lt; Пример Z_3 &times; Z_4 &gt;
P &times; Q ~= Q &times; P. Однако диагр. Х. будут совершенно непохожи.
P &times; Q ~= Q &times; P. Однако диагр. Х. будут совершенно непохожи.
-
Важна след. теорема: каждый частич. порядок вложим в произв. соотв. цепей: P &sub;-> C_1 &times ... &times; C_k.
+
Важна след. теорема: каждый частич. порядок вложим в произв. соотв. цепей: P &sub;-&gt; C_1 &times ... &times; C_k.
По поводу прямой суммы: '''1''' озн. один элмент, если есть P+Q, то есть и nP. Что такое n'''1'''? Антицепь из n элементов. А что такое 1 +O 1 +O ... +O 1? n-элем. цепь.
По поводу прямой суммы: '''1''' озн. один элмент, если есть P+Q, то есть и nP. Что такое n'''1'''? Антицепь из n элементов. А что такое 1 +O 1 +O ... +O 1? n-элем. цепь.
Строка 136: Строка 136:
P^n ~= Q^n &rArr; P ~= Q.
P^n ~= Q^n &rArr; P ~= Q.
-
Степень. Есть два ЧУМ, <P, &le;_P>, <Q, &le;_Q>, P^Q — множество всех изотонных отобр. из Q в P: {f: Q &rarr; P | f — изотонная}, порядок: f &le; g: &forall;_Q x: f(x) &le;_P q(x)
+
Степень. Есть два ЧУМ, &lt;P, &le;_P&gt;, &lt;Q, &le;_Q&gt;, P^Q — множество всех изотонных отобр. из Q в P: {f: Q &rarr; P | f — изотонная}, порядок: f &le; g: &forall;_Q x: f(x) &le;_P q(x)
Для д. Х. нет простого алгоритма. для примера лектор построит Z_4^{Z_3}:
Для д. Х. нет простого алгоритма. для примера лектор построит Z_4^{Z_3}:
-
< пример >
+
&lt; пример &gt;
'''2''' &times' '''3''':
'''2''' &times' '''3''':
Строка 190: Строка 190:
Полная решётка — inf/sup суш. у любого подмн-ва.
Полная решётка — inf/sup суш. у любого подмн-ва.
-
Другой подход к решётке: <L, |_|, П>. Эти операции подч. законам коммутативности: a |_| b = b |_| a (аналогич. для пересеч.); ассоциативности: a П (b П c) = (a П b) П c; jvybgjntynyjcnb x |_| x = x; полгощения x |_| (x П y) = x.
+
Другой подход к решётке: &lt;L, |_|, П&gt;. Эти операции подч. законам коммутативности: 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}.
Любое решёточно упор. множество есть решётка и наоборот. a |_| b = sup {a,b}, a П b = inf {a, b}.
Строка 234: Строка 234:
Элемент наз. неразлож. в объед, если из a = b |_| c &lArr; a = b || a = c
Элемент наз. неразлож. в объед, если из a = b |_| c &lArr; a = b || a = c
-
В рассм. в начале лекции примере <c> неразложим.
+
В рассм. в начале лекции примере &lt;c&gt; неразложим.
Множество всех неразлож. эл-тов L будем обозн. I_{rr}(L).
Множество всех неразлож. эл-тов L будем обозн. I_{rr}(L).
Строка 253: Строка 253:
* Z_k
* Z_k
* Забор с соед. кр. элементами. Малая корона — s_n
* Забор с соед. кр. элементами. Малая корона — s_n
-
* Двудольное ЧУМ, по n элементов, где верх. связ. со всеми ниж, кроме своего индекса: a_i < b_i, i &ne; j. Это наз. большая корона — S_n.
+
* Двудольное ЧУМ, по n элементов, где верх. связ. со всеми ниж, кроме своего индекса: a_i &lt; b_i, i &ne; j. Это наз. большая корона — S_n.
-
s_n, S_n — 2n-эл множества, n>3.
+
s_n, S_n — 2n-эл множества, n&gt;3.
Для n &ge; 3, k &ge; 0 вводится двудольный граф из 2(n+k) элементов, где верхние эл. соед. с нижними n, начиная с i+k+1, циклически. Обобщённая корона.
Для n &ge; 3, k &ge; 0 вводится двудольный граф из 2(n+k) элементов, где верхние эл. соед. с нижними n, начиная с i+k+1, циклически. Обобщённая корона.
Строка 267: Строка 267:
Зачем всё это: с решёткой пор. идеалов связано много комбинат. задач.
Зачем всё это: с решёткой пор. идеалов связано много комбинат. задач.
- 
-
{{СППМ}}
 
-
{{Lection-stub}}
 

Версия 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

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

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