Доказательство: Ln(y1, y2, ... , ym) есть L-класс Грина

[Marckus]

Доброго времени суток, уважаемые участники форума!
$T_n$ - полная полугруппа преобразований множества первых $n$ натуральных чисел.
$OT_n$ - подполугруппа $T_n$.
Элементы $OT_n$ определены следующим образом. $a$ из $OT_n$.
Вводится понятие ранга $a$ $rang(a)=dim(\{a(1), a(2), a(3), ... , a(n)\})$
(ранг равен мощности множества-образа трансформации)
и максимума $a$ $max(a)=max(\{a(1), a(2), a(3), ... , a(n)\})$.
Для элемента $a$ должно иметь место соотношение $rang(a)=max(a)$ (первое условие).
Для любого образа $a(i)$, $i=1, 2, ... , n$,
выполнется второе условие $a(i)\le i$.
И третье последнее условие
Пусть $max(a)=a(m)$, $a(1)\le a(m)\le a(n)$, тогда $dim(\{a(1), a(2), a(3), ... , a(n)\})=a(m)$.
Или приведенные три условия можно записать короче, а именно
$a(1)=1$,
$a(k)\le max(\{a(1),...,a(k-1)\})+1$ при $1<k\le n$.
Подмножество $L_{n}(y_1, y_2, ... , y_m)$ множества $OT_n$, где $y$ из $OT_n$,
$y_m=max\{y_1, y_2, ... ,y_m\}$, $y(1)=y_1$, $y(2)=y_2$, ... , $y(m)=y_m$.
Например., для $OT_3$.
$L_{3}(1)=\{Transformation(1, 1, 1)\}$,
$L_{3}(1, 1, 2) =\{Transformation(1, 1, 2)\}$,
$L_{3}(1, 2)=\{Transformation(1, 2, 1), Transformation(1, 2, 2)\}$
$L_{3}(1, 2, 3)=\{Transformation(1, 2, 3)\}$.
Нужно подтвердить, что $L_{n}(y_1, y_2, ... , y_m)$ есть $L$-классом Грина.
То есть возникла необходимость обосновать справедливость следующего утверждения.
Для любых двух элементов $a$ и $b$ произвольного класса $L_{n}(y_1, y_2, ... , y_m)$,
$m\le n$ полугруппы $OT_n$,
где
$y_{1}=1$, $y_k\le max(y_{1},...,y_{k-1})+1$, $1<k\le m$
множества $OT_n$ найдутся такие элементы $x$ и $y$ из множества $OT_n$ такие, что
$a = x*b$ и $b = y*a$
Элементы множества $OT_n$ перемножаются следующим образом. Для перемножения элементы множества $OT_n$ записывают в виде перестановок с повторениями и умножаются точно также как перестановки.
Например, $Transformation(1, 2, 3, 4, 4)*Transformation(1, 2, 2, 1, 1)=Transformation(1, 2, 2, 1, 1)$.
$\left( \begin{array}{ccccc} 1 & 2 &3 &4 &5 \\1 & 2 &3 &4 &4 \end{array} \right)*\left( \begin{array}{ccccc} 1 & 2 &3 &4 &5 \\1 & 2 &2 &1 &1 \end{array} \right)=\left( \begin{array}{ccccc} 1 & 2 &3 &4 &5 \\1 & 2 &2 &1 &1\end{array} \right)$
Или
$Transformation(1, 1, 2)*Transformation(1, 1, 2)=Transformation(1, 1, 1)$.
$\left( \begin{array}{ccc} 1 & 2 &3 \\1 & 1 &2 \end{array} \right)*\left( \begin{array}{ccc} 1 & 2 &3 \\1 & 1 &2 \end{array} \right)=\left( \begin{array}{ccc} 1 & 2 &3 \\1 & 1 &1 \end{array} \right)$
Если у кого есть какие-то мысли, то, пожалуйста, поделитесь.

[maxal]

Marckus писал(а):

Для любых двух элементов a и b произвольного класса Ln(y1, y2, ... , ym), m<=n полугруппы OTn,
где
y_{1}=1, y_k\le max(y_{1},...,y_{k-1})+1, 1<k\le m.
множества OTn найдутся такие элементы x и y из множества OTn такие, что a = x*b и b = y*a

Понятно, что достаточно доказать существование $x$ (в виду произвольности выбора $a$ и $b$).

Если я правильно понял, ваше умножение - это обратная композиция соответствующих подстановок: $(x*b)(k) = b(x(k))$ для всех $k$.

Пусть $s=\max(a)=\max(b)$. Для $1\leq k\leq s$ положим $i(k)$ равным минимальному числу $t$ такому, что $b(t)=k$. Другими словами, $i(k)$ - это минимальный элемент множества $b^{-1}(k)$.

Тогда $x$ можно определить как $x(k) = i(a(k))$. Тогда равенство a = x*b естественным образом выполняется. Осталось доказать, что x - это элемент OTn или, что $x(k)\leq max(x(1),\dots,x(k-1))+1$ для всех $1<k\leq n$. Но это легко доказывается индукцией по $k$.

[нг]

Marckus
На форуме принято записывать формулы, используя нотацию ($\TeX$; введение, справка).

Пожалуйста, исправьте и сообщите модератору (ЛС).

[Marckus]

Простите, возможно я ошибаюсь, но скорее всего в приведенном выше доказательстве имеется ошибка,
так как оно справедливо не для всех $L$-классов Грина. Привожу один контр-пример.
Полугруппа $OT_5$.
$L$-класс $L_{5}(1, 1, 2, 3)=\{Transformation(1, 1, 2, 3, 1), Transformation(1, 1, 2, 3, 2), Transformation(1, 1, 2, 3, 3)\}$.
Возьмём два элемента из этого класса.
$a=\left( \begin{array}{ccccc} 1 & 2 &3 &4 &5 \\1 & 1 &2 &3 &1 \end{array} \right)
и
$b=\left( \begin{array}{ccccc} 1 & 2 &3 &4 &5 \\1 & 1 &2 &3 &3 \end{array} \right)
Найдем $x$ используя вышеуказанный алгоритм.
Прообразы:
$b^{-1}(1)=\{1, 2\}$, $b^{-1}(2)=\{3\}$, $b^{-1}(3)=\{4, 5\}$.
Значения преобразования $x$:
$x(k)=min(b^{-1}(a(k)))$, где $x*b=a$.
$x(1)=min(b^{-1}(a(1)))=min(b^{-1}(1))=1$,
$x(2)=min(b^{-1}(a(2)))=min(b^{-1}(1))=1$,
$x(3)=min(b^{-1}(a(3)))=min(b^{-1}(2))=3$,
$x(4)=min(b^{-1}(a(4)))=min(b^{-1}(3))=4$,
$x(5)=min(b^{-1}(a(5)))=min(b^{-1}(1))=1$.
То есть
$x=\left( \begin{array}{ccccc} 1 & 2 &3 &4 &5 \\1 & 1 &3 &4 &1 \end{array} \right)
Должно быть, что $x(k)\leq max(x(1),\dots,x(k-1))+1$ для всех $1<k\leq n$
Но приведенное неравенство не есть истиннным, тоесть не выполняется.
$3=x(3)\leq max(x(1), x(2))+1=2$
Таким образом, $x$ элемент $T_n$, но $x$ не элемент $OT_n$