Циклы, составляющие одну и ту же подстановку, перестановочны - теорема

Предполагается, что все рассматриваемые подстановки принадлежат группе $\mathfrak{S}_n$,
которая действует на множестве $\{1,\ ...,\ n\}$.

Теорема 1. Циклы, составлющие одну и ту же подстановку, перестановочны.

Доказательство:

Пусть $T\in\mathfrak{S}_n$.

Ранее была доказана теорема о том, что подстановка является либо является циклом, либо произведением циклов. Более того, является произведением попарно непересекающихся циклов: принадлежность одному циклу --- отношение эквивалентности.

Если $T$ состоит из одного цикла, то доказывать нечего --- цикл перестановочен сам с собой.

Рассмотрим теперь случай, когда $T$ содержит более одного цикла:
$$
T=(\alpha_1\ ...\ \alpha_m)(\beta_1 ... \beta_l)\ ...\ (\gamma_1\ ...\ \gamma_k).
$$

Любые два различных цикла $(\alpha_1\ ...\ \alpha_m),\ (\beta_1 ... \beta_l)$, входящие в $T$, не пересекаются. Следовательно, по теореме 2, они перестановочны.

Получается, что любые два цикла, каждый из которых входит в $T$, перестановочны друг с другом.

Теорема доказана.

Key Words for FKN + antitotal forum (CS VSU):

vedro-compota's picture

Таким образом мы получили перестановочность наших циклов на множествах
$C$ и $A$

На $C$ перестановочны, так как $y \in C$ и было показано, что:
$$
(y)(\alpha_1\ ...\ \alpha_m)(\beta_1 ... \beta_l)=(y)(\beta_1 ... \beta_l)(\alpha_1\ ...\ \alpha_m).
$$

Но не понятно, где именно мы показали перестановочность на $A$ ?

_____________
матфак вгу и остальная классика =)

Если $y\in A$, то
$$
(y)(\beta_1 ... \beta_l)=y,
$$

и

$$
\left((y)(\alpha_1\ ...\ \alpha_m)\right)\in A,
$$

так как элемент $y$ в этом случае содержится среди элементов $(\alpha_1, \ ...,\ \alpha_m)$, и, следовательно, будет отображён подстановкой $(\alpha_1\ ...\ \alpha_m)$ в некоторый элемент из $A$.

Поэтому, если $y\in A$, то

$$
(y)(\alpha_1\ ...\ \alpha_m)(\beta_1 ... \beta_l)=(y)(\beta_1 ... \beta_l)(\alpha_1\ ...\ \alpha_m).
$$

То есть, как бы мы ни переставляли циклы $(\alpha_1\ ...\ \alpha_m)$ и $(\beta_1 ... \beta_l)$, их произведение, применённое к элементу $y\in A$ даст один и тот же результат.

vedro-compota's picture

Спасибо. Что-то я невнимательно читал первый раз.

_____________
матфак вгу и остальная классика =)

Можно сделать так.

Теорема. Если два цикла не содержат общих элементов, то они перестановочны.

Доказательство уже имеется.

Любую подстановку можно представить как произведение попарно непересекающихся циклов, используя эту схему. И, как следствие, эти циклы будут перестановочными.

vedro-compota's picture

Можно сделать так.

Теорема. Если два цикла не содержат общих элементов, то они перестановочны.

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

_____________
матфак вгу и остальная классика =)

Нет, они просто перестановочны.

В этой теореме циклы сами рассматриваются как элементы симметрической группы.

Если для элементов $A$ и $B$ группы $\mathfrak{G}$ выполняется
$$
AB=BA,
$$
то говорят, что $A$ и $B$ перестановочны.

vedro-compota's picture

В целом доказательство понятно, но тут уточнение по формулировке (вынес в отдельное обсуждение)

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

Думаю перед доказательством надо привести уточнение такое (примечание):

Далее в доказательстве мы подразумеваем (опираемся на то соображение), что после перестановки местами 2 циклов подстановка остаётся всё той же, если она действует на любой свой элемент так же, как и до изменения позиций этих циклов. Важно именно действие подстановки на элемент, так как подстановка является отображением.

Думаю его стоит добавить как напоминание.
Правильно ли это уточнение?

_____________
матфак вгу и остальная классика =)

Нет. Мы не опираемся на это. Это---результат рассуждения.

Схема здесь такова.

Нам дана некоторая подстановка $T$.

Зная $T$, мы можем получить её циклы.
Эти циклы попарно не пересекаются (или точнее, множества символов, из которых состоят циклы, попарно не пересекаются).

Выбираем любые два различных цикла из них. Общих элементов они не имеют.

Нам известна
Теорема. Если два цикла не содержат общих элементов, то они перестановочны.

Поэтому все циклы подстановки $T$ попарно перестановочны.

Пусть $(\alpha_1\ ...\ \alpha_m)$ --- один из циклов подстановки $T$. И
этот цикл сам является подстанокой. Ясно, что на множестве
$\{\alpha_1\ ...\ \alpha_m\}$ подстановки $(\alpha_1\ ...\ \alpha_m)$ и $T$ действуют одинаково. Отличные же от $(\alpha_1\ ...\ \alpha_m)$ циклы оставляют элементы
$\{\alpha_1\ ...\ \alpha_m\}$ неподвижными.

Поэтому подстановка $T$ является произведением своих циклов, и эти циклы перестановочны.

vedro-compota's picture

Но в оригинале вверху написана другая формулировка:

Циклы, составляющие одну и ту же подстановку, перестановочны.

То есть теорема вообще заведена с одной стороны для решения упражнения (или она его не решает?), а с другой стороны сюда ссылаемся из теоремы о том, что подстановка явл. либо циклом илбо произв. циклов в словах:

ПРИМЕЧАНИЕ: Эти циклы не могут попарно пересекаться, так как принадлежность двух элементов к одному и тому же циклу является отношением эквивалентности, что можно показать. Поэтому они перестановочны.

Новая же формулировка:

Если два цикла не содержат общих элементов, то они перестановочны.

Является...более общей что ли.
Потому что в оригинале разве мы не доказываем, что для некоторой подстановки заданной, скажем на мн-ве 3-х элементов верно:
$(1)(23)=(23)(1)$
?
Ведь в упражнении именно это требуется доказать?

_____________
матфак вгу и остальная классика =)

Но это всё детали. Их стало довольно много.
Я думаю, что необходимо обозначить какую-либо последовательность рассуждений
и проверить её.

Пусть дана некоторая подстановка $T$.

Зная $T$, мы можем получить её циклы.
Эти циклы попарно не пересекаются (или точнее, множества символов, из которых состоят циклы, попарно не пересекаются).
Выбираем любые два различных цикла из них. Общих элементов они не имеют. Это показано здесь.

Теорема 2. Если два цикла не содержат общих элементов, то они перестановочны.

Доказательство.

Пусть циклы $(\alpha_1\ ...\ \alpha_m),\ (\beta_1 ... \beta_l)$ не содержат общих элементов.
Пусть
$$
A=\{\alpha_1,\ ...,\ \alpha_m\}.
$$
$$
B=\{\beta_1,\ ...,\ \beta_l\}.
$$
$$
C=\{1,\ ...,\ n\}\setminus(A\cup B).
$$

Получается, если $y\in C$, то
$$
(y)(\alpha_1\ ...\ \alpha_m)=y
$$
и
$$
(y)(\beta_1 ...\ \beta_l)=y.
$$
Cледовательно, $y\in C$, то
$$
(y)(\alpha_1\ ...\ \alpha_m)(\beta_1 ... \beta_l)=(y)(\beta_1 ... \beta_l)(\alpha_1\ ...\ \alpha_m)=y.
$$
Если $y\in A$, то
$$
(y)(\beta_1 ... \beta_l)=y.
$$
Поэтому
$$
(y)(\alpha_1\ ...\ \alpha_m)(\beta_1 ... \beta_l)=(y)(\beta_1 ... \beta_l)(\alpha_1\ ...\ \alpha_m).
$$
Здесь мы, конечно, использовали то, что если $y\in A$, то $\left((y)(\alpha_1\ ...\ \alpha_m)\right)\in A$. Таким образом мы получили перестановочность наших циклов на множествах
$C$ и $A$.

Циклы $(\alpha_1\ ...\ \alpha_m)$ и $(\beta_1 ... \beta_l)$ входят в это рассуждение симметрично. Поэтому эти циклы перестановочны и на множестве $B$.
У нас есть перестановочность циклов на всём множестве $\{1,\ 2,\ ...,\ n\}$.

Теорема доказана.

Поэтому все циклы подстановки $T$ попарно перестановочны.

Пусть $(\alpha_1\ ...\ \alpha_m)$ --- один из циклов подстановки $T$. И
этот цикл сам является подстанокой. Ясно, что на множестве
$\{\alpha_1\ ...\ \alpha_m\}$ подстановки $(\alpha_1\ ...\ \alpha_m)$ и $T$ действуют одинаково. Отличные же от $(\alpha_1\ ...\ \alpha_m)$ циклы оставляют элементы
$\{\alpha_1\ ...\ \alpha_m\}$ неподвижными. Это есть здесь.

Поэтому подстановка $T$ является произведением своих циклов, и эти циклы перестановочны.

Следствие.

Циклы, составляющие одну и ту же подстановку, перестановочны.

vedro-compota's picture

Да, деталей не мало и лучше использовать более общую и изящную формулировку.
Тогда я буду заменять заметку выше на указанный вами текст.
Но сначала уточнить (ответить на) один вопрос (так как слова о симметрической группе исключены из нового текста).

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

Вынес данное рассуждение отдельно и добавил в словарь. Для теоремы этого утверждения указал, что она может рассматриваться как следствие.

_____________
матфак вгу и остальная классика =)