Свободные группы и Деревья от 29.07.06		Доклады
Мысль, которую Н.И. Лобачевский проводил повсюду, заключается в том, что понятия, которыми оперирует математика, приобретается чувствами, а затем уточняется в порядке отвлечения 1.4.1. Свободные группы Рассмотрим вместе с любым множеством И символов (или букв) множество И-1 символов вида а-1, где а из И. При этом считается, что в самом И не было символов а-1. Тогда множество И U И-1 называется групповым алфавитом, а его элементы - буквами. Под словом в алфавите И U И-1 (или под групповым словом в алфавите И) понимается всякая конечная последовательность х1...хn, где хi из И U И-1. Число n называется длиной данного слова Х = х1...хn и обозначается в дальнейшем |Х|. Удобно также рассматривать и слово нулевой длины - пустое слово. Например, если И = {a, b}, то aba-1 и baa-1 - различные слова длины 3. Последнее из них является сократимым. Вообще, слово Х = х1...хn сократимо, если для некоторого номера i буквы хi и хi + 1 в этой записи формально являются взаимно обратными. Если вычеркнуть взаимно обратные буквы хi и хi + 1, то получится слово длины n - 2. Говорят, что оно получилось из Х в результате сокращения. Если после нескольких сокращений их Х получилось несократимое слово Х', то Х' называют результатом полного сокращения в слове Х. Определим операцию умножения двух несократимых слов X и Y в алфавите И U И-1. Если на стыке слов X и Y невозможно сокращение, то слово XY (результат приписывания к слову X слова Y) обьявляется произведением слов X и Y в данном порядке. В противом случае произведением называется результат полного сокращения слова XY, например, aba-1*ab-1а = аа (вместо аа пишут также а2; аналогичен смысл записи аn). Теорема 4.1. Множество F(И) всех несократимых слов в алфавите И U И-1 является группой относительно определенной выше операции умножения (*). Единицей в F(И) является, очевидно, пустое слово. Поэтому его обозначают 1. Это обозначение, впрочем, употребляется наряду с - е - для единицы произвольной группы. Обратным для Х = х1...хn является слово хn-1...х1-1. Группа F(И) называется свободной группой. Отождествляя И с однобуквенными словами, считаем, что И - система порождающих для F(И). Ее называют также базисом свободной группы. Роль свободных групп проясняет Теорема 4.2. Для всякой группы G с произвольным множеством порождающих {gi} i из I существует сюрьективный гомоморфизм ф свободной группы F(И) с базисом И = {аi} i из I на G, при котором ф(аi) = для gi для i из I. 1.4.2. Определяющие соотношения Поскольку во всякой группе можно выбрать некоторую систему порождающих {gi} i из I по теореме 4.2 существует сюрьективный гомоморфизм ф: F(И) --> G, (где И = {аi} i из I), при котором ф(аi) =  gi. Такой гомоморфизм называют копредставлением группы G (в отличие от представлений, когда, наоборот, рассматривается гомоморфизм не в G, а из G в некоторую группу линейных операторов или перестановое и т.п.). Разумеется, копредставления зависят от выбора системы порождающих в G. Для всякого слова W из F(И) его значение W(gi1,...,gin) в G - это образ слова W =  W(аi1,...,аin) при гомоморфизме ф. (Более общо, g из G называется значением слова W, если g - образ слова W при некотором гомоморфизме F(И) --> G). По известной теореме о гомоморфизме G ~= F(И)/Ker(ф), и поэтому мы приходим к универсальной возможности задать всякую группу в виде фактор-группы свободной группы по некоторой ее нормальной подгруппе N. В связи с этим привлекает естественное внимание вопрос о способах задания нормальной подгруппы N в свободной группе F = F(И). Перечисление всех элементов из N крайне редко бывает удовлетворительным. Задание N своими порождающими как подгруппы также весьма громоздко и является бесконечным для неединичной нормальной подгруппы N бесконечного индекса. Следует учесть, однако, что подгруппа N нормальна, а значит, сопряженные с элементами из N должны лежать в N, чем мы сейчас и воспользуемся. Пусть G - группа и S - ее подмножество. Нормальным замыканием SG подмножества S в группе G называется наименьшая нормальная подгруппа группы G, содержащая подмножество S. Очевидно, что в SG входят все сопряженные gs+-1g-1, где s из S, g из G, и их произведения. С другой стороны, понятно, что всевозможные произведения конечного числа сомножителей вида Пni=1(gs+-1g-1), s из S, g из G, составляют нормальную группу в G, содержащую подмножество S. Стало быть, эта запись дает общий вид произвольного элемента из нормального замыкания SG. Определим теперь элементарные преобразования слов из F = F(И), которые не меняют смежного класса слова по подгруппе RF, где R - подмножество в F. 1а. Сокращение двух соседних взаимно обратных букв. 1б. Обратное преобразование, т.е. удлинение слова путем вставки в какое-то место двух соседних взаимно обратных букв. 2а. Замена слова х = х1r+-1х2, где r из R, словом х1х2. 2б. Обратное преобразование: замена слова х1r+-1х2 словом  х1r+-1х2, где r из R. Назовем здесь два слова Х и Y R-эквивалентными, если Y может быть получено из Х с помощью нескольких элементарных преобразований перечисленных типов. Понятно, что тем самым действительно введено на F отношение эквивалентности со всеми его атрибутами: рефлексивностью, симметричностью и транзитивностью. Скажем еще (временный термин), что соотношение W = V R-выводимо, или выводится из соотношений {r = 1 | r из R}, если W и V R-эквивалентны. Наконец, соотношение W = 1, где W из F, назовем следствием соотношений системы {r = 1 | r из R}, если для всякой группы G с выбранным в ней подмножеством {gi} i из I (а значит, с заданным гомоморфизмом ф: F --> G, при котором ф(аi) = gi) значение слова W равно 1 в G, если в G обращаются в 1 значения всех r из R. Теорема. 4.4. Следующие утверждения равносильны: 1) Соотношение W = 1 является следствием системы соотношений {r = 1 | r из R}, где R из F = F(И) 2) W принадлежит нормальному замыканию N = RF 3) соотношение W = 1 R-выводимо. Вследствии теоремы 4.4. при выполнении любого из трех ее условий можно в дальнейшем использовать лишь один термин: W = 1 - следствие системы соотношений {r = 1 | r из R}. Множество соотношений {r = 1 | r из R} называется определяющим для группы G = {gi | i из I}, если всякое другое соотношение между порождающими gi группы G следует из системы {r = 1 | r из R}. Соотношения r = 1 называют при этом определяющими соотношениями, а их левые части - определяющими словами для G. В этом случае G ~= F/RF, а значит определяющие соотношения действительно определяют всякую группу с точностью до изоморфизма. Пишут G = {И | r = 1 | r из R} и эту запись, как и гомоморфизм ф: F(И) --> G, называют копредставлением группы G (В книге - М.И. Каргаполов, Ю.И. Мерзляков. Основы теории групп. (М., Наука. 1982) - пару (И, R) предлагается называть генетическим кодом группы G). Введение Простое, но важное для комбинаторной теории групп наблюдение, сделанное ван Кампеном в 1933 г.,  осталось незамеченным более трех десятилетий. Суть леммы ван Кампена состоит в наглядной геометрической интерпретации вывода следствий из определяющих соотношений группы. Представление о таком способе изображения следствий можно получить из рис. 1а, 1б, где показан вывод следствия a2b3 = b3a2 из соотношения ab = ba и вывод следствия b6 = 1 из соотношений b2 = а и a3 = 1: при обходе границы любой области карты читается одно из заданных определяющих слов (aba-1b-1 в первом случае и b2a-1 и a3 во втором случае), а при обходе границы всей карты читается следствие (a2b3a-2b-3 в первом случае и b6 во втором), если при движении по ребру против стрелки читать обратную букву. Кроме алгебро-геометрической окраски лемма Ван Кампена имеет и логическую, ибо в диаграммах содержится не только информация о данных соотношениях и их следствиях, но и адекватно отражен процесс вывода следствий. 4. Диаграммы над группами Как уже говорилось во введении, в 1933 г. Ван Кампен сделал простое, но чрезвычайно интересное наблюдение об универсальной возможности геометрической интерпретации вывода следствий соотношений в группах. Была обнаружена новая связь между комбинаторно-топологическими и комбинаторно-групповыми понятиями. Она была действительно новой - ее не следует, например, смешивать с известным представлением произвольной группы как фундаментальной группы 2-мерного топологического пространства. Чтобы подчеркнуть это отличие, мы обратим внимание на то, что,  во-первых, в лемме ван Кампена рассматриваются лишь плоские комплексы (затем была обнаружена польза и других поверхностей), а не произвольные 2-комплексы. Во-вторых, лемма ван Кампена не только обьединяет абстрактно-алгебраические и топологические понятия, но и привносит, несомненно, в эту связь дух математической логики, ибо диаграмма ван Кампена адекватно отражает процесс вывода следствий из заданных групповых отношений. 4.11. 1. Наглядная интерпретация вывода следствий определяющих соотношений. Несколько примеров Прежде чем перейти к точным формулировкам, приведем некоторые примеры диаграмм, иллюстрирующих вывод следствий из определяющих соотношений, в добавлении к тем, что появились во введении. Если в некоторой группе выполнены соотношения a3 = 1 и bab-1 = с, то отсюда, очевидно, следует, что с3 = 1. Этот вывод отражен на рис. 24. Здесь обход треугольной клетки (против часовой стрелки) дает слово a3, обход любой из четырехугольных клеток - слово сbа-1b-1, а на контуре всего рисунка читаем с3, т.е. левую часть следствия соотношений a3 = 1 и сbа-1b-1 = 1. Несколько сложнее следующий пример, наглядно иллюстрирующий теорему о том, что в любой группе G с тождеством х3 = 1 каждый элемент а лежит в некоторой нормальной подгруппе N группы G. Для этого необходимо и достаточно показать, что а коммутирует с любым своим сопряженным элементом. (В качестве N тогда можно взять подгруппу, порожденными всеми элементами из G, сопряженными с а). Но в самом деле условие а(bаb-1) = (bаb-1)а равносильно равенству аbаb-1а-1bа-1b-1 = 1, которое на рис. 25 выводится из справедливых в группе G (с тождеством х3 = 1) соотношений b3 = 1, (аb)3 = 1 и (а-1b)3 = 1. (Левые части этих соотношений написаны на треугольных и шестиугольных клетках, а левая часть следствия читается при обходе контура рисунка по часовой стрелке начиная с отмеченной точки о.) Раскроем теперь тайну построения подобных примеров. Для этого подробнее проведем вывод следствия а3b-1а2b3 = 1 из соотношений а3 = 1 и b2 = а (т.е. а-1b2 = 1). Вспомним, что согласно теореме 4.4. в свободной группе F = F(a,b) должно выполняться равенство вида а3b-1а2b3 = Пni=1(ХiR+-1iХ-1i), где Хi из F, Ri - определяющие слова (т.е. а3 или а-1b2 в данном примере). В частности, в нашем случае в F справедливо равенство а3b-1а2b3 = (а3)(b-1а3b)(b-1а-1b2b). Изобразим сомножители в виде трех последовательных лепестков (рис. 26а). Каждый из них нарисован в виде круга с ножкой (возможно, пустой). Окружности размечаются так, чтобы прочитать R+-1i, т.е. здесь а+-3 или (а-1b2)+-1, а на ножке написано слово Хi (b-1 или пустое слово в нашем случае). Тогда, обходя последовательно лепестки, прочтем правую часть вышеуказанного равенства. Чтобы получить слово, графически совпадающее с левой частью этого равенства, нужно дополнительно провести сокращения. Эти сокращения в слове, написанном на контуре рисунка, можно осуществить путем последовательных склеиваний соседних ребер контура с одинаковыми метками (и согласованно направленными стрелками). В нашем примере сначала склеиваются ножки, а потом - по одному ребру клеток П2 и П3. В результате получается диаграмма, на контуре которой написано в точности слово а3b-1а2b3 (рис. 26б.), что и требовалось. Таким же способом можно построить диаграмму вывода любого следствия определяющих соотношений (причем даже для одного следствия W = 1 разные диаграммы выводов могут не быть клеточно эквивалентными). Лемма 11.1. Пусть W - произвольное непустое слово в алфавите И1 = И U И-1 U {1}. Тогда W = 1 в группе G, заданной копредставлением G = {И | r = 1 | r из R}, в том и только в том случае, когда существует дисковая диаграмма над этим копредставлением, метка контура которой графически равна W. Лемма 11.2. Пусть V и W - два непустых слова в алфавите И1. Тогда эти слова сопряжены в группе G, заданной копредставлением G = {И | r = 1 | r из R}, в том и только в том случае, когда существует кольцевая диаграмма над этим копредставлением, с контурами p и q такими, что ф(p) = V, ф(q) = W-1. А.Ю. Ольшанский. Геометрия определяющих соотношений в группах (М., Наука, 1989) Если у группы образующих больше, чем соотношений, то такая группа бесконечна. Сейчас мы установим значительно более точное утверждение. Рассмотрим группу {х1,...,хn | r1,...,rm} с n образующими и m соотношениями. Назовем d = n - m дефицитом этого задания. Следующий замечательный результат доказан Николаем Семеновичем Романовским (Алгебра и Логика, 1977, т.16, N.1, с. 88-97) Теорема о свободе Если d >= 0, то среди порождающих х1,...,хn найдутся d элементов, свободно порождающих свободную группу Fd ранга d. Н. Вавилов. Конкретная теория групп http://www.math.spbu.ru/user/valgebra/grou-book.pdf А.Б. Сосинский. Узлы и косы. (М., МЦНМО, 2001) http://www.mccme.ru/mmmf-lectures/books/books/books.php#book-10 http://sinsam.kirsoft.com.ru/KSNews_327.htm Ю.И. Манин. Вычислимое и невычислимое. (М., Советское радио. 1980) Пусть Г - группа с фиксированной конечной системой порождающих...Назовем теперь Г словесно-гиперболической, если любой асимптотический подконус Т группы Г является деревом, т.е. для каждой пары различных точек из Т существует ровно один топологический отрезок в этих точках (Этот отрезок гомеоморфен [0,1], причем точки соответствуют концам [0,1]). Это определение наиболее интуитивно ясное и, возможно, наиболее подходит для обобщений. Оно, по существу, утверждает, что Г со словесной метрикой из бесконечности выглядит как дерево М. Громов. Гиперболические группы (Москва-Ижевск. ИКИ. 2002. под редакцией О.В. Богопольского) 3.12. Упражнение. В свободной группе ранга n больше или равно 2 существуют свободные подгруппы всех конечных рангов. Указание. В группе F(a,b) подмножество {a, b-1ab,...,b-rabr} порождает свободную подгруппу ранга r + 1. 8.4. Следствие. Любая подгруппа свободной группы свободна 8.1. Предложение. Пусть Г(G, S) - граф, определенный группой G и подмножеством S из G. Тогда Г(G, S) - дерево (связный граф без петель) - тогда и только тогда, когда G - свободная группа с базисом S Свободные группы и только они действуют свободно и без инверсий ребер на деревьях О.В. Богопольский. Введение в теорию групп. (Москва-Ижевск. ИКИ. 2002) http://sinsam.kirsoft.com.ru/KSNews_283.htm В клетке хлорофилловые зерна располагаются неравномерно, а больше по краям или иногда пересекая клетку. И странно - хлорофилловые зерна как будто медленно движутся. Да, как зеленые вагончики, друг за другом будто сцепленные, они бегут в одну сторону по краям клетки и пересекая ее. Мы неверно назвали хлорофилловые зерна вагончиками, так как не они бегут, а бегут - струятся прозрачные рельсы. Это движется, струится замечательное живое вещество - протоплазма. Недаром она так называется. По-гречески протос - первый, плазма - образующееся вещество - первичное вещество. Протоплазма вечно движется в живых клетках, то медленнее, то быстрее Учебное пособие, переплывшее океан http://sivatherium.h12.ru/library/Verzilin/03_20.htm В предшествовавших лекциях мы ознакомились с тремя отправлениями растительного организма: питанием, ростом и воспроизведением, которое с известной точки зрения можно рассматривать как частный случай роста. При поверхностном взгляде на природу, имея в виду только те формы и те явления, которые встречаются на каждом шагу, мы легко можем притти к заключению, что этими тремя отправлениями исчерпывается вся жизненная деятельность растения. Эта мысль выразилась в том определении растительной жизни, которое сложилось, вероятно, с незапамятных времен: растение живет (т.е. растет, питается), но лишено движения; иногда еще поясняют: произвольного движения. В этом отсутствии движения, самодеятельности мы видим существенную черту, отличающую растение от животного: недаром и обратно о человеке, жизнь которого ограничивается чисто растительными процессами, мы говорим, что он прозябает. Но справедливо ли такое общее суждение о растении? Более широкий взгляд на растительное царство, более близкое знакомство с растением вскоре убеждают нас в поспешности такого обобщения: мы с удивлением открываем, что явления движения не только не отсутствуют, но даже очень распространены в растительном мире. Прежде всего обратимся за показаниями к микроскопу. Будем наблюдать при его помощи целую, неповрежденную клеточку в эпоху ее полного развития и при возможно естественных условиях. Для этого выберем волоски, покрывающие в виде пушка поверхность стеблей и листьев или молодых корней и состоящие из одной клетки или одного ряда клеток, или же осторожно вырежем острой бритвой ломтик из листа или стебля водяного растения, например, валлиснерии (растение, которого узкие тесьмовидные листья можно видеть в любом комнатном аквариуме, а цветы в период оплодотворения представляют любопытные явления, описанные в предшествующей лекции), такой тонкий, чтобы он был прозрачен, но чтобы при всем том рассматриваемые клеточки не были поранены. Водяные растения удобны именно потому, что все наблюдения под микроскопом производятся в воде. Следовательно, клеточка остается в естественной среде. Если все условия соблюдены, температура не слишком низка и клеточки не повреждены, через несколько минут на наших глазах обнаружится одно из самых любопытных явлений, какое может представить органический мир. Сок клеточки или, вернее, та составная часть ее содержимого, которую мы назвали протоплазмой (см. лекцию II) и которая в виде слоя густой жидкости выстилает внутреннюю поверхность стенок или же в виде струек перебрасывается через полость клетки, наполненную более жидким соком, - эта протоплазма сначала медленно, затем быстрее и быстрее начинает двигаться в каждой клеточке (не следует упускать из виду, что движение это увеличено микроскопом; в действительности оно очень медленно, обыкновенно не скорее движения минутной стрелки обыкновенных карманных часов). Движение это особенно ясно заметно в тех случаях (как у валиснерии), где в протоплазме плавают яркозеленые зернышки хлорофилла: можно видеть, как эти зернышки, увлекаемые быстрым током протоплазмы, несутся вдоль одной продольной стенки клеточки, заворачивают по другой поперечной стенке, чтобы вернуться к точке своего отправления, и затем вновь и вновь повторяют свое круговое странствие. Это быстрое вращательное движение протоплазмы можно наблюдать в одной и той же клеточке по целым часам и даже дням. В таких клеточках, в которых протоплазма образует общую сеть струек, движение не ограничивается круговым током вдоль стенок, а замечается и в тонких струйках, пересекающих полость клетки; движение можно заметить в любом волоске, в знакомых нам волосках традесканции, в жгучих волосках крапивы, а также в клеточках мякоти плодов, как, например, в тех крупных, свободных, видимых простым глазом клеточках, из которых состоят самые зрелые, рассыпчатые части арбуза. Стоит взять иглой несколько таких клеточек, и, положив их под микроскоп, в каждой из них увидим это любопытное явление струйчатого движения протоплазмы. Таким образом, протоплазма описанных клеточек находится в постоянном движении, и движении притом самостоятельном, так как оно не вызывается никакими внешними физическими деятелями, хотя эти деятели, как, например, теплота, электричество, могут изменять, т.е. ускорять или замедлять, или даже вовсе прекращать его. Нам известно так много примеров этого движения и в таких разнообразных случаях, что становится в высшей степени вероятным, что движение свойственно протоплазме всех клеточек, по крайней мере в известный период их существования К.А. Тимирязев. Жизнь растения. Лекция IX. Растение и животное http://sinsam.kirsoft.com.ru/KSNews_546.htm Подводя итоги рассмотренным закономерностям, мы приходим к следующим положениям. 1. Виды и роды, генетически близкие, характеризуются сходными рядами наследственной изменчивости с такой правильностью, что, зная ряд форм в пределах одного вида, можно предвидеть нахождение параллельных форм у других видов и родов. Чем ближе генетически расположены в общей системе роды и линнеоны, тем полнее сходство в рядах их изменчивости. 2. Целые семейства растений в общем характеризуются определенным циклом изменчивости, проходящей через все роды и виды, составляющие семейство. Николай Вавилов. Закон гомологических рядов в наследственной изменчивости http://sinsam.kirsoft.com.ru/KSNews_347.htm Мы представляем себе общество в виде организма, в котором отношения между отдельными его членами определяются не законами, наследием исторического гнета и прошлого варварства, не какими бы то ни было властителями, избранными или же получившими власть по наследию, а взаимными соглашениями, свободно состоявшимися, равно как и привычками и обычаями, также свободно признанными. Эти обычаи, однако, не должны застывать в своих формах и превращаться в нечто незыблемое под влиянием законов или суеверий. Они должны постоянно развиваться, применяясь к новым требованиям жизни, к прогрессу науки и изобретений и к развитию общественного идеала, все более разумного, все более возвышенного. Таким образом - никаких властей, которые навязывают другим свою волю, никакого владычества человека над человеком, никакой неподвижности в жизни, а вместо того - постоянное движение вперед, то более скорое, то замедленное, как бывает в жизни самой природы. Каждому отдельному лицу предоставляется, таким образом, свобода действий, чтобы оно могло развить все свои естественные способности, свою индивидуальность, т.е. все то, что в нем может быть своего, личного, особенного. Другими словами - никакого навязывания отдельному лицу каких бы то ни было действий под угрозой общественного наказания или же сверхъестественного мистического возмездия: общество ничего не требует от отдельного лица, чего это лицо само не согласно добровольно в данное время исполнить. Наряду с этим - полнейшее равенство в правах для всех. Мы представляем себе общество равных, не допускающих в своей среде никакого принуждения; и, несмотря на такое отсутствие принуждения, мы нисколько не боимся, чтобы в обществе равных вредные обществу поступки отдельных его членов могли бы принять угрожающие размеры. Общество людей свободных и равных сумеет лучше защитить себя от таких поступков, чем наши современные государства, которые поручают защиту общественной нравственности полиции, сыщикам, тюрьмам - т.е. университетам преступности, - тюремщикам, палачам и судам. В особенности сумеет оно предупреждать самую возможность противообщественных поступков путем воспитания и более тесного общения между людьми. Ясно, что до сих пор нигде еще не существовало общества, которое применяло бы на деле эти основные положения. Но во все времена в человечестве было стремление к их осуществлению. Каждый раз, когда некоторой части человечества удавалось хоть на время свергнуть угнетавшую его власть или же уничтожить укоренившиеся неравенства (рабство, крепостное право, самодержавие, владычество известных каст или классов), всякий раз, когда новый луч свободы и равенства проникал в общество, всегда народ, всегда угнетенные старались хотя бы отчасти провести в жизнь только что указанные основные положения. Поэтому мы вправе сказать, что анархия представляет собой известный общественный идеал, существенно отличающийся от всего того, что до сих пор восхвалялось большинством философов, ученых и политиков, которые все хотели управлять людьми и давать им законы. Идеалом господствующих классов анархия никогда не была. Но зато она часто являлась более или менее сознанным идеалом масс. П. Кропоткин. Наука и анархия http://sinsam.kirsoft.com.ru/KSNews_105.htm А Ченслобг утце дне нашя а рещеть Бъговi ченсла сва - а быте дне сврзенiу, нiже боте ноще, а оуснуте. Тоi бо се есе явскi, я Сыi есте во дне бжьстiем. А в носще нiкii есь, iножде Бг, Дiд Дуб Сноп нашь