Дискретно-непрерывная математика (стр. 74 )

1.8. Определение. Пусть Р — разбиение на полугруппе S, а P (S, Р) — совокупность пар (φ, Т), φ : S →→ Т, таких, что φ (s1) =φ (s2) влечет s1 ≡ s2 (mod Р). Если (φ, Т) P (S, Р), мы пишем φ : S →→ Т и φ называем Р гомоморфизмом полугруппы S.

1.9. Утверждение. Пусть Р — любое разбиение на полугруппе S. Тогда P (S, Р) имеет минимальный гомоморфный образ, обознача­емый как SP.

Доказательство. Пусть Q будет отношением конгруэнтности, по­рожденным Р, т. е. s1 ≡ s2 (mod Q), тогда и только тогда, когда αs1β ≡ αs2β (mod P) для всех элементов α, β S1. Пусть η : S →→ S/Q — канонический гомоморфизм. Тогда легко доказать, что (η, S/Q) будет минимальным гомоморфным образом полугруппы S по отношению к P (S, Р).

1.10. Замечание. а) Важный пример минимального гомоморфного образа по отношению к разбиению был приведен ранее. Если дан автомат f : ∑А→, то полугруппа fS автомата f будет в точности ми­нимальным гомоморфным образом для P (∑А, (mod f)), где (mod f) есть разбиение, которое f индуцирует на ∑А. Другими словами, fS =∑А (mod f).

б) Пусть φ: S →→ Т — эпиморфизм. Тогда (φ, Т) представляет собой минимальный гомоморфный образ по отношению к P (S, mod φ). Таким образом, если θ : S →→ Т1 —такой эпиморфизм, что из ра­венства θ (s1) ≡ θ (s2) вытекает отношение s1 ≡ s2 (mod φ) для всех s1, s2 S, то (θ, Т1) P (S, mod φ). Следовательно, существует эпи­морфизм j : Т1 →→ T, такой, что φ = jθ.

1.11. Обозначения. Пусть α— любое из отношений F, R, L или H на полугруппе S. Тогда α является разбиением на S и P (S, α) имеет минимальный гомоморфный образ S α. Отображение θ : S →→Т есть α гомоморфизм (или эпиморфизм), если (θ, Т) P (S, α). Напри­мер, θ будет H эпиморфизмом тогда и только тогда, когда для всех элементов s1, s2 S, таких, что θ (s1) = θ (s2), необходимо s1 H s2.

1.12. Определение. Пусть θ : S →→ T, θ называется γ эпимор­физмом, если ограничение θ на любую подгруппу полугруппы S вза­имно однозначное. Пусть α — одно из отношений F, R, L или H. Тогда θ называется γ (α) эпиморфизмом, если ограничение θ на любой α класс есть взаимно однозначное отображение. В частности, γ(α) эпиморфизм представляет собой γ эпиморфизм.

1.13. Утверждение. Пусть α — любое из отношений F, R, L или H. Тогда

а) композиция двух α эпиморфизмов будет α эпиморфизмом;

б) композиция двух γ(α) эпиморфизмов (соответственно γ эпи­морфизмов) будет γ(α) эпиморфизмом (соответственно γ эпиморфиз­мом).

Доказательство, а) Докажем, что если φ: S →→Т есть α эпи­морфизм, то каждый α класс полугруппы S отображается на α класс полугруппы Т. Следовательно, α классы полугруппы S и α классы по­лугруппы T находятся во взаимно однозначном соответствии, из этого легко вытекает требуемый результат.

Предположим, что α = F и φ (j1) F φ (j2). Пусть s, t, и, v S — такие любые элементы, что φ (s) φ (j1) φ(t) = φ (j2) и φ (u) φ (j2) φ(v) = φ (j1) . Тогда поскольку φ есть F эпиморфизм, имеем sj1tF j2 и uj2vF j1. Из этого следует, что j1F j2, следовательно, j1F j2 тогда и только тогда, когда φ (j1) F φ (j2).

Для отношений α = R, L и H доказательство проводится аналогично.

б) Оставляем доказательство читателю в качестве упражнения.

Мы докажем теперь основной результат этого пункта, а имен­но, что каждый эпиморфизм между двумя конечными полугруппами можно разложить в γ(H) и H эпиморфизмы.

1.14. Теорема. Пусть θ : S →→ T — эпиморфизм. Тогда θ можно записать как θ = θп, ... θ1 где θ 1, θ 3, θ 5, … будут γ(H) эпиморфиз­мами и θ 2, θ 4, θ 6, ... будут H эпиморфизмами (или наоборот).

Прежде чем приступить к доказательству теоремы, введем следую­щее определение.

1.15. Определение. Пусть θ : S →→ T —эпиморфизм. Тогда θ называется максимальным собственным эпиморфизмом (МРЕ), если из соотношения θ = θ2θ1 где θ1 и θ 2 — эпиморфизмы, следует, что одно и только одно из отображений θ1 ,θ2 взаимно однозначное.

Очевидно, что любой эпиморфизм θ будет изоморфизмом или может быть записан как θ = θп, ... θ1, где каждый θ k есть МРЕ. Поэтому из утверждения 1.13 легко следует, что теорема 1.14 эквивалентна следующему результату.

1.16. Теорема. Пусть θ : S →→ T есть МРЕ. Тогда θ является или γ(H), или H эпиморфизмом.

Для того чтобы доказать предыдущие теоремы, нам потребуются следующие определения и лемма.

1.17. Определение. Пусть θ : S →→ T —эпиморфизм. Тогда F класс J полугруппы S называется θ-сингулярным, если отображение θ взаимно однозначно на S — J.

1.18. Лемма. Пусть отображение θ : S →→ T есть МРЕ. Тогда существует θ - сингулярный F - класс полугруппы S.

Доказательство. Пусть I1 — максимальный (по включению) член из F = { I : I есть идеал полугруппы S и ограничение θ на I— вза­имно однозначное отображение}. I1≠S, поскольку θ не является вза­имно однозначным на полугруппе S. (F может быть пустым, но по сог­лашению мы будем рассматривать пустое множество как идеал.) Пусть J1 будет ≤-минимальным элементом из {J : J есть F класс полугруппы S и J I1 = }. Пусть I2 = I1 J1. Тогда I2— идеал полугруппы S, содержащий I1 как собственное подмножество. Следо­вательно, по определению I1θ, ограниченный на I2, не является вза­имно однозначным.

Пусть (mod θ) будет отношением конгруэнтности на S, задаваемым как s1 ≡s2 (mod θ), тогда и только тогда, когда θ (s1) = θ (s2).

Определим отношение эквивалентности ≡ на S, полагая s1 ≡ s2 тогда только тогда, когда имеем s1 = s2 или s1,s2 І2 и θ (s1) = θ (s2). Легко проверить, что отношение ≡ является конгруэнтностью. Пусть θ 1 : S →→ S/ ≡ есть канонический гомоморфизм. Тогда оче­видно, что равенство θ 1(s1) = θ 1(s2) влечет s1 ≡ s2 (mod θ), поэтому в силу пункта б) замечания 1.10 существует такой эпиморфизм θ 2 : S/ ≡→→ Т, что θ = θ 2 θ 1. Но поскольку θ = θ 1 на І2 и θ не взаимно однозначный на І2, θ не является взаимно однозначным. Следова­тельно, θ2 будет взаимно однозначным, так как θ есть МРЕ. Следователыю, отношения ≡ и (mod θ) равны и J1 есть θ - сингулярный F класс.

Доказательство теоремы 1.16. Эпиморфизм, представляющий со­бой γ(H) и H эпиморфизм, есть изоморфизм. Пусть θ : S →→ T естъ МРЕ с θ-сингулярным F классом J. Если θ является γ(H) эпиморфизмом, то требуемый результат получен, поэтому предполо­жим противное.

Определим отношение эквивалентности ≡ на полугруппе S, по­лагая s1 ≡s2 тогда и только тогда, когда s1 H s2 и θ (s1) = θ (s2). По­скольку класс J θ-сингулярный, ограничивая это отношение на S — J, получаем s1 ≡s2 тогда и только тогда, когда s1 = s2.

Проверим теперь, что ≡ представляет собой отношение конгру­энтности на S. Очевидно, что ≡ есть отношение конгруэнтности на S — J. Пусть s1 ≡s2, s1 и s2 J. Пусть х, у S1. Так как s1 H s2, то из результата Грина (см. утверждение 5 предыдушего микромодуля) известно, что или оба элемента xs1y и xs2y не принадлежат J, или xs1yHxs2y. В каж­дом случае θ (xs1y) = θ (xs2y). Так как класс J θ-сингулярный, то если xs1y, xs2уS—J, получим xs1y≡xs2y. Следовательно, ≡ есть отношение конгруэнтности. Поскольку θ не есть γ(H) эпиморфизм, отношение ≡ не является тождественным.