Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Группоиды, полугруппы, группы

Группоиды, полугруппы, группы


Рассмотрим алгебры, сигнатуры которых состоят из одной. бинарной операции. Эту операцию будем обозначать точкой [math](\,\cdot\,)[/math] и условно называть в этом случае умножением.


Группоидом называют любую алгебру [math]\mathcal{G}=(G,\cdot)[/math], сигнатура которой состоит из одной бинарной операции. В группоиде на бинарную операцию нет никаких ограничений.


Группоид [math](G,\cdot)[/math] называют полугруппой, если его операция ассоциативна, т.е. для любых элементов [math]a,\,b,\,c[/math] носителя [math]G[/math] выполняется равенство


[math]a\cdot (b\cdot c)= (a\cdot b)\cdot c\,.[/math]

Пример 2.6. а. Множество [math]V_3[/math] свободных векторов вместе с операцией векторного умножения является группоидом, но не полугруппой, так как векторное умножение не ассоциативно.


б. Множество натуральных чисел вместе с операцией возведения в степень также будет только группоидом, так как [math](a^b)^c\ne a^{(b^c)}[/math].


в. Множество [math]2^A[/math] всех подмножеств множества [math]A[/math] вместе с операцией [math]\setminus[/math] (разность множеств) тоже только группоид, поскольку указанная операция не ассоциативна.


г. Множество натуральных чисел [math]\mathbb{N}[/math] вместе с операцией сложения будет полугруппой.




Группоид [math]\mathcal{G}=(G,\cdot)[/math] называют моноидом, если его операция ассоциативна и относительно операции существует нейтральный элемент. Его называют нейтральным элементом моноида [math]\mathcal{G}[/math] или единицей моноида и обозначают [math]\bold{1}[/math].


Таким образом, моноид [math]\mathcal{G}=(G,\cdot)[/math] есть полугруппа, в которой для любого а имеют место равенства [math]a\cdot\bold{1}=\bold{1}\cdot a=a[/math], где [math]\bold{1}[/math] — нейтральный элемент (единица) моноида.


Поскольку нейтральный элемент относительно любой бинарной операции является единственным, мы можем рассматривать моноид как алгебру [math](G,\cdot,\bold{1}[/math], сигнатура которой состоит из двух операций: бинарной операции [math]{}\cdot{}[/math] (умножение) и нульарной операции [math]\bold{1}[/math] (нейтрального элемента). Введение [math]\bold{1}[/math] в сигнатуру моноида удобно тем, что зачастую при рассмотрении конкретных примеров моноидов целесообразно явно указать нейтральный элемент относительно его операции. Например, алгебра [math](2^{A\times A},\circ,\operatorname{id}A)[/math] есть моноид всех бинарных отношений на множестве [math]A[/math] с операцией композиции бинарных отношений, в котором нейтральным элементом является диагональ множества [math]A[/math].


Среди полугрупп выделяют полугруппы с коммутативной операцией — коммутативные полугруппы.




Пример 2.7. а. Множество всех бинарных отношений на произвольном множестве [math]A[/math] с операцией композиции отношений будет моноидом, нейтральным элементом которого служит диагональ множества [math]A[/math], поскольку для любых бинарных отношений [math]\rho,\tau[/math] и [math]\sigma[/math] на множестве [math]A[/math] имеют место равенства


[math]\rho\circ (\tau\circ\sigma)= (\rho\circ\tau)\circ\sigma[/math] и [math]\operatorname{id}A\circ\rho= \rho\circ\operatorname{A}=\rho.[/math].

б. Множество всех отображений некоторого множества [math]A[/math] в себя по операции композиции отображений есть моноид.


Напомним, что композиция отображений снова есть отображение и операция композиции имеет нейтральный элемент: тождественное отображение [math]A[/math] на себя. Поскольку любое отображение множества [math]A[/math] в себя можно рассматривать как бинарное отношение на этом множестве, а композицию отображений — как частный случай композиции отношений, требуемые свойства операции композиции отображений выполняются (см. пример 2.7.а). При этом тождественному отображению соответствует диагональ [math]\operatorname{id}A[/math] множества [math]A[/math]. Этот моноид называют часто симметрическим моноидом или симметрической полугруппой множества [math]A[/math].


в. Алгебра [math](\mathbb{N}_0,+)[/math], где носитель — множество [math]\mathbb{N}_0[/math] неотрицательных целых чисел, а сигнатура состоит из одной операции сложения, есть коммутативный моноид, в котором нейтральный элемент — это число 0. Действительно, сумма двух натуральных чисел есть натуральное число, операция сложения ассоциативна, коммутативна и для любого натурального числа [math]n[/math] имеет место равенство [math]n+0=n[/math].


Обратим внимание на то, что свойства нейтральных элементов и нулей ассоциируются со свойствами чисел 1 и 0 относительно операций умножения и сложения чисел.


г. Алгебра [math](\mathbb{Z},\cdot)[/math], у которой носителем является множество целых чисел, а сигнатура состоит из одной операции умножения, есть коммутативный моноид. Нейтральным элементом этого моноида является число 1.


д. Пусть [math]A[/math] — конечное множество, а [math]A^n[/math] — множество кортежей длины [math]n[/math]. На множестве всех кортежей [math]A^{+}= \mathop{\cup}\limits_{n\geqslant1}A^n[/math] определим операцию соединения (конкатенации) кортежей следующим образом:


[math](a_1,\ldots,a_m)\cdot (b_1,\ldots,b_k)= (a_1,\ldots,a_m,\, b_1,\ldots,b_k).[/math]

Можно видеть, что введенная операция ассоциативна, но не имеет нейтрального элемента. Таким образом, построена полугруппа, но не моноид.


Чтобы превратить эту полугруппу в моноид, расширим носитель полугруппы, введя понятие нулевой декартовой степени [math]A^0[/math] произвольного множества [math]A[/math]. Под [math]A^0[/math] понимают одноэлементное множество [math]\{\lambda\}[/math], единственный элемент которого называют пустым кортежем. Такое определение множества [math]A^0[/math] объясняется следующим: мощность положительной декартовой степени [math]A^n[/math] конечного множества равна [math]|A|^n[/math]. При [math]n=0[/math] должно быть [math]|A^0|=|A|^0=1[/math], откуда заключаем, что [math]A^0[/math] — одноэлементное множество.


Обозначив [math]A^{\ast}=A^{0}\cup A^{+}[/math], по определению для любого [math]x\in A^{\ast}[/math] полагаем [math]x\cdot\lambda= \lambda\cdot x=x[/math]. В результате получим алгебру [math](A^{\ast},\cdot)[/math], являющуюся моноидом, с нейтральным элементом [math]\lambda[/math]. Его называют свободным моноидом, порожденным множеством [math]A[/math].




Полурешетка в абстрактной алгебре


Полугруппу, операция которой коммутативна и идемпотентна, называют полурешеткой.


Пример 2.8. а. Алгебры [math](2^A,\cup),\, (2^A,\cap)[/math] (для произвольного фиксированного множества [math]A[/math]) являются полурешетками, поскольку операции [math]\cup[/math] и [math]\cap[/math] ассоциативны, коммутативны и идемпотентны.


б. Алгебра [math](\mathbb{N},\operatorname{lcm})[/math], где [math]\operatorname{lcm}[/math] — операция вычисления наименьшего общего кратного двух чисел, является полурешеткой. Покажем, что указанная операция ассоциативна. Рассмотрим произвольные натуральные числа [math]m,\,n[/math] и [math]l[/math]. Каждое из этих чисел можно разложить на произведение простых чисел и представить в виде


[math]m=p_1^{\alpha_1}\cdot \ldots\cdot p_k^{\alpha_k},\qquad n=p_1^{\beta_1}\cdot \ldots\cdot p_k^{\beta_k},\qquad l=p_1^{\gamma_1}\cdot \ldots\cdot p_k^{\gamma_k},[/math]

где набор простых чисел [math]p_1,\ldots,p_k[/math] выбран одинаковым для всех трех чисел, а некоторые из показателей [math]\alpha_i,\,\beta_i[/math] и [math]\gamma_i,~ i=\overline{1,k}[/math] могут быть равными нулю. Тогда для чисел тип имеем


[math]\operatorname{lcm}(n,m)= p_1^{\max(\alpha_1,\beta_1)}\cdot \ldots\cdot p_{k}^{\max(\alpha_k, \beta_k)}.[/math]

Таким образом, ассоциативность операции [math]\operatorname{lcm}[/math] сводится к ассоциативности операции max вычисления наибольшего из двух натуральных чисел. Ассоциативность последней вытекает из очевидного тождества [math]\max(a,\max(b,c))= \max(\max(a,b),c)[/math], верного для любых чисел [math]a,\,b[/math] и [math]c[/math].


Поскольку [math]\operatorname{lcm}(n,m)= \operatorname{lcm}(m,n)[/math], операция [math]\operatorname{lcm}[/math] коммутативна, а так как для любого натурального числа справедливо равенство [math]\operatorname{lcm}(n.n)=n[/math], то операция идемпотентна.


в. Алгебра [math](\mathbb{N},\gcd)[/math], где [math]\gcd[/math] — операция вычисления наибольшего общего делителя двух целых чисел, также является полурешеткой.




Способы задания группы как алгебры


Группоид [math]\mathcal{G}=(G,\cdot)[/math] называют группой, если операция ассоциативна, существует нейтральный элемент (единица) [math]\bold{1}[/math] относительно умножения и для каждого [math]x\in G[/math] существует такой элемент [math]x'\in G[/math], называемый обратным к [math]x[/math], что [math]x\cdot x'=x'\cdot x=\bold{1}[/math].


Таким образом, группа — это алгебра [math]\mathcal{G}=(G,\cdot)[/math], в которой для всех [math]a,b,c\in G[/math] выполняется равенство [math]a\cdot (b\cdot c)=(a\cdot b)\cdot c[/math], существует единственный элемент [math]\bold{1}\in G[/math], такой, что [math]a\cdot\bold{1}= \bold{1}\cdot a=a[/math] для любого [math]a\in G[/math], и для каждого [math]a\in G[/math] существует такой элемент [math]a'[/math], что [math]a\cdot a'=a'\cdot a=\bold{1}[/math]. Короче говоря, группа — это моноид, в котором для каждого элемента существует обратный элемент.


Отметим, что задать группу как алгебру можно несколькими способами в зависимости от состава операций, включенных в сигнатуру.


Во-первых, в сигнатуру может быть включена единственная бинарная операция. В этом случае пишут [math]\mathcal{G}=(G,\cdot)[/math], а все свойства операции описывают дополнительно.


Во-вторых, в сигнатуру может быть включена нульарная операция — нейтральный элемент группы. В этом случае пишут [math]\mathcal{G}=(G,\cdot,\bold{1})[/math] и дополнительно указывают существование обратного элемента относительно бинарной операции для всех элементов носителя.


Третий способ задания группы как алгебры вытекает из следующей теоремы.


Теорема 2.1. В любой группе [math]\mathcal{G}=(G,\cdot)[/math] для каждого [math]a\in G[/math] элемент, обратный к [math]a[/math], единственный.


Пусть в группе [math](G,\cdot)[/math] с единицей [math]\bold{1}[/math] для некоторого [math]a[/math] существуют два элемента [math]a'[/math] и [math]a''[/math], обратных к [math]a[/math]. Тогда [math]a'=a'\cdot\bold{1}[/math] в силу свойства единицы. Так как [math]\bold{1}=a\cdot a''[/math], то [math]a'=a'\cdot (a\cdot a'')[/math]. Используя ассоциативность и учитывая, что [math]a'[/math] — элемент, обратный к а, получим


[math]a'\cdot (a\cdot a'')= (a'\cdot a)\cdot a''= \bold{1}\cdot a''=a''.[/math]



Единственность для каждого элемента [math]a[/math] обратного элемента [math]a'[/math] группы [math]\mathcal{G}[/math] позволяет обозначать его как [math]a^{-1}[/math] и операцию [math]\phantom{A}^{-1}\colon a\mapsto a^{-1}[/math] вычисления (или взятия) обратного элемента ввести в сигнатуру группы. Таким образом, группу можно рассматривать и как алгебру [math]\mathcal{G}=(G,\cdot,\phantom{A}^{-1},\bold{1})[/math], сигнатура которой состоит из бинарной операции умножения, унарной операции взятия обратного элемента и нульарной операции — единицы группы (нейтрального элемента).


В дальнейшем в зависимости от контекста будем использовать все указанные варианты задания группы.


Среди групп также выделяют те, бинарная операция в которых коммутативна, — коммутативные (абелевы) группы. В коммутативных полугруппах и группах бинарную операцию часто обозначают знаком [math]{}+[/math] и называют сложением.


Уместно здесь рассмотреть вопрос о двух формах записи бинарной операции группы. В аддитивной записи операции ее обозначают знаком [math]{}+[/math], нейтральный элемент — знаком [math]\bold{0}[/math], а элемент, обратный к [math]a[/math] относительно операции [math]{}+[/math], записывают в виде [math]-a[/math], называя его при этом противоположным к [math]a[/math].


В мультипликативной записи операцию обозначают знаком [math]\cdot[/math], нейтральный элемент — знаком [math]\bold{1}[/math], а элемент, обратный к [math]a[/math], записывают в виде [math]a^{-1}[/math]. В этом случае бинарную операцию группы часто называют умножением (также умножением группы или групповым умножением), а элемент [math]a\cdot b[/math], как правило записываемый в виде [math]ab[/math], — произведением элементов [math]a[/math] и [math]b[/math].


В алгебраической литературе сложилась такая традиция, что аддитивная запись используется преимущественно для коммутативных групп. Поскольку одним из самых простых, распространенных и вместе с тем важных примеров коммутативной группы служит аддитивная группа целых чисел, то обозначения и термины для произвольной аддитивно записываемой коммутативной группы "скопированы" с терминов для группы [math](\mathbb{Z},+,0)[/math]. Аналогично мультипликативная запись произвольной группы " позаимствована" у мультипликативных групп рациональных и вещественных чисел.




Пример 2.9. а. Алгебра [math](\mathbb{Z},+)[/math] — коммутативная группа, поскольку на множестве целых чисел операция сложения ассоциативна и коммутативна, число 0 есть нейтральный элемент, и для каждого целого числа [math]n[/math] существует обратный по сложению элемент, а именно число [math]-n[/math], противоположное [math]n[/math]. Рассматриваемую группу называют аддитивной группой целых чисел.


б. Множество всех биекций некоторого множества [math]A[/math] на себя с операцией композиции отображений есть группа.


Это следует из того, что композиция двух биекций есть биекция, операция композиции ассоциативна, ее нейтральный элемент — тождественное отображение [math]\operatorname{id}A[/math] — есть биекция, для всякой биекций [math]f\colon A\to A[/math] отображение [math]f^{-1}[/math], обратное биекций [math]f[/math], определено, является биекцией и выполнены равенства


[math]f\circ f^{-1}= f^{-1}\circ f= \operatorname{id}A\,.[/math]

Эту группу называют симметрической группой множества [math]A[/math], а в том случае, когда множество [math]A[/math] конечно, — группой подстановок множества [math]A[/math]. Если множество [math]A[/math] состоит из [math]n[/math] элементов, группу подстановок этого множества называют также симметрической группой степени [math]n[/math] или группой подстановок n-й степени и обозначают [math]S_n[/math] (см. пример 2.10).


в. Алгебры [math](\mathbb{Q}\setminus \{0\},\cdot)[/math] и [math](\mathbb{R}\setminus \{0\}, \cdot)[/math] есть коммутативные группы. Их называют мультипликативной группой рациональных чисел и мультипликативной группой действительных чисел соответственно. В каждой из них число 1 есть нейтральный элемент (единица) группы, а обратный к числу [math]x[/math] по операции умножения элемент [math]x^{-1}[/math] есть число [math]x^{-1}=1/x[/math].


г. Для произвольно фиксированного множества [math]A[/math] рассмотрим алгебру [math](2^A,\triangle)[/math], где [math]\triangle[/math] — операция вычисления симметрической разности множеств. Операция [math]\triangle[/math] ассоциативна и коммутативна. Для любого [math]X\subseteq A[/math] имеем [math]X\,\triangle\,\varnothing=X[/math]. Кроме того, [math]X=Y[/math] тогда и только тогда, когда [math]X\,\triangle\,Y=\varnothing[/math]. Поэтому алгебра [math](2^A,\triangle)[/math] является абелевой группой, в которой каждый элемент обратен сам себе, а нейтральный элемент — пустое множество.


д. Рассмотрим алгебру [math]\mathbb{Z}_{k}^{+}=(\{0,1,\ldots,k-1\},\oplus_k)[/math], в которой операция [math]\oplus_k[/math] (сложения по модулю [math]k[/math]) определяется так: для любых двух [math]m[/math] и [math]n[/math] число [math]m\oplus_{k}n[/math], называемое суммой чисел [math]m[/math] и [math]n[/math] по модулю [math]k[/math], равно остатку от деления арифметической суммы [math]m+n[/math] на [math]k[/math]. Можно проверить, что эта алгебра является коммутативной группой. Ее называют аддитивной группой вычетов по модулю [math]k[/math]. Нейтральным элементом служит число 0, а обратным к числу [math]n[/math] будет [math]k-n[/math], поскольку [math]n\oplus_{k}(k-n)=0[/math].


е. Множество всех невырожденных (т.е. имеющих ненулевой определитель) числовых квадратных матриц порядка [math]n[/math] с операцией умножения матриц является группой. Действительно, произведение двух невырожденных матриц снова есть невырожденная матрица; единичная матрица порядка [math]n[/math] невырожденная, и матрица, обратная к невырожденной, также является невырожденной. Эту группу будем обозначать [math]\mathcal{M}_n[/math].





Из рассмотренных четырех видов алгебр — группоида, полугруппы, моноида и группы — последняя обладает наиболее интересными свойствами. Изучим более подробно операцию вычисления обратного элемента.


Теорема 2.2. Пусть [math]\mathcal{G}=(G,\cdot)[/math] — группа. Для любых элементов [math]a,b\in G[/math] верны тождества


[math](a\cdot b)^{-1}= b^{-1}\cdot a^{-1},\qquad (a^{-1})^{-1}=a\,.[/math]

В силу ассоциативности умножения группы имеем


[math](a\cdot b)\cdot (b^{-1}\cdot a^{-1})= \bigl((a\cdot b)\cdot b^{-1}\bigr)\cdot a^{-1}.[/math]

Используя еще раз ассоциативность, определение элемента, обратного к данному, и свойства единицы, получим


[math]\bigl((a\cdot b)\cdot b^{-1}\bigr)\cdot a^{-1}= a\cdot (b\cdot b^{-1})\cdot a^{-1}= a\cdot a^{-1}= \bold{1}\,.[/math]

Итак, [math](a\cdot b)\cdot (b^{-1}\cdot a^{-1})=\bold{1}[/math]. Точно так же доказывается, что [math](b^{-1}\cdot a^{-1})(a\cdot b)=\bold{1}[/math]. Поэтому элемент [math]b^{-1}\cdot a^{-1}[/math] является обратным к элементу [math]a\cdot b[/math]. Согласно теореме 2.1, обратный элемент единственный, и поэтому [math](a\cdot b)^{-1}=b^{-1}\cdot a^{-1}[/math]. Второе из доказываемых равенств следует непосредственно из определения элемента, обратного к данному. Действительно, определение элемента [math]a^{-1}[/math], обратного к [math]a[/math], равенством [math]a^{-1}\cdot a=a\cdot a^{-1}=\bold{1}[/math] можно рассматривать как определение [math](a^{-1})^{-1}[/math] — обратного элемента к [math]a^{-1}[/math], которым является, согласно этим равенствам, элемент [math]a[/math]. В силу теоремы 2.1 он единственный, то есть [math]a=(a^{-1})^{-1}[/math].


Таким образом, мы установили, что элемент, обратный к произведению [math]a\cdot b[/math], равен [math]b^{-1}\cdot a^{-1}[/math], а элемент, обратный к элементу, обратному к [math]a[/math], равен [math]a[/math].




Теорема 2.3. В любой группе [math]\mathcal{G}=(G,\cdot,\bold{1})[/math] справедливы левый и правый законы сокращения: если [math]a\cdot x=a\cdot y[/math], то [math]x=y[/math], и если [math]x\cdot a=y\cdot a[/math], то [math]x=y[/math].


Пусть [math]a\cdot x=a\cdot y[/math]. Умножая обе части этого равенства слева на элемент [math]a^{-1}[/math], получаем


[math]a^{-1}\cdot (a\cdot x)= a^{-1}\cdot (a\cdot y).[/math]

В силу ассоциативности групповой операции последнее равенство можно записать так:


[math](a^{-1}\cdot a)\cdot x= (a^{-1}\cdot a)\cdot y\,.[/math]

Поскольку [math]a^{-1}\cdot a=\bold{1}[/math], то [math]\bold{1}\cdot x=\bold{1}\cdot y[/math], откуда [math]x=y[/math]. Тем самым доказан левый закон сокращения. Аналогично доказывается и правый закон.




Пусть [math]\mathcal{G}=(G,\cdot,\bold{1})[/math] — группа, [math]a[/math] и [math]b[/math] — фиксированные элементы [math]G[/math]. Рассмотрим задачу решения уравнений


[math]a\cdot x=b,[/math]
(2.1)

[math]x\cdot a=b[/math]
(2.2)

в группе [math]\mathcal{G}[/math], т.е. поиска всех таких элементов [math]x\in G[/math], для которых уравнение (2.1) (или (2.2)) превращается в тождество.


Теорема 2.4. В любой группе [math]\mathcal{G}[/math] уравнения вида (2.1) и (2.2) имеют решения, и притом единственные.


Покажем, что [math]x=a^{-1}\cdot b[/math] есть решение (2.1). Действительно, [math]a\cdot (a^{-1}\cdot b)= (a\cdot a^{-1}\cdot b)=b[/math].


Докажем единственность решения. Пусть для фиксированных [math]a[/math] и [math]b[/math] и некоторого [math]x[/math] выполнено равенство [math]a\cdot x=b[/math]. В группе для любого [math]a[/math] существует и однозначно определен элемент [math]a^{-1}[/math], обратный к [math]a[/math]. Умножив на него обе части равенства, получим [math]a^{-1}\cdot (a\cdot x)= a^{-1}\cdot b[/math]. В силу ассоциативности преобразуем последнее равенство к виду [math](a^{-1}\cdot a)\cdot x=a^{-1}\cdot b[/math]. Поскольку [math]a^{-1}\cdot a=\bold{1}[/math], то [math]\bold{1}\cdot x=a^{-1}\cdot b[/math], откуда [math]x=a^{-1}\cdot b[/math]. Это решение единственное в силу единственности обратного элемента.


Аналогично из [math]x\cdot a=b[/math] получаем [math]x=b\cdot a^{-1}[/math], и это решение также единственное.




Замечание. При использовании аддитивной записи операции для коммутативной группы [math]\mathcal{G}=(G,+,\bold{0})[/math] оба написанных выше уравнения сводятся к одному:


[math]a+x=b\,,[/math]

а его решение есть [math]x=b+(-a)[/math]. Правую часть этого равенства в коммутативной группе называют разностью элементов [math]b[/math] и [math]a[/math] и обозначают [math]b-a[/math]. Саму же операцию, сопоставляющую упорядоченной паре [math](a,b)[/math] разность [math]b-a[/math], называют операцией вычитания. С учетом введенных обозначений решение уравнения в коммутативной группе можно записать так: [math]x=b-a[/math].


В случае коммутативной группы при употреблении для бинарной операции мультипликативной записи решения обоих уравнений имеют вид [math]x=b\cdot a^{-1}[/math]. Выражение [math]b\cdot a^{-1}[/math] в коммутативной группе называют частным от деления [math]b[/math] на [math]a[/math] и обозначают [math]\tfrac{b}{a}[/math] (или [math]b/a[/math]), а саму операцию называют операцией деления. Решение уравнения в этом случае записывают в виде [math]x=\tfrac{b}{a}[/math] (или [math]x=b/a[/math]).




Пример 2.10. Рассмотрим группу подстановок n-й степени [math]S_n[/math] всех биекций n-элементного множества [math]\{1,2,\ldots,n\}[/math]. Произвольную биекцию [math]\sigma[/math] из [math]S_n[/math] обычно записывают в виде


[math]\begin{pmatrix}1&2& \cdots &n\\ \alpha_1& \alpha_2& \cdots& \alpha_n \end{pmatrix}\!,[/math]

обозначая тем самым, что образ 1 (при отображении [math]\sigma[/math]) есть [math]\alpha_1[/math], образ 2 есть [math]\alpha_2,\ldots[/math] образ [math]n[/math] есть [math]\alpha_n[/math]. Биекцию множества [math]\{1,\ldots,n\}[/math] на себя называют подстановкой этого множества. Подстановку, которая отображает [math]\alpha_1[/math] в [math]\alpha_2[/math], [math]\alpha_2[/math] в [math]\alpha_3,\ldots,[/math], [math]\alpha_{k-1}[/math] в [math]\alpha_{k}[/math], а [math]\alpha_{k}[/math] в [math]\alpha_{1}[/math], где [math]1\leqslant \alpha_1,\alpha_2, \ldots,\alpha_k \leqslant n[/math] и все [math]\alpha_j[/math] попарно различны, а все элементы, отличные от [math]\alpha_1,\ldots,\alpha_k[/math], отображаются сами в себя, называют циклом длины [math]k[/math] и записывают ее в виде [math](\alpha_1,\alpha_2, \ldots,\alpha_k)[/math]. Например, подстановку из группы [math]S_4[/math]


[math]\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}[/math] можно записать в виде [math]\begin{pmatrix}1&3&4\end{pmatrix}[/math].

Цикл длины 2 называют транспозицией. Транспозиция представляет такое отображение множества [math]\{1,\ldots,n\}[/math] в себя, при котором два элемента меняются местами, а остальные остаются на своих местах. Так, полная запись транспозиции [math](3&4)[/math] в [math]S_4[/math] будет иметь вид


[math]\begin{pmatrix}1&2&3&4\\ 1&2&4&3\end{pmatrix}\!.[/math]

Подстановка, обратная подстановке [math]\begin{pmatrix}1&2&\cdots&n\\ \alpha_1& \alpha_2& \cdots& \alpha_n \end{pmatrix}[/math], есть подстановка, которая отображает [math]\alpha_1[/math] в 1, [math]\alpha_2[/math] в 2, [math]\ldots~ \alpha_n[/math] в [math]n[/math]. Отметим, что при записи обратной подстановки элементы первой строки тем не менее записываются в обычном порядке: [math]1,\ldots,n[/math].


В группе [math]S_3[/math] решим следующее уравнение:


[math]\begin{pmatrix}1&2&3\\3&1&1\end{pmatrix}\! \circ X\circ\! \begin{pmatrix}1&2&3\\ 2&3&1\end{pmatrix}= \begin{pmatrix}1&2&3\\ 3&2&1 \end{pmatrix}\!.[/math]

Умножив обе части уравнения слева на


[math]\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}^{-1}= \begin{pmatrix}1&2&3\\ 2&3&1 \end{pmatrix}[/math], получим [math]X\circ\! \begin{pmatrix}1&2&3\\ 2&3&1\end{pmatrix}= \begin{pmatrix}1&2&3\\ 2&1&3\end{pmatrix}[/math].

Далее, умножив полученное уравнение справа на


[math]\begin{pmatrix}1&2&3\\ 2&3&1\end{pmatrix}^{-1}= \begin{pmatrix}1&2&3\\ 3&1&2 \end{pmatrix}[/math] окончательно получим [math]X=\begin{pmatrix}1&2&3\\ 1&3&2 \end{pmatrix}= \begin{pmatrix}2&3 \end{pmatrix}[/math].



Степень элемента в полугруппе


В полугруппе в общем случае законы сокращения и разрешимость уравнений типа (2.1) и (2.2) могут не иметь места. Например, в полугруппе квадратных матриц фиксированного порядка с операцией умножения матриц из матричного равенства [math]AX=AY[/math], вообще говоря, не следует, что [math]X=Y[/math]. Это можно утверждать лишь при дополнительном предположении, что [math]\det{A}\ne0[/math]. Можно доказать, что в свободном моноиде, порожденном некоторым конечным множеством, оба закона сокращения справедливы, но никаких обратных элементов не существует.


В полугруппе можно умножать любой элемент [math]a[/math] сам на себя, причем в силу ассоциативности операции полугруппы элемент [math]\overbrace{a\cdot a\cdot\ldots\cdot a}^{n~\text{times}}[/math] определен однозначно. Этот элемент называют n-й степенью элемента [math]a[/math] и обозначают [math]a^n[/math]. При этом


[math]a^1=a,\quad a^n=a\cdot a^{n-1},\quad n=2,3,\ldots[/math]

В моноиде вводят также нулевую степень элемента, полагая [math]a^0=\bold{1}[/math].


Если [math](A,\cdot,\bold{1})[/math] — группа, то можно ввести и отрицательные степени элемента согласно равенству


[math]a^{-n}=(a^{-1})^n,\quad n=1,2,\ldots[/math]

Без доказательства сформулируем утверждения о свойствах степеней.




Теорема 2.5. Для любой полугруппы [math]a^m\cdot a^n= a^{m+n},~ (a^m)^n= a^{mn}~ (m,n\in \mathbb{N})[/math].


Теорема 2.6. Для любой группы [math]a^{-n}=(a^n)^{-1},~ a^m\cdot a^n=a^{m+n},~ (a^m)^n=a^{nm}~ (m,n\in \mathbb{Z})[/math].


Определение 2.4. Полугруппу (в частности, группу) [math](A,\cdot)[/math] называют циклической, если существует такой элемент [math]a[/math], что любой элемент [math]x[/math] полугруппы является некоторой (целой) степенью элемента [math]a[/math]. Элемент [math]a[/math] называют образующим элементом полугруппы (группы).


Пример 2.11. а. Полугруппа [math](\mathbb{N}_0,+,0)[/math] циклическая, с образующим элементом 1. При аддитивной записи бинарной операции возведение элемента [math]a[/math] в положительную степень [math]n[/math] есть сумма [math]n[/math] этих элементов, и это записывают [math]n\cdot a[/math] (или [math]na[/math], без знака умножения).


б. Группа [math](\mathbb{Z},+,0)[/math] также циклическая. Для нее образующими элементами могут быть 1 и –1. Рассмотрим элемент 1. Тогда


[math]\begin{gathered}0\cdot1=0,\quad 1= \underbrace{1+\ldots+1}_{n~ \text{times}}= n~(n>0), \quad (-1)\cdot1=-1,\\ (-n)\cdot1= n\cdot(-1)= \underbrace{(-1)+\ldots+(-1)}_{n~ \text{times}}=-n~ (n>0). \end{gathered}[/math]

Если в качестве образующего взять элемент –1, то [math]0\cdot(-1)=0[/math], отрицательные целые числа получаются как положительные "степени" –1, а положительные — как отрицательные "степени" –1. Например, [math](-2)\cdot(-1)=2,~ 4\cdot (-1)=-4[/math].


в. Группа [math](\mathbb{Z}_3,\oplus_3,0)[/math] вычетов по модулю 3 циклическая, причем любой ее ненулевой элемент является образующим.


Действительно, для 1 имеем [math]1\oplus_31=2,~ 1\oplus_3 1\oplus_3 1=0[/math], а для 2 получим


[math]2^2=2\oplus_3 2=1,\qquad 2\oplus_3 2\oplus_3 2=0.[/math]



Строение конечных циклических групп


Изучим подробнее строение конечных циклических групп, используя мультипликативную запись бинарной операции. Напомним, что конечная алгебра {конечная группа, в частности) — это алгебра, носитель которой — конечное множество.


Порядком конечной группы называют количество элементов в этой группе.


Так, например, аддитивная группа вычетов по модулю [math]k[/math] имеет порядок [math]k[/math]. Симметрическая группа степени [math]n[/math], т.е. группа подстановок [math]S_n[/math], имеет порядок [math]n[/math]!. Мультипликативная группа вычетов по модулю [math]p[/math], где [math]p[/math] — простое число, имеет порядок [math]p-1[/math].


Порядок элемента а циклической группы — это наименьшее положительное [math]n[/math], такое, что [math]a^n=\bold{1}[/math].


Теорема 2.7. Порядок образующего элемента конечной циклической группы равен порядку самой группы.


Пусть [math]\mathcal{G}=(G,\cdot,\bold{1})[/math] — конечная циклическая группа с образующим элементом [math]a[/math] и [math]n>0[/math] — порядок этого элемента.


Тогда все степени [math]a^0=\bold{1}, a^1=a,\ldots,a^{n-1}[/math] попарно различны. Действительно, если


[math]a^k=a^l,~ 0<l<k<n[/math], то [math]a^{k-l}= a^{k+(-l)}= a^ka^l= a^la^{-l}= a^{l-l}= \bold{1}[/math].

Поскольку [math]k-l<n[/math], получено противоречие с выбором [math]n[/math] как порядка элемента [math]a[/math] (ибо найдена степень, меньшая [math]n[/math], при возведении в которую элемента [math]a[/math] получится единица).


Осталось доказать, что любая степень элемента [math]a[/math] принадлежит множеству [math]\{\bold{1},a, \ldots, a^{n-1}\}[/math]. Для любого целого [math]m[/math] существуют также целые [math]n,k[/math], такие, что [math]m=kn+q[/math], где [math]q[/math] — целое и [math]0\leqslant q<n[/math]. Тогда


[math]a^m= a^{kn+q}= a^{kn}\cdot a^q= \bold{1}\cdot a^q= a^q\in \{\bold{1},a, \ldots, a^{n-1}\}.[/math]

Поскольку каждый элемент группы [math]\mathcal{G}[/math] есть некоторая степень элемента [math]a[/math], то [math]G=\{\bold{1},a, \ldots, a^{n-1}\}[/math] и порядок группы равен [math]n[/math].


Из доказанной теоремы следует, что в бесконечной циклической группе не существует такого [math]n>0[/math], что для образующего элемента [math]a[/math] группы выполняется равенство [math]a^n=\bold{1}[/math].


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved