нумерация положительных рациональных чисел

[RIP]

Определим функции $f\colon(0;+\infty)\to(0;+\infty)$ и $g\colon\mathbb N_0\to\mathbb Q\cap(0;+\infty)$ с помощью формул

$$f(x)=\frac1{\lfloor x\rfloor+1-\{x\}};$$

$$g(0)=1,\quad g(n+1)=f(g(n)).$$

Докажите, что $g$ --- биекция.

[Circiter]

Простите, а как следует понимать выражение $\mathbb Q \cap (0; +\infty)$? Расшифруйте чайнику...

[RIP]

Circiter в сообщении #277136 писал(а):

Простите, а как следует понимать выражение $\mathbb Q \cap (0; +\infty)$?

Это множество положительных рациональных чисел.

[Circiter]

Возможно опять глупость выйдет, но все-таки попробую порассуждать.

Насколько я понимаю, биективность $g$ равносильна отсутствию одинаковых элементов в последовательности $\{g(i)\}_{i=0}$. Если это не так, то дальше можете не читать.

Предлагаю два наброска:

1. Как можно доказать, что все $g(i)$ различны (попарно)? Очевидно, что если в этой последовательности действительно нет одинаковых элементов, то $g$ должна быть непериодична, или, иначе говоря, уравнение $g(n+T)=g(n)$ не должно иметь решений относительно $T\in\mathbb{N}$. Пользуясь определением $g$ можно записать это уравнение в виде
   $$g(n)=\underbrace{f(f(\ldots f}_{T}(g(n))\ldots)),$$
   и, таким образом, свести задачу к доказательству несуществования рациональных неподвижных точек композиции $T>0$ "штук" $f$ (i.e. неподвижных точек последовательных итераций $f$ или периодичных точек этого отображения).
   
   Как это доказать, незнаю. Интересно, следует ли несуществование периодичных точек $f$ из несуществования неподвижной точки $x=f(x)$? Наверное нет...
2. Следует ли биективность из однозначности (сюръективности) и обратимости (инъективности)? Если да, то достаточно (и необходимо) показать, что $g$ однозначна и обратима. Функция $g$ определяется через итерации $f$ и такая композиция нескольких копий $f$ является однозначной функцией, так как сама $f$ -- однозначна. Кроме того, эта композиция обратима, так как $f$ -- обратима (это легко проверить, пример обратной функции:$f^{-1}=\lfloor x^{-1}\rfloor+1-\{x^{-1}\}$). Получается, что $g$ тоже обладает этими свойствами, что особенно хорошо видно если записать определение этого отображения как $g(n)=f(f(\ldots f(1)\ldots))$, где $f$ входит в выражение ровно $n$ раз. То есть значение $g(n)$ зависит только от количества итераций $f$.

Э-э-э, бред какой-то получился... Не, точно бред, хотя-бы потому, что рациональность не эксплуатируется (разве что для удобства округления вниз и взятия дробной части). В общем, дайте подсказку.

[Дима Тишков]

А задача-то красивейшая.
Если я нигде не наврал, то я решил ее построив $g^{-1}$ с помощью конструкции, практически совпадающей с этой. Там только пару деталей изменить надо.

[covax]

Circiter в сообщении #277676 писал(а):

Следует ли биективность из однозначности (сюръективности) и обратимости (инъективности)?

Да.

Circiter в сообщении #277676 писал(а):

Получается, что $g$ тоже обладает этими свойствами, ...

Нет. Попробуйте, например, с функцией $f(x)=x$.

----

$\frac11, (1)$

$\frac12,\frac21, (2)$

$\frac13,\frac32,\frac23,\frac31, (4)$

$\frac14,\frac43,\frac35,\frac52,\frac25,\frac53,\frac34,\frac41, (8)$

$\frac15,\frac54,\frac47,\frac73,\frac38,\frac85,\frac57,\frac72,\frac27,\frac75,\frac58,\frac83,\frac37,\frac74,\frac45,\frac51, (16)$

$...$ двоично тут как-то все

И вот, что-то очень похожее:

[Дима Тишков]

Что мне не нравится в моем решении - это необходимость рассматривать 5 случаев. Обозначая $d_n$ строку из $n$ цифр $d$:

\begin{align*} \dots 00&\xrightarrow{+1}\dots 01 &&\longleftrightarrow & [0;k+1,\dots]&\xrightarrow f[1;k,\dots]\\ \dots 10&\xrightarrow{+1}\dots 11 &&\longleftrightarrow & [0;1,k,\dots]&\xrightarrow f[k+1;\dots]\\ \dots 001_n&\xrightarrow{+1}\dots 010_n &&\longleftrightarrow & [n;k+1,\dots]&\xrightarrow f[0;n,1,k,\dots]\\ \dots 101_n&\xrightarrow{+1}\dots 110_n &&\longleftrightarrow & [n;1,k,\dots]&\xrightarrow f[0;n,k+1,\dots]\\ 1_n&\xrightarrow{+1}10_n &&\longleftrightarrow & [n]&\xrightarrow f[0;n,1]\\ \end{align*}

Есть ли способ избежать такого разбора вариантов?

[RIP]

Честно говоря, удивлён, что никто до сих пор не кинул ссылку. Ладно, раскрою карты. Решение есть, например, в "Доказательствах из Книги". Половину решения можно посмотреть здесь.