Лекция дискрет 09
.pdf
Th.2.2.1 Конечная полугруппа [ M; ☼ ] с нейтральным элементом e = m0 изоморфна некоторой полугруппе [ T(M); ] преобразований множества М
Доказательство Th.2.2.1
По условию M = { m0, m1, m2, … , mn }
T(M) = { fi = |
m |
m |
m |
……… m |
|
|||
m |
0 |
m |
1 |
m |
2 |
……… mn |
} |
|
|
|
i0 |
|
i1 |
|
i2 |
in |
|
Каждому элементу miΜ поставим в соответствие преобразование fi множества М такое, что fi(mj) = mj ☼ mi для всех j=0,1,2,…,n
Так как [ M; ☼ ] по условию – полугруппа и множество М замкнуто относительно операции ☼, значение (mj ☼ mi) М, поэтому соответствие корректно для любых mi M, значит, построенное соответствие всюду определено на множестве М
fi(mj) = mj ☼ mi
|
M |
M |
|
|
|
m0 |
m0 ☼ mi |
|
m1 |
m1 |
☼ mi |
…. |
…. |
|
mi |
mi |
☼ mi |
…. |
…. |
|
mj |
mj ☼ mi |
|
…. |
…. |
|
mn |
mn ☼ mi |
|
Сюръективность – от противного.
Допустим, есть преобразование fi T(M), которое не является образом никакого mi M. Это означает, что для всякого i = 0,1,2,…,n найдётся хотя бы один индекс ji (ji = 0,1,2,…,n) такой, что (mji ☼ mi) M, что противоречит замкнутости М относительно ☼
Функциональность – от противного.
Допустим, имеется mi M, которому соответствуют два различных преобразования fi T(M) и fi T(M). Но
для этого хотя бы для одного mj M должно быть fi(mji) = mji ☼ mi mji ☼ mi = fi (mi ji) - противоречие
Также от противного – инъективность.
Допускаем существование различных m M и m M, |
||||||||
|
|
|
|
|
|
i |
i |
|
которым соответствует одно и то же fi T(M). Но тогда fi(mji) |
||||||||
= m |
☼ m = m |
☼ m |
для всех m |
M, в том числе для |
||||
m |
ji |
i ji |
i |
ji |
|
|
= m . |
|
= m = e, то есть получаем m = e ☼ m = e ☼ m |
||||||||
ji |
|
0 |
|
|
i |
i |
i |
i |
|
|
|
|
|
|
|
|
|
Итак, построили взаимно однозначное соответствие Γ: М Т(М) Остаётся проверить выполнение условия гомоморфности ( )
Г ( φi ( kj1, kj2, … , kjli ) ) = ψi ( Г(kj1), Г(kj2), … , Г(kjli) ) ( )
В данном случае: φ – операция ☼ на множестве М, ψ – композиция преобразований множества М, т.е. операция на Т(М), Γ – только что построенное соответствие между mi M и fi T(M)
φ(mi, mj) = mi ☼ mj = mk M |
Γ(mi) = fi |
Γ(mj) = fj , где |
|
fi(ms) = ms ☼ mi |
fj(mt) = mt ☼ mj |
Γ(mk) = fk : fk(ms) = ms ☼ mk M |
ψ(fi, fj) = fi |
fj = ft T(M) |
fk(ms) = ms ☼ mk = ms ☼ (mi ☼ mj) |
ft(ms) = fj(fi(ms)) = fj(ms ☼ mi) = |
|
|
= (ms ☼ mi) ☼ mj |
|
Показали, что Г: М Т(М) – гомоморфизм, а, в силу ранее доказанной взаимно однозначности - изоморфизм
Доказано Th.2.2.1
Пример. Ранее была построена Модель скрещивания
организмов
|
a |
b |
c |
d |
|
|
|
|
|
a |
a |
a |
a |
a |
b |
a |
b |
a |
b |
c |
a |
a |
c |
c |
d |
a |
b |
c |
d |
|
|
|
|
|
Четыре типа масти КРС: a – «чёрный одноцветный» b – «чёрный пятнистый»
c – «бурый одноцветный» d – «бурый пятнистый»
Убедились, что это моноид [ { a, b, c, d }; ]
Согласно Th.2.2.1 он изоморфен полугруппе преобразований
[ T({ a, b, c, d }); ] или, в общем виде, [ T({ 1, 2, 3, 0 }); ]
Подстановка (перестановка) на конечном множестве M = {m1, m2, … , mn} – взаимно однозначное преобразование множества М
Если М = { 1, 2, 3 }, то возможных подстановок 3! = 6
|
1 |
2 |
3 |
|
1 |
2 |
3 |
|
1 |
2 |
3 |
|
α = |
β = |
|
|
|
γ = |
|||||||
3 |
1 |
2 |
1 |
3 |
2 |
2 |
1 |
3 |
||||
|
|
|
δ = |
1 |
2 |
3 |
ε = |
1 |
2 |
3 |
ζ = |
1 |
2 |
3 |
|
2 |
3 |
1 |
1 |
2 |
3 |
3 |
2 |
1 |
||||
|
|
|
|
|
Правый операнд |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
α |
β |
γ |
δ |
ε |
ζ |
|
операнд |
|
|
|
|
|
|
|
|
α |
δ |
γ |
ζ |
ε |
α |
β |
||
|
||||||||
|
|
|
|
|
|
|
|
|
|
β |
ζ |
ε |
δ |
γ |
β |
α |
|
|
|
|
|
|
|
|
|
|
Левый |
γ |
β |
α |
ε |
ζ |
γ |
δ |
|
|
|
|
|
|
|
|
||
δ |
ε |
ζ |
β |
α |
δ |
γ |
||
|
||||||||
|
|
|
|
|
|
|
|
|
|
ε |
α |
β |
γ |
δ |
ε |
ζ |
|
|
|
|
|
|
|
|
|
|
|
ζ |
γ |
δ |
α |
β |
ζ |
ε |
|
|
|
|
|
|
|
|
|
|
В общем случае операция некоммутативна
Есть нейтральный элемент ε
Для каждого элемента имеется обратный:
α |
δ = ε |
δ |
α = ε |
β |
β = ε |
ε |
ε = ε |
γ |
γ = ε |
ζ |
ζ = ε |
Итак, некоммутативная группа подстановок конечного множества M = { 1, 2, 3 }
Th.2.2.2 (Теорема Кэли)
Конечная группа [ M; ☼ ] изоморфна некоторой группе [ T(M); ] подстановок на множестве элементов М
3) Группа вращений кубика Эрне Рубика (Венгрия, 1975)
Разбит на 27 одинаковых кубиков плоскостями, параллельными граням куба; 26 кубиков являются наружными, а один— внутренний. Внутренний кубик удалён, а наружные кубики с помощью крестовины сцеплены так, что любая из плит, образованных девятью кубиками, грани которых параллельны некоторой грани куба, может свободно вращаться вокруг центра в любом направлении.
Внешние грани кубиков окрашены в шесть разных цветов: красный, оранжевый, жёлтый, зелёный, синий, белый (по 9 граней каждого цвета).
Каждый из 8 угловых кубиков имеет по 3 окрашенных грани, и, соответственно, может быть тремя способами ориентирован в пространстве. Для каждого из 12 средних кубиков – по два цвета и две позиции. Центральные кубики граней – их 6, т.е. по одному на каждую внешнюю грань, окрашены лишь с одной стороны - той, которая при вращении центральных плит бессменно обращена наружу
При повороте одной из плит на углы 90°, 180° или 270° любую из плит снова можно вращать вокруг центра в любую сторону.
Цель игры состоит в том, чтобы, получив в руки такой пёстро окрашенный кубик, с помощью поворотов плит перейти к начальной раскраске, т.е. добиться такой расстановки кубиков, при которой все грани большого куба окрашены в один цвет.