Таблица кэли как строить

Источник

Таблица кэли как строить

Войти

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Дискретная математика (стр. 4 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5 6 7 8 9 10 11 12

Аналогично определяются и правые смежные классы, содержащие элементы вида h*g. Первым левым и первым правым смежными классами является сама подгруппа H. Среди смежных классов первый – единственная подгруппа, остальные классы – просто подмножества группы G.

Для получения второго левого смежного класса надо взять любой элемент g из группы G, не попавший в первый класс, и последовательно умножить его на все элементы подгруппы H (g*h). Результаты этого умножения образуют второй левый класс. Для получения третьего левого смежного класса надо взять любой элемент g из группы G, не попавший в первый и во второй классы, и последовательно умножить его на все элементы подгруппы H. Результаты этого умножения в свою очередь образуют третий левый класс. И так далее. В качестве последнего левого смежного класса берутся все оставшиеся (не попавшие в предыдущие классы) элементы G (умножать уже не надо).

Аналогично определяются и правые смежные классы. Множество левых классов образуют разбиение группы G, так же как и множество правых. У не коммутативной группы множество левых и правых классов могут и не совпасть. Если эти разбиения (правое и левое) совпадают, то подгруппа называется нормальным делителем. Например, рассмотрим разбиение симметрической группы степени три по подгруппе H = порядка два:

Здесь слева от элемента (с буквой l) показана его принадлежность к левому разбиению, а справа (с буквой r) – к правому. Для получения второго левого класса взят элемент g =, не попавший в первый класс, и умножен на элемент (1 2), так как на групповую единицу его можно не умножать. Результат умножения элементвместе с элементомобразуют второй левый класс.

Третий левый составили два элемента, не попавшие в первые два класса. Для получения второго правого класса взят тот же элемент g =, не попавший в первый класс, и элементумножен на него. Результат умножения элементвместе с элементомобразуют второй правый класс.

Так как левое разбиение не совпало с правым, то рассмотренная подгруппа H не является нормальным делителем. Любая подгруппа индекса два, порядок которой вдвое меньше порядка самой группы, является нормальным делителем. Первый смежный класс – это сама подгруппа, а второй – это те элементы, что не попали в первый класс. Значит, подгруппа H = – нормальный делитель симметрической группы степени три.

Для определения вида делителя – подгруппы можно воспользоваться следующим утверждением: H – нормальный делитель G если для каждого g и для каждого h существуют h` и h«, такие что, g*h = h`*g и h*g = g*h«. Отсюда у коммутативной группы все её подгруппы (если они есть) нормальные делители, так как здесь h = h` = h«.

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

Групп порядка 6 может быть только две: циклическая и симметрическая степени 3. Циклической подгруппы порядка 6 у этой группы порядка 12 нет, так как у неё нет элементов порядка 6. В симметрической подгруппе степени три имеются два элемента порядка три и три элемента порядка два. Возьмём в качестве примера подтаблицу таблицы Кэли для группы порядка двенадцать с элементами порядка три 2 и 3, которые являются квадратами друг друга, то есть вместе с 1 образуют подгруппу порядка три, и всеми тремя элементами порядка два: 10, 11 и 12:

Полученная подтаблица не является таблицей Кэли для подгруппы, так как в ней кроме элементов 1, 2, 3, 10, 11 и 12 присутствуют и другие элементы группы порядка двенадцать.

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

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

У второй группы порядка двенадцать элементы 2 и 6 имеют порядок шесть, элементы 4, 7, 8, 9, 10, 11 и 12 – порядок два, а элементы 3 и 5 имеют порядок три. Эта группа имеет похожее устройство, как и у не циклических групп порядков десять, восемь (с циклической подгруппой порядка четыре) и шесть. У них у всех есть циклическая подгруппа индекса два, а оставшиеся (не попавшие в подгруппу индекса два) элементы имеют порядок два.

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

Таблица 1 Таблица 2

Таблица 3 Таблица 4

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

В таблице Кэли 1 для симметрической группы степени три полностью заполнены только первая строка и первый столбец, потому что как работает единичный элемент в группе всегда понятно. Элементы 2 и 3 имеют порядок три, а остальные (4, 5 и 6) – порядок два. В таблице Кэли 1 заполнены подтаблицы для этих циклических подгрупп. Поскольку элемент 2 имеет порядок три, то вторая строка должна быть равноцикловым беспорядком из двух циклов порядка три. Элемент 2 – это квадрат элемента 3, и наоборот, элемент 3 – это квадрат элемента 2.

На трёх элементах 4, 5 и 6 можно сделать только два беспорядка: этоиВ таблице Кэли 2 для второй строки взят первый беспорядок, и сразу получаем для элемента 4, что 1 переходит в 4 и 4 – в 1, 2 переходит в 5 и, значит, 5 должен переходить в 2, 3 – в 6 и наоборот, 6 в 3, так как элемент 4 обратен сам себе и его столбец является равноцикловым беспорядком из трёх циклов длины два.

В таблице Кэли 3 для третьей строки взят второй беспорядок:и аналогично четвёртому в таблице 2 заполнены столбцы для двух оставшихся элементов порядка два (5 и 6). Осталось заполнить два неполных столбца для элементов порядка три или, что то же самое, три неполных строки для элементов порядка два. Если заполнять в таблице 4 строку для элемента 4 группы, то 6 переходит в 2, и, значит, 2 в 6, а так как 5 переходит в 3, то и 3 – в 5. Аналогично в таблице 4 заполним и две оставшихся строки и получим не симметричную таблицу Кэли для не коммутативной симметрической группы порядка шесть.

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

Подобным образом строились и вышеприведённые таблицы Кэли для двух не циклических групп порядка двенадцать. Для циклических групп таблица Кэли использовать такой способ построения нет необходимости. Если расположить элементы циклической группа, начиная с единичного, а затем в порядке возрастания степени образующего эту циклическую группу элемента, то каждая последующая строка таблицы Кэли будет циклическим сдвигом влево предыдущей. Например, циклическая группа порядка шесть, в которой 2 – образующий элемент, элемент 3 – это квадрат элемента 2, элемент 4 – куб элемента 2, …, элемент 6 – пятая степень элемента 2, 1 – единичный элемент и шестая степень элемента 2:

Глава 6. Кольца и поля

Кольца и поля – алгебраические структуры с двумя операциями, условно называемыми сложением и умножением и обозначаемыми обычно как + и *. Относительно операции сложения кольцо образует коммутативную группу, а относительно умножения – полугруппу. В кольце операции сложения и умножения связаны законом дистрибутивности: (a+b)*c=a*c+b*c и c*(a+b)= c*a+c*b для каждых a, b и c из непустого множества – носителя кольца.

Значит, кроме проверки кольца на группу по сложению и на полугруппу по умножению, надо проверить и дистрибутивность этих операций. Если умножение коммутативно, то кольцо тоже называют коммутативным; если по умножению в кольце есть моноид, то это кольцо с единицей. В кольце с единицей есть и нуль (0 – кольцевая (операционная) единица по сложению) и единица (1 – кольцевая единица по умножению).

1. Сложение не выводит из множества – носителя кольца.

2. a + (b + c) = (a + b) + c для каждых a, b и c. Сложение ассоциативно.

3. Существует кольцевой 0 (единица по сложению), такой, что для каждого элемента a кольца a + 0 = 0 + a = a.

5. Для каждых a и b кольца a + b = b + a. Сложение коммутативно, то есть кольцо – абелева группа по сложению.

6. Умножение не выводит из множества – носителя кольца.

7. a * (b * c)= (a * b) * c для каждых a, b и c. Умножение ассоциативно, то есть кольцо – полугруппа по умножению.

8. (a+b)*c=a*c+b*c и c*(a+b)= c*a+c*b для каждых a, b и c. Умножение дистрибутивно относительно сложения и справа и слева.

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

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

В кольце Z при операции сложения (+) целочисленно по модулю n складываются индексы элементов кольца, а при операции умножения (*) целочисленно по модулю n умножаются индексы элементов кольца. C + C = C, где mod(a + b) = d. C * C = C, где mod(a * b) = d. Операция mod(x) – это получение остатка от целочисленного деления числа x на число n.

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

1. Для каждого элемента a кольца a * 0 = 0 * a = 0, так как a + 0 = a, значит, a * (a + 0) = a * a = a * a + a * 0 = a * a + 0. Отсюда a * 0 = 0.

3. –a = (-1) * a, так как –a = (-a) * 1 = (-1) * a.

В кольцах целых чисел с операциями обычных сложения и умножения из того, что a * b = 0, следует, что или a = 0, или b = 0. В кольце Z это не так: C* C= 0 = C и C не равен C.

Если в кольце a*b=0 и a0, b0, то a – левый, а b – правый делитель нуля. В кольце Z элемент C — это делитель нуля. Если в кольце нет делителей нуля, то это кольцо без делителей нуля и в нём выполняется закон сокращения: если a * b = a * c и a не равно 0, то в = с. Доказательство: a * b – a * c = 0, отсюда по дистрибутивности a * (b – c) = 0, значит, b – c = 0 и b = c.

Кольцо Z не имеет делителей нуля, так как в таблице Кэли кольца по операции умножения нули (C = 0) есть только в первом столбце и первой строке:

В кольце с единицей могут быть обратимые элементы по операции умножения. Обратимый элемент не может быть делителем нуля, так как если a * b = 0, то a * (a * b) = 0 = (a * a) * b = 0 = 1 * b = 0 и, значит, b = 0.

Все обратимые элементы кольца с единицей образуют группу относительно операции умножения. Например, в кольце Z обратимый элемент – это C. C обратен сам себе и вместе с кольцевой единицей C образует коммутативную группу по операции умножения:

Поле – это коммутативное кольцо, в котором каждый ненулевой элемент обратим. В поле не может быть делителей нуля. Аддитивная группа поля (по операции сложения) содержит все его элементы, а мультипликативная его группа (по операции умножения) не содержит полевого нуля, т. е. содержит на один элемент меньше, чем аддитивная группа. Конечные поля Z, число элементов p в которых является простым числом, называются полями Галуа. Например, Z является полем:

Поле относительно операции умножения без полевого нуля образует коммутативную группу (мультипликативная группа поля). В полевой таблице Кэли по умножению полевой ноль не присутствует.

Можно считать, что в поле четыре операции: сложение, вычитание, умножение и деление. Уравнение b * x = a в поле имеет решение при b не равном полевому нулю: x = a / b = a * b.

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

1. Сложение не выводит из множества – носителя поля.

2. a + (b + c)= (a + b) + c для каждых a, b и c. Сложение ассоциативно.

3. Существует полевой 0 (единица по сложению), такой, что для каждого элемента a поля a + 0 = 0 + a = a.

5. Для каждых a и b поля a + b = b + a. Сложение коммутативно, то есть поле – это абелева группа по сложению.

6. Умножение не выводит из множества – носителя поля.

7. a * (b * c)= (a * b) * c для каждых a, b и c. Умножение ассоциативно.

8. Существует полевая 1 (единица по умножению), такая, что для каждого элемента a поля a * 1 = 1 * a = a.

9. Для каждого не равного 0 элемента a существует обратный элемент по умножению a: = a * a = a * a = 1.

10. Для каждых a и b поля a * b = b * a. Умножение коммутативно, то есть поле – это абелева группа по умножению без 0.

11. c*(a+b)= c*a+c*b для каждых a, b и c. Умножение дистрибутивно относительно сложения.

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

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

В этой алгебре работает недавно доказанная теорема Ферма: уравнение a + b = c имеет решение в целых положительных числах только при n = 2. Такие тройки чисел a, b и c называют пифагоровыми тройками. и так далее. Если в левой части уравнения увеличивать число слагаемых, то для n = 2 число слагаемых может быть равно трём, четырём и так далее.

Для n = 3 число слагаемых должно быть не менее трёх, и тогда будет решение уравнения в целых положительных числах:,и так далее. Для n = 4 число слагаемых должно быть не менее пяти (произошёл скачок в числе слагаемых):5),5) и так далее. Для n = 5 число слагаемых должно быть не менее шести, что косвенно подтверждает достоверность скачка слагаемых для n = 4:2),29 30) и так далее.

Во времена Ферма такие результаты получить было невозможно, так как не было компьютеров. Даже сейчас шестая степень (n = 6) не берётся. Возможно, что при дальнейшем развитии компьютеров удастся получить результаты по расширению теоремы Ферма для n > 5. Можно считать каждую вновь полученную степень n следующим этапом в развитии компьютеров.

Источник

Вам также может понравиться

Урок трудолюбия и активности: Поговорка Под лежачий камень вода не течёт

Приветствую, дорогие ученики! Сегодня я хочу поделиться

Умение экономить и ценить: Поговорка Меньше пей, да своё имей

Приветствую вас, мои маленькие ученики! «

Забота о других: Поговорка Хоть горшком назови, только в печку не ставь’

Привет, мои умные и любознательные ученики!

Урок терпения и сострадания: Поговорка Невестке в отместку

Привет, мои дорогие ученики! Сегодня я хочу рассказать