Экзаменационный теоретический минимум (ответы) (1127336), страница 3
Текст из файла (страница 3)
Поэтому, как правило, исследуются только левые действия.ФиксаторЗафиксируем перестановки и найдем все элементы множества, которые перестановка оставит на месте. Множество таких элементов фиксатор. F ix(g) = {m ∈ M : g(m) = m} ⊆ MСтабилизаторЗафиксируем элементы и найдем все перестановки, которые оставляют данный элемент неподвижным. Множество такихперестановок - стабилизатор. Stab(m) = {g ∈ G : g(m) = m} ⊆ GЛемма Бернсайда и её применение.ПодмножествоGm = {gm ∣ g ∈ G} ⊂ Mназывается орбитой элемента m∈ M.Действие группы G на множестве M определяет на нём отношение эквивалентности∀n, m ∈ M (n ∼G m) ⟺ (∃g ∈ G : gn = m) ⟺ (Gn = Gm).При этом классами эквивалентности являются орбиты элементов. Поэтому, если общее число классов эквивалентности равно k, тоM = Gm1 ⊔ Gm2 ⊔ … ⊔ Gmk ,где m1 ,m2 , … , mk ∈ M попарно неэквивалентны.
Для транзитивного действия k = 1.Лемма БернсайдаПусть G — конечная группа, действующая на множестве X. Для любого элемента g из G будем обозначать через Fix(g) множествоэлементов X, оставляемых на месте g . Лемма Бёрнсайда даёт формулу числа орбит группы G , обозначаемого C(G):C(G) =1|G|∑g∈G |F ix(g)|.ПримерСоставляются слова длины l ≥ 2 из алфавита A = a1 , a2 , ⋯ , am .
Слова считаются эквивалентными, если они получаютсяодно из другого перестановкой крайних букв. Определить число S неэквивалентных слов.= |T | = ml. Представим эквивалентности как орбиты некоторогодействия подходящей группы G на T. Поскольку g = e, то подходящей группой будет G = Z2 = {e, g}. Действие g переставляетв слове две крайние буквы. Число S неэквивалентных слов есть число классов эквивалентности C(G) действия Z2 : T .|F ix(e)| = |T | = ml , |F ix(g)| = ml−2 ∗ m = ml−1Решение: Пусть T - множество слов длины l в алфавите A. N2S = C(Z2 ) =12∗ ∑g∈G |F ix(g)| =ml +ml−12=ml−1∗(m+1)l2= 3, m = 2, S = 6Цикловой индекс действия группыСуществует универсальный способ вычисления числа орбит C(G)=g ∈ G вес w(g) по правилу:1|G|∑g∈G |Fix(g)|..
Сопоставим каждой перестановкеT ype(g) =≤ v1 , v2 , v3 , ⋯ , vn ≥, где vi - количество циклов длины i для перестановки g. w(g) = xv11 ∗ … ∗ xvNNЦикловой индекс группы G определяется как многочлен от n переменных x1 , x2 , … , xnP=1|G|v (g)∑g∈G x11v (g)⋅ x22v (a)⋅ … ⋅ xnnГруппы симметрий правильных многоугольников (диэдральные группы) и группывращений правильных многогранников. Примеры.
Их цикловые индексы.D3 = S3 (для треугольника = симметрической группе для 3 элементов)Рассматривает многоульник. Рассмотрим преобразования, которые его переводят в самого себяОтраженияПоворотыЗадача: группа октаедра (не будет) только куб посчитать цикловой индексВычислены цикловые индексы и есть формула для произвольного n (http://mathworld.wolfram.com/DihedralGroup.html)Теорема Редфилда-Пойа и её применениеЦикловой индекс действия группыСуществует универсальный способ вычисления числа орбит C(G)g ∈ G вес w(g) по правилу:=1|G|∑g∈G |Fix(g)|.. Сопоставим каждой перестановкеT ype(g) = ⟨v1 , v2 , v3 , ⋯ , vn ⟩, где vi - количество циклов длины i для перестановки g.
w(g) = xv11 ∗ … ∗ xvNNЦикловой индекс группы G определяется как многочлен от n переменных x1 , x2 , … , xnP=1|G|v (g)∑g∈G x11v (g)⋅ x22v (a)⋅ … ⋅ xnnТеорема Редфилда-ПойаК множеству T, |T|= N , группе G, |G| = n и действию Gα : T добавим множество R = {c1 , c2 , … , cr } меток иTTсовокупность функций F = R приписывания элементам меток. G, действуя на T , действует и на R . Дадим вес элементам R:w(ci ) = yi ∀i = 1, 2, … , rЦикловой индекс действия группы G на R есть W(F )Txk = y1k + … + yrk= P (Gα : RT ) = P (Gα : T , x1 , x2 , … , xN ), причемТеорему Редфилда-Пойа можно использовать для вычисления числа разметок данного типа(содержащих данное количество элементовконкретного типа). Лемму Бернсайда можно использовать для вычисления общего количества неэквивалентных разметок.ПримерЗадача об ожерельях - 5 бусин, 3 цвета(красный, зеленый, синий).
Ожерелья считаются одинаковыми, если они совпадают при ихповороте или перевороте. Сколько существует различных ожерелий, содержащих 2 красные бусины?x1 = y1 + y2 + y3 , x2 = y12 + y22 + y32 , … , xk = y1k + y2k + y3kw(КРАСНЫЙ) = y1, w(СИНИЙ) = y2, w(ЗЕЛЕНЫЙ) = y3y1 = y, y2 = y3 = 1x1 = y + 2, x2 = y 2 + 2, … , x5 = y 5 + 21P (x1 , x2 , … , x5 ) = 10∗ (x51 + 4 ∗ x5 + 5 ∗ x1 ∗ x22 )(было посчитано в простой задаче на ожерелья)P (y) = ∑5i=1 ui ∗ y i11P (y) = 10∗ (u0 + u1 ∗ u + u2 ∗ y 2 + … + u5 ∗ y 5 ) = 10∗ ((y + 2)5 + 4 ∗ (y 5 + 2) + 5 ∗ (y + 2) ∗ (y 2 + 2)2 )1P (y) = 10∗ (… + (10 ∗ 8 + 5 ∗ 2 ∗ 4) ∗ y 2 + …) → u2 = 12Идеалы и фильтры частично упорядоченного множества.
Конусы. Точные грани.ОпределениеПорядком, или частичным порядком, на множестве P называется бинарное отношение ≤ на P (определяемое некоторыммножеством R≤ ⊂ M × M ), удовлетворяющее следующим условиямРефлексивность: ∀a (a ≤ a)Транзитивность: ∀a, b, c (a ≤ b)&(b ≤ c) ⇒Антисимметричность: ∀a, b (a ≤ b)&(b ≤ a)a≤c⇒a=bЧастично упорядоченным множеством называется пара ⟨P , ≤⟩, где P — множество, а ≤ — отношение частичного порядка на P .Идеал частично упорядоченного множестваПодмножество J элементов частично упорядоченного множества ⟨P , ≤⟩ называется его идеалом(порядковым), если:(x ∈ J)&(y ≤ x) → y ∈ JФильтр частично упорядоченного множестваПодмножество F элементов P называется его фильтром(порядковым), если: (x∈ F)&(x ≤ y) → y ∈ FКонусПусть ⟨P , ≤⟩ частично упорядоченное множество и A⊆ P .
Множества A△ и A▽ определяемые условиями:A△ = {x ∈ P |∀a ∈ A(a ≤ x)}A▽ = {x ∈ P |∀a ∈ A(x ≤ a)}называются верхними и нижними конусами множества A, а их элементы верхними и нижними гранями соответственно.Точные граниПусть ⟨P , φ⟩ частично упорядоченное множество и A⊆P△Наименьший элемент в A называется точной верхней гранью множества A.▽Наибольший элемент в A называется точной нижней гранью множества A.Теорема Шпильрайна. Линейное продолжение частично упорядоченного множестваОпределениеЛинейно упорядоченное множество или цепь ― частично упорядоченное множество, в котором для любых двух элементов a иb имеет место a ⩽ b или b ⩽ a.Линеаризация.Теорема ШпильрайнаЛюбой частичный порядок ≤ может быть продлен до линейного на этом же множестве.Каждый порядок есть пересечение всех своих линейных продолжений (линеаризацией)Спектр и размерность частично упорядоченного множестваОпределениеРассмотрим вероятностное пространство на множестве всех линеаризаций частично-упорядоченного множества ⟨P , ≤⟩, в которомкаждая линеаризация равновероятна.
В этом пространстве рассматривают события E вида x ≤ y, (x ≤ y)&(x ≤ z)и т.д.Вероятность такого события P r[E]=числолинеаризаций,вкоторыхимеетместоEe(P)Спектр частично упорядоченного множестваSpec(P ) = {P r[a ≤ b]|a, b ∈ P , a ≠ b}Свойства:1спектр симметричен относительно 2 , поскольку P r[a{0,1, 1} - единственный трехэлементный спектр2≤ b] = 1 − P r[b ≤ a]РазмерностьНаименьшее число линейных порядков, дающих в пересечении данное частично упорядоченное множество P, называется егоразмерностью dim(P )Фундаментальная теорема о конечных дистрибутивных решётках.ОпределенияЧастично упорядоченное множество, для которого для любых двух элементов a, b существуют Inf{a, b}, Sup{a, b} называютрешеточно упорядоченным.
Решетка называется полной, если любое подмножество ее элементов имеет точные верхнюю и нижнююграни.Решётка может быть также определена как алгебра с двумя бинарными операциями (они обозначаются ∨ и ∧ или + и ·),удовлетворяющая следующим тождествамa∨a=aa∧a=a2. a ∨ b = b ∨ aa∧b=b∧a3. (a ∨ b) ∨ c = a ∨ (b ∨ c)(a ∧ b) ∧ c = a ∧ (b ∧ c)4. a ∧ (a ∨ b) = aa ∨ (a ∧ b) = a1.Связь между этими двумя определениями устанавливается при помощи формул:a ∨ b = sup(a, b),a ∧ b = inf(a, b),и обратно. При этом для любых элементов a и b эквивалентны следующие утверждения:a ⩽ b;a ∧ b = a;a ∨ b = b.Irr(L) - множество неразложимых в объединение элементов.Irr(x) = {y ∈ Irr(L)|y ≤ x}- множество неразложимых элементов в L, содержащихся в x.Фундаментальная теорема о конечных дистрибутивных решёткахВсякая конечная дистрибутивная решетка L изоморфна решетке порядковых идеалов частично упорядоченного множества еенеразложимых элементов L = J(Irr(L))Соответствия Галуа.ОпределениеяАнтимонотонность - a, b∈ P1 a ≤ b → ϕ(a) ≥ ϕ(b)Пусть P,Q - частично упорядоченные множества.
Пара отображений (ϕ, ψ), ϕ: P → Q, ψ : Q → P, удовлетворяющих свойствам:ϕ, ψ антимонотонны.pϕψ ≥ p, qψϕ ≥ q, где ϕψ, ψϕ операторы замыкания на P и Q соответственно.называются соответствием Галуа между P и Q. Свойство: ϕ= ϕψϕ, ψ = ψϕψИсточник — «http://bagnikita.dyndns.org/pa/index.php?title=Определения_All&oldid=178»Категория: ОпределенияПоследнее изменение этой страницы: 22:18, 17 января 2014.К этой странице обращались 3 раз.Содержимое доступно по лицензии Общественное достояние (если не указано иное)..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
