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

[Knight2023]

Вот как я это пытался:

$$ \begin{matrix} (1,1) & (1, 1/2)& (1, 2/1) & (1, 1/3) & (1, 3/1) & (1,1/4) & (1,4/1) & (1,2/3)&(1,3/2) & \cdots \\ (1/2, 1) & (1/2, 1/2) & (1/2, 2/1) & (1/2, 1/3) & (1/2, 3/1) & (1/2, 1/4) & (1/2, 4/1)&(1/2, 2/3) &(1/2,3/2) & \cdots \\ (2/1, 1) & (2/1, 1/2) & (2/1, 2/1) & (2/1, 1/3) & (2/1, 3/1) &( 2/1, 1/4) & (2/1, 4/1) & (2/1, 2/3) &(2/1, 3/2) \cdots \vdots \end{matrix} $$

Итак, в этом массиве первый элемент первой строки равен 1, а вторые элементы перечислены в порядке величины суммы их числителя и знаменателя. Аналогично, по мере продвижения вниз в первом столбце первые элементы перечисляются в соответствии с величиной суммы их числителя и знаменателя. Итак, перемещаясь по любой строке, мы бы нашли вторые элементы пар, перечисленных в порядке их числителя и знаменателя, и, опускаясь в любом столбце, мы бы нашли то же самое с первыми элементами. из пар. Таким образом, все пары могут быть перечислены таким образом.

Теперь мы бы начали считать следующим образом:

Разделите первую пару первой диагональной линией (от верхнего правого угла к нижнему левому), назовите ее 1. Во второй диагональной линии будут подсчитаны элементы $(1,1/2)$ и $1/2,1)$, и, таким образом, мы будем подсчитывать каждый элемент.

Верно ли мое доказательство?

[Andrey A]

Хочется поубедительней. Например так: каждой паре рациональных строго соответствует тройка целых $\dfrac{a}{c},\dfrac{b}{c}, \gcd (a,b,c)=1.$
Каждое натуральное $N \neq (8k+7) \cdot 2^{2n} (k,n\geqslant 0)$ представимо формой $a^2+b^2+c^2$ (квадрат расстояния целой точки трехмерного пространства до начала координат).

Разлагая в сумму трех квадратов натуральные $N_i$ по возрастанию, получаем все пары рациональных с возможностью "обратного учета".

[Knight2023]

Я ценю ваше предложение, но, извините, я не могу понять его. Не могли бы вы взять меня через путешествие вашего поезда мысли?

- С чего ты начал? Является ли он требованием, что все $ (a/c, b/c) $ формируются посредством интегрального решения в размере

$$a^2+b^2 +c^2=0$$

[Andrey A]

Knight2023
Да ладно, не парьтесь ) Посмотрите еще Ряд Фарея.

[Shadow]

А почему не воспользоватся тем, что любое рационально число можно уникальным (и обратимым) способом пронумеровать. И работать уже с парой натуральных (или целых неотрицательных) числах.

[Andrey A]

Shadow в сообщении #1606022 писал(а):

... любое рационально число можно уникальным (и обратимым) способом пронумеровать.

Интересно как? Для последовательности Фарея нужно указать порядок. В итоге имеем опять же тройку целых, добытую сложнее чем через $\gcd ().$

[TOTAL]

Knight2023 в сообщении #1606006 писал(а):

Вот как я это пытался

Что именно пытались сделать?
Доказать, что можно пронумеровать?
Или предложить конкретный способ нумерации?

[Shadow]

Andrey A в сообщении #1606026 писал(а):

Интересно как

Биекция между положительными рациональными и натуральными числами:
$1 \to 1$
Любое другое положительное рациональное число можно представить в виде

$r=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$, где $p$ - простые, $a$ - целые ненулевые числа. Если $a_i$ - отрицательное, то соответствующее простое - в знаменателе дроби.

Простые оставляем так, как есть, а для показателей - если $a_i$ - положительное, меняем на $2a_i-1$, а если отрицательное - на $(-2a_i)$

Напр. $\dfrac 2 9=2^1 \cdot 3^{-2} \to 2^1 \cdot 3^4$

Тоесть, числу $\dfrac{2}{9}$ соответствует номер $162$

Обратная задача - по номеру отпеделить число: Факторизация, если степень простого - четная, то делим да 2 и пишем в знаменателе, если нечетная - добавляем $1$, делим на $2$

Нужно добавить еще один бит для знака (положительное/отрицательное)....вобщем несложно.

[Andrey A]

Shadow
Любопытный расклад, Ваша идея? Мне понравилась. Но. Таким способом можем пронумеровать именно пропорции. Как это продолжить на пару пропорций не очень понятно. И потом через суммы трех квадратов оно проще, естественней выходит. Ведь задачи получить номер в списке для заданной тройки $\gcd (a,b,c)=1$ как таковой не стоит.

[EminentVictorians]

А не проще воспользоваться теоремой о том, что декартово произведение $A \times B$ счетных множеств $A$ и $B$ счетно?

[Anton_Peplov]

EminentVictorians в сообщении #1606067 писал(а):

А не проще воспользоваться теоремой о том, что декартово произведение $A \times B$ счетных множеств $A$ и $B$ счетно?

+1.
Ну, или можно воспроизвести доказательство этой теоремы в частном случае. Берем любую нумерацию рациональных чисел $n = n(q)$ и тем самым сводим задачу к нумерации пар натуральных чисел $(n_1, n_2)$.

[Rak so dna]

Andrey A в сообщении #1606064 писал(а):

Но. Таким способом можем пронумеровать именно пропорции. Как это продолжить на пару пропорций не очень понятно.

Можно так:
Определим набор кнопок $\slash~,~0~1~2~3~4~5~6~7~8~9$
Теперь для числа $N=2^{a_0}3^{a_1}..{p_{k+1}}^{a_k}$ трактуем последовательность $a_i$ как индексы элементов нашего набора. Т.о. можно шифровать последовательность нажатий кнопок одним числом. Например пара $\frac{1}{2},\frac{1}{3}$ будет соответствовать числу $2^3\cdot3^0\cdot5^4\cdot7^1\cdot11^3\cdot13^0\cdot17^5=66144038345000$

[Knight2023]

TOTAL в сообщении #1606027 писал(а):

Knight2023 в сообщении #1606006 писал(а):

Вот как я это пытался

Что именно пытались сделать?
Доказать, что можно пронумеровать?
Или предложить конкретный способ нумерации?

Что множество всех пар рациональных чисел счетно. Итак, цель состоит в том, чтобы их можно было пронумеровать.

-- 21.08.2023, 20:46 --

EminentVictorians в сообщении #1606067 писал(а):

А не проще воспользоваться теоремой о том, что декартово произведение $A \times B$ счетных множеств $A$ и $B$ счетно?

К сожалению, это следующая проблема в упражнении. Это требуется сделать без него, потому что это общий случай этого.

[svv]

Knight2023 в сообщении #1606079 писал(а):

Что множество всех пар рациональных чисел счетно. Итак, цель состоит в том, чтобы их можно было пронумеровать.

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

[TOTAL]

Knight2023 в сообщении #1606079 писал(а):

Что множество всех пар рациональных чисел счетно. Итак, цель состоит в том, чтобы их можно было пронумеровать.

Пара рациональных чисел задается четырьмя целыми числами. Сначала нумеруете все четверки, сумма которых равна 1. Затем с суммой 2. И т.д. Любая пара рациональных чисел встретится и получит какой-то номер.