Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ПОДСТАНОВКА
Перевод
ПОДСТАНОВКА
множества - взаимно однозначное отображение множества на себя. Термин "П." главным образом применяется для конечного множества X. В этом случае удобно считать, чтоХ={1, . . ., п}, изаписывать П. в виде
(*)
где i1, i2, . . ., in - нек-рая перестановка чисел 1, 2, . . ., n (впрочем, иногда термин "перестановка" употребляется как синоним термина "П.", см., напр., [2] с. 146). Запись (*) означает, что gпереводит число kв ik, то есть y(k)=ik (пишут также kg=ik).для i=1, 2, . . ., n. Число всех различных П. множества Xпри |Х| = n равно числу всех перестановок этого множества, т. е. n!. Произведение подстановок a и b множества определяется как последовательное выполнение отображений a и b и задается формулой ab(x)=a(b(x)) для всех . Совокупность всех П. множества Xобразует группу относительно введенного умножения, к-рая наз. симметрической группой. Любая подгруппа симметрич. группы наз. подстановок группой.
Симметрич. группа П. множества Xобозначается S(X), она содержит в качестве подгруппы SF(X) - группу, состоящую из таких подстановок g, к-рые перемещают лишь конечное подмножество элементов (то есть лишь для конечного множества элементов ). Если Xконечно и состоит из пэлементов, то симметрич. группа обозначаетсяSn.
Транспозицией наз. такая П. множества X, к-рая меняет местами только два элемента iи j; она обозначается (i, j). В S п имеется ровно ( п-1)/2 транспозиций. Любая подстановка g. из SF(X).представима в виде произведения транспозиций. В частности, каждая П. из Sn есть произведение транспозиций. П. может разлагаться в произведение транспозиций многими способами. Однако для данной g. характер четности числа множителей в разложении на транспозиции не зависит от способа разложения. П., представимая в виде произведения четного числа транспозиций, наз. четной, а разлагающаяся в произведение нечетного числа транспозиций - нечетной. В Sn имеется n!/2 четных П. и столько же нечетных. Если П. записана в виде (*), то ее четность совпадает с четностью числа инверсий перестановки i1, . . ., in к-рое равно числу таких пар {ik, ij}, что k<j, ik>ij. Транспозиция, очевидно, есть нечетная II. Применение одной транспозиции к любой перестановке меняет четность числа ее инверсий на противоположную. Произведение двух четных, а также двух нечетных П. ость четная П., а четной и нечетной П. (в любом порядке) - нечетная. Все четные П. составляют нормальную подгруппу (X).в группе SF(X), к-рая наз. знакопеременной. При |Х|= п подгруппа (X).обозначается А п.
Циклом длины lназ. такая подстановка а конечного множества Y={y1, . . ., у l], что
Конечный цикл обозначается (y1, y2, . . ., yl). Бесконечным циклом наз. такая П. счетного множества
что для любого целого i s(yi)=yi+1 Обозначение бесконечного цикла таково:
Цикл длины 2 есть транспозиция. Группа Sn содержит ( п-1)! циклов длины п. Для любой подстановки g из S(X).существует такое разбиение множества X на непересекающиеся подмножества, что на каждом из них g действует как цикл. Конечные подмножества этого разбиения имеют вид
где gl(x}=x, а бесконечные -
где при . Циклы, индуцируемые подстановкой Y на подмножествах разбиения, наз. независимыми циклами подстановки g. Например, (1, 3, 4) и (2, 5)- независимые циклы П.
g записывается в виде
и является произведением своих независимых циклов. Вообще, если g нетождественная П., имеющая лишь конечное число циклов неединичной длины, то g - произведение таких циклов. В частности, каждая нетождественная П. из SF(X).является произведением своих независимых циклов неединичной длины. Порядок подстановки g из SF(X), т. е.порядок циклич. группы <g>, равен наименьшему общему кратному длин ее независимых циклов.
Из независимых циклов данной П. можно получить независимые циклы П., сопряженной с ней. Напр., если
произведение независимых циклов подстановки g из Sn, а и d( а i)=bi, i=l, . . ., п, то
- разложение подстановки в произведение независимых циклов. Две П. группы Sn тогда и только тогда сопряжены в Sn, когда они имеют одно и то же число независимых циклов каждой длины.
Пусть , k - число независимых циклов подстановки s, включая и циклы длины 1. Тогда разность п-kназ. декрементом подстановки s. Наименьшее число множителей при разложении подстановки s в произведение транспозиций совпадает с ее декрементом. Четность П. совпадает с четностью ее декремента.
П. возникли впервые в комбинаторике 18 в. В кон. 18 в. Ж. Лагранж (J. Lagrange) применил их при исследовании разрешимости алгебраич. уравнении в радикалах. О. Коши (A. Cauchy) посвятил многочисленные исследования этому понятию. Ему, в частности, принадлежит идея разложения П. в произведение циклов. Исследования групповых свойств П. восходит к Н. Абелю (N. Abel) и особенно к Э. Галуа (Е. Galois). См. Галуа теория, Подстановок группа.
Лит.:[1] Jordan С., Traite des substitutions et des equations altfebriques, P., 1057; [2] Кострикин А. И., Введение в алгебру, М., 1977; [3] Курош А. Г., Курс высшей алгебры, 11 изд., М., 1975; [4] Холл М., Теория групп, пер. с англ., М., 1962. Д. А. Супруненко.
Перевод
Прямое произведение групп
Прямое или декартово произведение множеств — множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств. Данное понятие употребляется не только в теории множеств, но также в алгебре, топологии и прочих разделах математики благодаря тому, что прямое произведение часто наследует структуры (алгебраические, топологические и т. д.), существующие на перемножаемых множествах.
Содержание
|
|
|
|
|
|
|
|
|
|
|
в |
в |
в |
в |
в |
в |
в |
в |
|
и |
и |
и |
и |
и |
и |
и |
и |
|
к |
к |
к |
к |
к |
к |
к |
к |
|
Произведение множества {в, и, к} |
Пусть дано два множества X и Y. Прямое произведение множества X и множества Y есть такое множество , элементами которого являются упорядоченные пары (x,y) для всевозможных и .
Отображения произведения множеств в его множители ( и ) называют координатными функциями.
Аналогично строятся произведения нескольких множеств.
|
000 |
001 |
002 |
010 |
011 |
012 |
020 |
021 |
022 |
|
100 |
101 |
102 |
110 |
111 |
112 |
120 |
121 |
122 |
|
200 |
201 |
202 |
210 |
211 |
212 |
220 |
221 |
222 |
|
{0, 1, 2}3, 33 = 27 элементов |
n-я Декартова степень множества X определяется для целых неотрицательных n, как n-кратное Декартово произведение X на себя:
При положительных n Декартова степень Xn состоит из всех упорядоченных наборов (кортежей) элементов из X длины n.
При n = 0, Декартова степень X0 по определению содержит единственный элемент — пустой кортеж.
Дальнейшее обобщение понятия прямого произведения приводит к произведениям по индексному множеству I (возможно, бесконечному): X = ΠXi, элементы которого сопоставляют каждому индексу i из I элемент множества Xi.
Пусть f — отображение из A в B, а g — отображение из X в Y. Их прямым произведением называется отображение из в : .
Аналогично вышеизложенному, данное определение обобщается на многократные и бесконечные произведения.
Прямое (декартово) произведение двух групп (G, * ) и — это группа из всех пар элементов (g,h) с операцией поэлементного умножения: . Эта группа обозначается как . Сомножители G и H изоморфны двум нормальным подгруппам своего произведения, и соответственно. Пересечение этих подгрупп состоит из одного элемента (1G,1H), который является единицей группы-произведения. Координатные функции произведения групп являются гомоморфизмами.
Это определение распространяется на произвольное конечное число перемножаемых групп; ассоциативность декартова произведения следует из ассоциативности операций перемножаемых групп.
Однако, для бесконечного числа перемножаемых групп понятия декартового и прямого произведения принято различать. В общем случае, , где и . (Операция в правой части — это операция группы Gi.) Единицей группы-произведения будет последовательность, составленная из единиц всех перемножаемых групп: . Например, для счётного числа групп: , где в правой части стоит множество всех бесконечных двоичных последовательностей.
Подгруппа на множестве всех f, носитель которых (то есть множество ) конечен, называется прямым произведением. Например, прямое произведение того же самого набора множеств содержит все двоичные последовательности с конечным числом единиц, а их можно трактовать какдвоичные представления натуральных чисел.
Аналогично произведению групп, можно определить произведения колец, алгебр, модулей и линейных пространств, причём в определении прямого произведения 1i (см. выше) следует заменить нулём. Однако, как правило, произведения этих структур называют прямой суммой.
Пусть X и Y — два топологических пространства. Топология произведения задаётся базой, состоящей из всевозможных произведений , где U — открытое подмножество X и V — открытое подмножество Y.
Определение легко обобщается на случай произведения нескольких пространств. Для бесконечного произведения X = ΠXi определение усложняется. Определим открытый цилиндр , где и U — открытое подмножество Xi.
Топология бесконечного произведения будет задаваться базой, составленной из всевозможных пересечений конечного числа открытых цилиндров (такая топология аналогичнакомпактно-открытой топологии пространств отображений если считать индексное множество I имеющим дискретную топологию).
Теорема Тихонова утверждает компактность произведений любого количества компактных пространств; однако для бесконечных произведений её не удаётся доказать без использования аксиомы выбора (или равносильных ей утверждений теории множеств).
Также, теорема Александрова показывает, что любое топологическое пространство можно вложить в (бесконечное) произведение связных двоеточий, если только выполненааксиома Колмогорова (а иные пространства и не рассматриваются).
|
|
— |
|
|
|
— |
|
|
|
|
|
|
|
— |
|
Множество вершин прямого произведения двух графов G и H задаётся как произведение вершин графов сомножителей. Рёбрами будут соединены следующие па́ры вершин:
Иначе говоря, множество рёбер произведения графов является объединением двух произведений: рёбер первого на вершины второго, и вершин первого на рёбра второго.
Дальнейшее развитие идея прямого произведения получила в теории категорий, где она послужила основой для понятия произведения объектов. Неформально, произведение двух объектов A и B — это наиболее общий объект в данной категории, для которого существуют проекции на A и B. Во многих категориях (множеств, групп, графов, …) произведением объектов является именно их прямое произведение. Важно, что в большинстве случаев важно не столько конкретное определение прямого произведения, сколько указанное выше свойство универсальности. Различные определения будут давать при этом изоморфные объекты.
ПОДГРУППА
Перевод
ПОДГРУППА
- подмножество Н группы G, само являющееся группой относительно операции, определяющей G. Подмножество Нгруппы Gявляется ее подгруппой тогда и только тогда, когда: (1) H содержит произведение любых двух элементов из H, (2) H содержит вместе со всяким своим элементом hобратный к нему элемент h-1. В случае конечных и, вообще, периодич. групп проверка условия (2) является излишней.
Подмножество группы G, состоящее из одного элемента 1, будет, очевидно, подгруппой, и эта П. наз. единичной П. группы G и обозначается обычно символом Е. Сама G также является своей П. Всякая П., отличная от всей группы, наз. истинной П. этой группы. Истинная П. нек-рой бесконечной группы может быть изоморфна самой группе. Сама группаG и подгруппа Еназ. несобственными П. группы G, все остальные - собственными.
Теоретико-множественное пересечение любых двух (и любого множества) П. группы G является П. группы G. Пересечение всех П. группы G, содержащих все элементы нек-рого непустого множества М, наз. подгруппой, порожденной множеством М, и обозначается символом {М}. Если Мсостоит из одного элемента а, то {а} наз. циклической П. элемента а. Группа, совпадающая с одной из своих циклических П., наз. циклической группой.
Теоретико-множественное объединение П., вообще говоря, не обязано являться П. Объединением подгрупп , наз. П., порожденная объединением множеств Hi.
Произведение подмножеств S1 и S2 группы G есть множество, состоящее из всевозможных (различных) произведений s1s2, где , . Произведение подгрупп Н1 Н 2 есть П. тогда и только тогда, когда H1H2=H2H1, и в этом случае произведение Н 1 Н 2 совпадает с объединением подгрупп Н 1 и H2.
Гомоморфный образ П.- подгруппа. Если группа G1 изоморфна нек-рой подгруппе H группы G, то говорят, что группа G1 может быть вложена в группу G. Если даны две группы и каждая из них изоморфна нек-рой истинной П. другой, то отсюда еще не следует изоморфизм самих этих групп. О. А. Иванова.
ГРУППА
Перевод
ГРУППА
ГРУППА
- множество, на к-ром определена операция, наз. умножением и удовлетворяющая спец. условиям (групповым аксиомам): в Г. существует единичный элемент; для каждого элемента Г. существует обратный; операция умножения ассоциативна. Понятие Г. возникло как обобщение при рассмотрении конкретных групп преобразований (взаимно однозначных отображений разл. множеств на себя). Для преобразований роль умножения играет композиция преобразований, т. е. последоват. выполнение сначала одного из них, а потом второго. Такая операция по определению ассоциативна. Роль единицы играет тождественное преобразование. Любую Г. можно реализовать как Г. преобразований, сохранив при этом внутр. алгебраич. структуру.
Пусть
— произвольная подстановка степени п. Если для некоторого I число отлично от I, то говорят, что подстановка а действительно перемещает число в противном случае говорят, что подстановка а оставляет число I на месте.
Рассмотрим циклическую подгруппу группы состоящую из степеней подстановки а. Если — порядок этой подгруппы, то она состоит из подстановок
причем все эти подстановки различны. Пусть — произвольное действительно перемещаемое подстановкой а число. Обозначим через число, в которое переводит число подстановка . Очевидно, что подстановка а переводит число в число . Если бы оказалось, что , то, применяя к этому равенству подстановку мы получили бы, что т. е. что подстановка а оставляет, вопреки предположению, число на месте. Следовательно, все числа действительно перемещаются подстановкой а. Среди этих чисел имеется не более различных, ибо очевидно, равно Если числами
исчерпываются все числа, действительно перемещаемые подстановкой а, то подстановка а называется циклом и обо-Эначается символом ().
В этом случае все числа различны,
Действительно, если, например, где то, применяя к этому равенству подстановку мы получили бы, что , т. е. что подстановка оставляет число на месте. Но для любого q подстановка переводит число в число , подстановка оставляет число на месте и подстановка переводит число в число Следовательно, подстановка оставляет на месте любое число т. е., согласно условию, любое число, действительно перемещаемое подстановкой а. С другой стороны, любое число, оставляемое подстановкой а на месте, подстановка также оставляет на месте. Следовательно, подстановка оставляет на месте все числа, т. е. что невозможно, ибо
Заметим, что для любой системы различных чисел существует цикл (очевидно, единственный), переводящий число в число число в число число в число и, наконец, число в число . Этот цикл представляется символом
где — все числа из ряда отличные от чисел
Заметим еще, что запись цикла в виде неоднозначна. Именно
т. e. запись цикла можно начйнать с любого действительно перемещаемого им числа. С точностью до преобразований такого рода запись цикла, как легко видеть, однозначна.
Количество чисел, действительно перемещаемых циклом а, называется его длиной. Из сказанного выше ясно, что длина цикла равна его порядку.
Наименьшая возможная длина цикла равна двум. Циклы длины два называются транспозициями. Транспозиция переводит число I в число число j — в число t и оставляет все остальные числа на месте.
Задача. Доказать, что подстановка, действительно перемещающая только два числа, является транспозицией.
Любой цикл длины является произведением транспозиций.
Действительно,
Два цикла называются независимыми, если они не имеют общих действительно перемещаемых чисел. Очевидно, что при перемножении независимых циклов порядок множителей не играет никакой роли (т. е. независимые циклы, как говорят, перестановочны).
Оказывается, что любая не тождественная подстановка является произведением независимых циклов.
Мы докажем это утверждение индукцией по числу s действительно перемещаемых чисел. С этой целью заметим, во-первых, что число s не может быть равно единице. Действительно, если подстановка а переводит число I в число , то число Y она не может оставлять на месте, так как в противном случае два различных числа i к j переводились бы подстановкой а в одно и то же число j. Поэтому . Если , то подстановка является транспозицией, и следовательно, теорема для нее справедлива. Тем самым начальный этап индукции обоснован.
Предположим теперь, что теорема уже доказана для всех подстановок, действительно перемещающих менее s чисел, и рассмотрим произвольную подстановку а, действительно перемещающую s чисел. Пусть — одно из чисел, действительно перемещаемых подстановкой а. Применяя к этому числу изложенное выше построение (т. е. воздействуя на него степенями подстановки ), мы получим числа действительно перемещаемые подстановкой а (см. выше). Пусть первое из этих чисел с положительным номером, совпадающее с числом . Такое число существует, так как, например, число , где — порядок подстановки а, равно числу . Докажем, что числа все различны. Действительно, если, например, то, применяя к этому равенству подстановку мы получим что в силу минимальности числа q невозможно.
Поскольку числа все различны (и , ибо ; см. выше), то мы можем составить цикл
Подстановка оставляет на месте все числа, которые оставляются на месте подстановкой , а кроме того и все числа Таким образом, она действительно перемещает не более s — q чисел и, следовательно, по предположению индукции, разлагается в произведение независимых циклов. Для завершения доказательства остается заметить, что эти циклы независимы и с циклом
Так как каждый цикл разлагается на транспозиции, то из доказанной теоремы следует, что любая подстановка разлагается в произведение транспозиций (уже, вообще говоря, не независимых).
Числа, входящие в независимые циклы, на которые разложена некоторая подстановка, суть числа, действительно перемещаемые этой подстановкой. Каждый цикл разложения состоит из тех чисел, которые перемещаются друг в друга степенями данной подстановки. Таким образом, количество и строение независимых циклов, на которые разлагается подстановка, однозначно определяются этой подстановкой. Другими словами, разложение подстановки в произведение независимых циклов однозначно (с точностью до порядка множителей).