Ещё немного биекций

[Asker Tasker]

Задача 1
Отобразите взаимно однозначно луч $0 \leq x < \infty$ на всю числовую прямую.
1. Первое, что приходит в голову, - это экспонента (с обратной функцией логарифмом), но для неё нужно избавиться от нуля, тогда биекция будет такой:
$ y = $\ln(x)$ $
$0 < x < \infty \leftrightarrow -\infty < x < \infty$
2. Чтобы избавиться от нуля, выберем во множестве $0 < x < \infty$ последовательность $ \{ a_{n} \} = \{ \frac{1}{n} \}_{n=1}^{\infty}$. А теперь построим последовательность $ \{ b_{n} \}$, такую, что $b_{1} = 0$ и $b_{k} = a_{k-1} (k > 1)$. Все члены каждой из последовательностей различны, поэтому последовательности задают две следующие биекции со множеством натуральных чисел:
$a_{n} \leftrightarrow \mathbb{N}$
$ \mathbb{N} \leftrightarrow b_{n}$
Композиция этих биекций - одна часть биекции, необходимой для пункта 2, а вторая часть - перевод всех оставшихся (вне последовательностей) точек исходных множеств в самих себя.

Задача 2
Установите взаимно однозначное соответствие между точками открытого квадрата $0 < x < 1; \ 0 < y < 1$ и точками плоскости.
Идей как-то маловато. Поскольку оба множества счётны (это предполагается известным), то можно занумеровать элементы одного, элементы другого и поставить в соответствие друг другу элементы с одинаковыми номерами. Но вот как сделать это конструктивно?! Потому что доказать счётность множества $\mathbb{Q}^{2}$ просто, а вот явно занумеровать - это уже я не знаю как.

Другая идея - воспользоваться чем-то известным. При доказательстве несчётности множества Кантора используется переход в другую систему счисления и с кучей всяких нюансов всё-таки удаётся построить биекцию. Может, и тут можно сделать что-то такое? Допустим, начнём с двоичной системы, тогда каждому числу соответствует пара последовательностей нулей и единиц. А нам нужна одна последовательность. Первое, что приходит в голову, - смешать эти последовательности, например, беря в качестве чётных членов представителей первой, а в качестве нечётных - второй. И вроде бы всё хорошо, но внутренний голос подсказывает, что чего-то не хватает. Может, подскажете, чего именно? Или обрадуете, что всё хорошо :)


Задача 3
Установите биекцию между множеством всех целых чисел и множеством всех квадратных трёхчленов с целочисленными коэффициентами.
Ну, квадратный трёхчлен - это $ ax^{2} + bx + c $. Он взаимно однозначно задаётся тройкой целых чисел $(a; b; c)$. То есть (если я нигде ничего не напутал), нужно построить биекцию $\mathbb{Z} \leftrightarrow \mathbb{Z}^{3}$

Для случая неотрицательных целых чисел, кажется, достаточно рассмотреть тройку как цифры записи числа (с учётом возможных нулей в начале тройки, естественно), но вот что делать в общем целом случае?

[Joker_vD]

Во второй задаче можно тангенс попробовать: тангенс дает взаимно-однозначное соответствие между $(-\frac\pi2,\frac\pi2)$ и $\mathbb R$. Ну, а уж превратить $(0,1)$ в $(-\frac\pi2,\frac\pi2)$ вы сумеете.

В третьей много способов, но можно, например, так: раздуваете сферу с центром в $(0,0,0)$ и нумеруете точки $\mathbb Z^3$ по мере того, как они проходят сквозь эту сферу.

[Asker Tasker]

Joker_vD в сообщении #589434 писал(а):

Во второй задаче можно тангенс попробовать: тангенс дает взаимно-однозначное соответствие между $(-\frac\pi2,\frac\pi2)$ и $\mathbb R$. Ну, а уж превратить $(0,1)$ в $(-\frac\pi2,\frac\pi2)$ вы сумеете.

Вы имеете в виду следующее (или я Вас не так понял):
1. строим биекцию $(0; 1) \leftrightarrow (-\frac{\pi}{2}; \frac{\pi}{2})$ функцией $y = \pi \cdot x - \frac{\pi}{2}$
2. строим биекцию $(-\frac\pi2,\frac\pi2) \leftrightarrow \mathbb R$ функцией $y = $\tg(x)$ $
3. множеству точек открытого квадрата ставим в соответствие множество точек $ (tg(x); tg(y)) $
?

А вот со сферами что-то не очень понял. Первая точка (и она же - первая сфера) - начало координат. А как теперь увеличивать? С целым приращением, наверное? Если да, то следующая сфера - единичная. В неё попадут точки $(1; 0; 0), (0; 1; 0), (0; 0; 1)$... Понятно, что в сферу данного радиуса попадёт лишь конечное число "целочисленных" точек, но, насколько я понимаю задание, нужно построить явную биекцию

[Joker_vD]

Да, по второй так.

По третьей... "явная" — это все-таки сильное слово Можно каждой тройке $(x,y,z)$ сопоставить "вес" $|x|+|y|+|z|$, разбить $\mathbb Z^3$ на семейства троек с одним "весом" ($0,1,2,\ldots$), пронумеровать тройки внутри каждого семейства (их там конечное число), а затем сшить эти нумерации.

По крайней мере, явной аналитической формулы нету.

[Asker Tasker]

Joker_vD в сообщении #589470 писал(а):

По крайней мере, явной аналитической формулы нету.

О. Задача становится интереснее.
Поясню. Предыдущие задачи либо сводились к тангенсам/экспонентам, либо к выделению счётной/несчётной части во множестве и построения биекции (отрезок в интервал, сфера в сферу без одной точки и так далее) - то есть можно было явно и внятно указать правило сопоставления точек. А вот в трёх задачах не знаю, что делать:
а)Установите биекцию между множеством всех целых чисел и множеством всех квадратных трёхчленов с целочисленными коэффициентами.
б)Установите биекцию между множеством всех действительных чисел и множеством всех точек плоскости
в)Установите биекцию между множеством всех действительных чисел и множеством всех квадратных трёхчленов с действительными коэффициентами.

Задачу а) мы вроде бы решили: или по сферам нумеровать, или по высоте, или ещё как-то наверняка можно.
Задача в) вроде бы похожая, но всё же там действительные числа - по сферам и высоте уже не занумеруешь.. Видимо, не зря эта задача после задачи б) идёт) Наверное, предполагается, что если удастся построить биекцию с плоскостью, то и с пространством (тройки точек) удастся. Хочется верить :)

Вот задача б). Может, как я уже где-то писал, чётно-нечётно расположить цифры, соответствующие координатам точки плоскости - тогда получим точку на прямой, а из записи числа на прямой тем же методом восстановить какую-то точку на плоскости. Но тут возникает проблема с двоякими записями: $7,(9) = 8,(0)$ и всё такое.. Как их можно обойти? Будет ли достаточно просто сказать "при двояком варианте записи числа рассматриваем представление с нулями"?

Хотя можно иначе. На прямой счётное множество целых чисел, кратных десяти. В любом единичном отрезке при делении его на десять частей получаем конечное число отрезков. При делении этих "маленьких отрезков" на десять частей... и так далее. В общем, получим, что число "двояких" точек на прямой счётно. Тогда на плоскости имеем декартово произведение счётных множеств - опять счётное множество. По определению между ними можно установить биекцию. Это не конструктивно, но, кажется, правильно. Или всё-таки нет, как считаете? Какой вариант лучше (если хоть один правилен)?

-- 27.06.2012, 03:14 --

P.S.
А с трёхмерным пространством - брать (3k-2)-ую цифру, (3k-1)-ую и 3k-ую цифру числа на прямой и ставить им в соответсвие k-ую цифру числа на той или иной оси координат? Как-то слишком просто