Stable Quasiorderings on Some Permutable Inverse Monoids
Let G be an arbitrary group of bijections on a finite set. By I(G), we denote the set of all injections each of which is included in a bijection from G. The set I(G) forms an inverse monoid with respect to the ordinary operation of composition of binary relations. We study different properties of th...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська Англійська |
| Опубліковано: |
Institute of Mathematics, NAS of Ukraine
2014
|
| Онлайн доступ: | https://umj.imath.kiev.ua/index.php/umj/article/view/2147 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Репозитарії
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860508084931133440 |
|---|---|
| author | Derech, V. D. Дереч, В. Д. |
| author_facet | Derech, V. D. Дереч, В. Д. |
| author_sort | Derech, V. D. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2019-12-05T10:25:15Z |
| description | Let G be an arbitrary group of bijections on a finite set. By I(G), we denote the set of all injections each of which is included in a bijection from G. The set I(G) forms an inverse monoid with respect to the ordinary operation of composition of binary relations. We study different properties of the semi-group I(G). In particular, we establish necessary and sufficient conditions for the inverse monoid I(G) to be permutable (i.e., ξ ○ φ = φ ○ ξ for any pair of congruences on I(G)). In this case, we describe the structure of each congruence on I(G). We also describe the stable orderings on I(A n ), where A n is an alternating group. |
| first_indexed | 2026-03-24T02:19:35Z |
| format | Article |
| fulltext |
УДК 512.534.5
В. Д. Дереч (Вiнниц. нац. техн. ун-т)
СТАБIЛЬНI КВАЗIПОРЯДКИ
НА ДЕЯКИХ ПЕРЕСТАВНИХ IНВЕРСНИХ МОНОЇДАХ
Let G be an arbitrary group of bijections on a finite set. By I(G) we denote the set of all injections each of which is
included in a bijection from G. The set I(G) forms an inverse monoid with respect to the ordinary operation of composition
of binary relations . We investigate different properties of the semigroup I(G). In particular, we establish necessary and
sufficient conditions for the inverse monoid I(G) to be permutable (i.e., ξ ◦ ϕ = ϕ ◦ ξ for any pair of congruences ξ, ϕ
on I(G)). In this case, we describe the structure of each congruence on I(G). We also describe stable orders on I(An),
where An is alternating group.
Пусть G — произвольная группа биекций на конечном множестве. Обозначим через I(G) множество всех инъекций,
каждая из которых включается в биекцию из G. Множество I(G) относительно обычной операции композиции
бинарных отношений образует инверсный моноид. В данной статье изучаются различные свойства полугруппы
I(G). В частности, установлены необходимые и достаточные условия для того, чтобы инверсный моноид I(G) был
перестановочным (т. е. ξ ◦ϕ = ϕ ◦ ξ для любой пары конгруэнций ξ, ϕ на I(G)), и в этом случае описана структура
каждой конгруэнции на I(G). Приведено описание стабильных порядков на I(An), гдеAn — альтернативная группа.
Нехай G — довiльна група бiєкцiй на скiнченнiй множинi N = {1, 2, 3, . . . , n}, а ISn — си-
метрична iнверсна напiвгрупа на N. Розглянемо множину I(G) = {ϕ ∈ ISn : ϕ ⊆ η для
деякого η ∈ G}. Легко перевiрити, що таким чином вiдносно операцiї композицiї ми одержує-
мо iнверсний моноїд, в якому група оборотних елементiв збiгається з G. Зокрема, якщо взяти
симетричну групу Sn, то очевидно, що моноїд I(Sn) — це симетрична iнверсна напiвгрупа на
множинi N. З означення iнверсного моноїда I(G) безпосередньо випливає, що вiн є розкладним,
тобто I(G) = G ◦ E, де E — напiврешiтка iдемпотентiв моноїда I(G). Моноїд I(G) є простим
прикладом iнверсної алгебри в сенсi статтi [1]. В роботi [2] дослiджуються деякi властивостi
iнверсної напiвгрупи I(An), де An— альтернативна група. В статтi [3] наведено опис групи
автоморфiзмiв скiнченного моноїда I(G), а також встановлено необхiднi i достатнi умови, за
яких будь-який стабiльний порядок на I(G) є фундаментальним або антифундаментальним.
У данiй статтi ми продовжуємо вивчати властивостi моноїда I(G). Зокрема, у пунктi 1 вста-
новлено необхiднi i достатнi умови, за яких iнверсний моноїд I(G) буде переставним (тобто
для будь-яких конгруенцiй θ i ξ на I(G) виконується рiвнiсть θ ◦ ξ = ξ ◦ θ). У пунктi 3 ви-
вчаються властивостi стабiльних квазiпорядкiв на переставному моноїдi I(G). У пунктi 4 дано
опис конгруенцiй на I(G), а у пунктi 5 з’ясовано структуру будь-якого стабiльного порядку на
iнверсному моноїдi I(An).
1. Необхiдна i достатня умова для того, щоб iнверсний моноїд I(G) був переставним.
Напiвгрупа називається переставною, якщо для будь-яких двох її конгруенцiй ρ i σ виконується
рiвнiсть ρ ◦ σ = σ ◦ ρ, де ◦ — позначення композицiї бiнарних вiдношень. У цьому пунктi ми
встановимо необхiднi i достатнi умови, за яких iнверсний моноїд I(G) є переставним. Перед
тим як сформулювати вiдповiдну теорему наведемо кiлька означень.
Означення. Скiнченну групуG бiєкцiй на множинi N = {1, 2, 3, . . . , n} назвемо глобально-
транзитивною, якщо для довiльних пiдмножин A i B множини N таких, що |A| = |B|, iснує
бiєкцiя ξ ∈ G така, що (A)ξ = B.
Очевидно, що скiнченна симетрична група є глобально-транзитивною. До глобально-транзи-
тивних груп також належить альтернативна група An. Цей факт вiдмiчено в [2] (лема 6). Чи
c© В. Д. ДЕРЕЧ, 2014
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4 445
446 В. Д. ДЕРЕЧ
iснують глобально-транзитивнi групи, вiдмiннi вiд Sn i An? Вiдповiдь ствердна. Наведемо
приклад.
Приклад. Нехай S5 — симетрична група на множинi {1, 2, 3, 4, 5}. Розглянемо пiдгрупу
групи S5, що породжується двома перестановками
(
1 2 3 4 5
2 3 4 5 1
)
i
(
1 2 3 4 5
1 3 5 2 4
)
.
Перелiчимо всi 20 елементiв цiєї пiдгрупи:(
1 2 3 4 5
1 2 3 4 5
)
,
(
1 2 3 4 5
2 3 4 5 1
)
,
(
1 2 3 4 5
3 4 5 1 2
)
,
(
1 2 3 4 5
4 5 1 2 3
)
,(
1 2 3 4 5
5 1 2 3 4
)
,
(
1 2 3 4 5
1 5 4 3 2
)
,
(
1 2 3 4 5
3 2 1 5 4
)
,
(
1 2 3 4 5
5 4 3 2 1
)
,(
1 2 3 4 5
2 1 5 4 3
)
,
(
1 2 3 4 5
4 3 2 1 5
)
,
(
1 2 3 4 5
1 3 5 2 4
)
,
(
1 2 3 4 5
4 2 5 3 1
)
,(
1 2 3 4 5
1 4 2 5 3
)
,
(
1 2 3 4 5
2 4 1 3 5
)
,
(
1 2 3 4 5
3 5 2 4 1
)
,
(
1 2 3 4 5
4 1 3 5 2
)
,(
1 2 3 4 5
5 2 4 1 3
)
,
(
1 2 3 4 5
3 1 4 2 5
)
,
(
1 2 3 4 5
5 3 1 4 2
)
,
(
1 2 3 4 5
2 5 3 1 4
)
.
Безпосередня перевiрка показує, що дана група є глобально-транзитивною. Зазначимо, що
ця група є максимальною (за включенням) пiдгрупою симетричної групи S5.
Проблема. Знайти джерело скiнченних глобально-транзитивних груп.
Для α ∈ I(G) число | im (α)| називають рангом перетворення α i позначають через rank (α).
Далi через dom (ϕ) i im (ϕ) будемо позначати вiдповiдно область визначення i множину значень
iн’єкцiї ϕ ∈ I(G). Нехай Sn — симетрична група на множинi N = {1, 2, 3, . . . , n}. Якщо G —
пiдгрупа групи Sn, то зрозумiло, що кожний iдемпотент напiвгрупи I(G) має вигляд ∆A —
вiдношення рiвностi на множинi A (A ⊆ N).
Наступне твердження нам знадобиться в подальших викладках.
Твердження 1 (див. [4], теорема 2). Нехай S — iнверсна напiвгрупа скiнченного рангу з
нулем. Тодi S є переставною в тому i лише в тому випадку, коли виконуються такi двi умови:
1) для будь-яких a, b ∈ S, якщо rank (a) = rank (b), то SaS = SbS;
2) для будь-якого e ∈ E(S)(rank (e) ≥ 2) iснують iдемпотенти f i g такi, що f 6= g, f < e,
g < e i rank (f) = rank (g) = rank (e)− 1.
Зазначимо, що умова 1 твердження 1 еквiвалентна лiнiйнiй впорядкованостi (вiдносно
включення) iдеалiв напiвгрупи S.
Тепер сформулюємо i доведемо основну теорему першого пункту.
Теорема 1. Нехай G — пiдгрупа симетричної групи Sn. Наступнi властивостi є еквiва-
лентними:
(a) G — глобально-транзитивна група;
(b) iдеали iнверсного моноїда I(G) утворюють ланцюг вiдносно включення;
(c) моноїд I(G) є переставним.
Доведення. Спочатку обґрунтуємо еквiвалентнiсть (a)⇔ (b). Отже, припустимо, що група
G є глобально-транзитивною. Доведемо, що iдеали iнверсного моноїда I(G) утворюють лан-
цюг вiдносно включення. Позначимо через Id довiльний iдеал напiвгрупи I(G). Нехай ∆A
— iдемпотент найбiльшого рангу серед усiх iдемпотентiв, що належать iдеалу Id. Доведе-
мо, що I(G) ◦ ∆A ◦ I(G) = Id. Включення I(G) ◦ ∆A ◦ I(G) ⊆ Id є очевидним. Обґрун-
туємо зворотне включення. Нехай ψ ∈ Id, dom (ψ) = D, im (ψ) = R. Легко зрозумiти, що
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
СТАБIЛЬНI КВАЗIПОРЯДКИ НА ДЕЯКИХ ПЕРЕСТАВНИХ IНВЕРСНИХ МОНОЇДАХ 447
rank (ψ) ≤ rank (∆A). Тодi iснує пiдмножина B множини A така, що |B| = |D| = |R|.
Оскiльки група G глобально-транзитивна, то iснує ξ ∈ G таке, що (D)ξ = B. Звiдси лег-
ко випливає, що iснує iн’єкцiя η ∈ I(G) така, що dom (η) = D i im (η) = B. Аналогiчно
доводимо, що iснує iн’єкцiя ϕ ∈ I(G) така, що dom (ϕ) = B i im (ϕ) = R. Зрозумiло, що
dom (η ◦∆A ◦ϕ) = D. Кожний iдеал iнверсної напiвгрупи є iнверсною пiднапiвгрупою. Оскiль-
ки η ◦ ∆A ◦ ϕ ∈ I(G) ◦ ∆A ◦ I(G), то (η ◦ ∆A ◦ ϕ)−1 ∈ I(G) ◦ ∆A ◦ I(G). Очевидно, що
(η ◦ ∆A ◦ ϕ) ◦ (η ◦ ∆A ◦ ϕ)−1 = ∆D. Оскiльки ∆D ∈ I(G) ◦ ∆A ◦ I(G) i ∆D ◦ ψ = ψ, то
ψ ∈ I(G) ◦∆A ◦ I(G). Отже, Id ⊆ I(G) ◦∆A ◦ I(G). Враховуючи справедливiсть зворотного
включення, робимо висновок, що Id = I(G)◦∆A◦I(G). Таким чином, кожний iдеал iнверсного
моноїда I(G) є головним, а отже (див. [5], теорема 2), iдеали iнверсного моноїда I(G) лiнiйно
впорядкованi вiдносно включення.
Припустимо тепер, що iдеали iнверсного моноїда I(G) утворюють ланцюг вiдносно вклю-
чення. НехайB i C — пiдмножини множини N = {1, 2, 3, . . . , n}, причому |B| = |C|. Зрозумiло,
що ∆B ∈ I(G) i ∆C ∈ I(G). Крiм того, rank (∆B) = rank (∆C). Тодi (див. [5], теорема 2) має
мiсце рiвнiсть I(G) ◦∆B ◦ I(G) = I(G) ◦∆C ◦ I(G) . Звiдси випливає, що iснують β ∈ I(G)
i µ ∈ I(G) такi, що ∆B = β ◦ ∆C ◦ µ. Зрозумiло, що ∆C ◦ µ ∈ I(G), dom (∆C ◦ µ) = C,
im (∆C ◦ µ) = B. Нехай перестановка φ ∈ G така, що ∆C ◦ µ ⊆ φ. Очевидно, що (C)φ = B.
Отже, група G є глобально-транзитивною.
Еквiвалентнiсть (a)⇔ (b) доведено.
Далi, вiдомо (див. [6], теорема 4), що iдеали будь-якої переставної напiвгрупи утворюють
ланцюг вiдносно включення, тобто виконується iмплiкацiя (c)⇒ (b).
Нарештi обґрунтуємо iмплiкацiю (b)⇒ (c).
Оскiльки iдеали iнверсного моноїда I(G) утворюють ланцюг вiдносно включення, то ви-
конується умова 1 твердження 1. Далi, нехай A — довiльна пiдмножина множини N = {1, 2,
3, . . . , n}. Очевидно, що вiдношення рiвностi на множинi A (ми його позначаємо через ∆A) є
iдемпотентом моноїда I(G). Iнших iдемпотентiв в I(G) немає. Отже, зрозумiло, що напiврешiт-
ка iдемпотентiв iнверсного моноїда I(G) iзоморфна напiврешiтцi усiх пiдмножин множини N
вiдносно операцiї перетину. Звiдси робимо висновок, що виконується i умова 2 твердження 1.
До того ж очевидно, що моноїд I(G) мiстить нуль (порожнє перетворення). Отже, має мiсце
iмплiкацiя (b)⇒ (c).
Теорему доведено.
2. Деякi властивостi переставного iнверсного моноїда I(G). У цьому пунктi ми перелi-
чимо низку властивостей переставного iнверсного моноїда I(G). Спочатку наведемо кiлька
означень. Частковий порядок Φ на довiльнiй напiвгрупi S називається стабiльним, якщо з умо-
ви (x, y) ∈ Φ випливає (zx, zy) ∈ Φ i (xz, yz) ∈ Φ для будь-якого z ∈ S. Частковий порядок
Ω на довiльнiй напiвгрупi S називається фундаментальним (див. [7] i [8] або [9]), якщо iснує
гомоморфiзм ξ напiвгрупи S у напiвгрупу PT (X) усiх часткових перетворень деякої множи-
ни X такий, що виконується еквiвалентнiсть (a, b) ∈ Ω ⇔ (a)ξ ⊆ (b)ξ. Легко показати, що
за цих умов частковий порядок Ω є стабiльним, а гомоморфiзм ξ — iзоморфiзмом. Якщо ζ —
фундаментальне вiдношення порядку на напiвгрупi S, то вiдношення порядку ζ−1 називається
антифундаментальним.
Твердження 2. Якщо група G є глобально-транзитивною, то будь-який стабiльний поря-
док на iнверсному моноїдi I(G) є фундаментальним або антифундаментальним.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
448 В. Д. ДЕРЕЧ
Доведення. Очевидно, що глобально-транзитивна група є транзитивною. Отже, згiдно з
твердженням 3 (див. [3]) будь-який стабiльний порядок на iнверсному моноїдi I(G) є фунда-
ментальним або антифундаментальним.
Далi, нехай S = (S, ·) — довiльна напiвгрупа. Зафiксуємо елемент a ∈ S i визначимо на
S нову операцiю ?a згiдно з правилом x ?a y = x · a · y. Легко перевiрити, що операцiя ?a
є асоцiативною. Напiвгрупа (S, ?a) називається варiантом напiвгрупи (S, ·) (див. [10, c. 237]).
Одне з найважливiших питань, яке виникає при вивченнi варiантiв напiвгрупи, формулюється
таким чином: нехай a i b — елементи напiвгрупи (S, ·). За яких умов напiвгрупи (S, ?a) i
(S, ?b) будуть iзоморфними? Для скiнченної симетричної iнверсної напiвгрупи ISn вiдповiдний
результат одержано в [11] (див. також [10, c. 237]). Сформулюємо його.
Теорема 2 ([11], теорема 1). Напiвгрупи (ISn, ?α) i (ISn, ?β) iзоморфнi тодi i лише тодi,
коли rank (α) = rank (β).
Має мiсце аналогiчний, але бiльш загальний результат.
Теорема 3 (див. [12], теорема 1). Нехай iнверсний моноїд S з групою оборотних елементiв
G задовольняє такi умови:
1) напiврешiтка iдемпотентiв моноїда має скiнченну довжину;
2) iдеали моноїда S лiнiйно впорядкованi вiдносно включення;
3) для будь-якого x ∈ S iснує такий елемент g ∈ G, що x ≤ g.
Тодi для будь-яких a i b напiвгрупи (S, ?a) i (S, ?b) iзоморфнi тодi i лише тодi, коли
rank (a) = rank (b).
Твердження 3. Нехай G — глобально-транзитивна пiдгрупа симетричної групи Sn. Напiв-
групи (I(G), ?α) i (I(G), ?β) iзоморфнi тодi i лише тодi, коли rank (α) = rank (β).
Доведення. Оскiльки iнверсний моноїд I(G) є скiнченним, то виконується умова 1 тео-
реми 3. Позаяк група G є глобально транзитивною, то, згiдно з теоремою 1, iдеали моноїда
I(G) лiнiйно впорядкованi вiдносно включення, тобто виконується умова 2 теореми 3. Умова
3 теореми 3 також виконується. Це безпосередньо випливає з означення iнверсного моноїда
I(G).
Iнверсна напiвгрупа називається фундаментальною, якщо будь-яка конгруенцiя, яка вклю-
чається в H-вiдношення Грiна, є вiдношенням рiвностi.
Твердження 4. Iнверсний моноїд I(G) є фундаментальним.
Доведення є безпосереднiм наслiдком твердження 1 статтi [3].
Щодо групи автоморфiзмiв iнверсного моноїда I(G), то має мiсце наступне твердження.
Твердження 5 (див. [3], твердження 5). Нехай G — довiльна пiдгрупа симетричної групи
Sn, тодi Aut (I(G)) ∼= N(G), де N(G) — нормалiзатор групи G в симетричнiй групi Sn.
Для симетричної iнверсної напiвгрупи I(Sn) опис вiдношення Грiна J є вiдомим (див.,
наприклад, [10], теорема 4.5.1). Аналогiчна характеристика вiдношення Грiна J має мiсце для
моноїда I(G) у випадку, коли група G є глобально-транзитивною. Оскiльки I(G) — скiнченна
напiвгрупа, то вiдношення Грiна D i J на нiй збiгаються.
Твердження 6. Нехай G — глобально-транзитивна пiдгрупа симетричної групи Sn. В iн-
версному моноїдi I(G) (α, β) належить D тодi i лише тодi, коли rank (α) = rank (β).
Доведення. Нехай rank (α) = rank (β). Позначимо dom (α) i dom (β) вiдповiдно через A i
B. Оскiльки група G є глобально-транзитивною, то знайдеться елемент ϕ ∈ I(G) такий, що
dom (ϕ) = B i im (ϕ) = A. Оскiльки ϕ◦α◦α−1◦ϕ−1 = ∆B, то β = ∆B◦β = ϕ◦α◦α−1◦ϕ−1◦β.
Отже, β ∈ I(G) ◦ α ◦ I(G). Звiдси I(G) ◦ β ◦ I(G) ⊂ I(G) ◦ α ◦ I(G). Зворотне включення
доводиться аналогiчно. Таким чином, (α, β) ∈ D.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
СТАБIЛЬНI КВАЗIПОРЯДКИ НА ДЕЯКИХ ПЕРЕСТАВНИХ IНВЕРСНИХ МОНОЇДАХ 449
Нехай тепер (α, β) ∈ D, тодi I(G) ◦α ◦ I(G) = I(G) ◦ β ◦ I(G). Отже, знайдуться елементи
λ, τ ∈ I(G) такi, що α = λ ◦ β ◦ τ. Звiдси rank (α) = rank (λ ◦ β ◦ τ) ≤ rank (λ ◦ β) ≤ rank (β).
Аналогiчно, rank (β) ≤ rank (α). Таким чином, rank (α) = rank (β).
3. Стабiльнi квазiпорядки на переставному iнверсному моноїдi I(G). Рефлексивне i
транзитивне бiнарне вiдношення на множинi X називають квазiпорядком. Зрозумiло, що на
алгебраїчних системах розглядають переважно стабiльнi квазiпорядки, тобто такi, якi узгод-
жуються з операцiями алгебраїчної системи. Серед стабiльних квазiпорядкiв особливе мiсце
займають конгруенцiї i порядки.
В цьому пунктi ми вимагаємо, щоб група G була глобально-транзитивною.
Нехай Σ — стабiльний квазiпорядок на I(G). Легко перевiрити, що I l = {f ∈ I(G) : (f, 0) ∈
∈ Σ} i Ir = {f ∈ I(G) : (0, f) ∈ Σ} є iдеалами напiвгрупи I(G). Отже, кожному стабiльному
квазiпорядку на I(G) вiдповiдає пара iдеалiв (I l, Ir). Згiдно з теоремою 1 iдеали iнверсного
моноїда I(G) утворюють ланцюг вiдносно включення. Тому (див. [5], теорема 2) кожний iдеал
напiвгрупи I(G) має форму It = {f ∈ I(G) : rank (f) ≤ t} (тут t — невiд’ємне цiле число).
Отже, iснують невiд’ємнi цiлi числа k i m такi, що I l = {f ∈ I(G) : rank (f) ≤ k} = Ik i
Ir = {f ∈ I(G) : rank (f) ≤ m} = Im. Впорядковану пару чисел (k,m) назвемо iндексом
квазiпорядку Σ i позначимо через ind (Σ).
Лема 1. Стабiльний квазiпорядок Σ на iнверсному моноїдi I(G) є вiдношенням рiвностi
тодi i лише тодi, коли ind (Σ) = (0, 0).
Доведення. Якщо Σ є вiдношенням рiвностi, то, очевидно, ind (Σ) = (0, 0).
Нехай тепер ind (Σ) = (0, 0). Припустимо, що квазiпорядок Σ не є рiвнiстю, тобто iснує
пара (ϕ, ξ) ∈ Σ така, що ϕ 6= ξ. Розглянемо два можливi випадки.
1-й випадок: dom (ϕ) = dom (ξ).
Оскiльки ϕ 6= ξ, то iснує елемент a ∈ N = {1, 2, 3, . . . , n} такий, що (a)ϕ 6= (a)ξ. Тодi((
a
a
)
◦ ϕ,
(
a
a
)
◦ ξ
)
∈ Σ або
((
a
(a)ϕ
)
,
(
a
(a)ξ
))
∈ Σ. Нехай (a)ϕ = b i (a)ξ = c. Оскiльки((
a
b
)
,
(
a
c
))
∈ Σ, то
((
a
b
)
◦
(
b
b
)
,
(
a
c
)
◦
(
b
b
))
∈ Σ. Позаяк b 6= c, то
((
a
b
)
, 0
)
∈ Σ, тодi
ind (Σ) 6= (0, 0). Суперечнiсть.
2-й випадок: dom (ϕ) 6= dom (ξ).
Нехай для конкретностi a ∈ dom (ϕ) i a 6∈ dom (ξ). Тодi
((
a
a
)
◦ ϕ,
(
a
a
)
◦ ξ
)
∈ Σ. Оскiльки(
a
a
)
◦ ξ = 0, то
((
a
a
)
◦ ϕ, 0
)
∈ Σ. Суперечнiсть.
Лема 2. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому ind (Σ) =
= (k,m). Вiдношення Σ є порядком тодi i лише тодi, коли k = 0 або m = 0.
Доведення. Нехай Σ — стабiльний порядок на I(G). Покажемо, що k = 0 або m = 0.
Припустимо протилежне, тобто k 6= 0 i m 6= 0. Оскiльки k 6= 0, то iснує елемент ϕ ∈ I(G)
такий, що rank (ϕ) = 1 i (ϕ, 0) ∈ Σ. Аналогiчно, позаяк m 6= 0, то iснує ρ ∈ I(G) такий, що
rank (ρ) = 1 i (0, ρ) ∈ Σ. Оскiльки I1 = I(G) ◦ ϕ ◦ I(G), то iснують α, β ∈ I(G) такi, що
α ◦ ϕ ◦ β = ρ. Таким чином, якщо (ϕ, 0) ∈ Σ, то (α ◦ ϕ ◦ β, 0) ∈ Σ, тобто (ρ, 0) ∈ Σ, а отже,
бiнарне вiдношення Σ не є антисиметричним. Суперечнiсть.
Доведемо зворотне твердження.
Якщо k = 0 i m = 0, то згiдно з попередньою лемою Σ є вiдношенням рiвностi.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
450 В. Д. ДЕРЕЧ
Нехай тепер k = 0 i m 6= 0. Доведемо, що вiдношення Σ є антисиметричним. Припустимо
протилежне, тобто iснують η, ξ ∈ I(G) такi, що (η, ξ) ∈ Σ, (ξ, η) ∈ Σ i η 6= ξ.
Якщо η = 0 або ξ = 0, то вiдразу одержуємо суперечнiсть.
Нехай тепер η 6= 0 i ξ 6= 0. Розглянемо можливi випадки.
1. Якщо dom (η) = dom (ξ), то iснує a ∈ dom (η) такий, що (a)η 6= (a)ξ. Позначимо (a)η i
(a)ξ вiдповiдно через b i c.Оскiльки (η, ξ) ∈ Σ, то
((
a
a
)
◦ η,
(
a
a
)
◦ ξ
)
∈ Σ.Отже,
((
a
b
)
,
(
a
c
))
∈
∈ Σ. Позаяк
(
a
c
)
◦
(
b
b
)
= 0, то
((
a
b
)
, 0
)
∈ Σ. З останнього випливає, що k 6= 0. Суперечнiсть.
2. Нехай dom (η) 6= dom (ξ). Припустимо, що x ∈ dom (η) i x /∈ dom (ξ), тодi
((
x
x
)
◦ η, 0
)
∈
∈ Σ. До того ж
(
x
x
)
◦ η 6= 0. Отже, k 6= 0. Суперечнiсть.
Припустимо тепер, що z ∈ dom (ξ) i z /∈ dom (η). Оскiльки (ξ, η) ∈ Σ, то
((
z
z
)
◦ ξ, 0
)
∈ Σ.
Позаяк
(
z
z
)
◦ ξ 6= 0, то k 6= 0. Суперечнiсть.
Лема 3. Якщо A i B — непорожнi скiнченнi множини, причому A ( B, то iснує множина
C така, що |B ∩ C| = |B| − 1 i |A ∩ C| = |A| − 1.
Доведення. Нехай a — довiльний елемент множини A. Для множини C = B−{a} очевидно
виконуються рiвностi |B ∩ C| = |B| − 1 i |A ∩ C| = |A| − 1.
Лема 4. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому ind (Σ) =
= (k,m). Якщо (η, ξ) ∈ Σ i rank (η) > k, то rank (η) ≤ rank (ξ).
Доведення. Припустимо, що rank (η) > rank (ξ). Позначимо dom (η) через A. Позаяк
(η, ξ) ∈ Σ, то (∆A◦η,∆A◦ξ) ∈ Σ. Очевидно, що rank (∆A◦η) = rank (η). Якщо rank (∆A◦ξ) ≤
≤ k, то одержуємо суперечнiсть.
Нехай тепер rank (∆A ◦ ξ) > k. Очевидно, що dom (∆A ◦ ξ) ( dom (∆A ◦ η) = dom (η).
Тодi згiдно з попередньою лемою iснує множина C (звiсно, що C ⊂ {1, 2, . . . , n}) така, що
| dom (∆A ◦ η) ∩C| = | dom (∆A ◦ η)| − 1 i |dom (∆A ◦ ξ) ∩C| = |dom (∆A ◦ ξ)| − 1. Оскiльки
(∆A ◦ η,∆A ◦ ξ) ∈ Σ, то (∆C ◦ ∆A ◦ η,∆C ◦ ∆A ◦ ξ) ∈ Σ. До того ж rank (∆C ◦ ∆A ◦ η) =
= rank (∆A ◦ η) − 1 i rank (∆C ◦∆A ◦ ξ) = rank (∆A ◦ ξ) − 1. Якщо rank (∆C ◦∆A ◦ ξ) ≤ k,
то одержуємо суперечнiсть. У випадку, коли rank (∆C ◦∆A ◦ ξ) > k, повторюємо попередню
дiю, i так далi, аж поки не приходимо до суперечностi.
Лема 5. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому ind (Σ) =
= (k,m). Якщо (η, ξ) ∈ Σ i rank (ξ) > m, то rank (ξ) ≤ rank (η).
Доведення аналогiчне доведенню попередньої леми.
Лема 6. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому ind (Σ) =
= (k,m). Якщо (η, ξ) ∈ Σ i rank (η) > max{k,m}, то rank (η) = rank (ξ).
Доведення. Згiдно з лемою 4
rank (η) ≤ rank (ξ). (1)
Припустимо, що rank (ξ) ≤ m, тодi rank (η) > rank (ξ). Повторюючи мiркування, що мали
мiсце при доведеннi леми 4, приходимо до суперечностi. Таким чином, rank (ξ) > m, а отже,
згiдно з лемою 5
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
СТАБIЛЬНI КВАЗIПОРЯДКИ НА ДЕЯКИХ ПЕРЕСТАВНИХ IНВЕРСНИХ МОНОЇДАХ 451
rank (ξ) ≤ rank (η). (2)
З (1) i (2) випливає рiвнiсть rank (η) = rank (ξ).
Лема 7. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому ind (Σ) =
= (k,m). Якщо (η, ξ) ∈ Σ i rank (ξ) > max{k,m}, то rank (η) = rank (ξ).
Доведення аналогiчне доведенню леми 6.
Лема 8. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому ind (Σ) =
= (k,m). Якщо (η, ξ) ∈ Σ ∩ (Dr ×Dr) (тут Dr — множина елементiв моноїда I(G) рангу r)
i r > min{k,m}, то im (η) = im (ξ).
Доведення. Нехай для конкретностi k ≤ m. Позначимо im (η) через B. Припустимо, що
im (ξ) 6= B. Оскiльки (η, ξ) ∈ Σ, то (η ◦∆B, ξ ◦∆B) ∈ Σ. Звiдки rank (η) > rank (ξ ◦∆B), що
суперечить лемi 4.
Якщо ж припустити, що m ≤ k, то аналогiчним чином ми приходимо до суперечностi з
лемою 5.
Лема 9. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому ind (Σ) =
= (k,m). Якщо (η, ξ) ∈ Σ ∩ (Dr ×Dr) (тут Dr — множина елементiв моноїда I(G) рангу r)
i r > min{k,m}, то dom (η) = dom (ξ).
Доведення. Нехай для конкретностi k ≤ m. Позначимо dom (η) через A. Припустимо, що
dom (ξ) 6= A. Оскiльки (η, ξ) ∈ Σ, то (∆A ◦ η,∆A ◦ ξ) ∈ Σ. Звiдси rank (η) > rank (∆A ◦ ξ), що
суперечить лемi 4.
Якщо ж припустити, що m ≤ k, то аналогiчним чином приходимо до суперечностi з
лемою 5.
Лема 10. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому
ind (Σ) = (k,m). Якщо (η, ξ) ∈ Σ ∩ (Dr × Dr) (тут Dr — множина елементiв моноїда
I(G) рангу r) i r > min{k,m}, то (η, ξ) ∈ H.
Доведення є безпосереднiм наслiдком двох попереднiх лем.
Лема 11. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому
ind (Σ) = (k,m). Якщо (η, ξ) ∈ Σ ∩ (Dr × Dr) (тут Dr — множина елементiв моноїда
I(G) рангу r) i r ≥ min{k,m}+ 2, то η = ξ.
Доведення. З лем 8 i 9 випливає dom (η) = dom (ξ) i im (η) = im (ξ). Нехай x — довiльний
елемент, що належить dom (η). Позначимо множину dom (η) − {x} через B. Оскiльки (∆B ◦
◦η,∆B ◦ξ) ∈ Σ i rank (∆B ◦η) = r−1 > min{k,m}, то згiдно з лемою 8 im (∆B ◦η) = im (∆B ◦
◦ ξ). Крiм того, очевидно, що im (η) = im (∆B ◦ η) ∪ {(x)η} i im (ξ) = im (∆B ◦ ξ) ∪ {(x)ξ}.
Звiдси випливає, що (x)η = (x)ξ. Отже, η = ξ.
Лема 12. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому
ind (Σ) = (k,m) i k 6= m. Якщо (η, ξ) ∈ Σ, rank (η) > max{k,m} або rank (ξ) > max{k,m},
то η = ξ.
Доведення. З лем 6 i 7 випливає rank (η) = rank (ξ). Оскiльки k 6= m, то rank (η) =
= rank (ξ) ≥ min{k,m}+ 2. Отже, згiдно з лемою 11 η = ξ.
Лема 13. Нехай Σ — стабiльний квазiпорядок на iнверсному моноїдi I(G), причому
ind (Σ) = (k,m). Якщо (η, ξ) ∈ Σ i k + 2 ≤ rank (η) < rank (ξ) ≤ m, то η ⊂ ξ.
Доведення. Позначимо dom (η) через A. Оскiльки (η, ξ) ∈ Σ, то (∆A◦η,∆A◦ξ) ∈ Σ. Згiдно
з лемою 4 rank (η) ≤ rank (∆A ◦ ξ). Крiм того, rank (∆A ◦ ξ) ≤ rank (∆A) = rank (η). Отже,
rank (η) = rank (∆A ◦ ξ). Тепер, застосовуючи лему 11, одержуємо η = ∆A ◦ ξ. З останньої
рiвностi випливає η ⊂ ξ.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
452 В. Д. ДЕРЕЧ
Лема 14. Нехай Ω — стабiльне бiнарне вiдношення на iнверсному моноїдi I(G). Якщо
(α, β) ∈ Ω i α ⊆ β, то (α−1, β−1) ∈ Ω.
Доведення. Оскiльки (α, β) ∈ Ω, то (β−1 ◦ α ◦ β−1, β−1 ◦ β ◦ β−1) ∈ Ω, тобто (β−1 ◦ α ◦
◦ β−1, β−1) ∈ Ω. Позаяк α ⊆ β, то β−1 ◦ α ◦ β−1 = α−1. Отже, (α−1, β−1) ∈ Ω.
Лема 15. Нехай Ω — стабiльний квазiпорядок на iнверсному моноїдi I(G). Якщо (α, β) ∈ Ω
i α ⊆ β, то (α ◦ α−1, β ◦ β−1) ∈ Ω.
Доведення. Оскiльки (α, β) ∈ Ω, то (α ◦ α−1, β ◦ α−1) ∈ Ω. За попередньою лемою
(α−1, β−1) ∈ Ω. Звiдси (β ◦ α−1, β ◦ β−1) ∈ Ω. Враховуючи транзитивнiсть Ω, одержуємо
(α ◦ α−1, β ◦ β−1) ∈ Ω.
4. Конгруенцiї на переставному iнверсному моноїдi I(G). В цьому пунктi наведемо
опис конгруенцiй на переставному iнверсному моноїдi I(G). Отже, нехай G — глобально-
транзитивна пiдгрупа симетричної групи Sn. Позначимо через Θ довiльну конгруенцiю на
I(G), iндекс якої дорiвнює (k,m).Оскiльки конгруенцiя є симетричним бiнарним вiдношенням,
то, очевидно, k = m. Тому далi замiсть ind (Θ) = (k, k) будемо писати ind (Θ) = k. Якщо
k = n, то, очевидно, конгруенцiя Θ є тотальною, тобто Θ = I(G)× I(G). Нехай тепер k < n.
Оскiльки iнверсний моноїд I(G) є переставним i мiстить нуль, то згiдно з теоремою 4 (див.
[5]) конгруенцiя Θ має форму Θ = Ik × Ik ∪ Ω, де Ik — iдеал напiвгрупи I(G),Ω ⊆ H (H —
вiдношення Грiна).
Лема 16. Нехай G — глобально-транзитивна пiдгрупа симетричної групи Sn i Θ — кон-
груенцiя на I(G), причому ind (Θ) = k. Якщо (η, ξ) ∈ Θ i rank (η) = k + 1, то (η, ξ) ∈ H, де
H— вiдношення Грiна.
Доведення. Згiдно з лемою 6 rank (η) = rank (ξ). Застосовуючи лему 10, одержуємо (η, ξ) ∈
∈ H.
Лема 17. Нехай G — глобально-транзитивна пiдгрупа симетричної групи Sn i Θ — кон-
груенцiя на I(G), причому ind (Θ) = k. Якщо (η, ξ) ∈ Θ i rank (η) ≥ k + 2, то η = ξ.
Доведення. Згiдно з лемою 6 rank (η) = rank (ξ). Застосовуючи лему 11, одержуємо рiвнiсть
η = ξ.
Нехай G — глобально-транзитивна пiдгрупа симетричної групи Sn. Розглянемо iнверсний
моноїд I(G). Нехай k — невiд’ємне цiле число таке, що k < n. Легко перевiрити, що фактор-
напiвгрупа Ik+1/Ik є напiвгрупою Брандта. Нехай σ — конгруенцiя, вiдмiнна вiд унiверсальної
на фактор-напiвгрупi Ik+1/Ik. Зазначимо, що опис конгруенцiй на напiвгрупi Брандта є вiдомим
(див. [13]). На моноїдi I(G) визначимо бiнарне вiдношення Σ таким чином:
Σ = Ik × Ik ∪ ((Dk+1 ×Dk+1) ∩ σ) ∪4,
де Dk+1 = {ϕ ∈ I(G) : rank (ϕ) = k + 1} i ∆ — вiдношення рiвностi на I(G).
Теорема 4. Нехай G — глобально-транзитивна пiдгрупа симетричної групи Sn. Бiнарне
вiдношення Σ є конгруенцiєю на iнверсному моноїдi I(G). Кожна вiдмiнна вiд унiверсальної
конгруенцiя на I(G) має таку форму.
Доведення. Легко перевiрити, що бiнарне вiдношення Σ є еквiвалентнiстю на iнверсному
моноїдi I(G). Покажемо стабiльнiсть еквiвалентностi Σ. Нехай (ψ,ϕ) ∈ Σ. У випадку, коли
ψ = ϕ або (ψ,ϕ) ∈ Ik × Ik, зрозумiло, що (ψ ◦ η, ϕ ◦ η) ∈ Σ i (η ◦ ψ, η ◦ ϕ) ∈ Σ для довiльного
η ∈ I(G). Припустимо тепер, що (ψ,ϕ) ∈ (Dk+1×Dk+1)∩σ. Тодi згiдно з теоремою 4 (див. [5])
dom (ψ) = dom (ϕ) i im (ψ) = im (ϕ). Якщо елемент ξ ∈ I(G) такий, що rank (ψ ◦ ξ) ≤ k,
то rank (ϕ ◦ ξ) ≤ k. Отже, (ψ ◦ ξ, ϕ ◦ ξ) ∈ Ik × Ik ⊂ Σ. Аналогiчно (ξ ◦ ψ, ξ ◦ ϕ) ∈ Σ. Тепер
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
СТАБIЛЬНI КВАЗIПОРЯДКИ НА ДЕЯКИХ ПЕРЕСТАВНИХ IНВЕРСНИХ МОНОЇДАХ 453
розглянемо випадок, коли rank (ψ ◦ ξ) = k + 1. Тодi i rank (ϕ ◦ ξ) = k + 1. Очевидно, що
ψ ◦ ξ = ψ ◦ ψ−1 ◦ ψ ◦ ξ i ϕ ◦ ξ = ϕ ◦ ϕ−1 ◦ ϕ ◦ ξ. До того ж ψ−1 ◦ ψ ◦ ξ = ϕ−1 ◦ ϕ ◦ ξ i
rank (ψ−1 ◦ ψ ◦ ξ) = k+ 1. Враховуючи, що (ψ,ϕ) ∈ (Dk+1 ×Dk+1)∩ σ, робимо висновок, що
(ψ ◦ ξ, ϕ◦ ξ) ∈ (Dk+1×Dk+1)∩σ. Аналогiчно, (ξ ◦ψ, ξ ◦ϕ) ∈ (Dk+1×Dk+1)∩σ. Таким чином,
Σ — конгруенцiя на I(G).
Нехай тепер Θ — конгруенцiя, вiдмiнна вiд унiверсальної на iнверсному моноїдi I(G).Нехай
ind (Θ) = k. Тодi Ik × Ik ⊂ Θ. Далi, якщо (ρ, τ) ∈ Θ i rank (ρ) > k + 1, то згiдно з лемою
17 ρ = τ. Крiм того, конгруенцiя Θ iндукує конгруенцiю Θ∗ на фактор-напiвгрупi Ik+1/Ik,
а саме, Θ∗ = (Θ ∩ (Dk+1 × Dk+1)) ∪ {(0, 0)}, де 0 – нуль фактор-напiвгрупи Ik+1/Ik. Отже,
Θ = Ik × Ik ∪ ((Dk+1 ×Dk+1) ∩Θ∗) ∪4.
Теорему доведено.
Таким чином, у випадку, коли група G є глобально-транзитивною пiдгрупою симетрич-
ної групи Sn, опис конгруенцiй iнверсного моноїда I(G) аналогiчний опису конгруенцiй на
скiнченнiй симетричнiй iнверснiй напiвгрупi (див. [14]). У свою чергу результат Лiбера [14]
є аналогом результату Мальцева, одержаного в [15] для симетричної напiвгрупи усiх повних
перетворень довiльної множини.
5. Стабiльнi порядки на iнверсному моноїдi I(An). Як i в попередньому пунктi, вва-
жаємо, що група G(G ⊂ Sn) є глобально-транзитивною, а отже, згiдно з теоремою 1 iнверсний
моноїд I(G) є переставним. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(G) i
ind (Ω) = (k,m). Тодi згiдно з лемою 2 k = 0 або m = 0. Якщо k = 0 i m = 0, то згiдно з
лемою 1 стабiльний порядок Ω є вiдношенням рiвностi.
Лема 18. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(G), причому ind (Ω) =
= (0,m). Якщо (η, τ) ∈ Ω i rank (η) > m, то η = τ.
Доведення. Якщо m = 0, то згiдно з лемою 1 вiдношення Ω є рiвнiстю. Отже, η = τ. Якщо
ж 0 6= m, то за лемою 12 знову η = τ.
Лема 19. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(G). Якщо ind (Ω) =
= (0,m), де (m 6= 0) i (η, τ) ∈ Ω, то η ⊂ τ.
Доведення. Якщо rank (η) = 0, то η = ∅. Отже, η ⊂ τ. Нехай тепер rank (η) 6= 0. Припу-
стимо, що η * τ. Тодi iснує елемент
(
x
y
)
∈ I(G) такий, що
(
x
y
)
∈ η i
(
x
y
)
/∈ τ. Оскiльки
(η, τ) ∈ Ω, то
((
x
x
)
◦ η,
(
x
x
)
◦ τ
)
∈ Ω або
((
x
y
)
,
(
x
x
)
◦ τ
)
∈ Ω.
Якщо x /∈ dom (τ), то
(
x
x
)
◦ τ = ∅. Отже,
((
x
y
)
,∅
)
∈ Ω, а це суперечить умовi (адже
k = 0).
Якщо ж x ∈ dom (τ), то
(
x
x
)
◦τ =
(
x
z
)
(де за припущенням z 6= y). Отже,
((
x
y
)
,
(
x
z
))
∈
∈ Ω. Тому
((
x
y
)
◦
(
y
y
)
,
(
x
z
)
◦
(
y
y
))
∈ Ω. Звiдси
((
x
y
)
,∅
)
∈ Ω, що суперечить умовi.
Таким чином, η ⊆ τ.
Лема 20. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(G), причому ind (Ω) =
= (0,m). Якщо (η, ϕ) ∈ Ω, то (η ◦ η−1, ϕ ◦ ϕ−1) ∈ Ω i (η−1 ◦ η, ϕ−1 ◦ ϕ) ∈ Ω.
Доведення. Згiдно з лемою 19 η ⊂ ϕ. Застосовуючи лему 15, одержуємо (η ◦η−1, ϕ◦ϕ−1) ∈
∈ Ω. Аналогiчно (η−1 ◦ η, ϕ−1 ◦ ϕ) ∈ Ω.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
454 В. Д. ДЕРЕЧ
Далi будемо розглядати стабiльнi порядки на iнверсному моноїдi I(An), де An — альтерна-
тивна група, причому n ≥ 4.
Лема 21. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(An), причому ind (Ω) =
= (0,m). Припустимо, що (∆B,∆B∗) ∈ Ω. Якщо |B| = |X|, |B∗| = |X∗| i X ⊂ X∗, то
(∆X ,∆X∗) ∈ Ω.
Доведення. Оскiльки (∆B,∆B∗) ∈ Ω, то згiдно з лемою 19 має мiсце включення ∆B ⊂ ∆B∗ .
Звiдси B ⊂ B∗. Нехай елемент α ∈ Sn такий, що (X)α = B i (X∗)α = B∗. Розглянемо можливi
випадки.
1-й випадок: α ∈ An, тобто α — парна перестановка. Тодi (α ◦ ∆B, α ◦ ∆B∗) ∈ Ω. Згiдно
з лемою 20 (α ◦ ∆B ◦ α−1, α ◦ ∆B∗ ◦ α−1) ∈ Ω. Легко перевiрити, що α ◦ ∆B ◦ α−1 = ∆X i
α ◦∆B∗ ◦ α−1 = ∆X∗ . Отже, (∆X ,∆X∗) ∈ Ω.
2-й випадок: α /∈ An, тобто α — непарна перестановка.
а) Нехай |X| ≥ 2. Тодi iснують x1, x2 ∈ X i x1 6= x2. Позначимо (x1)α через b1 i (x2)α
через b2. Визначимо перестановку ξ ∈ Sn таким чином: (x)ξ = (x)α, якщо x /∈ {x1, x2}. Крiм
того, (x1)ξ = b2 i (x2)ξ = b1. Iншими словами, перестановку ξ ми одержали з перестановки
α, помiнявши мiсцями два елементи другого рядка перестановки α. Як вiдомо, при такiй дiї
парнiсть перестановки змiнюється на протилежну, тобто перестановка ξ є парною. До того ж
очевидно, що (X)ξ = B i (X∗)ξ = B∗. Далi дiємо так само, як i в першому випадку.
b) Нехай |X∗ −X| ≥ 2. Тодi iснують x1, x2 ∈ X∗ −X i x1 6= x2. Далi мiркуємо так само,
як i у випадку а).
с) Нехай |X| < 2 i |X∗ − X| < 2. Оскiльки ми припустили, що n ≥ 4, то |N − X∗| ≥ 2
(нагадаємо, що N = {1, 2, 3, . . . , n}). Отже, iснують a1, a2 ∈ N−X∗ i a1 6= a2. Далi дiємо так
само, як i в пунктi а).
Зазначимо, що при n = 3, тобто для iнверсного моноїда I(A3), щойно доведена лема не
виконується.
Лема 22. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(An), причому ind (Ω) =
= (0,m). Припустимо, що (α, β) ∈ Ω. Якщо rank (η) = rank (α), rank (τ) = rank (β) i η ⊂ τ,
то (η, τ) ∈ Ω.
Доведення. Згiдно з лемою 20 (α ◦ α−1, β ◦ β−1) ∈ Ω. Оскiльки η ⊂ τ, то ∆dom (η) ⊂
⊂ ∆dom (τ). До того ж, | dom (η)| = | dom (α)| i |dom (τ)| = |dom (β)|. Отже, згiдно з лемою
21 (∆dom (η),∆dom (τ)) ∈ Ω. Звiдси випливає, що (∆dom (η) ◦ τ,∆dom (τ) ◦ τ) ∈ Ω. Оскiльки
∆dom (η) ◦ τ = η i ∆dom (τ) ◦ τ = τ, то (η, τ) ∈ Ω.
Лема 23. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(An), причому ind (Ω) =
= (0,m). Якщо (∆A,∆B) ∈ Ω i (∆C ,∆F ) ∈ Ω, крiм того |B| = |C|, то iснує множина
M(M ⊂ N) така, що |M | = |F | i (∆A,∆M ) ∈ Ω.
Доведення. Оскiльки групаAn є глобально-транзитивною i |B| = |C|, то iснує перестановка
ϕ ∈ An така, що (B)ϕ = C. Позаяк (∆C ,∆F ) ∈ Ω, то (ϕ ◦ ∆C , ϕ ◦ ∆F ) ∈ Ω. Зрозумiло, що
dom (ϕ ◦ ∆C) = B i rank (ϕ ◦ ∆F ) = |F |. Згiдно з лемою 19 ϕ ◦ ∆C ⊂ ϕ ◦ ∆F . Тепер,
застосовуючи лему 15, одержуємо (ϕ ◦∆C ◦ (ϕ ◦∆C)−1, ϕ ◦∆F ◦ (ϕ ◦∆F )−1)) ∈ Ω. Оскiльки
dom (ϕ ◦ ∆C) = B, то ϕ ◦ ∆C ◦ (ϕ ◦ ∆C)−1 = ∆B. Отже, (∆B, ϕ ◦ ∆F ◦ ϕ−1) ∈ Ω. Крiм
того, rank (ϕ ◦ ∆F ◦ ϕ−1) = rank (ϕ ◦ ∆F ) = |F |. Оскiльки вiдношення Ω є транзитивним,
то (∆A, ϕ ◦ ∆F ◦ ϕ−1) ∈ Ω. Позначимо dom (ϕ ◦ ∆F ◦ ϕ−1) через M. Очевидно, що ∆M =
= ϕ ◦∆F ◦ ϕ−1. Отже, (∆A,∆M ) ∈ Ω.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
СТАБIЛЬНI КВАЗIПОРЯДКИ НА ДЕЯКИХ ПЕРЕСТАВНИХ IНВЕРСНИХ МОНОЇДАХ 455
Лема 24. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(An), причому ind (Ω) =
= (0,m). Якщо (α, β) ∈ Ω, (τ, ρ) ∈ Ω, де rank (α) = a, rank (β) = rank (τ) = b i rank (ρ) = r,
то (Da ×Dr) ∩ ω ⊂ Ω, де ω — канонiчний порядок на I(An).
Доведення. Нехай (ϕ,ψ) ∈ (Da×Dr)∩ω, тобто rank (ϕ) = a, rank (ψ) = r i ϕ ⊆ ψ. Згiдно
з лемою 19 α ⊂ β i τ ⊂ ρ. Використовуючи лему 15, одержуємо (α ◦ α−1, β ◦ β−1) ∈ Ω i
(τ ◦ τ−1, ρ ◦ ρ−1) ∈ Ω. Позначимо dom (α ◦ α−1) через A, тодi α ◦ α−1 = ∆A. Згiдно з лемою
23 iснує множина R (R ⊂ N) така, що (∆A,∆R) ∈ Ω, причому rank (∆A) = rank (α ◦ α−1) =
= rank (α) = a i rank (∆R) = rank (ρ) = r. Залишається скористатися лемою 22, щоб одержати
(ϕ,ψ) ∈ Ω.
Лема 25. Нехай Ω — стабiльний порядок на iнверсному моноїдi I(An), причому ind (Ω) =
= (0,m). Якщо (α, β) ∈ Ω i rank (α) = r, rank (β) = r + k (k 6= 0), то (Ir × Ir+k) ∩ ω ⊂ Ω, де
ω — канонiчний порядок на iнверсному моноїдi I(An).
Доведення. По-перше, зрозумiло, що ({0} × Im) ⊂ Ω. Далi будемо вважати, що r 6= 0.
Згiдно з лемами 19 i 20 α ⊂ β i (α ◦ α−1, β ◦ β−1) ∈ Ω. Нехай dom (α) = {x1, x2, . . . , xr}
i dom (β) = {x1, x2, . . . , xr, xr+1, . . . , xr+k}. Припустимо, що τ, η ∈ I(An), причому τ ⊂ η,
rank (τ) = s, rank (η) = l (де s ≤ r, s < l ≤ r + k ≤ m). Покажемо, що (τ, η) ∈ Ω. Якщо
rank (τ) = r i rank (η) = r + k, то згiдно з лемою 22 (τ, η) ∈ Ω. Позначимо через Bs,t
множину {x1, x2, . . . , xs, xr+1, . . . , xr+t}, де {x1, x2, . . . , xs} ⊂ dom (α) i 1 ≤ t ≤ k. Очевидно,
Bs,t ⊂ dom (β).
Нехай rank (τ) = r−1. Позаяк (α◦α−1, β◦β−1) ∈ Ω, то (∆Br−1,t◦α◦α−1,∆Br−1,t◦β◦β−1) ∈
∈ Ω, де 1 ≤ t ≤ k. Зрозумiло, що rank (∆Br−1,t ◦ α ◦ α−1) = r − 1 i rank (∆Br−1,t ◦ β ◦ β−1) =
= r−1+t. Отже, якщо rank (η) = r−1+t (де 1 ≤ t ≤ k), то, застосовуючи лему 22, одержуємо
(τ, η) ∈ Ω. Розглянемо випадок, коли rank (η) = r + k. Оскiльки (α ◦ α−1, β ◦ β−1) ∈ Ω, то
(∆Br−1,1 ◦ α ◦ α−1,∆Br−1,1 ◦ β ◦ β−1) ∈ Ω. (3)
Очевидно, що rank (∆Br−1,1 ◦ α ◦ α−1) = r− 1 i rank (∆Br−1,1 ◦ β ◦ β−1) = r. Використовуючи
спiввiдношення 3 i умову (rank (α) = r i rank (β) = r + k), а також лему 24, одержуємо
(τ, η) ∈ Ω.
Нехай тепер rank (τ) = r−2. Оскiльки (α◦α−1, β ◦β−1) ∈ Ω, то (∆Br−2,t ◦α◦α−1,∆Br−2,t ◦
◦β◦β−1) ∈ Ω. Зрозумiло, що rank (∆Br−2,t ◦α◦α−1) = r−2 i rank (∆Br−2,t ◦β◦β−1) = r−2+t.
Отже, якщо rank (η) = r−2+t (де 1 ≤ t ≤ k), то, застосовуючи лему 22, одержуємо (τ, η) ∈ Ω.
Тепер розглянемо випадок, коли rank (η) = r − 1 + k. Оскiльки (α ◦ α−1, β ◦ β−1) ∈ Ω, то
(∆Br−2,1 ◦ α ◦ α−1,∆Br−2,1 ◦ β ◦ β−1) ∈ Ω. (4)
Очевидно, що rank (∆Br−2,1 ◦α◦α−1) = r−2 i rank (∆Br−2,1 ◦β◦β−1) = r−1. Використовуючи
спiввiдношення (4) i спiввiдношення
(∆Br−1,k
◦ α ◦ α−1,∆Br−1,k
◦ β ◦ β−1) ∈ Ω (5)
(зазначимо, що rank (∆Br−1,k
◦ α ◦ α−1) = r − 1 i rank (∆Br−1,k
◦ β ◦ β−1) = r − 1 + k) i
застосовуючи лему 24, одержуємо (τ, η) ∈ Ω. Розглянемо випадок, коли rank (η) = r + k.
Зрозумiло, що (∆Br−1,1 ◦ α ◦ α−1,∆Br−1,1 ◦ β ◦ β−1) ∈ Ω, rank (∆Br−1,1 ◦ α ◦ α−1) = r − 1 i
rank (∆Br−1,1 ◦ β ◦ β−1) = r. Крiм того, за умовою rank (α) = r i rank (β) = r+ k. З огляду на
леми 22 i 24 одержуємо (Dr−2 ×Dr) ∩ ω ⊂ Ω i (Dr ×Dr+k) ∩ ω ⊂ Ω. Звiдси (τ, η) ∈ Ω.
Всi iншi випадки (тобто, коли rank (τ) = r − 3, r − 4, . . . , 1) обґрунтовуються аналогiчно.
Тепер можемо сформулювати основний результат цього пункту.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
456 В. Д. ДЕРЕЧ
Теорема 5. Кожнiй послiдовностi невiд’ємних цiлих чисел 0 < k1 < k2 < . . . < kr < lr <
< lr−1 < . . . < l1 < m ≤ n, m ≥ 1, на iнверсному моноїдi I(An), n ≥ 4, вiдповiдає стабiльний
порядок Σ = (∆∪ ({0}× Im)∪ (Ik1 × Il1)∪ (Ik2 × Il2)∪ . . .∪ (Ikr × Ilr))∩ω (де ω — канонiчний
порядок на I(An).
Будь-який вiдмiнний вiд вiдношення рiвностi стабiльний порядок на I(An), iндекс якого
дорiвнює (0,m), має таку форму.
Доведення. Спочатку покажемо, що бiнарне вiдношення Σ є стабiльним вiдношенням по-
рядку. Рефлексивнiсть i антисиметричнiсть вiдношення Σ є очевидними. Покажемо його транзи-
тивнiсть. Нехай (α, β) ∈ (Iki×Ili)∩ω i (β, ξ) ∈ (Ikj×Ilj )∩ω. Припустимо, що ki < kj < lj < li.
Оскiльки ξ ∈ Ilj , то rank (ξ) ≤ lj < li. Отже, (α, ξ) ∈ (Iki × Ili)∩ω. Розглянемо тепер випадок,
коли kj < ki < li < lj . Позаяк β ∈ Ikj , то rank (β) ≤ kj . Оскiльки α ⊂ β, то rank (α) ≤ kj .
Звiдси (α, ξ) ∈ (Ikj × Ilj ) ∩ ω. Легко встановити, що порядок Σ є стабiльним.
Тепер покажемо, що будь-який стабiльний порядок (вiдмiнний вiд рiвностi) на iнверсному
моноїдi I(An) має форму Σ. Отже, нехай Ω — стабiльний порядок на iнверсному моноїдi I(An),
причому ind (Ω) = (0,m). Нагадаємо (див. лему 1), якщо m = 0, то Ω є вiдношенням рiвностi.
Далi будемо вважати, що m 6= 0. Серед усiх бiнарних вiдношень, якi мають форму (Ia× Ib)∩ω
(де 0 ≤ a < b ≤ m) i включаються в Ω, розглянемо максимальнi: {0}×Im, (Ik1×Il1)∩ω, (Ik2×
×Il2)∩ω, . . . , (Ikr×Ilr)∩ω, де 0 < k1 < k2, . . . , < kr < lr < lr−1 <, . . . , < l1 < m. Тодi бiнарне
вiдношення ∆ ∪ ({0} × Im) ∪
⋃r
i=1 ((Iki × lli) ∩ ω) збiгається з Ω. Дiйсно, якщо (τ, ζ) ∈ Ω, де
τ 6= ζ, rank (τ) = t, rank (ζ) = z, то згiдно з лемою 25 (It× Iz)∩ω ⊂ Ω. Зрозумiло, що бiнарне
вiдношення (It × Iz) ∩ ω включається в деяке максимальне вiдношення (Iki × Ili) ∩ ω. Отже,
(τ, ζ) ∈ Ω.
Теорему доведено.
Зауваження 1. Конструкцiя будь-якого стабiльного порядку на iнверсному моноїдi I(An)
цiлком аналогiчна конструкцiї довiльного порядку на скiнченнiй симетричнiй iнверснiй напiв-
групi ISn (див. [16]), однак доведення рiзняться (див. лему 21), оскiльки при доведеннi основної
теореми статтi [16] неявно використано той факт, що симетрична група Sn є n-транзитивною.
Як вiдомо, альтернативна група An є (n− 2)-транзитивною.
Зауваження 2. Стабiльний порядок Ψ на I(An), iндекс якого (m, 0), є оберненим до ста-
бiльного порядку Ψ−1, iндекс якого (0,m).
1. Leech J. Inverse monoids with a natural semilattice ordering // Proc. London Math. Soc. – 1995. – 70, № 3. –
P. 146 – 182.
2. Lipscomb S. L. The alternating semigroups: generators and congruences //Semigroup Forum. – 1992. – 44. – P. 96 –
106.
3. Дереч В. Д. Про один клас розкладних i фундаментальних iнверсних моноїдiв // Укр. мат. журн. – 2013. – 65,
№ 6. – С. 780 – 786.
4. Дереч В. Д. Характеристика напiврешiтки iдемпотентiв переставної iнверсної напiвгрупи скiнченного рангу з
нулем // Укр. мат. журн. – 2007. – 59, № 10. – С. 1353 – 1362.
5. Дереч В. Д. Конгруенцiї переставної iнверсної напiвгрупи скiнченного рангу // Укр. мат. журн. – 2005. – 57,
№ 4. – С. 469 – 473.
6. Hamilton H. Permutability of congruences on commutative semigroups // Semigroup Forum. – 1975. – 10. – P. 55 – 66.
7. Вагнер В. В. Представление упорядоченных полугрупп // Мат. сб. – 1956. – 38, № 2. – С. 203 – 240.
8. Шайн Б. М. Представление упорядоченных полугрупп // Мат. сб. – 1964. – 65, № 2. – С. 188 – 197.
9. Goberstein S. M. Fundamental order relations on inverse semigroups and on their generalizations // Semigroup
Forum. – 1980. – 21. – P. 285 – 328.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
СТАБIЛЬНI КВАЗIПОРЯДКИ НА ДЕЯКИХ ПЕРЕСТАВНИХ IНВЕРСНИХ МОНОЇДАХ 457
10. Ganyushkin O., Mazorchuk V. Classical finite transformation semigroups. An introduction. – Springer-Verlag, 2009. –
xii + 314 p.
11. Цяпута Г. Ю. Напiвгрупи перетворень iз деформованим множенням // Вiсн. Київ. ун-ту. Сер. фiз.-мат. науки. –
2003. – № 3. – С. 82 – 88.
12. Дереч В. Д. Варiанти iнверсних напiвгруп скiнченного рангу // Вiсн. Київ. ун-ту. Сер. фiз.-мат. науки. – 2008. –
№ 19/20. – С. 80 – 83.
13. Клиффорд А., Престон Г. Алгебраическая теория полугрупп: В 2 т. – М.: Мир, 1972. – Т. 1. – 286 с; Т. 2. –
422 с.
14. Либер А. Е. О симметрических обобщенных группах // Мат. сб. – 1953. – 33, № 3. – С. 531 – 544.
15. Мальцев А. И. Симметрические группоиды // Мат. сб. – 1952. – 31, № 1. – С. 136 – 151.
16. Могилевский М. Г. Отношения порядка на симметрической инверсной полугруппе // Теория полугрупп и ее
приложения. – 1974. – Вып. 3. – С. 63 – 70.
Одержано 05.06.13
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
|
| id | umjimathkievua-article-2147 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:19:35Z |
| publishDate | 2014 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/55/f0165d7fb722a62fc7932fc573030255.pdf |
| spelling | umjimathkievua-article-21472019-12-05T10:25:15Z Stable Quasiorderings on Some Permutable Inverse Monoids Стабільні квазіпорядки на деяких переставних інверсних моноїдах Derech, V. D. Дереч, В. Д. Let G be an arbitrary group of bijections on a finite set. By I(G), we denote the set of all injections each of which is included in a bijection from G. The set I(G) forms an inverse monoid with respect to the ordinary operation of composition of binary relations. We study different properties of the semi-group I(G). In particular, we establish necessary and sufficient conditions for the inverse monoid I(G) to be permutable (i.e., ξ ○ φ = φ ○ ξ for any pair of congruences on I(G)). In this case, we describe the structure of each congruence on I(G). We also describe the stable orderings on I(A n ), where A n is an alternating group. Пусть $G$ — произвольная группа биекций на конечном множестве. Обозначим через $I(G)$ множество всех инъекций, каждая из которых включается в биекцию из $G$. Множество $I(G)$ относительно обычной операции композиции бинарных отношений образует инверсный моноид. В данной статье изучаются различные свойства полугруппы $I(G)$. В частности, установлены необходимые и достаточные условия для того, чтобы инверсный моноид $I(G)$ был перестановочным (т. е. $ξ ○ φ = φ ○ ξ$ для любой пары конгруэнций $ξ, φ$ на $I(G)$), и в этом случае описана структура каждой конгруэнции на $I(G)$. Приведено описание стабильных порядков на $I(A_n)$, где $A_n$ — альтернативная группа. Institute of Mathematics, NAS of Ukraine 2014-04-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/2147 Ukrains’kyi Matematychnyi Zhurnal; Vol. 66 No. 4 (2014); 445–457 Український математичний журнал; Том 66 № 4 (2014); 445–457 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/2147/1296 https://umj.imath.kiev.ua/index.php/umj/article/view/2147/1297 Copyright (c) 2014 Derech V. D. |
| spellingShingle | Derech, V. D. Дереч, В. Д. Stable Quasiorderings on Some Permutable Inverse Monoids |
| title | Stable Quasiorderings on Some Permutable Inverse Monoids |
| title_alt | Стабільні квазіпорядки на деяких переставних інверсних моноїдах |
| title_full | Stable Quasiorderings on Some Permutable Inverse Monoids |
| title_fullStr | Stable Quasiorderings on Some Permutable Inverse Monoids |
| title_full_unstemmed | Stable Quasiorderings on Some Permutable Inverse Monoids |
| title_short | Stable Quasiorderings on Some Permutable Inverse Monoids |
| title_sort | stable quasiorderings on some permutable inverse monoids |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/2147 |
| work_keys_str_mv | AT derechvd stablequasiorderingsonsomepermutableinversemonoids AT derečvd stablequasiorderingsonsomepermutableinversemonoids AT derechvd stabílʹníkvazíporâdkinadeâkihperestavnihínversnihmonoídah AT derečvd stabílʹníkvazíporâdkinadeâkihperestavnihínversnihmonoídah |