Разбиение полугруппы

[AlexDem]

Верно ли предположение, что для любой ассоциативной некоммутативной полугруппы $<G, \circ>$:

если не существует таких $g_i, g_j$, что $g_1 \circ g_i = g_2$ и $g_2 \circ g_j = g_1$, где $g_1, g_2 \in G$,

то исходное множество $G$ разбивается ровно на два непересекающихся подмножества $G_1 \cap G_2 = \varnothing$ при условии, что для всех остальных элементов (по крайней мере внутри подмножеств) преобразование существует?

[Lion]

Пара вопросов по условию задачи.
1. Элементы $g_i$, $g_j$ фиксированы, а $g_1$, $g_2$ --- произвольные элементы из $G$?
2. Подмножества $G_1$, $G_2$ должны быть полугруппами?
3. Что означает последняя фраза: "...При условии, что для всех остальных элементов (по крайней мере внутри подмножеств) преобразование существует?"? О каком преобразовании идет речь?

[AlexDem]

Lion писал(а):

Пара вопросов по условию задачи.

Немного наврал, поправил первое сообщение. Попробую описать задачу более подробно. Преобразование = суперпозиция - это групповая операция.

Элементы $g_i, g_j$ - "отсутствующие". Например, берем симметрическую полугруппу - там есть все возможные функции над некоторым, пусть бесконечным множеством $X$. В рассматриваемой же полугруппе $<G, \circ>$ отсутствуют, по крайней мере, две функции - $g_i$ и $g_j$, такие, что при суперпозиции с ними конкретный элемент $g_1$ преобразуется в конкретный $g_2$ и наоборот.

Очевидно, что если бы отсутствовала только одна функция, скажем $g_i$, то внутри $<G, \circ>$ можно было бы рассмотреть два подмножества - $G_1$ и $G_2$, где $G_1$ состояло бы по крайней мере из элемента $g_1$ и было бы замкнутым относительно групповой операции суперпозиции (иначе бы цепочку преобразований от него к $g_2$ можно было обозвать функцией $g_i$).

Если же выкидываем два элемента - как $g_i$, так и $g_j$, то никакое преобразование между $g_1$ и $g_2$ будет невозможным, но разобъется ли исходная только на две полугруппы? (Можно сказать - на два подмножества внутри полугруппы, но ведь если каждое из них замкнуто относительно групповой операции, то как раз получится две полугруппы).

Очевидно, что для этого в исходной $<G, \circ>$ должны отсутствовать как единица, так и обратные функции - иначе преобразование между $g_1$ и $g_2$ будет возможно всегда.

Может я ставлю задачу вообще некорректно?..

[bot]

Неасилил. Попробуйте всё-таки сформулировать точнее. Всякую полугруппу, конечно, можно рассматривать как полугруппу преобразований (не всех) некоторого множества, но часто от этой конкретики можно абстрагироваться. Если вопрос можно сформулировать без участия преобразований, то надо так и делать. Если же преобразования по существу вопроса, то так и делайте: пусть G полугруппа преобразований, возьмём в ней два элемента, ... а зачем их индексами-то снабжать? ... Что означает, что они выброшены?

[radical]

Если я смог уловить суть, то речь идет о следующем:
Исследовать строение некоммутатвной полугруппы <G, \circ>, где есть два элемента a и b такие, что либо неразрешимо уравнение a \circ x =b, либо неразрешимо уравнение b \circ y =a.

[AlexDem]

Нет, где неразрешимы оба уравнения. Если неразрешимо только одно (в моем изложении - $g_i$), то вывод достаточно прост. Я попробую формализовать задачу - напишу попозже. Кстати, у меня везде прямой порядок записи суперпозиции: $f(g(x)) = (g \circ f)(x)$

[radical]

Ясно, просто Вы пишете

AlexDem писал(а):

не существует таких $g_i, g_j$, что $g_1 \circ g_i = g_2$ И $g_2 \circ g_j = g_1$, где $g_1, g_2 \in G$,?

что ж оставалось думать? просто построил отрицание...

[AlexDem]

Вот, насколько меня сегодня хватило... Абстрагироваться от отображений не смог - иначе у меня не получается определить полноту. То, что написано раньше, можно забыть. Здесь и далее для ясности отказываюсь от обозначений $g_i, g_j$, заменяя их на $h_i, h_j$. Индексы $i, j$ означают в точности "любые, возможно не равные, элементы множества".

Итак, будем рассматривать неполную полугруппу $<G, \circ>$ отображений бесконечного множества $X$ в множество $X$ (мне достаточно рассмотреть счетное $X$). Элементы этой полугруппы будем записывать в виде $g_1, g_2,... \in G$. Групповая операция суперпозиции будет записываться в прямом порядке: $(g_2 \circ g_1)(x) = g_1(g_2(x))$.

Определение 1
Полугруппу назовем неполной, если на множестве $X$ существуют такие отображения, которые не принадлежат множеству $G$. Обозначим множество таких отображений через $H$, имея ввиду, что $H \cap G = \varnothing$, а $H \cup G = F$ представляет собой множество всех отображений множества $X$ в себя. Если мы не уверены в принадлежности каких-либо отображений, будем обозначать их $f_1, f_2,... \in F$.

Определение 2
Отсутствующими, или выброшенными, назовем все элементы $h_1, h_2,... \in H$.

Определение 3
Будем говорить, что полугруппа разбивается на два непересекающихся подмножества $G_a$ и $G_b$ в том случае, когда для любых $f_i, f_j \in F$, любых $g_a \in G_a$ и любых $g_b \in G_b$ справедливо следующее: если $g_a \circ f_i = g_b$, то $f_i \in H$; если $g_b \circ f_j = g_a$, то $f_j \in H$.

Определение 4
Будем говорить, что полугруппа разбивается на две подполугруппы, если каждое из множеств $G_a$ и $G_b$ в отдельности замкнуто относительно групповой опрерации. То есть, если $g_i, g_j \in G_a$, то $g_i \circ g_j \in G_a$.

Определение 5
Будем говорить, что элемент $g_1 \in G$ преобразуется в элемент $g_2 \in G$ (или, что то же самое, - что элемент $g_2$ выводится из $g_1$), если существует такой элемент $g_i \in G$, что $g_1 \circ g_i = g_2$.

Исходные условия
Известно, что некоторый элемент $g_1$ исходной неполной полугруппы $<G, \circ>$ не преобразуется и не выводим из другого элемента $g_2$ этой полугруппы в смысле Определения 5.

Вопрос
Каково будет разбиение полугруппы $<G, \circ>$ в смысле Определения 3? (И имеет ли задача решение вообще, потому как, например, в циклической группе такое невозможно).


Может стоит подступиться с другой стороны? Взять сперва полную полугруппу $<F, \circ>$, выкинуть ее произвольный элемент, а так же все, которые в него преобразуются (в смысле Определения 5)? Не будет ли полученная полугруппа искомой $<G, \circ>$?

Вопрос о разбиении в смысле Определения 4 - это другая задача, но вроде тоже интересная

Вот, надеюсь, ничего не напутал...

[AlexDem]

Можно рассмотреть один пример, он вроде не сводится к исходной задаче, но зато на нем проще понять суть дела.

Пусть $G$ - множество натуральных чисел. Рассмотрим коммутативную полугруппу $<G, *>$ с операцией умножения. В ней можно рассмотреть подмножества четных $G_a$ и нечетных $G_b$ чисел.

Тогда эта полугруппа легко разбивается на две подполугруппы $<G_a, *>$ и $<G_b, *>$ в смысле Определения 4. Поэтому такая задача может быть и не столь интересна.

Рассмотрим разбиение полугруппы в смысле Определения 3. Очевидно, что никакой нечетный элемент из $G_b$ не выводится из $G_a$ - для любых $g_a \in G_a$ и $g_i \in G$ произведение $g_a * g_i \in G_a$ (то есть оно всегда будет четным). Но это утверждение не справедливо в обратную сторону - если мы возьмем нечетный элемент, то его произведение с произвольным элементом из $G$ может дать как четный, так и нечетный элемент из $G$. Поэтому такое разбиение не удовлетворяет условиям задачи - необходимо, чтобы утверждение было справедливо в обе стороны.

Между тем, в этой полугруппе можно найти такие элементы, которые не преобразуются и не выводимы друг из друга в смысле Определения 5. Например, числа 2 и 3. И тем не менее, полугруппа не разбивается на подмножества в смысле определения 3. Так что, возможно, исходная задача некорректна (хотя мне кажется, что этого нельзя утверждать в точности для исходной полугруппы отображений)...

[bot]

Ну и нагородили!
И отображения не причём пока.
Пусть $F$ - произвольная полугруппа. Зачем подполугруппу $G$ в ней называеть неполной, если это означает всего-навсего, что она собственная, то есть $G\ne F$ ?
Отсутствующие элементы - это просто элементы дополнения $F - G$.
Разбиение множества $G$ на подмножества $G_1$ и $G_2$ ясно без пояснений. Вы дополнительно к этому в определении 3 требуете, чтобы уравнения $g_1 x = g_2$ и $g_2 x = g_1$ были неразрешимы в $G$ ни для каких $g_1 \in G_1$ и $g_2 \in G_2$?
А в определении 4 ещё дополнительно к этому хотите, чтобы $G_1$ и $G_2$ были подполугруппами в $G$?
Преобразуемость (выводимость) элемента $g_1 \in G$ из элемента $g_2 \in G$ - это просто разрешимость уравнения $g_2 x = g_1$ в $G$.
Вы спрашиваете: Каково будет разбиение полугруппы $<G, \circ>$ в смысле Определения 3?
Замечу, что вообще даже просто разбиение алгебраической системы (полугруппы в частности) на две непересекающиеся подсистемы явление экзотическое, а уж с дополнительными условиями - неясно, правда какими, и подавно.
Вот несколько примеров такой экзотики:
1) Полугруппа с нулевым умножением, то есть произведение любых элементов равно одному выбранному элементу который обозначим нулём.
2) Полугруппа левых единиц - это полугруппа, в которой для любых элементов $x$ и $y$ справедливо равенство $xy=y$. Её с тем же успехом можно назвать полугруппой правых нулей.
3) Полугруппа с двумя образующими $a$ и $b$ и определяющими соотношениями: $ab=aa, ba = bb$.
В первых двух примерах любое подмножество образует подполугруппу, а в третьем полугруппа разбивается в объединение двух циклических, порожденными элементами $a$ и $b$. Можно построить примеры поизощрённее - было бы зачем.

В любом случае не видно, где тут по существу отображения-то?
Имеется стандартная процедура погружения любой полугруппы $G$ в полугруппу отображений. Для этого надо присоединить к $G$ единицу, если её там нет и далее (как и в группах) каждому элементу сопоставляем правый сдвиг.

[AlexDem]

bot писал(а):

А в определении 4 ещё дополнительно к этому хотите, чтобы $G_1$ и $G_2$ были подполугруппами в $G$?

По-моему, Определение 4 менее строгое - в приведенном примере с четными и нечетными числами его требования выполнялись, а требования Определения 3 - нет (оно вообще ни для каких коммутативных полугрупп не выполняется).

bot писал(а):

Пусть $F$ - произвольная полугруппа. Зачем подполугруппу $G$ в ней называеть неполной, если это означает всего-навсего, что она собственная, то есть $G \ne F$?

Прошу прощения за путаницу с определениями - я поэтому и нагородил, чтобы разговаривать на одном языке... В принципе, все верно - можно рассматривать неразрешимость уравнений $g_1x=g_2$ и $g_2x=g_1$ для любых $g_1 \in G_1$, $g_2 \in G_2$ и $x \in G$.

Попробую смоделирую ситуацию на какой-нибудь конечной полугруппе - может прояснится что-нибудь. Спасибо за подробный ответ - мне будет гораздо проще разбираться