Как составить таблицу кэли
Перейти к содержимому

Как составить таблицу кэли

  • автор:

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

Таблица Кэли — квадратная таблица, описывающая структуру конечной алгебраической системы и состоящая из результатов применения бинарной операции к её элементам. Названа в честь английского математика Артура Кэли, использовавшего её в теории групп. Имеет важное значение в дискретной математике.

Например, таблица Кэли для стандартной операции умножения на множестве имеет вид:

× 1 −1
1 1 −1
−1 −1 1

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

В абстрактной алгебре таблицы Кэли используются для описания конечных групп, колец, полей и других алгебраических структур. Для бесконечных структур и структур с большим количеством элементов их использование нецелесообразно. В этом случае структуры чаще всего задают образующими и соотношениями.

История Править

Таблицы Кэли впервые появились в статье Кэли «On The Theory of Groups, as depending on the symbolic equation θ n = 1» в 1854 году. В этой статье это были просто таблицы, используемые в иллюстративных целях. Называть таблицами Кэли их стали позже в честь их создателя.

Структура Править

Поскольку таблицы Кэли используются для операций, не обязательно являющихся коммутативными, произведение ab может быть не равно произведению ba. Чтобы избежать путаницы, принимается, что множитель, соответствующий строкам, идёт первым, а множитель, соответствующий столбцам — вторым. Например, пересечение строки a и столбца b — это ab, а не ba, что показано в следующем примере:

* a b c
a a 2 ab ac
b ba b 2 bc
c ca cb c 2

Кэли в своей работе в первой строке и первом столбце размещал нейтральный элемент, что позволяло ему не выделять отдельных строки и столбца с указанием элементов, как это видно в примере выше. Например, та же самая таблица представлялась в виде:

a b c
b c a
c a b

В этом примере циклической группы Z3 элемент a является нейтральным элементом, и он появляется в верхнем левом углу таблицы. Легко видеть, например, что b 2 = c и что cb = a. Вопреки этому большинство современных текстов, в том числе и эта статья, включают заголовочные строку и столбец для большей ясности.

Свойства и использование Править

Коммутативность Править

Таблица Кэли показывает, является ли операция коммутативной. А именно, это свойство эквивалентно симметричности таблицы Кэли относительно её диагонали. Например, циклическая группа порядка 3 выше, а также по обычному умножению, обе являются примерами абелевых групп, и симметрия их таблиц Кэли доказывает это. А вот наименьшая неабелева группа — диэдральная группа шестого порядка, не имеет симметрии в таблице Кэли.

Ассоциативность Править

Поскольку ассоциативность в группах присутствует по определению, часто она предполагается и в таблицах Кэли. Однако таблицы Кэли можно использовать для описания операций в квазигруппах, в которых ассоциативность не требуется (более того, таблицы Кэли можно использовать для описания операции в любой конечной магме). В общем случае невозможно простым обзором таблицы определить, ассоциативна операция или нет, в отличие от коммутативности. Это обусловлено тем, что ассоциативность зависит от трёх элементов в равенстве, , в то время как таблица Кэли показывает произведения двух элементов. Тем не менее, тест ассоциативности Лайта может определить ассоциативность с меньшими усилиями, чем грубый перебор.

Перестановки Править

Поскольку сокращение [en] для групп выполняется (более того, выполняется даже для квазигрупп), никакая строка или столбец таблицы Кэли не может содержать один элемент дважды. Таким образом, каждая строка и столбец таблицы является перестановкой элементов группы.

Чтобы увидеть, почему строки и столбцы не могут содержать одинаковых элементов, положим a, x и y — элементы группы, при этом x и y различны. Теперь в строке, соответствующей элементу a, и столбце, соответствующем элементу x, будет находиться произведение ax. Аналогично в столбце, соответствующем y, будет находиться ay. Пусть два произведения равны, то есть строка a содержит элемент дважды. По правилу сокращения мы из ax = ay можем заключить, что x = y, что противоречит выбору x и y. Точно те же рассуждения верны и для столбцов. Ввиду конечности группы по принципу Дирихле каждый элемент группы будет представлен в точности по одному разу в каждой строке и в каждом столбце.

То есть таблица Кэли для группы является примером латинского квадрата.

Построение таблиц Кэли для групп Править

Используя структуру групп, часто можно «заполнить» таблицы Кэли, которые имеют незаполненные поля, даже не зная ничего об операции группы. Например, поскольку каждая строка и каждый столбец должны содержать все элементы группы, один отсутствующий элемент в строке (или столбце) можно заполнить, совершенно не зная ничего о группе. Это показывает, что это свойство и некоторые другие свойства групп дают возможность построения таблиц Кэли, даже если мы мало что знаем о группе.

«Скелет нейтральных элементов» конечной группы Править

Поскольку в любой группе, даже не в абелевой, любой элемент перестановочен со своим обратным, распределение нейтральных элементов в таблице Кэли симметрично относительно диагонали. Нейтральные элементы, лежащие на диагонали, соответствуют элементам, совпадающим со своими обратными.

Поскольку порядок строк и столбцов в таблице Кэли произвольны, удобно расположить их в следующем порядке: начинаем с нейтрального элемента группы, который всегда совпадает со своим обратным, затем перечисляем все элементы, которые совпадают со своими обратными, а затем выписываем пары элементов (элемент и обратный к нему).

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

Группы с различными скелетами не могут быть изоморфны, однако обратное неверно (например, циклическая группа C8 и группа кватернионов Q не изоморфны, хотя и имеют одинаковые скелеты).

Пусть имеется шесть элементов группы e, a, b, c, d и f. Пусть e — нейтральный элемент. Поскольку нейтральный элемент совпадает со своим обратным, а обратный элемент единственнен, должен быть, по крайней мере, ещё один элемент, совпадающий со своим обратным. Таким образом, получаем следующие возможные скелеты:

  • все элементы совпадают со своими обратными,
  • все элементы, за исключением d и f, совпадают со своими обратными, а эти два обратны друг другу,
  • a совпадает со своим обратным, b и c обратны, d и f обратны.

В нашем случае не существует группы первого типа порядка 6. Более того, из того, что скелет возможен, совсем не следует, что существует группа, у которой скелет совпадает с ним.

Любая группа, в которой любой элемент совпадает с его обратным, абелева.

Заполнение таблицы по скелету нейтральных элементов Править

Если задан скелет нейтральных элементов, можно приступить к заполнению таблицы Кэли. Например, выберем второй скелет группы порядка 6 из описанных выше:

e a b c d f
e e
a e
b e
c e
d e
f e

Очевидно, что строка e и столбец e могут быть заполнены немедленно. Как только это сделано, может оказаться необходимым (и это необходимо в нашем случае) сделать предположение, которое впоследствии может привести к противоречию, что будет означать, что предположение неверно. Мы предположим, что ab = c. Тогда:

e a b c d f
e e a b c d f
a a e c
b b e
c c e
d d e
f f e

Умножая ab = c слева на a, получим b = ac. Умножение справа на c даёт bc = a. Умножение ab = c справа на b даёт a = cb. Умножение bc = a слева на b даёт c = ba, а умножение справа на a даёт ca = b. После заполнения этих произведений в таблице мы обнаружим, что ad и af остаются незаполненными в строке a. Поскольку каждый элемент должен появиться в строке ровно один раз, получим, что ad должен быть либо d, либо f. Однако этот элемент не может равняться d, поскольку в противном случае a был бы равен e, в то время как мы знаем, что эти два элемента различны. Таким образом, ad = f и af = d.

Теперь, поскольку обратный элементу d есть f, умножение ad = f справа на f даёт a = f 2 . Умножение слева на d даёт da = f. Умножив справа на a, мы получим d = fa.

После внесения всех этих произведений таблица Кэли примет вид:

e a b c d f
e e a b c d f
a a e c b f d
b b c e a
c c b a e
d d f e
f f d e a

Поскольку каждый элемент группы должен появиться в каждой строке ровно один раз, две пустые ячейки таблицы в строке b должны быть заняты либо d, либо f. Однако в соответствующих столбцах уже присутствуют d и f. Таким образом, что бы мы ни поставили в эти поля, получим повторение в столбцах, что показывает, что начальное предположение ab = c было неверным. Однако мы теперь знаем, что abc.

Осталось две возможности — либо ab = d, либо ab = f. Поскольку d and f взаимно обратны и выбор букв произволен, результат будет одинаковым с точностью до изоморфизма. Без потери общности можно считать, что ab = d. Если мы теперь получим противоречие, нам придётся признать, что для этого скелета нет соответствующей группы.

Получаем новую таблицу Кэли:

e a b c d f
e e a b c d f
a a e d
b b e
c c e
d d e
f f e

Умножая ab = d слева на a, мы получаем b = ad. Умножение справа на f даёт bf = a, а умножение слева на b даёт f = ba. Умножив справа на a, мы получим fa = b, а умножив слева на d, получим a = db. Внеся результаты в таблицу Кэли, получим (новые элементы выделены красным):

e a b c d f
e e a b c d f
a a e d b
b b f e a
c c e
d d a e
f f b e

В строке a отсутствуют c и f, но поскольку af не может равняться f (иначе a будет равен e), мы можем заключить, что af = c. Умножение слева на a даёт f = ac, и это мы можем умножить справа на c, что даёт fc = a. Умножение последнего на d слева даёт c = da, что мы можем умножить справа на a и получить ca = d. Таким же образом, умножая af = c справа на d, получим a = cd. Обновим таблицу (последние изменения выделены синим):

e a b c d f
e e a b c d f
a a e d f b c
b b f e a
c c d e a
d d c a e
f f b a e

Поскольку в строке b отсутствуют c и d, а bc не может равняться c, мы выводим, что bc = d, а потому произведение bd должно быть равно c. Умножение справа на f даёт нам b = cf, что можно преобразовать в cb = f умножением на c слева. Рассуждая аналогично, можно вывести, что c = fb и dc = b. Вносим изменения в таблицу (внесённые элементы выделены зелёным цветом):

e a b c d f
e e a b c d f
a a e d f b c
b b f e d c a
c c d f e a b
d d c a b e
f f b c a e

В строке d отсутствует только f, так что d 2 = f. Таким же образом получаем, что f 2 = d. Мы заполнили всю таблицу и не пришли к противоречию. Таким образом, мы нашли группу порядка 6, соответствующую скелету. Просмотр таблицы показывает, что она не абелева. Фактически это наименьшая неабелева группа, диэдрическая группа D3:

* e a b c d f
e e a b c d f
a a e d f b c
b b f e d c a
c c d f e a b
d d c a b f e
f f b c a e d

Генерация матрицы перестановок Править

В стандартной форме таблицы Кэли порядок строк и столбцов совпадает. Другим способом упорядочения является расстановка столбцов таким образом, чтобы n-ый столбец соответствовал обратным элементам n-ой строки. В нашем примере для D3 нам необходимо только переставить два последних столбца, поскольку только f и d не являются обратными себе, зато являются обратными друг другу.

e a b c f=d −1 d=f −1
e e a b c f d
a a e d f c b
b b f e d a c
c c d f e b a
d d c a b e f
f f b c a d e

В нашем примере можно создать шесть перестановочных матриц (все элементы равны 1 или 0, по одной единице в каждой строке и каждом столбце). 6×6 матрица содержит единицу, если метка столбца совпадает с меткой строки, и нули во всех остальных полях, символ Кронекера для метки. (Заметим, что для строки e получим единичную матрицу.) Например, для a получим перестановочную матрицу.

e a b c f d
e 0 1 0 0 0 0
a 1 0 0 0 0 0
b 0 0 0 0 1 0
c 0 0 0 0 0 1
d 0 0 1 0 0 0
f 0 0 0 1 0 0

Это показывает, что любая группа порядка n является подгруппой группы перестановок Sn порядка n!.

Обобщения Править

Описанные выше свойства зависят от некоторых аксиом для групп. Естественно распространить таблицы Кэли на некоторые другие алгебраические структуры, такие как полугруппы, квазигруппы и магмы, но для них некоторые выше указанные свойства выполняться не будут.

См. также Править

  • Таблица умножения
  • Латинский квадрат

Ссылки Править

  • Cayley, Arthur. «On the theory of groups, as depending on the symbolic equation θn = 1», Philosophical Magazine, Vol. 7 (1854), pp. 40-47. Available on-line at Google Books as part of his collected works.
  • Cayley, Arthur. «On the Theory of Groups», American Journal of Mathematics, Vol. 11, No. 2 (Jan 1889), pp. 139—157. Available at JSTOR.
  • Проверить качество перевода с иностранного языка.
  • Исправить статью согласно стилистическим правилам Википедии.

После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.

Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры

Дата публикации: Октябрь 18, 2023, 10:56 am
Самые читаемые

Открытый чемпионат Катара по теннису среди женщин 2024

Отечественная война 1812 г.

Орос, Чаба

Ок-Крик

Нюлль, Эдуард ван дер

Новгород-на-Волхове

Новотны, Йенс

Новоандреевка (Амурская область)

Николаев, Дмитрий Александрович (режиссёр)

Надежин, Иван Павлович

© Copyright 2021, Все права защищены.

Tablica Keli kvadratnaya tablica opisyvayushaya strukturu konechnoj algebraicheskoj sistemy i sostoyashaya iz rezultatov primeneniya binarnoj operacii k eyo elementam Nazvana v chest anglijskogo matematika Artura Keli ispolzovavshego eyo v teorii grupp Imeet vazhnoe znachenie v diskretnoj matematike Naprimer tablica Keli dlya standartnoj operacii umnozheniya displaystyle times na mnozhestve 1 1 displaystyle 1 1 imeet vid 1 11 1 1 1 1 1Takie tablicy pozvolyayut proyasnit nekotorye svojstva algebraicheskih sistem naprimer yavlyayutsya li oni kommutativnymi i imeyut li oni nejtralnyj element a esli imeyut pozvolyayut najti obratnye elementy k dannym V abstraktnoj algebre tablicy Keli ispolzuyutsya dlya opisaniya konechnyh grupp kolec polej i drugih algebraicheskih struktur Dlya beskonechnyh struktur i struktur s bolshim kolichestvom elementov ih ispolzovanie necelesoobrazno V etom sluchae struktury chashe vsego zadayut obrazuyushimi i sootnosheniyami Soderzhanie 1 Istoriya 2 Struktura 3 Svojstva i ispolzovanie 3 1 Kommutativnost 3 2 Associativnost 3 3 Perestanovki 4 Postroenie tablic Keli dlya grupp 4 1 Skelet nejtralnyh elementov konechnoj gruppy 4 2 Zapolnenie tablicy po skeletu nejtralnyh elementov 5 Generaciya matricy perestanovok 6 Obobsheniya 7 Sm takzhe 8 SsylkiIstoriya PravitTablicy Keli vpervye poyavilis v state Keli On The Theory of Groups as depending on the symbolic equation 8 n 1 v 1854 godu V etoj state eto byli prosto tablicy ispolzuemye v illyustrativnyh celyah Nazyvat tablicami Keli ih stali pozzhe v chest ih sozdatelya Struktura PravitPoskolku tablicy Keli ispolzuyutsya dlya operacij ne obyazatelno yavlyayushihsya kommutativnymi proizvedenie ab mozhet byt ne ravno proizvedeniyu ba Chtoby izbezhat putanicy prinimaetsya chto mnozhitel sootvetstvuyushij strokam idyot pervym a mnozhitel sootvetstvuyushij stolbcam vtorym Naprimer peresechenie stroki a i stolbca b eto ab a ne ba chto pokazano v sleduyushem primere a b ca a2 ab acb ba b2 bcc ca cb c2Keli v svoej rabote v pervoj stroke i pervom stolbce razmeshal nejtralnyj element chto pozvolyalo emu ne vydelyat otdelnyh stroki i stolbca s ukazaniem elementov kak eto vidno v primere vyshe Naprimer ta zhe samaya tablica predstavlyalas v vide a b cb c ac a bV etom primere ciklicheskoj gruppy Z3 element a yavlyaetsya nejtralnym elementom i on poyavlyaetsya v verhnem levom uglu tablicy Legko videt naprimer chto b2 c i chto cb a Vopreki etomu bolshinstvo sovremennyh tekstov v tom chisle i eta statya vklyuchayut zagolovochnye stroku i stolbec dlya bolshej yasnosti Svojstva i ispolzovanie PravitKommutativnost Pravit Tablica Keli pokazyvaet yavlyaetsya li operaciya kommutativnoj A imenno eto svojstvo ekvivalentno simmetrichnosti tablicy Keli otnositelno eyo diagonali Naprimer ciklicheskaya gruppa poryadka 3 vyshe a takzhe 1 1 po obychnomu umnozheniyu obe yavlyayutsya primerami abelevyh grupp i simmetriya ih tablic Keli dokazyvaet eto A vot naimenshaya neabeleva gruppa diedralnaya gruppa shestogo poryadka ne imeet simmetrii v tablice Keli Associativnost Pravit Poskolku associativnost v gruppah prisutstvuet po opredeleniyu chasto ona predpolagaetsya i v tablicah Keli Odnako tablicy Keli mozhno ispolzovat dlya opisaniya operacij v kvazigruppah v kotoryh associativnost ne trebuetsya bolee togo tablicy Keli mozhno ispolzovat dlya opisaniya operacii v lyuboj konechnoj magme V obshem sluchae nevozmozhno prostym obzorom tablicy opredelit associativna operaciya ili net v otlichie ot kommutativnosti Eto obuslovleno tem chto associativnost zavisit ot tryoh elementov v ravenstve a b c a b c displaystyle ab c a bc nbsp v to vremya kak tablica Keli pokazyvaet proizvedeniya dvuh elementov Tem ne menee test associativnosti Lajta mozhet opredelit associativnost s menshimi usiliyami chem grubyj perebor Perestanovki Pravit Poskolku sokrashenie en dlya grupp vypolnyaetsya bolee togo vypolnyaetsya dazhe dlya kvazigrupp nikakaya stroka ili stolbec tablicy Keli ne mozhet soderzhat odin element dvazhdy Takim obrazom kazhdaya stroka i stolbec tablicy yavlyaetsya perestanovkoj elementov gruppy Chtoby uvidet pochemu stroki i stolbcy ne mogut soderzhat odinakovyh elementov polozhim a x i y elementy gruppy pri etom x i y razlichny Teper v stroke sootvetstvuyushej elementu a i stolbce sootvetstvuyushem elementu x budet nahoditsya proizvedenie ax Analogichno v stolbce sootvetstvuyushem y budet nahoditsya ay Pust dva proizvedeniya ravny to est stroka a soderzhit element dvazhdy Po pravilu sokrasheniya my iz ax ay mozhem zaklyuchit chto x y chto protivorechit vyboru x i y Tochno te zhe rassuzhdeniya verny i dlya stolbcov Vvidu konechnosti gruppy po principu Dirihle kazhdyj element gruppy budet predstavlen v tochnosti po odnomu razu v kazhdoj stroke i v kazhdom stolbce To est tablica Keli dlya gruppy yavlyaetsya primerom latinskogo kvadrata Postroenie tablic Keli dlya grupp PravitIspolzuya strukturu grupp chasto mozhno zapolnit tablicy Keli kotorye imeyut nezapolnennye polya dazhe ne znaya nichego ob operacii gruppy Naprimer poskolku kazhdaya stroka i kazhdyj stolbec dolzhny soderzhat vse elementy gruppy odin otsutstvuyushij element v stroke ili stolbce mozhno zapolnit sovershenno ne znaya nichego o gruppe Eto pokazyvaet chto eto svojstvo i nekotorye drugie svojstva grupp dayut vozmozhnost postroeniya tablic Keli dazhe esli my malo chto znaem o gruppe Skelet nejtralnyh elementov konechnoj gruppy Pravit Poskolku v lyuboj gruppe dazhe ne v abelevoj lyuboj element perestanovochen so svoim obratnym raspredelenie nejtralnyh elementov v tablice Keli simmetrichno otnositelno diagonali Nejtralnye elementy lezhashie na diagonali sootvetstvuyut elementam sovpadayushim so svoimi obratnymi Poskolku poryadok strok i stolbcov v tablice Keli proizvolny udobno raspolozhit ih v sleduyushem poryadke nachinaem s nejtralnogo elementa gruppy kotoryj vsegda sovpadaet so svoim obratnym zatem perechislyaem vse elementy kotorye sovpadayut so svoimi obratnymi a zatem vypisyvaem pary elementov element i obratnyj k nemu Teper dlya konechnoj gruppy nekotorogo poryadka legko opredelit skelet nejtralnyh elementov nazvannyj tak po toj prichine chto nejtralnye elementy libo lezhat na glavnoj diagonali libo ryadom s nej Gruppy s razlichnymi skeletami ne mogut byt izomorfny odnako obratnoe neverno naprimer ciklicheskaya gruppa C8 i gruppa kvaternionov Q ne izomorfny hotya i imeyut odinakovye skelety Pust imeetsya shest elementov gruppy e a b c d i f Pust e nejtralnyj element Poskolku nejtralnyj element sovpadaet so svoim obratnym a obratnyj element edinstvennen dolzhen byt po krajnej mere eshyo odin element sovpadayushij so svoim obratnym Takim obrazom poluchaem sleduyushie vozmozhnye skelety vse elementy sovpadayut so svoimi obratnymi vse elementy za isklyucheniem d i f sovpadayut so svoimi obratnymi a eti dva obratny drug drugu a sovpadaet so svoim obratnym b i c obratny d i f obratny V nashem sluchae ne sushestvuet gruppy pervogo tipa poryadka 6 Bolee togo iz togo chto skelet vozmozhen sovsem ne sleduet chto sushestvuet gruppa u kotoroj skelet sovpadaet s nim Lyubaya gruppa v kotoroj lyuboj element sovpadaet s ego obratnym abeleva Zapolnenie tablicy po skeletu nejtralnyh elementov Pravit Esli zadan skelet nejtralnyh elementov mozhno pristupit k zapolneniyu tablicy Keli Naprimer vyberem vtoroj skelet gruppy poryadka 6 iz opisannyh vyshe e a b c d fe ea eb ec ed ef eOchevidno chto stroka e i stolbec e mogut byt zapolneny nemedlenno Kak tolko eto sdelano mozhet okazatsya neobhodimym i eto neobhodimo v nashem sluchae sdelat predpolozhenie kotoroe vposledstvii mozhet privesti k protivorechiyu chto budet oznachat chto predpolozhenie neverno My predpolozhim chto ab c Togda e a b c d fe e a b c d fa a e cb b ec c ed d ef f eUmnozhaya ab c sleva na a poluchim b ac Umnozhenie sprava na c dayot bc a Umnozhenie ab c sprava na b dayot a cb Umnozhenie bc a sleva na b dayot c ba a umnozhenie sprava na a dayot ca b Posle zapolneniya etih proizvedenij v tablice my obnaruzhim chto ad i af ostayutsya nezapolnennymi v stroke a Poskolku kazhdyj element dolzhen poyavitsya v stroke rovno odin raz poluchim chto ad dolzhen byt libo d libo f Odnako etot element ne mozhet ravnyatsya d poskolku v protivnom sluchae a byl by raven e v to vremya kak my znaem chto eti dva elementa razlichny Takim obrazom ad f i af d Teper poskolku obratnyj elementu d est f umnozhenie ad f sprava na f dayot a f2 Umnozhenie sleva na d dayot da f Umnozhiv sprava na a my poluchim d fa Posle vneseniya vseh etih proizvedenij tablica Keli primet vid e a b c d fe e a b c d fa a e c b f db b c e ac c b a ed d f ef f d e aPoskolku kazhdyj element gruppy dolzhen poyavitsya v kazhdoj stroke rovno odin raz dve pustye yachejki tablicy v stroke b dolzhny byt zanyaty libo d libo f Odnako v sootvetstvuyushih stolbcah uzhe prisutstvuyut d i f Takim obrazom chto by my ni postavili v eti polya poluchim povtorenie v stolbcah chto pokazyvaet chto nachalnoe predpolozhenie ab c bylo nevernym Odnako my teper znaem chto ab c Ostalos dve vozmozhnosti libo ab d libo ab f Poskolku d and f vzaimno obratny i vybor bukv proizvolen rezultat budet odinakovym s tochnostyu do izomorfizma Bez poteri obshnosti mozhno schitat chto ab d Esli my teper poluchim protivorechie nam pridyotsya priznat chto dlya etogo skeleta net sootvetstvuyushej gruppy Poluchaem novuyu tablicu Keli e a b c d fe e a b c d fa a e db b ec c ed d ef f eUmnozhaya ab d sleva na a my poluchaem b ad Umnozhenie sprava na f dayot bf a a umnozhenie sleva na b dayot f ba Umnozhiv sprava na a my poluchim fa b a umnozhiv sleva na d poluchim a db Vnesya rezultaty v tablicu Keli poluchim novye elementy vydeleny krasnym e a b c d fe e a b c d fa a e d bb b f e ac c ed d a ef f b eV stroke a otsutstvuyut c i f no poskolku af ne mozhet ravnyatsya f inache a budet raven e my mozhem zaklyuchit chto af c Umnozhenie sleva na a dayot f ac i eto my mozhem umnozhit sprava na c chto dayot fc a Umnozhenie poslednego na d sleva dayot c da chto my mozhem umnozhit sprava na a i poluchit ca d Takim zhe obrazom umnozhaya af c sprava na d poluchim a cd Obnovim tablicu poslednie izmeneniya vydeleny sinim e a b c d fe e a b c d fa a e d f b cb b f e ac c d e ad d c a ef f b a ePoskolku v stroke b otsutstvuyut c i d a bc ne mozhet ravnyatsya c my vyvodim chto bc d a potomu proizvedenie bd dolzhno byt ravno c Umnozhenie sprava na f dayot nam b cf chto mozhno preobrazovat v cb f umnozheniem na c sleva Rassuzhdaya analogichno mozhno vyvesti chto c fb i dc b Vnosim izmeneniya v tablicu vnesyonnye elementy vydeleny zelyonym cvetom e a b c d fe e a b c d fa a e d f b cb b f e d c ac c d f e a bd d c a b ef f b c a eV stroke d otsutstvuet tolko f tak chto d2 f Takim zhe obrazom poluchaem chto f2 d My zapolnili vsyu tablicu i ne prishli k protivorechiyu Takim obrazom my nashli gruppu poryadka 6 sootvetstvuyushuyu skeletu Prosmotr tablicy pokazyvaet chto ona ne abeleva Fakticheski eto naimenshaya neabeleva gruppa diedricheskaya gruppa D3 e a b c d fe e a b c d fa a e d f b cb b f e d c ac c d f e a bd d c a b f ef f b c a e dGeneraciya matricy perestanovok PravitV standartnoj forme tablicy Keli poryadok strok i stolbcov sovpadaet Drugim sposobom uporyadocheniya yavlyaetsya rasstanovka stolbcov takim obrazom chtoby n yj stolbec sootvetstvoval obratnym elementam n oj stroki V nashem primere dlya D3 nam neobhodimo tolko perestavit dva poslednih stolbca poskolku tolko f i d ne yavlyayutsya obratnymi sebe zato yavlyayutsya obratnymi drug drugu e a b c f d 1 d f 1e e a b c f da a e d f c bb b f e d a cc c d f e b ad d c a b e ff f b c a d eV nashem primere mozhno sozdat shest perestanovochnyh matric vse elementy ravny 1 ili 0 po odnoj edinice v kazhdoj stroke i kazhdom stolbce 6×6 matrica soderzhit edinicu esli metka stolbca sovpadaet s metkoj stroki i nuli vo vseh ostalnyh polyah simvol Kronekera dlya metki Zametim chto dlya stroki e poluchim edinichnuyu matricu Naprimer dlya a poluchim perestanovochnuyu matricu e a b c f de 0 1 0 0 0 0a 1 0 0 0 0 0b 0 0 0 0 1 0c 0 0 0 0 0 1d 0 0 1 0 0 0f 0 0 0 1 0 0Eto pokazyvaet chto lyubaya gruppa poryadka n yavlyaetsya podgruppoj gruppy perestanovok Sn poryadka n Obobsheniya PravitOpisannye vyshe svojstva zavisyat ot nekotoryh aksiom dlya grupp Estestvenno rasprostranit tablicy Keli na nekotorye drugie algebraicheskie struktury takie kak polugruppy kvazigruppy i magmy no dlya nih nekotorye vyshe ukazannye svojstva vypolnyatsya ne budut Sm takzhe PravitTablica umnozheniya Latinskij kvadratSsylki PravitCayley Arthur On the theory of groups as depending on the symbolic equation 8 n 1 Philosophical Magazine Vol 7 1854 pp 40 47 Available on line at Google Books as part of his collected works Cayley Arthur On the Theory of Groups American Journal of Mathematics Vol 11 No 2 Jan 1889 pp 139 157 Available at JSTOR Dlya uluchsheniya etoj stati zhelatelno Proverit kachestvo perevoda s inostrannogo yazyka Ispravit statyu soglasno stilisticheskim pravilam Vikipedii Posle ispravleniya problemy isklyuchite eyo iz spiska Udalite shablon esli ustraneny vse nedostatki Istochnik https ru wikipedia org w index php title Tablica Keli amp oldid 128370026

Таблица Кэли

Назван в честь 19 века британцев математик Артур Кэли, таблица Кэли описывает структуру конечной группы, упорядочивая все возможные произведения всех групп элементы в квадратной таблице, напоминающие сложение или таблицу умножения. Многие свойства группы — например, является ли она абелевой, какие элементы инвертируют какие элементы, а также размер и содержимое center группы — можно узнать из его таблицы Кэли.

Простым примером таблицы Кэли является таблица для группы при обычном умножении :

Таблицы Кэли были первыми представленный в статье Кэли 1854 года «О теории групп, как зависящей от символического уравнения θ = 1». В этой статье они назывались просто таблицами и были просто иллюстративными — позже они стали известны как таблицы Кэли в честь своего создателя.

Структура и макет

Поскольку многие таблицы Кэли описывают группы, которые не являются абелевыми, произведение ab относительно бинарной операции группы не является гарантированно равняется произведению ba для всех a и b в группе. Во избежание путаницы принято, что фактор, маркирующий строку (названный Кэли более близким фактором), идет первым, а фактор, маркирующий столбец (или дополнительный фактор), является вторым. Например, строка a и столбец b пересекаются ab, а не ba, как в следующем примере:

* a b c
a a ab ac
b ba b bc
c ca cb c

Кейли изначально настроил свои таблицы так, чтобы элемент идентификации был первым, что позволило избежать необходимость в отдельных заголовках строк и столбцов, показанных в примере выше. Например, они не отображаются в следующей таблице:

В этом примере циклическая группа Z3, a является элементом идентичности и, таким образом, отображается в верхнем левом углу таблицы. Например, легко увидеть, что b = c и cb = a. Несмотря на это, большинство современных текстов — и эта статья — включают заголовки строк и столбцов для большей ясности.

Свойства и использование

Коммутативность

Таблица Кэли сообщает нам, является ли группа абелевой. Поскольку групповая операция абелевой группы коммутативна, группа является абелевой тогда и только тогда, когда значения ее таблицы Кэли симметричны вдоль ее диагональной оси. Циклическая группа порядка 3, приведенная выше, и при обычном умножении, также указанное выше, являются примерами абелевых групп, и проверка симметрии их таблиц Кэли подтверждает это. Напротив, самая маленькая неабелева группа, диэдральная группа порядка 6, не имеет симметричной таблицы Кэли.

Ассоциативность

Поскольку ассоциативность принимается как аксиома при работе с группами, при работе с таблицами Кэли ее часто принимают как должное. Однако таблицы Кэли могут также использоваться для характеристики работы квазигруппы , которая не принимает ассоциативность в качестве аксиомы (действительно, таблицы Кэли могут использоваться для характеристики работы любой конечной магмы ). К сожалению, обычно невозможно определить, является ли операция ассоциативной, просто взглянув на ее таблицу Кэли, как это происходит с коммутативностью. Это связано с тем, что ассоциативность зависит от трехчленного уравнения, (ab) c = a (bc) , в то время как таблица Кэли показывает 2- срочные продукты. Однако тест ассоциативности Light может определить ассоциативность с меньшими усилиями, чем грубая сила.

Перестановки

Поскольку свойство отмены выполняется для групп (и даже квазигрупп), ни одна строка или столбец таблицы Кэли не может содержать один и тот же элемент дважды. Таким образом, каждая строка и столбец таблицы представляет собой перестановку всех элементов в группе. Это сильно ограничивает, какие таблицы Кэли могли предположительно определять допустимую групповую операцию.

Чтобы понять, почему строка или столбец не может содержать один и тот же элемент более одного раза, пусть a, x и y все являются элементами группы, причем x и y различны. Затем в строке, представляющей элемент a, столбец, соответствующий x, содержит произведение ax, и аналогично столбец, соответствующий y, содержит произведение ay. Если бы эти два продукта были равны — то есть строка a содержала один и тот же элемент дважды, наша гипотеза, — тогда ax было бы равно ay. Но поскольку закон сокращения выполняется, мы можем заключить, что если ax = ay, то x = y, противоречие. Следовательно, наша гипотеза неверна, и строка не может содержать один и тот же элемент дважды. Точно такого же аргумента достаточно, чтобы доказать случай столбца, и поэтому мы заключаем, что каждая строка и столбец не содержат элементов более одного раза. Поскольку группа является конечной, принцип «голубятни» гарантирует, что каждый элемент группы будет представлен в каждой строке и в каждом столбце ровно один раз.

Таким образом, таблица Кэли группы является примером латинского квадрата.

Другое, возможно, более простое доказательство: свойство отмены подразумевает, что для каждого x в группе, функция одной переменной yf (x, y) = xy должна быть отображением один к одному. И взаимно однозначные отображения s на конечных множествах являются перестановками.

Построение таблиц Кэли

Из-за структуры групп очень часто можно «заполнить» таблицы Кэли, в которых отсутствуют элементы, даже не имея полной характеристики рассматриваемой групповой операции. Например, поскольку каждая строка и столбец должны содержать каждый элемент в группе, если все элементы учтены, за исключением одного, и есть одно пустое место, ничего не зная о группе, можно сделать вывод, что неучтенный элемент должен занимают оставшееся пустое место. Оказывается, что это и другие наблюдения о группах в целом позволяют нам построить таблицы Кэли для групп, очень мало зная об этой группе.

«Каркас идентичности» конечной группы

Поскольку в любой группе, даже в неабелевой группе, каждый элемент коммутирует со своим собственным обратным, отсюда следует, что распределение единичных элементов на стол Кэли будет симметричным по диагонали стола. Те, что лежат на диагонали, сами по себе уникальны.

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

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

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

Рассмотрим группу из шести элементов с элементами e, a, b, c, d и f. По соглашению, e является элементом идентичности группы. Поскольку элемент идентичности всегда является своим собственным обратным, а обратные элементы уникальны, тот факт, что в этой группе 6 элементов, означает, что по крайней мере один элемент, отличный от e, должен быть его собственным обратным. Итак, у нас есть следующие возможные скелеты:

  • все элементы являются их собственными инверсиями,
  • все элементы, кроме d и f, являются их собственными инверсиями, каждый из последних двух является инверсией другого,
  • a является обратным к самому себе, b и c — обратными, а d и f — обратными.

В нашем конкретном примере не существует группы первого типа порядка 6; действительно, просто потому, что конкретный каркас идентичности мыслим, в целом не означает, что существует группа, которая ему подходит.

Любая группа, в которой каждый элемент является своим собственным обратным, является абелевой: пусть a и b элементы группы, тогда ab = (ab) = ba = ba.

Заполнение скелета идентичности

После того, как определен конкретный скелет идентичности, можно начинать заполнение таблицы Кэли. Например, возьмем каркас идентичности группы порядка 6 второго типа, описанный выше:

e a b c d f
e e
a e
b e
c e
d e
f e

Очевидно, что строка e и столбец e могут быть заполнены немедленно. Как только это будет сделано, может потребоваться (а в нашем случае это необходимо) сделать предположение, которое впоследствии может привести к противоречию — то есть просто то, что наше первоначальное предположение было ложным. Будем считать, что ab = c. Тогда:

e a b c d f
e e a b c d f
a a e c
b b e
c c e
d d e
f f e

Умножение ab = c слева на a дает b = ac. Умножение справа на c дает bc = a. Умножение ab = c справа на b дает a = cb. Умножение bc = a слева на b дает c = ba, а умножение справа на a дает ca = b. После заполнения этих продуктов в таблице мы обнаруживаем, что ad и af все еще не учтены в строке a; поскольку мы знаем, что каждый элемент группы должен появляться в каждой строке ровно один раз, и что только d и f не учитываются, мы знаем, что ad должно быть равно d или f; но он не может равняться d, потому что, если бы это было так, это означало бы, что a равно e, если мы знаем, что они различны. Таким образом, мы имеем ad = f и af = d.

Кроме того, поскольку d равно f, умножение ad = f справа на f дает a = f. Умножив это слева на d, мы получим da = f. Умножив это справа на a, получим d = fa.

Заполняя все эти продукты, таблица Кэли теперь выглядит следующим образом:

e a b c d f
e e a b c d f
a a e c b f d
b b c e a
c c b a e
d d f e
f f d e a

Поскольку каждая строка должна иметь каждый элемент группы, представленный ровно один раз, легко увидеть, что два пустых места в b строка должна быть занята d или f. Однако, если исследовать столбцы, содержащие эти два пустых места — столбцы d и f, — можно обнаружить, что d и f уже были заполнены в обоих, что означает, что независимо от того, как d и f размещены в строке b, они будут всегда нарушают правило перестановки. Поскольку наши алгебраические выводы до этого момента были правильными, мы можем только заключить, что наше прежнее безосновательное предположение о том, что ab = c, было на самом деле ложным. По сути, мы угадали и угадали неправильно. Однако мы кое-что узнали: ab ≠ c.

Тогда остаются только две возможности: ab = d или ab = f; мы ожидаем, что каждое из этих двух предположений будет иметь одинаковый результат, с точностью до изоморфизма, потому что d и f являются обратными друг другу, и буквы, которые их представляют, в любом случае по своей сути произвольны. Поэтому без ограничения общности возьмем ab = d. Если мы приходим к другому противоречию, мы должны предположить, что ни одна группа порядка 6 не имеет идентичного скелета, с которым мы начали, поскольку мы исчерпали все возможности.

Вот новая таблица Кэли:

e a b c d f
e e a b c d f
a a e d
b b e
c c e
d d e
f f e

Умножая ab = d слева на a, мы получаем b = ad. Умножение справа на f дает bf = a, а умножение слева на b дает f = ba. Умножая справа на a, получаем fa = b, а умножение слева на d дает a = db. Заполняя таблицу Кэли, мы теперь имеем (новые добавления красного цвета):

e a b c d f
e e a b c d f
a a e d b
b b f e a
c c e
d d a e
f f b e

Поскольку в строке a отсутствуют c и f и поскольку af не может быть равно f (или a будет равно e, если мы знаем, что они различны), можно заключить, что af = c. Умножение слева на a дает f = ac, которое мы можем умножить справа на c, чтобы получить fc = a. Умножение этого слева на d дает нам c = da, которое мы можем умножить справа на a, чтобы получить ca = d. Точно так же умножение af = c справа на d дает нам a = cd. Обновляя таблицу, мы получаем следующее, с самыми последними изменениями синего цвета:

e a b c d f
e e a b c d f
a a e d f b c
b b f e a
c c d e a
d d c a e
f f b a e

Поскольку в строке b отсутствуют c и d, и поскольку bc не может быть равно c, отсюда следует, что bc = d, и поэтому bd должно быть равно c. Умножение справа на f дает нам b = cf, которое мы можем в дальнейшем преобразовать в cb = f, умножив на c слева. По аналогичной логике мы можем вывести, что c = fb и что dc = b. Заполнив их, мы получим (с последними добавлениями зеленым цветом):

e a b c d f
e e a b c d f
a a e d f b c
b b f e d c a
c c d f e a b
d d c a b e
f f b c a e

Поскольку в строке d отсутствует только f, мы знаем, что d = f, и, следовательно, f = d. Поскольку нам удалось заполнить всю таблицу, не получив противоречия, мы нашли группу порядка 6: проверка показывает, что она неабелева. Фактически эта группа является наименьшей неабелевой группой, группой диэдра D3:

* e a b c d f
e e a b c d f
a a e d f b c
b b f e d c a
c c d f e a b
d d c a b f e
f f b c a e d

Генерация матрицы перестановок

В стандартной форме таблицы Кэли порядок элементов в строках такой же, как и в порядок в столбцах. Другая форма состоит в том, чтобы расположить элементы столбцов так, чтобы n-й столбец соответствовал обратному элементу в n-й строке. В нашем примере D 3 нам нужно только переключить последние два столбца, поскольку f и d — единственные элементы, которые не являются своими собственными инверсиями, а вместо этого инвертируют друг друга.

e a b c f = d d = f
e e a b c f d
a a e d f c b
b b f e d a c
c c d f e b a
d d c a b e f
f f b c a d e

Этот конкретный пример позволяет нам создать шесть матриц перестановок (все элементы 1 или 0, ровно одна 1 в каждой строке и столбце). Матрица 6×6, представляющая элемент, будет иметь 1 в каждой позиции, которая имеет букву элемента в таблице Кэли, и ноль в каждой другой позиции, функция дельта Кронекера для этого символа. (Обратите внимание, что e находится в каждой позиции по главной диагонали, что дает нам единичную матрицу для матриц 6×6 в этом случае, как и следовало ожидать.) Вот матрица, которая представляет наш элемент a, например.

e a b c f d
e 0 1 0 0 0 0
a 1 0 0 0 0 0
b 0 0 0 0 1 0
c 0 0 0 0 0 1
d 0 0 1 0 0 0
f 0 0 0 1 0 0

Это показывает нам напрямую, что любая группа порядка n является подгруппой группы перестановок Snпорядка n !.

Вышеуказанные свойства зависят от некоторых аксиом, действующих для групп. Естественно рассматривать таблицы Кэли для других алгебраических структур, например, для полугрупп, квазигрупп и магм, но некоторые из приведенных выше свойств не выполняются.

  • Кэли, Артур. «К теории групп в зависимости от символического уравнения θ = 1», Philosophical Magazine, Vol. 7 (1854), стр. 40–47. Доступно в Интернете в Google Книгах как часть его собрания сочинений.
  • Кэли, Артур. «К теории групп», American Journal of Mathematics, Vol. 11, No. 2 (январь 1889 г.), стр. 139–157. Доступно в JSTOR.

19.2. Таблица Кэли для операции

Бинарная операция это, по определению, отображение множества A ╢ A в множество A, при этом образ пары (x, y) обозначим, например, x  y, где  символ операции. Здесь A — произвольное непустое множество и A╢ A — множество всех упорядоченных пар (x, y) — таких, что x, y  A (то есть, декартов квадрат множества A). Непустое множество A называется основным множеством операции.

Можно составить следующую иерархию множеств с бинарной операцией (разумеется, вместо  может быть вставлена любая — +, √, *,  ,  ,  ,  ,  ,  и т.д. и т.п. — в зависимости от необходимости и вкуса автора.

Группоид , обозначаемый символом (A,  ) — множество A, на котором задана некоторая бинарная операция, обозначаемая  . Если множество группоида конечно, то есть ╫A╫ = card (A) = n, то таблица Кэли операции группоида есть таблица n ╢ n, в которой элемент x  y  A находится в клетке пересечения строки x и столбца y. Конечный группоид можно считать заданным, если выписана его таблица Кэли.

Задача об авторитетах

У Саши и Даши авторитет Даша.

У Саши и Маши авторитет Саша.

У Саши авторитет Саша.

У Даши и Маши авторитет Саша.

У Даши авторитет Даша.

У Маши авторитет Петя.

У Пети и Даши авторитет Петя.

У Пети и Маши авторитет Петя.

У Пети и Саши авторитет Саша.

У Пети авторитет Саша.

ТАБЛИЦА КЭЛИ ДЛЯ ОПЕРАЦИИ «АВТОРИТЕТ»

* Затенен операционный квадрат

ТАБЛИЦА КЭЛИ, КОРЕЙСКИЙ ВАРИАНТ

Квазигруппа (от латинского слова quasi — как будто, почти и слова группа) — группоид, бинарная операция которого (например,  ) такова, что каждое из уравнений a  x = b, y  a = b имеет единственное решение для любых элементов a, b этого множества. Квазигруппа — одно из обобщений понятия группа. Особенно близки к группам квазигруппы с единицей — лупы, определение которых получается из аксиом групп отбрасыванием требования ассоциативности. Квазигруппу можно рассматривать и как унивесальную алгебру с тремя бинарными операциями (дополнительно левое и правле деление).

Гомоморфный образ квазигруппы, вообще говоря, не квазигруппа, а группоид с делением. Гомоморфизмам квазигруппы на квазигруппе соответствуют конгруэнции специального типа (т.н. нормальные конгруэнции). Значительно большую роль, чем гомоморфизмы, в теории и классификации групп играют изотопии. Изотопия — отношение эквивалентности для бинарных операций на фиксированном множестве, определяемое с помощью трех подстановок этого множества. Оказывается, что всякий группоид, изотопный квазигруппе, — сам квазигруппа, а всякая квазигруппа изотопна некоторой лупе. Для групп понятие изотопии совпадает с понятием изоморфизма.

Таблица умножения конечной квазигруппы (ее таблица Кэли) в комбинаторике известна по названием латинский квадрат. Одна из задач комбинаторной теории квазигрупп — отыскание систем взаимно ортогональных квазигрупп на заданном множестве — важна для построения конечных проективных плоскостей.

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

Полугруппа — множество, с определенной на нем бинарной операцией, удовлетворяющей закону ассоциативности, т.е. группоид ( A ,  ), в котором для каждой тройки элементов a , b и с выполняется условие a ( b  с) =(a  b)  с). Понятие полугруппы есть обобщение понятия группы: из аксиом группы остается лишь одна; этим объясняется и термин «полугруппа».

Теория полугрупп принадлежит к числу сравнительно молодых областей алгебры. Первые исследования, посвященные полугруппам, относятся к 20-м гг. 20 в. и связаны с именем А. К. Сушкевича. Он, в частности, определил строение конечной полугруппы без собственных идеалов. К концу 50-х гг. теория полугрупп сформировалась в самостоятельную ветвь современной алгебры с богатой проблематикой, разнообразными методами и тесными связями с многими областями математики — как собственно алгебраическими (в первую очередь, с теорией групп и теорией колец), так и другими, например, с функциональным анализом, дифференциальной геометрией, алгебраической теорией автоматов.

  • Примеры полугрупп чрезвычайно многочисленны. Это, например:
  • различные множества чисел вместе с операцией сложения или умножения, замкнутые относительно рассматриваемой операции (т.е. содержащие вместе с любыми двумя своими элементами их сумму или, соответственно, произведение);
  • Полугруппа матриц относительно умножения;
  • Полугруппа функций относительно «поточечного» умножения  , задаваемого формулой (f g) (x) = f(x) g(x);
  • Полугруппа матриц относительно операции пересечения или объединения;
  • Один из простейших примеров полугруппы — множество всех натуральных чисел относительно сложения; эта полугруппа является частью (подполугруппой) группы целых чисел по сложению или, как говорят, вложима в группу целых чисел.

Далеко не всякая полугруппа вложима в какую-нибудь группу: необходимыи условием такой вложимости является закон сокращения — каждое из равенств ac = bc, ca = cb влечет за собой a = b; выполнение закона сокращения не достаточно для такой вложимости, но, например, коммутативная полугруппа с законом сокращения вложима в группу.

  • Если на множестве FX всех конечных последовательностей элементов произвольного множества (алфавита) X задать операцию  формулой

то FX станет полугруппой; она называется свободной полугруппой над алфавитом X. Роль свободных полугрупп в общей теории определяется тем, что всякая полугруппа есть гомоморфный образ подходящей свободной полугруппы. Важную роль играют свободные полугруппы и в некоторых приложениях, прежде всего в теории формальных языков и кодов.

  • Всякая совокупность пребразований произвольного множества M, замкнутая относительно операции композиции (последовательного выполнения), будет полугруппой относительно этой операции; такова, в частности, совокупность всех преобразований множества M, называемая симметрической полугруппой на множестве M. Многие важные совокупности преобразований оказываются полугруппами относительно композиции, причем часто они не являются группами. С другой стороны, всякая полугруппа изоморфна некоторой полугруппе преобразований. Все это определяет как роль полугрупп преобразований в общей теории полугрупп, так и роль теории полугрупп для изучения в самом общем виде преобразований с точки зрения их композиции. В большой степени через рассмотрение преобразований осуществляются связи теории полугрупп с другими областями математики.

Как и в других алгебраических теориях, одной из главных задач теории полугрупп является классификация всевозможных полугрупп, описание их строения. Это осуществляется прежде всего наложением на рассматриваемые полугруппы различых ограничений и выделение тем самым различных типов полугрупп. Среди важных типов — регулярные полугруппы, то есть полугруппы, в которых для любого элемента a существует такой элемент x, что axa = a. Регулярными являются, например, полугруппа всех матриц данного порядка над телом, симметрические полугруппы, полугруппы всех частичных преобразований множеств. Регулярные полугруппы принадлежат к числу наиболее активно изучаемых в теории полугрупп.

Заметную часть общей теории составляет теория представлений полугрупп преобразованиями и матрицами. Точка зрения теории представлений нередко проливает дополнительный свет на некоторые типы полугрупп, естественно определяемые с точки зрения аксиоматики. Внесение в полугруппы дополнительных структур, согласованных с полугрупповой операцией, выделяет особые разделы теории полугрупп, такие, как теория топологических полугрупп, теория упорядоченных полугрупп.

Моноид — это, по определению, полугруппа с единицей.

Группа (нем. Gruppe ) — одно из основных понятий современной математики — есть лупа, являющаяся в то же время полугруппой.

Теория групп изучает в самой общей форме операции, наиболее часто встречающиеся в математике и ее приложениях (примеры таких операций — сложение чисел, умножение чисел, сложение векторов, последовательное выполнение преобразований и т.п.). При этом теория групп изучает не совсем произвольные операции, а лишь те, которые обладают рядом основных войств, перечисляемых в определении группы.

Формальное определение группы таково. Пусть G — произвольное непустое множество, на котором задана бинарная алгебраическая операция  , т.е. для любых двух элементов a, b, из G определен некоторый элемент (обозначаемый, например, ab) также из G. Если при этом выполняются условия: 1) (ab)  c = a (bc) для любых a, b и c из G; 2) в G существует такой элемент e (называемый единицей, иногда — нейтральным элементом), что ae = ea = a для любого a из G; 3) для любого a из G существует такой элемент a √1 (обратный к a элемент), что a  a √1 = a √1  a = e, то множество G с заданной на нем операцией  назовем группой.

Примеры групп. 1) множество G различных движений эвклидовой плоскости, самосовмещающих данную фигуру, операцией на котором служит композиция движений (если  ,  — два движения из G, то результатом их композиции назовем движение   , равносильное последовательному выполнению сначала движения  , а затем движения  ), образует т.н. группу симметрий фигуры. Единицей в этой группе будет тождественное преобразование плоскости, а обратным к  элементом — обратное к  преобразование. Группа G является характеристикой большей или меньшей симметричности фигуры: чем больше множество G, тем симметричнее фигура. Например, группа симметрий квадрата (рис., а) состоит из восьми движений

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

Если  — множество всех целых чисел, а операция на  — их обычное сложение  , то  — группа. Роль e будет играть число 0, а роль обратного к z элемента — число √z. Часть H множества  , состоящая из четных чисел, сама будет группой относительно той же операции. В таком случае говорят, что Hподгруппа группы  . Обе групы  и H удовлетворяют следующему дополнительному условию: 4) a + b = b + a для любых a и b из группы. Всякая группа, в которой выполняется условие 4) называется коммутативной или абелевой.

3) Множество всех подстановокn символов образует группу относительно умножения подстановок, называемую симметрической группой. При n  3 симметрическая группа неабелева. Порядок (число элементов) симметрической группы равен n!.

Как составить таблицу кэли

LiveJournal

Войти

Нет аккаунта? Зарегистрироваться

Авторизуясь в LiveJournal с помощью стороннего сервиса вы принимаете условия Пользовательского соглашения LiveJournal

16 мая 2009, 13:12

Таблица Кэли для операции

Бинарная операция это, по определению, отображение множества A ╢ A в множество A, при этом образ пары (x, y) обозначим, например, x © y, где © символ операции. Здесь A — произвольное непустое множество и A ╢ A — множество всех упорядоченных пар (x, y) — таких, что x, y Î A (то есть, декартов квадрат множества A). Непустое множество A называется основным множеством операции.

Можно составить следующую иерархию множеств с бинарной операцией (разумеется, вместо © может быть вставлена любая — +, √, *, È , Ç , Å , Ä , Ñ , ° и т.д. и т.п. — в зависимости от необходимости и вкуса автора.

Группоид, обозначаемый символом (A, © ) — множество A, на котором задана некоторая бинарная операция, обозначаемая © . Если множество группоида конечно, то есть ╫ A ╫ = card (A) = n, то таблица Кэли операции группоида есть таблица n ╢ n, в которой элемент x © y Î A находится в клетке пересечения строки x и столбца y. Конечный группоид можно считать заданным, если выписана его таблица Кэли.

Задача об авторитетах

У Саши и Даши авторитет Даша.

У Саши и Маши авторитет Саша.

У Саши авторитет Саша.

У Даши и Маши авторитет Саша.

У Даши авторитет Даша.

У Маши авторитет Петя.

У Пети и Даши авторитет Петя.

У Пети и Маши авторитет Петя.

У Пети и Саши авторитет Саша.

У Пети авторитет Саша.

ТАБЛИЦА КЭЛИ ДЛЯ ОПЕРАЦИИ «АВТОРИТЕТ»

* Затенен операционный квадрат

ТАБЛИЦА КЭЛИ, КОРЕЙСКИЙ ВАРИАНТ

Квазигруппа (от латинского слова quasi — как будто, почти и слова группа) — группоид, бинарная операция которого (например, © ) такова, что каждое из уравнений a © x = b, y © a = b имеет единственное решение для любых элементов a, b этого множества. Квазигруппа — одно из обобщений понятия группа. Особенно близки к группам квазигруппы с единицей — лупы, определение которых получается из аксиом групп отбрасыванием требования ассоциативности. Квазигруппу можно рассматривать и как унивесальную алгебру с тремя бинарными операциями (дополнительно левое и правле деление).

Гомоморфный образ квазигруппы, вообще говоря, не квазигруппа, а группоид с делением. Гомоморфизмам квазигруппы на квазигруппе соответствуют конгруэнции специального типа (т.н. нормальные конгруэнции). Значительно большую роль, чем гомоморфизмы, в теории и классификации групп играют изотопии. Изотопия — отношение эквивалентности для бинарных операций на фиксированном множестве, определяемое с помощью трех подстановок этого множества. Оказывается, что всякий группоид, изотопный квазигруппе, — сам квазигруппа, а всякая квазигруппа изотопна некоторой лупе. Для групп понятие изотопии совпадает с понятием изоморфизма.

Таблица умножения конечной квазигруппы (ее таблица Кэли) в комбинаторике известна по названием латинский квадрат. Одна из задач комбинаторной теории квазигрупп — отыскание систем взаимно ортогональных квазигрупп на заданном множестве — важна для построения конечных проективных плоскостей.

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

Полугруппа — множество, с определенной на нем бинарной операцией, удовлетворяющей закону ассоциативности, т.е. группоид (A, © ), в котором для каждой тройки элементов a , b и с выполняется условие a © ( b © с) =(a © b) © с). Понятие полугруппы есть обобщение понятия группы: из аксиом группы остается лишь одна; этим объясняется и термин «полугруппа».

Теория полугрупп принадлежит к числу сравнительно молодых областей алгебры. Первые исследования, посвященные полугруппам, относятся к 20-м гг. 20 в. и связаны с именем А. К. Сушкевича. Он, в частности, определил строение конечной полугруппы без собственных идеалов. К концу 50-х гг. теория полугрупп сформировалась в самостоятельную ветвь современной алгебры с богатой проблематикой, разнообразными методами и тесными связями с многими областями математики — как собственно алгебраическими (в первую очередь, с теорией групп и теорией колец), так и другими, например, с функциональным анализом, дифференциальной геометрией, алгебраической теорией автоматов.

  • Примеры полугрупп чрезвычайно многочисленны. Это, например:
  • различные множества чисел вместе с операцией сложения или умножения, замкнутые относительно рассматриваемой операции (т.е. содержащие вместе с любыми двумя своими элементами их сумму или, соответственно, произведение);
  • Полугруппа матриц относительно умножения;
  • Полугруппа функций относительно «поточечного» умножения * , задаваемого формулой (f* g) (x) = f(x) g(x);
  • Полугруппа матриц относительно операции пересечения или объединения;
  • Один из простейших примеров полугруппы — множество всех натуральных чисел относительно сложения; эта полугруппа является частью (подполугруппой) группы целых чисел по сложению или, как говорят, вложима в группу целых чисел.

Далеко не всякая полугруппа вложима в какую-нибудь группу: необходимыи условием такой вложимости является закон сокращения — каждое из равенств ac = bc, ca = cb влечет за собой a = b; выполнение закона сокращения не достаточно для такой вложимости, но, например, коммутативная полугруппа с законом сокращения вложима в группу.

  • Если на множестве FX всех конечных последовательностей элементов произвольного множества (алфавита) X задать операцию * формулой

то FX станет полугруппой; она называется свободной полугруппой над алфавитом X. Роль свободных полугрупп в общей теории определяется тем, что всякая полугруппа есть гомоморфный образ подходящей свободной полугруппы. Важную роль играют свободные полугруппы и в некоторых приложениях, прежде всего в теории формальных языков и кодов.

  • Всякая совокупность пребразований произвольного множества M, замкнутая относительно операции композиции (последовательного выполнения), будет полугруппой относительно этой операции; такова, в частности, совокупность всех преобразований множества M, называемая симметрической полугруппой на множестве M. Многие важные совокупности преобразований оказываются полугруппами относительно композиции, причем часто они не являются группами. С другой стороны, всякая полугруппа изоморфна некоторой полугруппе преобразований. Все это определяет как роль полугрупп преобразований в общей теории полугрупп, так и роль теории полугрупп для изучения в самом общем виде преобразований с точки зрения их композиции. В большой степени через рассмотрение преобразований осуществляются связи теории полугрупп с другими областями математики.

Как и в других алгебраических теориях, одной из главных задач теории полугрупп является классификация всевозможных полугрупп, описание их строения. Это осуществляется прежде всего наложением на рассматриваемые полугруппы различых ограничений и выделение тем самым различных типов полугрупп. Среди важных типов — регулярные полугруппы, то есть полугруппы, в которых для любого элемента a существует такой элемент x, что axa = a. Регулярными являются, например, полугруппа всех матриц данного порядка над телом, симметрические полугруппы, полугруппы всех частичных преобразований множеств. Регулярные полугруппы принадлежат к числу наиболее активно изучаемых в теории полугрупп.

Заметную часть общей теории составляет теория представлений полугрупп преобразованиями и матрицами. Точка зрения теории представлений нередко проливает дополнительный свет на некоторые типы полугрупп, естественно определяемые с точки зрения аксиоматики. Внесение в полугруппы дополнительных структур, согласованных с полугрупповой операцией, выделяет особые разделы теории полугрупп, такие, как теория топологических полугрупп, теория упорядоченных полугрупп.

Моноид — это, по определению, полугруппа с единицей.

Группа (нем. Gruppe) — одно из основных понятий современной математики — есть лупа, являющаяся в то же время полугруппой.

Теория групп изучает в самой общей форме операции, наиболее часто встречающиеся в математике и ее приложениях (примеры таких операций — сложение чисел, умножение чисел, сложение векторов, последовательное выполнение преобразований и т.п.). При этом теория групп изучает не совсем произвольные операции, а лишь те, которые обладают рядом основных войств, перечисляемых в определении группы.

Формальное определение группы таково. Пусть G — произвольное непустое множество, на котором задана бинарная алгебраическая операция ° , т.е. для любых двух элементов a, b, из G определен некоторый элемент (обозначаемый, например, a ° b) также из G. Если при этом выполняются условия: 1) (a ° b) ° c = a ° (b ° c) для любых a, b и c из G; 2) в G существует такой элемент e (называемый единицей, иногда — нейтральным элементом), что a ° e = e ° a = a для любого a из G; 3) для любого a из G существует такой элемент a √1 (обратный к a элемент), что a ° a √1 = a √1 ° a = e, то множество G с заданной на нем операцией ° назовем группой.

Примеры групп. 1) множество G различных движений эвклидовой плоскости, самосовмещающих данную фигуру, операцией на котором служит композиция движений (если j , y — два движения из G, то результатом их композиции назовем движение j ° y , равносильное последовательному выполнению сначала движения j , а затем движения y ), образует т.н. группу симметрий фигуры. Единицей в этой группе будет тождественное преобразование плоскости, а обратным к j элементом — обратное к j преобразование. Группа G является характеристикой большей или меньшей симметричности фигуры: чем больше множество G, тем симметричнее фигура. Например, группа симметрий квадрата (рис., а) состоит из восьми движений

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

Если Z — множество всех целых чисел, а операция на Z — их обычное сложение + , то Z — группа. Роль e будет играть число 0, а роль обратного к z элемента — число √z. Часть H множества Z , состоящая из четных чисел, сама будет группой относительно той же операции. В таком случае говорят, что Hподгруппа группы Z . Обе групы Z и H удовлетворяют следующему дополнительному условию: 4) a + b = b + a для любых a и b из группы. Всякая группа, в которой выполняется условие 4) называется коммутативной или абелевой.

3) Множество всех подстановокn символов образует группу относительно умножения подстановок, называемую симметрической группой. При n ¨ 3 симметрическая группа неабелева. Порядок (число элементов) симметрической группы равен n!.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *