Установить взаимно-однозначное соответствие

[gogoshik]

Прошу помочь, плиз, с такой задачей. Необходимо установить взаимно-однозначное соответствие между множествами $\mathbb{Q}^+$ и $\mathbb{N}$. Что-то я не понимаю как это сделать?
Есть идея рассмотреть пары чисел $(m, n)$ (числитель и знаменатель дроби) и каждой такой паре сопоставить число из $\mathbb{N}$, но как это правильно сделать ...

[provincialka]

gogoshik
Ну, либо книжки почитайте... либо расположите свои пары $(m,n)$ в виде бесконечной таблицы и помедитируйте над ней...

[gogoshik]

provincialka, книжки почитать я могу, но Вы уточните какие? Я конечно могу и погуглить, но не хочу прочитать ответ.

provincialka в сообщении #1274690 писал(а):

в виде бесконечной таблицы и помедитируйте над ней

C этой техникой я мало знаком ). Это как?

[provincialka]

Понимаете, я же не могу (по правилам) выдать вам полное решение... Ну, давайте попробую намекнуть. Вот, у вас есть множество пар натуральных чисел $(m,n)$. "установить взаимно-однозначное соответствие с $\mathbb N$" -- значит пронумеровать эти пары.

Вот и запишите их в виде таблички и попробуйте клтки таблички пронумеровать. Но "не уходя в бесконечность"

[arseniiv]

Там, конечно, будут попадаться пары, соответствующие одинаковым рациональным числам, но с этим можно справиться.

Кстати, а вы уже доказывали, что объединение счётного семейства конечных множеств счётно? Если да, это можно применить к сей таблице довольно прямо. Хотя ещё прямее — что объединение счётного семейства и счётных множеств тоже счётно.

[Dan B-Yallay]

gogoshik
как Вы думаете, здесь все дроби вида $\dfrac m n$ перечислены или каких-то не хватает?

$$ \begin{matrix} \dfrac 1 1 & \dfrac 1 2& \dfrac 1 3 & \dfrac 1 4 & \ldots \end{matrix} $$

[gogoshik]

Когда я в начале темы написал, что нужно "каждой паре сопоставить число из $\mathbb{N}$", то я под этим понимал нумерацию пар. Я даже представил это в виде таблице (аналог таблицы умножения), где допустим по строкам располагаются числа $m_1, m_2, ..., m_k$, а по столбцам числа $n_1, n_2, ..., n_k$. На пересечении строка/столбец стоит число $m_i/n_j$. Запнулся на том моменте, что встречаются одинаковые числа: $1/1, 2/2, ...; 2/1, 4/2, ...$.

-- 14.12.2017, 01:12 --

Dan B-Yallay в сообщении #1274701 писал(а):

как Вы думаете, здесь все дроби вида $\dfrac m n$ перечислены или каких-то не хватает?

$$ \begin{matrix} \dfrac 1 1 & \dfrac 1 2& \dfrac 1 3 & \dfrac 1 4 & \ldots \end{matrix} $$

В моем представлении должно быть как то так: $1/1, 1/2, 1/3, 1/4, ...; 2/1, 2/2, 2/3, 2/4, ...; 3/1, 3/2, 3/3, 3/4, ...; ...$

[Dan B-Yallay]

gogoshik в сообщении #1274702 писал(а):

В моем представлении должно быть как то так: $1/1, 1/2, 1/3, 1/4, ...; 2/1, 2/2, 2/3, 2/4, ...; 3/1, 3/2, 3/3, 3/4, ...; ...$

Верно, только давайте, Вы поместите дроби с числителем 2 во вторую строчку, с числителем 3 - в третью и т.д.

[arseniiv]

gogoshik
А вы можете что-то установить, если имеете сюръекцию из $\mathbb N$ в интересующее множество?

[Dan B-Yallay]

gogoshik в сообщении #1274702 писал(а):

Я даже представил это в виде таблице (аналог таблицы умножения), где допустим по строкам располагаются числа $m_1, m_2, ..., m_k$, а по столбцам числа $n_1, n_2, ..., n_k$. На пересечении строка/столбец стоит число $m_i/n_j$.

Тогда Вы на верном пути. Моя предыдущая подсказка отменяется.

[ewert]

gogoshik в сообщении #1274702 писал(а):

Запнулся на том моменте, что встречаются одинаковые числа: $1/1, 2/2, ...; 2/1, 4/2, ...$.

Нормальный выход из положения: начнём нумеровать, а как только попадётся уже встречавшееся число -- его пропускаем. Не пуритански, но зато всем ежам всё понятно. Все нормальные люди так и делают.

Ненормальный (мазохистский, именно на него намекал arseniiv). Множество несократимых дробей с фиксированным знаменателем $n$, очевидно, счётно (оно заведомо не более чем счётно, но и не менее чем, т.к. включает в себя дроби вида $$m+\frac1n$). А объединение счётного набора счётных множеств -- счётно.

Ну и ещё один мазохистский вариант: в формальное оправдание первого подхода повозиться с подпоследовательностями.

[Booker48]

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

Там, конечно, будут попадаться пары, соответствующие одинаковым рациональным числам, но с этим можно справиться.

Можно пересчитать вершины дерева Штерна-Броко.

[arseniiv]

И доказать ещё, что в нём попадутся все числа из $\mathbb{Q}^+$ по разу. Но вообще это, конечно, красивая идея, сам это дерево люблю. (А ещё подобным свойством обладает чуть менее известное дерево Калкина—Уилфа, примерно так же просто строящееся.)

[gogoshik]

$ \begin{matrix} \dfrac 1 1 & \dfrac 1 2& \dfrac 1 3 & \dfrac 1 4 & \ldots \\\\ \dfrac 2 1 & \dfrac 2 2& \dfrac 2 3 & \dfrac 2 4 & \ldots \\\\ \dfrac 3 1 & \dfrac 3 2& \dfrac 3 3 & \dfrac 3 4 & \ldots \\\\ \end{matrix} $

Спасибо Всем-Всем. А после составления такой таблицы, нужно ли еще показывать порядок нумерации на ней, то есть что будет являться решением задачи - запись самой таблицы или запись порядка (схема) нумерации на ней?

[Mikhail_K]

gogoshik, конечно же, таблица - это только первый шаг.
Теперь надо пронумеровать все элементы этой таблицы, то есть соотнести каждой дроби какое-то натуральное число - её номер.