Обсуждение док-ва - "Доказать, что циклы, составлющие одну и ту же подстановку, перестановочны "

Primary tabs

vedro-compota's picture
Submitted by vedro-compota on Sat, 12/12/2015 - 18:36

Forums:


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

Прошу ещё раз показать идею доказательства утверждения:

Доказать, что циклы, составлющие одну и ту же подстановку, перестановочны

Я начал его так:

Принадлежность двух элементов множества подстановки одному и тому же циклу является отношением эквивалентности, а потому элемент может принадлежать только одному циклу.

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

  • Log in to post comments
  • 13031 reads

math2

Sat, 12/12/2015 - 22:58

Принадлежность двух элементов множества подстановки одному и тому же циклу

Лучше написать по-другому. Например
Принадлежность двух элементов множества, на котором действует группа подстановок, одному и тому же циклу...
Если рассматривать цикл только как множество, то это совпадёт с понятием орбиты элемента. Там тоже речь идёт об отношении эквивалентности, и множество, на котором действует группа разбивается на непересекающиеся классы.
Но цикл---не просто подмножество множества, на котором действует симметрическая группа. Здесь цикл---это отображение.

О перестановочности циклов.

[рассуждение перенесено сюда]

math2

Wed, 12/30/2015 - 12:52

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

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

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

Но подстановка может быть представлена и произведением таких циклов, которые содержат общие элементы. Например,
$$
(1\ \ 2\ \ 3)(1\ \ 4\ \ 5)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{pmatrix}.
$$
Если мы переставим эти циклы, то получим
$$
(1\ \ 4 \ \ 5)(1\ \ 2\ \ 3) =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 1 & 5 & 2 \end{pmatrix}.
$$
Этот пример показывает, что циклы неперестановочны.

vedro-compota's picture

vedro-compota

Sat, 01/02/2016 - 21:10

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

действительно, в оригинальной формулировке задания (Упражнение 4) написано так:

Доказать, что циклы, составляющие одну и ту же подстановку (т.е. лишённые общих цифр) перестановочны

То, есть необходимо добавить эту уточнение (об отсутствии общих цифр) в формулировку теоремы,
но с другой стороны мы же вроде как указываем:

........Можно показать, что $A\cap B=\emptyset$

, что принадлежность циклу это отношение эквивалентности?
То есть элемент циклы разбивают мн-во элементов подстановки на классы, а потому вот такое:

$$
(1\ \ 2\ \ 3)(1\ \ 4\ \ 5)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{pmatrix}.
$$

невозможно. (да и непонятно, почему в примере выше 1 не переходит в 3, а перехожит в 4)

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

math2

Wed, 02/17/2016 - 23:25

То есть элемент циклы разбивают мн-во элементов подстановки на классы, а потому вот такое:

$$
(1\ \ 2\ \ 3)(1\ \ 4\ \ 5)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{pmatrix}.
$$

невозможно. (да и непонятно, почему в примере выше 1 не переходит в 3, а перехожит в 4)

Такое возможно.
Нужно различать разложение подстановки на попарно непересекающиеся циклы,
и разложение на циклы, где пересечения не исключены.

vedro-compota's picture

vedro-compota

Thu, 02/18/2016 - 13:11

$$
(1\ \ 2\ \ 3)(1\ \ 4\ \ 5)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{pmatrix}.
$$

Число 3 в подстановке уже **не переходит** в 1 как указывает то левый цикл (а переходит в 4-ре). И это противоречит определению. Конечно в случае, если что-то специально оговорено, под циклами можно что угодно подразумевать.

Думаю, это уже несущественные детали (для обсуждения).

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

math2

Thu, 02/18/2016 - 16:32

Здесь цикл понимается как подстановка.
Подстановки умножаются "слева направо".
3 отображается в 1 циклом $(1\ 2 \ 3)$, 1 --- в 4 циклом $(1\ 4\ 5)$.
И поэтому произведение $(1\ 2 \ 3)(1\ 4\ 5)$ двух этих циклов отображает 3 в 4.

vedro-compota's picture

vedro-compota

Thu, 02/18/2016 - 18:49

согласен. моя ошибка. тут пример композиции циклов с общим элементом)

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