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

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

* '''Аудиозапись:''' http://esyr.org/lections/audio/am_2009_summer/am_soc_09_03_23.ogg

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

d
 / \
 a  c
    |
    b

I &sub; P: x &isin; I, y &le; x &rArr; y &isin; I

* &empty; — идеал
* Идеал, порожд. a:
 <a>  &lt;b> = J(b)
   \  /
     &empty;
* Идеал, порожд. a и b:
   <a,b>
   /  \
 <a>  <b> = J(b)
   \  /
     &empty;
* c:
   <a,b> <c>
   /  \ /
 <a>  <b> = J(b)
   \  /
     &empty;
* Объед. идеалов c и a,b:
      <a,c>
      /  \
   <a,b> <c>
   /  \  /
 <a>  <b> = J(b)
   \  /
     &empty;
* Объед. идеалов d:
      <d>
       |
      <a,c>
      /  \
   <a,b> <c>
   /  \  /
 <a>  <b> = J(b)
   \  /
     &empty;

Операции над множествами.

Далее нам потр. ЧУМ спец. вида:

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, &le;_P>, <Q, &le;_q>, то P &cup; Q наз. множеством объед., а порядок задан след. образом: x &le; y &hArr; x &le;_P y || x &le;_Q y.

Частично мы делаем вот для чего: обычно все ЧУМ необозримы, и какая-то их классиф., нет её. Например, попытка разл. ЧУМ в прямую сумму и рассм. компоннты. Наск. она удачна, увидим позже.

Вторая операция — порядковая сумма, P +O Q. Это тоже ЧУМ с носителем, порядок опред. след. образом: x &le; y, если либо x &le;_P y || x &le;_Q y || (x &isin; P && x &isin; 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, &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'))

На уровне диагграмм Х.: надо нарис. 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 &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 >

P &times; Q ~= Q &times; P. Однако диагр. Х. будут совершенно непохожи.

Важна след. теорема: каждый частич. порядок вложим в произв. соотв. цепей: P &sub;-> C_1 &times ... &times; C_k.

По поводу прямой суммы: '''1''' озн. один элмент, если есть P+Q, то есть и nP. Что такое n'''1'''? Антицепь из 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&times;Q ~= P&times;R &rArr; Q ~= R.

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)

Для д. Х. нет простого алгоритма. для примера лектор построит Z_4^{Z_3}:

< пример >

'''2''' &times' '''3''':
     bz
    / \
   by  az
   / \ /
  bz  ay
   \ /
   ax

Что известно про степень:
* P^Q ~= P^R &rArr; Q ~= R
* P^Q ~= R^Q. Гарри ... предп, что из этого следует, что P ~=R. Док. нет до сих пор, хотя для многих ЧУМ это справедливо.

Что здесь следует сказать: для этих операций (больше опер. вводиться не будет) +, &times;, &uarr; действ. законы коммут., ассоц., дистриб., как в обыкн. алгебре.
* P &times; (Q + R) ~= P&times;Q+P&times;R
* P^{Q &times; 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''' &times; P}

Д/З: '''3'''^{'''3'''}

Понятие решётки. Можно вывести из понятия ЧУМ, ЧУМ специального вида, решёточно-упорядоч.

В ЧУМ у нас были опр. верхнего и нижнего конусы: A_&delta;, A^&nabla;, A&sub;P, это ЧУМ, наслед. исх. порядок. Может так статься, что у верхнего конуса найдётся наим. элемент, тогда он наз. sup A, а в нижнем может оказ. макс. элемент, inf A. Решёточноу упор. мн-во такое, что любая пара элементов имеет inf и sup. Кдассический пример:

d
   / \
   | |
  /   \
 |  c  |
 | / \ |
 a     b

Понятно, что это не реш., так как конус для a и b не им. sup. A^&delta; = {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 &sub; P):
* X^^&delta; = G(x)
* X^^&nabla; = L(x)
Утв., что '''P'''*(P) есть решётка.

(пример)

Добавились замыкания Мак Нила. Конструкция, которую предложил Додекинд для постр. действ. чисел сечениями, может быть продолжена для любых ЧУМ. Поэтому это замык. наз. Додекинда-Мак Нила.

Понятие дистр. решётки: та же решётка плюс вып. закон дистрибутивности:
* (a |_| b) П c = (a П c) |_| ( b П c)

Было время, когда Додекинд и другие великие думали, что вообще все решётки дистриб.

Дистриб решётки интересны вот почему: оказывается, решётка порядоквых идеалов есть дистрибутивная решётка. Док-во: объед. пордяк. идеалов есть пордяк. идеал (sup), пересеч. тоже (inf), это алгебра, а алгебра дистриб. Такая констр. наз. кольцо множеств. (не путать с алгебр. кольцом). Если есть опер. дополнния, то поле множеств.

Лектор говорил, что эл-ты, непоср. след. за 0, наз. атомами. В решётке атомов 2, в цепи — 1. В дистр. решётках, в булевых алгебрах понятие атома имеет центр. роль, если мы знаем атомы, знаем всё. В теории дистр. решёток центральную роль игр. не атомы, тут центр. роль решают неразложимые в объед. элементы.

Элемент наз. неразлож. в объед, если из a = b |_| c &lArr; a = b || a = c

В рассм. в начале лекции примере <c> неразложим.

Множество всех неразлож. эл-тов L будем обозн. I_{rr}(L).

Важность этих элементов: любой элемент: x = |_| a, a &isin; I_rr(x), I_rr(x) = I_rr(L) &cap; X^&nabla;.

Любой элемент может предст. как объед. неразложимых, в нём содерж.

Пусть есть ЧУМ P. Множество пор. идеалов J(P) есть дистриб. решётка. А если взять Irr(J(P)), то что это такое? Irr(J(P)) ~= P. Доказательство: в дистр. решётке какой эл-т неразложим? Только собст., порожд. одним элементом.

Изоморфизм &phi;(x) = x^&nabla; ставит в соотв. элементу его главный идеал.

Мы взяли ЧУМ, взяли множ. идеалов, взяли разлож и получили то, что было. А если назад: J(Irr(L)), будет ли это то, что было? Да, если L конеч-дистр.

Этот факт в случае, если L конеч. и дистриб., наз. фактом о конеч. дистр. решётках, ФТКДР.

Теперь переходим к самому интересному. Есть ЧУМ, по нему можно постр. решётку пор. идеалов. Нас будет интиер. вопрос выч. элементов этой решётки. |J(P)| = j(P). Основными действ. элементами будут явл. след. множества:
* Z_k
* Забор с соед. кр. элементами. Малая корона — s_n
* Двудольное ЧУМ, по n элементов, где верх. связ. со всеми ниж, кроме своего индекса: a_i < b_i, i &ne; j. Это наз. большая корона — S_n.
s_n, S_n — 2n-эл множества, n>3.

Для n &ge; 3, k &ge; 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

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

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.name/wiki/%D0%A1%D0%9F%D0%9F%D0%9C/%D0%A7%D0%A3%D0%9C%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_23_%D0%BC%D0%B0%D1%80%D1%82%D0%B0%29

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

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