О взаимно однозначных отображениях конечных множеств

[grisania]

О взаимно однозначных отображениях конечных множеств.
Пусть $\Omega =\left\{ {{\omega }_{1}},{{\omega }_{1}},\ldots ,{{\omega }_{n}} \right\}$ – конечное множество$\left( \Omega ,\mathcal{A} \right)$, тогда любое взаимно однозначное отображение $f:\bar{\Omega }\to \bar{\Omega }$ – это обычная перестановка элементов $\Omega$. Пусть имеем разбиение $\Omega $ на непересекающие подмножества ${{A}_{i}},i=1,...k$ такие, что $\bigcup{{{A}_{i}}}=\Omega$. Отождествив каждое подмножество ${{A}_{i}},i=1,...k$ с элементом, и образуем новое множество $\bar{\Omega }=\left\{ {{A}_{1}},{{A}_{1}},...,{{A}_{k}} \right\}$.
Теперь вопрос.
Существует ли такое разбиение множества $\Omega$, что $f:\bar{\Omega }\to \bar{\Omega }$ взаимно однозначное отображение?
Ясно, что тривиальное $\bar{\Omega }=\left\{ \varnothing ,\bar{\Omega } \right\}$ удовлетворяет, так как $\Omega =\varnothing \bigcup \Omega$. Также удовлетворяет такое разбиение $\Omega =\left\{ {{\omega }_{1}},{{\omega }_{1}},\ldots ,{{\omega }_{n}} \right\}$, так как $\Omega ={{\omega }_{1}}\bigcup {{\omega }_{1}}\bigcup \ldots \bigcup {{\omega }_{n}}$.
Замечание.
Если элементы перенумеровать, то можно переставлять только числа $\Omega =\left\{ 1,2,\ldots ,n \right\}$.
Вообще, что известно для не конечных $\Omega$? Для отрезка, т. е. $\Omega =\left[ 0,1 \right]$ и $f:\left[ 0,1 \right]\to \left[ 0,1 \right]$ - монотонной я умею доказывать, что существует такое разбиение, где подмножества разбиения борелевские.

[Xaositect]

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

Рассмотрим множество $E_k = \{0,1,\dots,k-1\}$
Вместо разбиения будем рассматривать отношение эквивалентности $\sim$ на $E_k$ (каждое разбиение порождает эквивалентность $x\sim y \LeftRightarrow x,y\in A_i$ и наоборот, каждая эквивалентность разбивает $E_k$ на классы эквивалентности).
Пусть $\pi$ - наша перестановка. Эквивалентность $\sim$ удовлетворяет требованиям задачи, если и только если $x\sim y \Leftrightarrow \pi x \sim \pi y$, т.е. перестановка сохраняет эквивалентность. (докажите!).
Теперь заметим такую особенность: если $x\sim \pi^k x$ (а это всегда верно для некоторого $k$), то $\pi^k x\sim \pi^{2k} x$, а значит $x\sim pi^{ik} x$. То есть каждый класс эквивалентности является объединением некоторых циклов перестановок $\pi^k$.

Например, для множества из 5 элементов и перестановки $\begin{pmatrix}0& 1& 2& 3& 4\\1& 2& 3& 4& 0 \end{pmatrix}$ только тривиальные эквивалентности будут сохраняться.

Проверьте, я мог где-то ошибиться.

[maxal]

grisania в сообщении #220041 писал(а):

Существует ли такое разбиение множества $\Omega$, что $f:\bar{\Omega }\to \bar{\Omega }$ взаимно однозначное отображение?

Представьте перестановку $f$ на $\Omega$ в виде произведения циклов. Всякое разбиение, для которого $f$ является взаино-однозначным на $\bar\Omega$, строится так: для каждого цикла $f$ нужно выбрать $k$, делящее его порядок, и разбить цикл на части, определяемые $f^k$, с возможным последующим урупнением частей (путем их объединения), не нарущающим однозначности $f$ на $\bar\Omega$.

[Xaositect]

maxal в сообщении #220104 писал(а):

для того, чтобы $f$ было взаино-однозначным на $\bar\Omega$, необходимо, чтобы каждый цикл целиком содержался в какой-то части разбиения.

Нет.
Рассмотрим $f = \begin{pmatrix}0& 1& 2& 3\\1& 2& 3& 0\end{pmatrix}$. У нее один цикл, и между тем на разбиении $\{0,2\}\cup\{1,3\}$ она взаимно однозначна.

-- Сб июн 06, 2009 18:16:09 --

maxal в сообщении #220108 писал(а):

$f(1)=2$, то есть элемент первой части переводится $f$ во вторую.

Хмм.
Мы, видимо, по разному понимаем условие.
Я так понимаю, что одни компоненты разбиения должны переходит в другие: $\{0,2\}\mapsto \{1,3\}$ и обратно

[maxal]

Xaositect
Согласен. В такой постановке надо рассматривать также степени $f$ - поправил.

-- Sat Jun 06, 2009 10:50:07 --

Xaositect в сообщении #220049 писал(а):

Кажется, таким образом можно доказать, что эквивалентность будет удовлетворять условию тогда и только тогда, когда классы эквивалентности являются объединениями циклов перестановок $\pi^k$, для которых соответствующие циклы перестановки перестановки $pi$ различаются.

Не совсем так. Например, третья степень перестановки $(1,2,3)(4,5)$ (произведение циклов) равна $(1)(2)(3)(4,5)$, однако же $\{1,4,5\}$ в качестве части взять нельзя.

[Xaositect]

maxal в сообщении #220110 писал(а):

Не совсем так. Например, третья степень перестановки $(1,2,3)(4,5)$ (произведение циклов) равна $(1)(2)(3)(4,5)$, однако же $\{1,4,5\}$ в качестве части взять нельзя.

Да, согласен.

[grisania]

Пока я отвечал, пост на который я отвечал исчез, но я отвечу на него

В моем посте выше я указываю, что эти задачи просто эквивалентны, т. е. если существует не взаимно однозначное отображение $g:\Omega \to \Omega$, для которого $f\left( g\left( \omega \right) \right)=g\left( f\left( \omega \right) \right)$ (коммутативность), то не взаимно однозначное отображение $g:\Omega \to \Omega$ порождает искомое разбиение для заданного взаимно однозначного отображения $f$.
Это разбиение порождается заданием эквивалентности
"если ${{\omega }_{1}},{{\omega }_{2}}\in \Omega$, то будем говорить${{\omega }_{1}}\sim {{\omega }_{2}}$, если $g\left( {{\omega }_{1}} \right)=g\left( {{\omega }_{2}} \right)$."

Аналогично, если выполняется $f\left( g\left( \omega \right) \right)=g\left( h\left( \omega \right) \right)$, то надо установить существование необходимых отображений: $h:\Omega \to \Omega $ – взаимно однозначного и $g:\Omega \to \Omega$ не взаимно однозначного для заданного взаимно однозначного отображения $f$.

Свой нечаянно стер, как его восстановить? Запутался.

[maxal]

Обсуждение терминологических вопросов выделено в тему перестановка vs. подстановка

[grisania]

А что известно о неподвижных точках перестановок?
Если они есть, то их можно выбросить и задачу, поставленную в начальном посте темы, решать для перестановок без неподвижных точек. Мне кажется , что должны быть стандартные перестановки, к которым сопряжением приводятся перестановоки без неподвижных точек.
Определение.
Пусть $G$ и $S$ некоторые перестановки. Будем говорить, что они сопряжены, если существует такая перестановка $U$, что выполняется $G=US{{U}^{-1}}$

[Xaositect]

Ну, любая перестановка разлагается в произведение независимых циклов. А сопряжением можно привести к произведению "последовательных" циклов: $(0 1 \dots a_1)(a_1+1 \dots a_2)\dots$