Доказательство: биекция, композиция, симметрия

[DaddyM]

Изучаю "Основы классического и современного математического анализа" Ляшко, Емельянова, Боярчука. На стр. 19 пункт 1.9 этой книги приведено упражнение №5 в решении которого у меня есть затруднение.

Задача (цитата):
Биекция $f:X\leftrightarrow X$ называется симметрией, если $f^{-1}=f$. Доказать, что любая биекция множества на себя представима в виде композиции двух симметрий.

Ниже привожу набросок своего решения.

Решение:
Условие не специфицирует конечность или счётность множества. В тексте учебника до этого упражнения рассматриваются любые множества. Поэтому трактую условие задачи для любых множеств.

1) Запишем задачу на математическом языке

Пусть $f$ - биекция множества $X$ на себя: $f: X\leftrightarrow X$.
Пусть $h$ - симмерия на множестве $X$, что означает: $h: X\leftrightarrow X$ and $h^{-1} = h$.
Пусть $g$ - симметрия на множестве $X$, что означает: $g: X\leftrightarrow X$ and $g^{-1} = g$.

2) Требуется доказать, что

$$\forall f:X\leftrightarrow X \exists (h:X\leftrightarrow X, h^{-1}=h \;\text{и}\; g:X\leftrightarrow X, g^{-1}=g):f= g\circ h.$$

3) Доказательство

Доказать, что существуют $h$ и $g$, такие что $f=g\circ h$.

1. Композиция симметрий - есть композиция биекций по определению. Композиция биекций - есть биекция согласно теореме (см, например, Кострикин Алгебра том 1).
2. Не могу доказать, что для любой биекции есть такая композиция, что она из двух симметрий. Понимаю, что могу представить любую биекцию в виде композиции биекций, например, поставив в область значений $h(x)$ множество равное области определения $f(x)$, но с одной перестановкой. Интуитивно понимаю, что среди всех возможных вариантов (перестановок, не уверен, что подходящий термин для бесконечного множества) есть симметрии такие, которые дают композицию симметрий, но никак не найду откуда схватиться, чтобы логически это доказать в общем случае.


Прошу помочь разобраться в доказательстве.

[arseniiv]

(Сомнительный термин они выбрали, конечно — «симметрия», когда обычно симметрии не так специфичны, а в этом случае говорят «инволюция».)

DaddyM
Придётся, видимо, следить за орбитами $a\to f(a)\to f(f(a))\to\ldots$ элементов при этой биекции; будем рассматривать их все как ориентированный граф. Например если у нас выйдет доказать для связного графа (все элементы входят в одну орбиту), то точно выйдет и для произвольного (собирая функции из кусочков, определённых на непересекающихся подмножествах $X$). Биективность $f$ ясно переводится в свойство этого графа: каждая вершина должна иметь по одному входящему и исходящему ребру.

Орбиты при биекции бывают только нескольких простых видов, попробуйте для каждого.

[DaddyM]

arseniiv в сообщении #1426499 писал(а):

(Сомнительный термин они выбрали, конечно — «симметрия», когда обычно симметрии не так специфичны, а в этом случае говорят «инволюция».)

DaddyM
Придётся, видимо, следить за орбитами $a\to f(a)\to f(f(a))\to\ldots$ элементов при этой биекции; будем рассматривать их все как ориентированный граф. Например если у нас выйдет доказать для связного графа (все элементы входят в одну орбиту), то точно выйдет и для произвольного (собирая функции из кусочков, определённых на непересекающихся подмножествах $X$). Биективность $f$ ясно переводится в свойство этого графа: каждая вершина должна иметь по одному входящему и исходящему ребру.

Орбиты при биекции бывают только нескольких простых видов, попробуйте для каждого.

Спасибо, с этой стороны не рассматривал. А разве графы подойдут нам для несчётного множества, ведь оно может быть несчётно?

Я пока ещё верю, что задачи приводятся авторами так, что их можно решить, пользуясь почти полностью аппаратом, который авторы дали в предшествующей теории. В случае этой книги авторы дали следующие понятия (привожу основные по порядку):
- множество с операциями, универсум, пустое множество
- натуральные числа
- метод математической индукции
- упорядоченная пара
- декартово произведение
- бинарное отношение, проекция бинарного отношения, сечение бинарного отношения, обратное бинарное отношение
- функциональное бинарное отношение
- отображение, область отправления/прибытия отображения, график отображения, специальные виды отображений (единичное, постоянное), область определения/значений отображения, отображение "в", отображение "на", образ и прообраз элемента множества при отображении,
- обратное отображение, биекция
- композиция отображений
в задачах дали доказать $f\circ (g\circ h)=(f\circ g)\circ h, f\circ f^{-1}=1_Y, f^{-1}\circ f=1_X, f\circ 1_X=f, 1_Y\circ f = f$

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

[vpb]

1) Это задача, собственно, по алгебре, а не по анализу. См. учебник Кострикина.
2) Докажите, что $n$-цикл $(1,2,\ldots,n-1,n)$ является произведением двух подстановок порядка 2 из $S_n$ (повозиться надо будет, однако....). (В вырожденном случае $n=2$ одну из этих подстановок берем единичной, так что, строго говоря, правильнее было бы написать "порядка не более 2"; а иначе при $n=2$ не получится.)
3) Используя это и разлагая произвольную подстановку на циклы, докажите, что любой элемент из $S_n$ --- произведение двух элементов порядка не более $2$.
4) Можно показать (а вдруг сумеете ?), что бесконечный цикл $(\ldots,-2,-1,0,1,2,3,4,\ldots)$ НЕ является произведением двух инволюций, внезапно. Так что для бесконечных множеств утверждение задачи неверно.
5) Поменьше общих слов !
6) Не всё во всех книжках хорошо. Есть и пробелы в изложении (часто), и ошибки (иногда). Привыкайте.

[eugensk]

vpb в сообщении #1426529 писал(а):

бесконечный цикл $(\ldots,-2,-1,0,1,2,3,4,\ldots)$ НЕ является произведением двух инволюций

Что если сперва $x \rightarrow -x$, потом $x \rightarrow 1-x$ ?
И для любого другого бесконечного цикла, если какой-то его элемент обозначить нулём.

[vpb]

eugensk в сообщении #1426530 писал(а):

Что если сперва $x \rightarrow -x$, потом $x \rightarrow 1-x$ ?

Действительно, это я ошибку сделал (и сейчас минут 5 не мог понять, в каком месте...). Т.е. утверждение задачи таки верно всегда.

-- 18.11.2019, 09:20 --

eugensk в сообщении #1426530 писал(а):

для любого другого бесконечного цикла,

Да и не бесконечного тоже (впрочем, это уже подсказка ТС).

[vpb]

DaddyM
"Не могу молчать. " (с)

Про учебник. Посмотрел его. Как-то слишком своеобразно, в плохом смысле. Слишком конспективно, и с претензиями на общность и абстрактность. (При том, что авторы как математики отнюдь не большие.).

Через полторы страницы будет порция задач про мощность. Там например, даются в качестве упражнений (а) доказать неравномощность $X$ и $2^X$, и (б) доказать теорему Кантора-Бернштейна-Шредера, фактически на пустом месте. Интересно, каким образом предполагается, что студенты это решать будут ?

В общем, советую бросить эту книжку и читать нормальные учебники, как-то: Фихтенгольц, Зорич, Кудрявцев, Камынин, Решетняк, Никольский. Или по крайней мере не только ее читать.

[arseniiv]

vpb в сообщении #1426529 писал(а):

повозиться надо будет, однако....

Я вчера (но поздно, чтобы сюда написать) придумал удобную аналогичную задачу, которая должна уменьшать количество возни: есть правильный $n$-угольник, включая $\infty$-угольник — прямую, разбитую на примыкающие друг к другу отрезки равной длины. Этот $n$-угольник нам будет заодно напоминать про орбиту при биекции. Мы хотим перевести каждую вершину в соседнюю по одну и ту же сторону, и для «круглого» многоугольника это будет поворот, а для «прямого» — параллельный перенос. Но действовать мы можем только отражениями (привет инволюциям из этой задачи). И тут можно помнить из геометрии, как представить и тот, и тот композицией двух отражений, притом в нашем случае они будут и симметриями (в нормальном смысле а не как в том учебнике) многоугольника, то есть они переводят интересующие нас точки в них же, а не куда-то в другое место плоскости. Так что мы получили конструкцию, которую и хотели: какие две инволюции одной орбиты при биекции (конечной ли, бесконечной ли) надо сделать, чтобы получить эту биекцию.

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

vpb в сообщении #1426529 писал(а):

4) Можно показать (а вдруг сумеете ?), что бесконечный цикл $(\ldots,-2,-1,0,1,2,3,4,\ldots)$ НЕ является произведением двух инволюций, внезапно. Так что для бесконечных множеств утверждение задачи неверно.

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

[iifat]

arseniiv в сообщении #1426563 писал(а):

можем выразить двумя инволюциями вообще любую степень нашей биекции

Не потому ли, что любая степень биекции оказывается опять же биекцией? Или я чего не понял?

[arseniiv]

iifat в сообщении #1426586 писал(а):

Не потому ли, что любая степень биекции оказывается опять же биекцией?

Да, и поэтому, но в таком виде это скучно.

[vpb]

(Оффтоп)

arseniiv в сообщении #1426563 писал(а):

Что интересно, я вчера тоже долго так думал,

Ибо во многом знании много печали.... (т.е. от большого ума мысль может не туда поехать).

[DaddyM]

vpb в сообщении #1426538 писал(а):

DaddyM
"Не могу молчать. " (с)

Про учебник. Посмотрел его. Как-то слишком своеобразно, в плохом смысле. Слишком конспективно, и с претензиями на общность и абстрактность. (При том, что авторы как математики отнюдь не большие.).

Через полторы страницы будет порция задач про мощность. Там например, даются в качестве упражнений (а) доказать неравномощность $X$ и $2^X$, и (б) доказать теорему Кантора-Бернштейна-Шредера, фактически на пустом месте. Интересно, каким образом предполагается, что студенты это решать будут ?

В общем, советую бросить эту книжку и читать нормальные учебники, как-то: Фихтенгольц, Зорич, Кудрявцев, Камынин, Решетняк, Никольский. Или по крайней мере не только ее читать.

Спасибо за это. У меня есть аналогичные мысли на тему учебника Ляшко, Емельянова, Боярчука, но посоветоваться было не с кем.
Начинал с двухтомника Никольского (1990 г.) и двухтомника Фихтенгольца (Краткий курс). В этих книгах изложение начинается с действительного числа.
Кудрявцев (трёхтомник 80-е) норм, куча опечаток правда. Он начинает с множеств. Вводит натуральные, целые числа. Это хорошо, но он обходит топологию совсем как-то упрощая всё.
У Боярчука (обсуждаемая книга) мне понравился подход к изложению. Он нестандартный для курсов по матану - авторы используют тополого-множественный подход для введения. Понятия мажоранты, миноранты, супремума, инфимума, предела последовательности вводятся без рассмотрения чисел. Порядок изложения красивый - множество, отношение порядка, упорядоченное пространство. Классические курсы начинают с действительного числа, хотя по сути это конкретика, а не беспристрастная абстракция, какой является теоретико-множественная топология. Такой подход перекликается с подходами Дьедонне, Шварца, Грауэрта.

Решетняка и Камынина не видел книги. Надо посмотреть.

Что Вы думаете относительно достоинств и недостатков классического и топологического подходов при начале изучения мат анализа?

P.S. однако странно, что у Ляшко, Боярчука упражнения нерешаемы без привлечения дополнительного теоретического аппарата. Я думал, что не вижу какую-то очевидность и сейчас ребята на форуме укажут мне на неё. А тут надо часть Кострикина сначала перелопатить, чтобы решить задачку из первого параграфа.

-- 18.11.2019, 21:30 --

arseniiv в сообщении #1426499 писал(а):

(Сомнительный термин они выбрали, конечно — «симметрия», когда обычно симметрии не так специфичны, а в этом случае говорят «инволюция».)

DaddyM
Придётся, видимо, следить за орбитами $a\to f(a)\to f(f(a))\to\ldots$ элементов при этой биекции; будем рассматривать их все как ориентированный граф. Например если у нас выйдет доказать для связного графа (все элементы входят в одну орбиту), то точно выйдет и для произвольного (собирая функции из кусочков, определённых на непересекающихся подмножествах $X$). Биективность $f$ ясно переводится в свойство этого графа: каждая вершина должна иметь по одному входящему и исходящему ребру.

Орбиты при биекции бывают только нескольких простых видов, попробуйте для каждого.

Орбита для меня новое понятие. Где посоветуете почитать релевантный материал?

[arseniiv]

DaddyM в сообщении #1426644 писал(а):

Орбита для меня новое понятие. Где посоветуете почитать релевантный материал?

Если в какой-то глубине, то там, где говорят про действие (полу)групп на множествах; в теории групп может быть, в комбинаторике, в теории динамических систем. Но конкретно здесь ничего особенного о свойствах орбит знать не надо — тут нужно просто разбить $X$ на $f$-орбиты, чтобы удобнее записать решение (и найти его изначально это помогает). Две точки $x, y\in X$ входят в одну орбиту, если одна переходит в другую несколькими применениями $f$, иначе говоря существует целое $n$ такое, что $f^n(x) = y$. Ну и дальше можно будет пронумеровать точки одной орбиты и через эту нумерацию очень быстро описать инволюции, которые вдвоём дадут $f$.

-- Пн ноя 18, 2019 22:55:43 --

Это даже не самое общее понимание орбиты, довольно простое выходит. Бывает сложнее.

[eugensk]

Наверное, не надо сильно напирать на то, что будто бы задача больше из алгебры чем из анализа (математика одна!), и правильно, что тут ничего дополнительно для решения знать не надо. А то выработается отношение "мы это еще не проходили", и это станет впоследствии проблемой :)

[arseniiv]

Да, не нужно, но решение уже почти и изложено: деталь тут, подход там… даже аллюзии с движениями плоскости (что меня лично найти порадовало, не знаю как других).