Операции над множествами
<<  Множества, операции над ними лекция №1 Множества и операции над ними  >>
Научно-практическая конференция учащихся Псковской области «Шаг в
Научно-практическая конференция учащихся Псковской области «Шаг в
Введение
Введение
Цель работы – дать аналитические оценки количества полугрупп,
Цель работы – дать аналитические оценки количества полугрупп,
Задачи
Задачи
Бинарные операции и свойство ассоциативности
Бинарные операции и свойство ассоциативности
Определение 2. Бинарная операция на непустом множестве X —
Определение 2. Бинарная операция на непустом множестве X —
Определение 3. Бинарная алгебраическая операция * на
Определение 3. Бинарная алгебраическая операция * на
Определение 5. Множество Х с заданной на нем бинарной алгебраической
Определение 5. Множество Х с заданной на нем бинарной алгебраической
Определение 7. Пусть (X,*) — полугруппа
Определение 7. Пусть (X,*) — полугруппа
Определение 9. Пара (Х,*), состоящая из множества Х и бинарной
Определение 9. Пара (Х,*), состоящая из множества Х и бинарной
Определение 11
Определение 11
Пусть S и T – полугруппы с операциями
Пусть S и T – полугруппы с операциями
Теорема 1. Любая полугруппа с единицей изоморфна некоторой полугруппе
Теорема 1. Любая полугруппа с единицей изоморфна некоторой полугруппе
Теперь каждому a
Теперь каждому a
F – подмножество в T(X), и нужно убедиться, что оно замкнуто
F – подмножество в T(X), и нужно убедиться, что оно замкнуто
Теперь убедимся, что отображение
Теперь убедимся, что отображение
Определение 12: Подстановкой n - ой степени называется взаимно
Определение 12: Подстановкой n - ой степени называется взаимно
3.Задача классификации и оценки количества конечных полугрупп
3.Задача классификации и оценки количества конечных полугрупп
Список всех бинарных операций на множестве { 1, 2 }
Список всех бинарных операций на множестве { 1, 2 }
4. Асимптотическая оценка количества полугрупп на n элементах
4. Асимптотическая оценка количества полугрупп на n элементах
Лемма 1. Пусть S – конечная полугруппа
Лемма 1. Пусть S – конечная полугруппа
(II)?(I): пусть k=max { ks | s
(II)?(I): пусть k=max { ks | s
Теорема 1. Пусть S будет нильпотентной полугруппой порядка n, (n
Теорема 1. Пусть S будет нильпотентной полугруппой порядка n, (n
Теорема 3. Пусть S – нильпотентная полугруппа порядка n (n
Теорема 3. Пусть S – нильпотентная полугруппа порядка n (n
Теорема 5. Для n
Теорема 5. Для n
Теорема 6. Для n
Теорема 6. Для n
Выводы
Выводы
Список литературы
Список литературы
Спасибо за внимание
Спасибо за внимание

Презентация: «БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ». Автор: 1. Файл: «БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ.ppt». Размер zip-архива: 110 КБ.

БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ

содержание презентации «БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ.ppt»
СлайдТекст
1 Научно-практическая конференция учащихся Псковской области «Шаг в

Научно-практическая конференция учащихся Псковской области «Шаг в

будущее» 11 – 13 декабря 2013 года, г. Псков БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ Работу выполнил: Кузьминский Евгений Михайлович МАОУ «Гуманитарный лицей» г. Псков, 11 класс. Научный руководитель: Яблокова Галина Анатольевна учитель математики МАОУ «Гуманитарный лицей» г. Псков. г. Псков 2013

2 Введение

Введение

Задача исчерпывающего описания всех конечных полугрупп появилась в алгебре практически одновременно с возникновением теории групп и полугрупп. С использованием трудоемких вычислительных процедур, требующих применения самых современных аппаратных решений, к середине 2013 года были получены точные значения для количества различных (с точностью до изоморфизма) полугрупп мощности от 1 до 10. В представленной работе сделана попытка дать аналитическую оценку для количества полугрупп специального вида, прежде всего – полугрупп с рангом нильпотентности 3.

3 Цель работы – дать аналитические оценки количества полугрупп,

Цель работы – дать аналитические оценки количества полугрупп,

состоящих из n элементов, с точностью до изоморфизма.

4 Задачи

Задачи

Провести алгебраическое описание задачи оценивания количества полугрупп над конечными множествами; Описать ситуация с оценками количества бинарных ассоциативных операций (полугрупп) над конечными множествами; Дать определение нильпотентных и r-нильпотентных полугрупп, установлены основные свойства нильпотентных полугрупп; Установить, что асимптотически количество полугрупп над конечным множеством может быть оценено количеством полугрупп над этим множеством с индексом нильпотентности 3; Получить формула суммирования, определяющая количество полугрупп с индексом нильпотентности 3.

5 Бинарные операции и свойство ассоциативности

Бинарные операции и свойство ассоциативности

Определение 1. Пусть A, B, C— тройка непустых множеств. Бинарной или двуместной операцией в паре A, B со значениями в C называется отображение P?C где P содержится в A?B. Если A=B=C, то действие называется внутренним, если A=C или B=C — внешним. В частности, любое внутреннее действие является внешним.

6 Определение 2. Бинарная операция на непустом множестве X —

Определение 2. Бинарная операция на непустом множестве X —

пределение 2. Бинарная операция на непустом множестве X — это отображение ? из прямого произведения X?X в X. Пример: пусть P(U) — множество всех подмножеств множества U. Операции пересечения и объединения - это бинарные алгебраические операции на множестве P(U).

7 Определение 3. Бинарная алгебраическая операция * на

Определение 3. Бинарная алгебраическая операция * на

пределение 3. Бинарная алгебраическая операция * на множестве X называется коммутативной, если x * y = y * x для всех x, y ? Х . Определение 4. Бинарная алгебраическая операция * на множестве Х называется ассоциативной, если ( x * y )* z = x * ( y * z) для всех x, y, z ? Х. Пример: операция сложения на множестве целых чисел является коммутативной и ассоциативной.

8 Определение 5. Множество Х с заданной на нем бинарной алгебраической

Определение 5. Множество Х с заданной на нем бинарной алгебраической

пределение 5. Множество Х с заданной на нем бинарной алгебраической операцией, называется группоидом. Определение 6. Пара (Х,*), состоящая из множества Х и бинарной алгебраической операции * называется полугруппой, если операция * ассоциативна. Пример: множество натуральных чисел (N,+) является полугруппой, так как операция сложения на N ассоциативна.

9 Определение 7. Пусть (X,*) — полугруппа

Определение 7. Пусть (X,*) — полугруппа

пределение 7. Пусть (X,*) — полугруппа. Подмножество называется замкнутым относительно операции *, если x*y принадлежит Y для всех x,y ? Y. Определение8. Пусть .Пара (Y,*) называется подполугруппой полугруппы (X,*), если Y замкнуто относительно операции *.

10 Определение 9. Пара (Х,*), состоящая из множества Х и бинарной

Определение 9. Пара (Х,*), состоящая из множества Х и бинарной

пределение 9. Пара (Х,*), состоящая из множества Х и бинарной алгебраической операции * называется моноидом, если операция * ассоциативна и существует нейтральный элемент е ? Х, такой, что е*х=х*е=х Определение 10. Моноид Х с операцией * называется коммутативным, если * — коммутативна.

11 Определение 11

Определение 11

Пусть Y — подмножество в X. Будем говорить, что (Y,*) является подмоноидом моноида (X,*), если Y содержит нейтральный элемент e и замкнуто относительно операции *.

12 Пусть S и T – полугруппы с операциями

Пусть S и T – полугруппы с операциями

и * соответственно. Изоморфизмом S на T называется всякое взаимно однозначное отображение ? S на T, удовлетворяющее условию: для любых x, y ?S ?(x?y) = ?(x) * ?(y). Полугруппы, для которых существует изоморфизм одной на другую, называются изоморфными.

13 Теорема 1. Любая полугруппа с единицей изоморфна некоторой полугруппе

Теорема 1. Любая полугруппа с единицей изоморфна некоторой полугруппе

преобразований.

Доказательство: Итак, пусть S – произвольная полугруппа. Будем считать, что она мультипликативная. Нужно указать такое множество X, что в полной полугруппе преобразований T(X) найдется подполугруппа, изоморфная S. В качестве X возьмем множество, полученное из S присоединением символа 1, не принадлежащего S. Распространим умножение в S на множество X, определив произведения a ? 1 и 1 ?a для любого a ?S, а также произведение 1 ? 1. Положим a ? 1 = 1 ?a = a, 1 ? 1 = 1. Тем самым задана операция умножения на множестве X. Легко убедиться, что она ассоциативна, то есть X является полугруппой относительно этой операции. Видим, что 1 есть единица в X.

14 Теперь каждому a

Теперь каждому a

S поставим в соответствие преобразование fa множества X, заданное условием: для любого x ?X fa(x) = ax Ясно, что fa действительно является преобразованием X: ведь, согласно определению умножения на X, мы имеем ax ?S и, значит, ax ?X. Множество всех таких преобразований fa обозначим через F. Установим, что F есть подполугруппа в T(X), изоморфная S, тем самым теорема будет доказана.

15 F – подмножество в T(X), и нужно убедиться, что оно замкнуто

F – подмножество в T(X), и нужно убедиться, что оно замкнуто

относительно умножения, то есть для любых fa, fb?F найдется такой элемент c ?S, что fa fb= fc. Пользуясь определением преобразований, составляющих F и определением умножения преобразований, а также ассоциативностью умножения в X, получаем для любого x ?X последовательно fa fb(x) = fa(fb(x)) = a(bx) = (ab)x = fab(x). Мы видим, что в качестве требуемого элемента c можно взять ab.

16 Теперь убедимся, что отображение

Теперь убедимся, что отображение

, сопоставляющее каждому элементу a ?S преобразование fa , будет искомым изоморфизмом S на F. По определению, ? отображает S на F, надо проверить, что ? взаимно однозначно, то есть из того, что ?(a) = ?(b), следует a = b. Так как ?(a) = fa и ?(b) = fb , условие ?(a) = ?(b) означает, что fa = fb , а это означает, что для любого x ?X fa(x) = fb(x). В частности, fa(1) = fb(1), то есть a ? 1 = b ? 1. Но a ? 1 = a, b ? 1 = b, значит, a = b. Осталось убедиться, что для любых a, b ?S ?(ab) = ?(a)?(b), то есть для любого x ?X ?(ab)(x) = ?(a)?(b)(x). Сделаем это цепочкой равенств, пользуясь соответствующими определениями и ассоциативностью умножения: ?(ab)(x)=fab(x)=(ab)x=a(bx)=fa(fb(x))=fafb(x) =?(a)?(b)(x).

17 Определение 12: Подстановкой n - ой степени называется взаимно

Определение 12: Подстановкой n - ой степени называется взаимно

однозначное отображение множества А из n элементов в себя. Пусть множество А = {а1, а2, а3}, тогда существуют шесть различных перестановок элементов а1, а2, а3: (а1, а2, а3), (а1, а3, а2), (а2, а1, а3), (а2, а3, а1), (а3, а1, а2), (а3, а2, а1). В случае, когда ?А? = n всевозможных различных перестановок элементов множества А будет n?= 1?2?3?…?n (n-факториал). 3!=1?2?3=6. Определение 13: Произведением двух подстановок называется подстановка, получаемая в результате последовательного выполнения сначала 1 - ой, а затем 2 - ой из перемножаемых подстановок.

18 3.Задача классификации и оценки количества конечных полугрупп

3.Задача классификации и оценки количества конечных полугрупп

Наиболее сложной задачей, связанной с описанием всего многообразия конечных полугрупп, является задача полной классификации всех полугрупп порядка n. В общем случае не существует удовлетворительных описаний структуры всех полугрупп для n>10. Однако для небольших значений n можно дать исчерпывающие описания для полугрупп соответствующей мощности. Простейшим случаем является случай n=2. Для этого значения существует всего 16 бинарных операций на множестве и все их можно явным образом описать:

19 Список всех бинарных операций на множестве { 1, 2 }

Список всех бинарных операций на множестве { 1, 2 }

Список всех бинарных операций на множестве { 1, 2 }

Список всех бинарных операций на множестве { 1, 2 }

Список всех бинарных операций на множестве { 1, 2 }

?Полугруппа ({0,1},

? Полугруппа ({0,1},

1

1

1

1

1

1

1

1

1

1

1

2

2

1

2

2

Тривиальная полугруппа O2

)

2·(1·2) = 2, (2·1)·2 = 1

Полугруппа с левым нулем LO2

1

2

1

2

1

2

1

2

1

1

1

2

2

1

2

2

2·(1·2) = 1, (2·1)·2 = 2

Полугруппа с правым нулем RO2

? Группа (Z2, +2)

)

2

1

2

1

2

1

2

1

1

1

1

2

2

1

2

2

1·(1·2) = 2, (1·1)·2 = 1

? Группа (Z2, +2)

1·(1·1) = 1, (1·1)·1 = 2

1·(2·1) = 1, (1·2)·1 = 2

2

2

2

2

2

2

2

2

1

1

1

2

2

1

2

2

1·(1·1) = 2, (1·1)·1 = 1

1·(2·1) = 2, (1·2)·1 = 1

1·(1·2) = 2, (1·1)·2 = 1

Тривиальная полугруппа O2

20 4. Асимптотическая оценка количества полугрупп на n элементах

4. Асимптотическая оценка количества полугрупп на n элементах

Обозначим для натурального числа n через ?(n) количество неизоморфных полугрупп мощности n. Для полугруппы S обозначим Sk= {s1s2 · · · sk | si ? S}. Определение. Полугруппа S называется нильпотентной, если существует число r?N такое, что . Наименьшее такое rназывается рангом нильпотентности полугруппы S, а сама полугруппа S называется r-нильпотентной.

21 Лемма 1. Пусть S – конечная полугруппа

Лемма 1. Пусть S – конечная полугруппа

Следующие два утверждения равносильны: (I) S является нильпотентной (II) S содержит нулевой элемент z и для каждого элемента s?S существует ks?N, такое что Доказательство (I)?(II): Если S является r-нильпотентной и через z обозначить единственный элемент в , тогда sz=zs=z для всех s?S, таких, что zs, sz ? . Таким образом, z - нулевой элемент полугруппы. Более того, для всех s?S.

22 (II)?(I): пусть k=max { ks | s

(II)?(I): пусть k=max { ks | s

S} и n=|S|. Рассмотрим произведение элементов s1s2…sk+1 длины k+1 в S. Тогда последовательность префиксов вида (s1…si) где 1?i?k+1 должна будет содержать дубликаты, например, для определённости, s1s2…sh=s1…sm, где h<m?k+1. Выполняя последовательные замены вида s1…sh на s1…sm получим, что s1…sh=s1…sh(sh+1…sm)=…= =s1…shz=z. Поскольку h строго меньше m и, тем более, числа k, можно утврждать, что s1s2…sk=z Таким образом, все произведения длины по крайней мере k будут равны z, следовательно, полугруппа S является k-нильпотентной.

23 Теорема 1. Пусть S будет нильпотентной полугруппой порядка n, (n

Теорема 1. Пусть S будет нильпотентной полугруппой порядка n, (n

4) и рангом нильпотентности n-1. Тогда S=T?{x}, где Т – моногенная подполугруппа в S с рангом нильпотентности n-1 Теорема 2. Для n?5 существует n+[n/2] нильпотентных полугрупп мощности n и рангом нильпотентности n-1

24 Теорема 3. Пусть S – нильпотентная полугруппа порядка n (n

Теорема 3. Пусть S – нильпотентная полугруппа порядка n (n

5) и рангом нильпотентности n-2. если n?6 или S имеет минимальное порождающее множество мощности 3, то S=T?{x, y}, где Т – моногенная подполугруппа в S с рангом нильпотентности n-2 Теорема 4. Для n?6 количество нильпотентных полугрупп мощности n и ранга нильпотентности n-2 и минимальным порождающим множеством из 3 элементов равно (21n?+22n-96)/8 для чётных n и (21n?+22n-81)/8 для нечётных n.

25 Теорема 5. Для n

Теорема 5. Для n

7 существует 5n+ [n/2]+[n/3]-1 нильпотентных полугрупп мощности n, рангом нильпотентности n-2 и минимальным порождающим множеством из 2 элементов. Как следствие, количество таких полугрупп равно (21n?+66n-104)/8-[n/3] для чётных n и (21n?+80n-93)/8-[n/3] для нечётных n.

26 Теорема 6. Для n

Теорема 6. Для n

N количество различных 3-нильпотентных полугрупп мощности n равно где Таким образом, получена искомая формула, позволяющая оценить количество различных бинарных ассоциативных операций

27 Выводы

Выводы

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

28 Список литературы

Список литературы

Takayuki Tamura. Notes on finite semigroups and determination of semigroups of order 4, J. Gakugei. Tokushima Univ. Math., 5:17–27,1954. S.K.Winker, L.Wos, and E.L.Lusk. Semigroups, antiautomorphisms, and involutions: a computer solution to an open problem. I. Math. Comp., 37(156):533–545,1984. Andreas Distler and Tom Kelsey. The monoids of orders eight, nine & ten. Ann. Math. Artif. Intell., 56(1):3–21,2009. Jobst Heitzig and Jurgen Reinhold. Counting finite lattices. Algebra Universalis, 48(1):43–53,2002. Vaclav Koubek and Vojtech Rodl. Note on the number of monoids of order n. Comment. Math. Univ. Carolin., 26(2):309–314,1985.

29 Спасибо за внимание

Спасибо за внимание

«БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ»
http://900igr.net/prezentacija/algebra/binarnye-assotsiativnye-operatsii-i-polugruppy-nad-konechnymi-mnozhestvami-260650.html
cсылка на страницу
Урок

Алгебра

35 тем
Слайды
900igr.net > Презентации по алгебре > Операции над множествами > БИНАРНЫЕ АССОЦИАТИВНЫЕ ОПЕРАЦИИ И ПОЛУГРУППЫ НАД КОНЕЧНЫМИ МНОЖЕСТВАМИ