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

Что значит, что два числа $i$, $j$ принадлежат одному и тому же циклу? Это значит, что существует такой $s\in\mathbb{Z}$, $s\ge 0$, что $(i)A^s=j$, то есть мы можем придти к от $i$ к $j$ применяя несколько раз подстановку $A$.

Определение. Будем говорить, что $i$ принадлежит тому же циклу, что и $j$, если существует такой $s\in\mathbb{Z}$, $s\ge 0$, что $(i)A^s=j$.

Свойства

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

Обозначим длину цикла через $k$. Если $s \lt 0$, то мы можем взять вместо $s$ его остаток от деления на $k$.

  1. Рефлексивность. Действительно, любое число $i$ принадлежит тому же циклу, что и $i$, покажем это:

    Доказательство. Мы можем взять в нашем определении $s=0$:
    $$(i)A^0=(i)J=i.$$
    Получается, что существует такое целое число $s\geq 0$, что
    $$
    (i)A^s=i.
    $$
    Предложение доказано.

  2. Симметричность. Пусть $i$ лежит в одном цикле с $j$, то есть $(i)A^s=j$. Тогда и $(j)A^{-s}=i$.
  3. Транзитивность. Пусть $(i)A^s=j,\ \ (j)A^t=k.$ Тогда $(i)A^{s+t}=k$, то есть $i$ и $k$ принадлежат одному циклу.

Отношение эквивалентности разбивает множество на попарно непересекающиеся классы.

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

vedro-compota's picture

Вопрос:

Рефлексивность. Действительно, любое число $i$ принадлежит тому же циклу, что и $i$. Цикл числа $i$ вычисляется однозначно.

здесь показано, что, действительно, число $i$ принадлежит циклу, если оно уже ему принадлежит ("очевидность") - то есть после этого рефлексивность уже показана, но зачем добавляется добавлять:

......Цикл числа $i$ вычисляется однозначно.

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

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

но зачем добавляется добавлять:

......Цикл числа i вычисляется однозначно.

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

Да, эту строку лучше удалить отсюда. Но это верное утверждение.

Мы можем взять $s=0$.
Тогда $A^s=J$, где $J$---единица симметрической группы. Поэтому условия определения выполнены:
$$
(i)A^0=(i)J=i.
$$

vedro-compota's picture

Да, эту строку лучше удалить отсюда.

убрал, а вот дальше:

Да, эту строку лучше удалить отсюда. Но это верное утверждение.

Мы можем взять $s=0$.
Тогда $A^s=J$, где $J$---единица симметрической группы. Поэтому условия определения выполнены:
$$
(i)A^0=(i)J=i.
$$

то есть:
$$
(i)A^0=(i)J=i.
$$
показывает, что цикл числа определяется однозначно? Не очень понятно почему)

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

Нет. С предложения

Мы можем взять $s=0$.

начинается новый абзац по другой теме. А в строке

$(i)A^0=(i)J=i$

показано, что число $i$ содержится в одном цикле с $i$ (с самим собой).
Этим показана рефлексивность.

Предложение.
Отношение принадлежности одному циклу рефлексивно.

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

$(i)A^0=(i)J=i.$

Мы можем взять в нашем определении $s=0$.

Получается, что существует такое целое число $s\geq 0$, что
$$
(i)A^s=i.
$$
Предложение доказано.

vedro-compota's picture

Спасибо, теперь понял. Добавил доказательство в качестве пояснения в основной текст свойств.

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

vedro-compota's picture

Мой коллега, math2 выше пишет что:

Симметричность. Пусть $i$ лежит в одном цикле с $j$, то есть $(i)A^s=j$. Тогда и $(j)A^{-s}=i$.

- здесь: $(j)A^{-s} = (j)(A^{-1})^{s}$ - то есть фактически упомянута обратная к $A$ подстановка $A^{-1}$, которая действительно существует для $A$, так как элемент $A$ является элементом симметрической группы.

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

vedro-compota's picture

Зачем нам уточнение:

Обозначим длину цикла через $k$. Если $s \lt 0$, то мы можем взять вместо $s$ его остаток от деления на $k$.

?

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

Будем рассматривать некоторый цикл $V$ (входящий в нашу подстановку $A$) как подстановку. Если длина этого цикла равна $k$, то и порядок этого цикла (как элемента симметрической группы) будет $k$:
$$
V^k=J.
$$
Пусть $i,j\in V$.
В определении были указаны только неотрицательные степени:
$$
s\geq 0.
$$
Если случилось так, что $(j)A^{-s}=i$ и $s\gt 0$, то мы можем разделить $-s$ на $k$ c остатком:
$$
-s=bk+r, \ k\gt r\geq 0.
$$
Остаток будет неотрицательным числом.
$$
(j)A^{-s}=i
$$
$$
(j)A^{-s}=(j)V^{-s}=(j)V^{bk+r}=(j)V^{bk}V^{r}=(j)V^r=(j)A^r.
$$
Мы получили здесь неотрицательную степень, которую требует наше определение.
Остаётся лишь подробнее расписать, что действие подстановки $A$ на элемент $i$, входящий в цикл $V$ (цикл $V$ входит в $A$), сводится к действию цикла $A$. Здесь мы будем рассуждать так же, как при доказательстве перестановочности: все циклы, входящие в $A$ и отличные от $V$ отображают $i$ в $i$.

vedro-compota's picture

Если случилось так, что $(j)A^{-s}=i$ и $s\gt 0$, то мы можем разделить $-s$ на $k$ c остатком:
$$
-s=bk+r, \ r\geq 0.
$$
Остаток будет неотрицательным числом.

Почему неотрицательным? Ведь:
$-5/2 = -2*2 + (-1), \;\; -1 \lt 0 $

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

$$-5/2 = -2*2 + (-1), \;\; -1 \lt 0$$

Это неверное выражение. Из него следует
$$
-2.5 = -5.
$$
Ясно, что при делении -5 на 2 можно записать
$$
(-5)=2\cdot (-2) + (-1).
$$
Но всегда можно найти положительный остаток:
$$
(-5)=2\cdot (-3) + 1.
$$

vedro-compota's picture

$$-5/2 = -2*2 + (-1), \;\; -1 \lt 0$$
--Это неверное выражение. Из него следует

ну здесь под дробью (/) я подразумевал деление с остатком =)

Но всегда можно найти положительный остаток:
$$
(-5)=2\cdot (-3) + 1.
$$

Да, теперь вижу. Почему-то раньше я этого не подозревал))

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

vedro-compota's picture

Если длина этого цикла равна $k$, то и порядок этого цикла (как элемента симметрической группы) будет $k$:

Ещё надо бы отдельно выписать определение порядка цикла, а то у нас его нет.

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

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

vedro-compota's picture

да, но про порядок такого цикла в самом учебнике впервые говорится только, когда речь заходит про m-членные циклы. Там же условно "показывается", что, действительно:

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

Но согласен - отдельно добавлять не будем. Хотя получается что сложно доказать то что раньше, не используя того, что позже (по тексту книги).

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