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

[Shadow]

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

Как это продолжить на пару пропорций не очень понятно

Ну, вообще-то не для пары пропорций, а для пары натуральных чисел (номера данных рациональных). А тут все просто - бит из первого, бит из второго и т.н (если порядок одного меньше другого, то допоняется нулями).
Кстати, пол. рациональное число тоже упорядоченая пара натуральных чисел, но для них такой способ не подходит, потому что $1/2, 2/4, 3/6 \cdot $ - одно и то же рациональное число. И биекция не получится. А без дополнительных требований, просто упорядоченая пара (тойка, четверка) - нет проблем. Насчет моя ли идея - да, не нравились мне какие-то диагонали, хотел придумать четкий алгоритм, буквално функции QToN и NtoQ, но вряд ли это что-то новое. А ваша идея с суммой квадратов мне еще надо обдумать.

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

$(12,9876) \to 09081726=9081726$

0012
9876

[EminentVictorians]

Anton_Peplov в сообщении #1606070 писал(а):

Ну, или можно воспроизвести доказательство этой теоремы в частном случае.

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

[Andrey A]

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

бит из первого, бит из второго и т.н (если порядок одного меньше другого, то допоняется нулями).

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

[Shadow]

Andrey A, да. Я все про биекцию, да про биекцию. А топикстартеру биекция то не нужна. Ему просто нужно пронумеровать. А то, что в нумерации будут "дырки" - на счетность не влияет.

(Оффтоп)

Бит из $a$, бит из $b$, бит из $c$, бит из $d$...

[gefest_md]

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

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

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

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

Решил задачу для общего случая $A\times B$, взятую из учебника, используя следующую, ранее предложенную в учебнике, функцию: $p\colon \omega\times\omega\to\omega,\quad p(i,j)=2^i(2j+1)-1.$
Но ведь эта же функция подходит для частного случая $\mathbb{Q}\times\mathbb{Q}.$

[StepV]

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

Любое другое положительное рациональное число можно представить в виде

Случайно подняли тему, и я заинтересовался предложенным вами алгоритмом. Если в вашем рассуждении поменять приведение чисел с классов вычетов по модулю $2$ к классам по модулю $3$, то алгоритм легко распространяется на все рациональные числа:
- для степеней знаменателя берем класс вычетов $0$, т.е. $a_i \rightarrow (-3a_i)$
- для степеней числителя при положительном рациональном числе берем класс вычетов $1$, т.е. $a_i \rightarrow (3a_i+1)$
- для степеней числителя при отрицательном рациональном числе берем класс вычетов $2$, т.е. $a_i \rightarrow (3a_i+2)$
Восстановление и алгоритм описаны вами, но только формулы изменить для расчета для классов вычетов по модулю 3. Тогда для представления положительного числа степени делятся либо на $3$, либо дают в остатке $1$, или $0$ и $2$ для отрицательного рационального числа.

[Shadow]

StepV, да получится биекция. (только $3a-1$ и $-2$, ведь $|a_j| \ge 1$). И еще нуля надо пронумерировать.

Получится что-то типа $n \to n^3$. Но все же $n \to 2n^2$ кажется экономичнее.

[Shadow]

StepV, я тут подумал - нет, не получится биекция. Пусть у нас есть положительное целое число. Тогда все степени простых будут $1 \mod 3$.

И какое рационалное число имеет номер $2^1 \cdot 3^2$ - непонятно.

[StepV]

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

нет, не получится биекция.

Согласен. Получается инъекция, т.к. на целые, которые представимы простыми числами со степенями, у которых остатки $1$ и $2$, отображаемого рационального числа нет. Все равно классная идея. Получается инъекция рациональных чисел на натуральные числа. Вот что делают бесконечности! Внутренне понимаешь, что поле рациональных чисел должно быть больше количества натуральных чисел, а тут оказывается, что оно все отображается только на часть натуральных.

[Shadow]

StepV в сообщении #1642317 писал(а):

Получается инъекция рациональных чисел на натуральные числа. Вот что делают бесконечности!

Да, самый просто способ получить такую инъекцию - чередовать знак числителя со знаком знаменателя. (дополнив нулями, если число знаков не совпадают).