Размежевание

[AGu]

Пусть $X$ — множество всех двухзначных последовательностей $x:\mathbb N\to\{0,1\}$.

Последовательности $x,y\in X$ назовем смежными,
если $x$ и $y$ различны ровно в одной позиции, т.е. $(\exists!\,n\in\mathbb N)\bigl(\,x(n)\ne y(n)\,\bigr)$.

Размежеванием назовем такую функцию $\delta:X\to\{0,1\}$,
что $\delta(x)\ne \delta(y)$ для любой пары смежных последовательностей $x,y\in X$.

Гипотеза.
Существует размежевание.

[Профессор Снэйп]

Скажем, что последовательности $x,y \in X$ эквивалентны, если множество

$$ \{ n \in \mathbb{N} : x(n) \neq y(n) \} $$

конечно. Ясно, что введённое отношение есть отношение эквивалентности и что функцию размежевания $\delta$ можно задавать независимо на каждом классе эквивалентности. Выберем в каждом классе эквивалентности $m$ представитель $x^m$ и для любого $y \in m$ положим $\delta(y)$ равным остатку от деления количества элементов множества $\{ n \in \mathbb{N} : y(n) \neq x^m(n) \}$ на $2$.

-- Вс май 30, 2010 21:52:41 --

Кстати, видно, что любая функция размежевания задаётся подобным образом. Следовательно, всего различных функций размежевания будет два в степени континуум.

[Padawan]

Будем смотреть на $X$ как на линейное пространство над полем $\mathbb Z_2$. Рассмотрим его подпространство $L\subset X$, состоящее из всех финитных последовательностей. Определим на $L$ линейный функционал $\delta(x)=\sum\limits_{n\in\mathbb N} x(n)$. Дальше продолжим этот функционал с $L$ на всё $X$ с сохранением линейности. Продолжение обозначим тем же символом $\delta$. Оно будет искомым размежеванием.

Линейное продолжение $\delta$ с $L$ на $X$ легко организуется при помощи базисов Гамеля: дополняем базис Гамеля $L$ до базиса Гамеля $X$ и на новых векторах определяем $\delta$ произвольным образом, например, нулями.

[AGu]

Профессор Снэйп в сообщении #325659 писал(а):

Выберем в каждом классе эквивалентности $m$ представитель $x^m$ и для любого $y \in m$ положим $\delta(y)$ равным остатку от деления количества элементов множества $\{ n \in \mathbb{N} : y(n) \neq x^m(n) \}$ на $2$.

Браво, Профессор!
Вы блестяще реализовали идею одного из решений, задуманных вашим покорным.

Среди прочих подходов было задумано довольно утомительное применение
леммы Цорна к упорядоченному множеству «частичных размежеваний».

Еще есть простое решение на основе теоремы de Bruijn — Erdős о раскраске графов
(из раскрашиваемости конечных подграфов следует раскрашиваемость всего графа).

А еще было задумано (не для публики) решение в рамках нестандартной теории множеств,
где размежевание получается как стандартизация «гиперконечного размежевания».

Профессор Снэйп в сообщении #325659 писал(а):

Кстати, видно, что любая функция размежевания задаётся подобным образом. Следовательно, всего различных функций размежевания будет два в степени континуум.

Выражаю Вам свое $\varphi$.
Я сам планировал задать вопрос о количестве размежеваний!

Padawan в сообщении #325661 писал(а):

Будем смотреть на $X$ как на линейное пространство над полем $\mathbb Z_2$. Рассмотрим его подпространство $L\subset X$, состоящее из всех финитных последовательностей. Определим на $L$ линейный функционал $\delta(x)=\sum\limits_{n\in\mathbb N} x(n)$. Дальше продолжим этот функционал с $L$ на всё $X$ с сохранением линейности.

Прелесть!
Уж не знаю, следует ли мне стыдиться, но такого финта я не ожидал.
Я не устаю восхищаться Вашим джедайством, Padawan!

Отмечу, что все решения (и задуманные, и воспроизведенные)
так или иначе опираются на аксиому выбора.
Подозреваю, что без нее существование размежевания недоказуемо.

[Профессор Снэйп]

Вот, по моему, из той же серии: как определить $\mathrm{sgn}(\sigma)$ для перестановки $\sigma: \mathbb{N} \to \mathbb{N}$?

[Профессор Снэйп]

Нет, действительно интересно.

Пусть $\mathrm{Perm}(\mathbb{N})$ --- группа всех перестановок натурального ряда, а $\mathrm{Perm}_{\mathrm{fin}}(\mathbb{N})$ --- её подгруппа, состоящая из всех перестановок с конечным носителем (то есть таких перестановок $\sigma$, для которых множество $\{ x \in \mathbb{N} : \sigma(x) \neq x \}$ конечно). Для каждой $\sigma \in \mathrm{Perm}_{\mathrm{fin}}(\mathbb{N})$ определим $\mathrm{sgn}(\sigma) \in \{ -1, 1 \}$ следующим образом: $\mathrm{sgn}(\sigma) = 1$ тогда и только тогда, когда $\sigma$ может разложена в произведение чётного числа транспозиций.

В стандартном курсе алгебры доказывается, что это определение корректно и что для любых $\sigma, \tau \in \mathrm{Perm}_{\mathrm{fin}}(\mathbb{N})$ справедливо равенство $\mathrm{sgn}(\sigma \circ \tau) = \mathrm{sgn}(\sigma) \cdot \mathrm{sgn}(\tau)$.

Вопрос: можно ли продолжить функцию $\mathrm{sgn}$ на всю группу $\mathrm{Perm}(\mathbb{N})$ так, чтобы сохранялось указанное равенство?

[Mathusic]

Ваш вопрос эквивалентен, очевидно, выяснению существования гомоморфизма $ \operatorname{sgn}: \mathrm{Perm}(\mathbb{N}) \to (\{\pm1\}, \cdot)$, уже определённого на перестановках с конечным носителем.
Очевидно, например, что если вообще не существует гомоморфизма из $\mathrm{Perm}(\mathbb{N})$ в $(\{\pm1\}, \cdot)$, то ответ на ваш вопрос отрицательный.

P.S. Простой вопросик: гомоморфна ли группа $\mathrm{Perm}(\mathbb{N})$ некоторой конечной группе $G \not=\{e\}$?

[Профессор Снэйп]

Пусть $G = \mathrm{Perm}(\mathbb{N})$ и $H = \mathrm{Perm}_{\mathrm{fin}}(\mathbb{N})$. Ясно, что $H$ --- нормальная подгруппа в $G$. Задачу можно свести к следующим двум пунктам:

1) Найти сюрьективный гомоморфизм из $G/H$ на $\langle \{ -1,1 \}, \cdot \rangle \cong \langle \mathbb{Z}_2, + \rangle$, либо доказать, что такого гомоморфизма не существует.

2) Допустим, что гомоморфизм $\varphi$ из предыдущего пункта существует. Требуется найти (анти)гомоморфизм $f : G/H \to G$, такой что $f(gH) \in gH$ для любой перестановки $g \in G$, либо доказать, что подобного гомоморфизма не существует.

Если $\varphi$ из первого пункта и $f$ из второго пункта существуют, то мы, как и в случае с размежеваниями, сможем легко продолжить $\mathrm{sgn}$ на $G$, положив $\mathrm{sgn}(f(gH)h) = \varphi(gH) \cdot \mathrm{sgn}(h)$ при любых $g \in G$ и $h \in H$. То есть положительный ответ на вопросы обоих пунктов является достаточным для утверждения о существовании продолжения функции $\mathrm{sgn}$. Насчёт его необходимости не уверен...

-------------------

Но всё это конечно, довольно муторно. Лучше, не обращая внимания на факторы, доказать следующий простой факт: продолжение $\mathrm{sgn}$ на группу $G$ существует тогда и только тогда, когда в $G$ существует подгруппа индекса $2$, не содержащая ни одной транспозиции. И сформулировать задачу как задачу о существовании такой подгруппы.

-- Вт июн 08, 2010 15:02:04 --

P. S. Хотел написать вместо "существование подгруппы" фразу "существование нормальной подгруппы", но вовремя вспомнил, что каждая подгруппа индекса $2$ нормальна

-- Вт июн 08, 2010 15:08:06 --

Для начала зададимся совсем простым вопросом: существует ли в $G$ хоть какая-нибудь подгруппа индекса $2$ (неважно, содержащая транспозиции или нет). Или подгруппа хоть какого-нибудь конечного индекса (вопрос, заданный Mathusic в предыдущем сообщении)?

[Mathusic]

Просто гомоморфизм $\mathrm{Perm}(\mathbb{N})$ на $(\mathbb{Z}_2,+)$ существует.

[Профессор Снэйп]

Покажите этот гомоморфизм, пожалуйста.

[Mathusic]

Посмотрел на свой вчера сочинённый пример, оказалось, это не пример.

[Mathusic]

Профессор Снэйп, а вам самим известен пример нужного гомоморфизма? А то что-то я уже стал сомневаться в его существовании...

[Профессор Снэйп]

Нет, не известен.

[Sonic86]

Профессор Снэйп писал(а):

Для начала зададимся совсем простым вопросом: существует ли в $G$ хоть какая-нибудь подгруппа индекса $2$ (неважно, содержащая транспозиции или нет).

$$\{ \sigma: \sigma (1) = 1 , \sigma (2) = 2 \}$$

или нет?

[Padawan]

подстановки $\tau$, $\rho$ принадлежат одному классу смежности по подгруппе $G$, тогда и только тогда, когда $\tau(1)=\rho(1)$, $\tau(2)=\rho(2)$. Так что этих классов смежности $|X|^2=|X|$ (каждый класс смежности однозначно задаётся первыми двумя элементами подстановки).