Докажите что множество рациональных чисел счетно
Перейти к содержимому

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

  • автор:

Счетные множества

Определение. Множество, эквивалентное множеству всех натуральных чисел, называют счетным множеством.

Можно сказать иначе: множество счетно, если все его элементы можно занумеровать всеми натуральными числами.

Всякое бесконечное подмножество счетного множества счетно.

Действительно, пусть дано счетное множество

\[B = \{x_1, x_2. x_n. \},\]

а — его бесконечное подмножество. Располагая в порядке возрастания номеров все элементы подмножества

\[x_{n_1}, x_{n_2}. x_{n_k}. ~~(~n_1 < n_2 <. < n_k < . ),\]

можно перенумеровать их заново всеми натуральными числами, взятыми по порядку (в роли нового номера будет выступать индекс . Следовательно, счетно.

Объединение конечной или счетной совокупности счетных множеств есть счетное множество.

Объединением множеств называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств, и обозначается через .

Рассмотрим сначала случай конечного числа множеств. Пусть даны счетные множества

\[A_1=\{a_{11},~a_{12}. a_{1n}. \},\]

\[A_2=\{a_{21},~a_{22}. a_{2n}. \},\]

\[. \;\;\;\;\;(*)\]

\[A_n=\{a_{m1},~a_{m2}. a_{mn}. \}\]

Выпишем элементы множеств в виде следующей таблицы:

\[a_{11}, ~a_{12},~. ~a_{1n},~. \]

\[a_{21}, ~a_{22},~. ~a_{2n},~. \]

\[a_{m1}, ~a_{m2},~. ~a_{mn},~. \]

Теперь перенумеруем заново все элементы этой таблицы, располагая их по столбцам:

\[a_{11},a_{21}. a_{m1}, a_{12},a_{22},~. a_{m2}. a_{1n},a_{2n}. a_{mn}. \]

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

где все множества счетны. Выпишем элементы множеств в виде таблицы, аналогичной таблице , но содержащей счетное множество строк. Элементы такой таблицы можно перенумеровать располагая их по группам элементов с равной суммой индексов:

\[a_{11};~a_{21},~a_{12};~a_{31},~a_{22},~a_{13};~a_{41},~a_{32},~a_{23},~ a_{14};~. \]

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

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

Действительно, множество всех рациональных чисел есть объединение следующих счетных множеств:

\[A_1=\left\{\frac{n}{1} |~n=0, \pm1,\pm2. \right\},\]

\[A_2=\left\{\frac{n}{2 } |~n=0, \pm1,\pm2. \right\},\]

\[A_k=\left\{\frac{n}{k} |~n=0, \pm1,\pm2. \right\},\]

т.е. . Множества , составляют счетную совокупность счетных множеств. Из 11.3 следует, что их объединение счетно.

Теория функций действительного переменного/Счётные множества

Определение 1. Если множество A эквивалентно множеству N > (множеству натуральных чисел) (если A ∼ N > ), то множество A называется счётным множеством. Иначе говоря, для счётного множества A существует биекция f : N → A \to A> . Существование биекции означает, что элементы множества А можно записать в виде последовательности
a1, a2, …, an, …,
в которой нет равных членов, и каждый элемент множества A равен одному из членов последовательности.

Пример. Множество Z > (множество целых чисел) счётно, так как его элементы можно записать в виде следующей последовательности:
0, -1,+1, -2,+2, …, -n,+n, …
Счётны также множества < 1 1 , 1 2 , 1 3 , . . . , 1 n , . . . >>,<\frac >,<\frac >. <\frac >. \right\>> , < 2 1 , 2 2 , 2 3 , … , 2 n , … >, < 1 3 , 2 3 , … , n 3 , … >.

Теорема 1 . Множество N × N \times \mathbb > (декартово произведение множества натуральных чисел и множества натуральных чисел, множество пар натуральных чисел) счётно, то есть N × N ∼ N \times \mathbb \sim \mathbb > .

Доказательство

Доказательство проиллюстрируем следующим рисунком. На рисунке в отличие от русской математической символики символ «/» обозначает не дробь, а стоит вместо запятой, обозначая упорядоченную пару — элемент множества N × N \times \mathbb > .

В результате расстановки, указанной стрелками, все элементы множества N × N \times \mathbb > приобретут номер. Так как элементы множества N × N \times \mathbb > можно занумеровать, множество N × N \times \mathbb > счётно.

Теорема 2 . Декартово произведение конечного числа счётных множеств есть множество счётное.

1. Пусть множества A1 и A2 счётные, то есть A 1 ∼ N \sim \mathbb > и A 2 ∼ N \sim \mathbb > . Тогда по теореме 2 из главы «Эквивалентные множества» A 1 × A 2 ∼ N × N \times A_\sim \mathbb \times \mathbb > . Так как по теореме 1 N × N ∼ N <\displaystyle \mathbb \times \mathbb \sim \mathbb > , то A 1 × A 2 ∼ N \times A_\sim \mathbb > . Теорема верна для двух сомножителей.

2. Предположим, что теорема верна для n сомножителей. Докажем справедливость теоремы для (n+1) сомножителя. Пусть множества A1, A2, …, An+1 счётны. Сопоставляя элементу ( ( a 1 , a 2 , . . . , a n ) , a n + 1 ) ,a_. a_),a_)> множества ( A 1 × A 2 × . . . × A n ) × A n + 1 \times A_\times . \times A_\right)\times A_> элемент ( a 1 , a 2 , . . . , a n , a n + 1 ) ,a_. a_,a_)> множества A 1 × A 2 × . . . × A n × A n + 1 \times A_\times . \times A_\times A_> , получим биекцию множества ( A 1 × A 2 × . . . × A n ) × A n + 1 \times A_\times . \times A_)\times A_> на множество A 1 × A 2 × . . . × A n × A n + 1 \times A_\times . \times A_\times A_> . Следовательно, ( A 1 × A 2 × . . . × A n ) × A n + 1 \times A_\times . \times A_)\times A_> ∼ A 1 × A 2 × . . . × A n × A n + 1 \times A_\times . \times A_\times A_> . Но по предположению индукции A 1 × A 2 × . . . × A n ∼ N \times A_\times . \times A_\sim \mathbb > . Поэтому, применяя уже доказанный частный случай теоремы для декартова произведения двух сомножителей ( A 1 × A 2 ∼ N \times A_\sim \mathbb > ), получим ( A 1 × A 2 × . . . × A n ) × A n + 1 ∼ N \times A_\times . \times A_)\times A_\sim \mathbb > . Следовательно, и A 1 × A 2 × . . . × A n × A n + 1 ∼ N \times A_\times . \times A_\times A_\sim \mathbb > .

Пример. Множество Z 2 ^> (множество точек плоскости с целыми координатами) счётно. Множество Z 2 ^> есть Z 2 = Z × Z ^=\mathbb \times \mathbb > .

Теорема 3 . Всякое бесконечное множество содержит счётное подмножество.

Доказательство

Пусть B — бесконечное множество. Тогда множество B содержит хотя бы один элемент a1. В силу бесконечности B в нём найдется элемент a2, отличный от a1. Так как злементы a2 и a1 не исчерпывают всего множества B, то в B найдется элемент a3, отличный и от a2 и от a1. Если уже выделено n элементов (a1, a2, …, an), то в силу бесконечности B в B найдётся ещё один элемент, который обозначим an+1 и который отличен от всех ранее выбранных элементов. Таким образом, для каждого натурального числа n можно выделить элемент an из B. Причём все выделенные элементы попарно различны. Выделенные элементы образуют последовательность
a1, a2, …, an, …
Множество членов последовательности по определению счётно. Множество членов последовательности есть часть множества B.

Теорема 4 . Всякое бесконечное подмножество счётного множества счётно.

Доказательство

Пусть A — счётное множество, B — бесконечное подмножество множества A. По теореме 3 множество B содержит счётное подмножество C. Так как множества A и C счётны, A ∼ C . Кроме того, C ⊂ B ⊂ A . По теореме 4 главы 1 B ∼ A , то есть множество B эквивалентно счётному множеству и потому само счётно.

Теорему 4 можно перефразировать следующим образом. 4′ . Всякое подмножество счётного множества конечно или счётно.

Теорема 5 . При любом отображении образ счётного множества конечен или счётен.

Доказательство

Пусть A — счётное множество, B — произвольно множество и f — некоторое отображение:
f: A→B.

Требуется доказать, что множество C = f ( A ) конечно или счётно.

Выберем для любого элемента c ∈ C в его полном прообразе f -1 произвольным образом точку ac. В результате образуется множество A 1 = < a c >c ∈ C =\\>_> . Множество A 1 > является частью счётного множества A, и потому, согласно теореме 4′ , конечное или счётное. Так как для различных элементов c и c’ множества C их полные прообразы f -1 (c) и f -1 (c’) не пересекаются, то a c ≠ a c ′ \neq a_> , и, следовательно, соответствие c ↦ a c > является биекцией множества C на множество A1. Поэтому вместе с множеством A1 и множество C конечно или счётно.

Теорема 6 . Множество Q > (множество рациональных чисел) счётно.

Доказательство

Так как множество Z > счётно, то по теореме 2 и декартово произведение Z × N \times \mathbb > счётно. Поставим в соответствие произвольному элементу (p,q) множества Z × N \times \mathbb > рациональное число p q >> . Получившееся отображение f : Z × N → Q \times \mathbb \to \mathbb > сюръективно. Действительно, всякое рациональное число r можно представить в виде отношения двух целых чисел: r = p q >> , причём знаменатель можно считать положительным; тогда пара (p,q) является, очевидно, прообразом точки r относительно отображения f. Таким образом, множество Q <\displaystyle \mathbb > счётно как образ счётного множеста при некотором отображении, учитывая при этом, что конечным оно заведомо не является.

Пример. Пусть A — множество рациональных точек интервала (a,b). Требуется доказать, что множество A счётно. Множество A бесконечно и является частью счётного множества Q > , поэтому по теоремам 6 и 4 является счётным.

Теорема 7 . Всякое семейство < Δ x >x ∈ X \>_> попарно не пресекающихся непустых интервалов конечно или счётно.

Доказательство

Всякий интервал содержит бесконечно много рациональных точек. Выберем из каждого интервала Δ x > одну рациональную точку rx. Получившееся множество A = < r x >x ∈ X \>_> как часть счётного множества Q > конечно или счётно. Исходное множество интервалов (множество < Δ x >x ∈ X \>_> ), так как эквивалентно множеству A, тоже конечно или счётно.

Теорема 8 . Объединение конечной или счётной совокупности конечных или счётных множеств конечно или счётно.

Доказательство

Если A = ⋃ n = 1 k A n ^A_> , где все слагаемые являются множествами конечными или счётными, то, полагая для любого натурального числа m>k Am = Ak, получим A = ⋃ n ∈ N A n >A_> , то есть случай конечного объединения сводится к случаю счётного объединения, каковой мы и будем дальше предполагать выполненным.

Занумеруем элементы множества An в последовательность

an1, an2, …, anm, …, (*)

Причём, если An конечно и содержит kn элементов, то будем считать, что первые kn членов этой последовательности попарно различны и исчерпывают всё множество An, а для m>kn, полагаем anm = ankn.

Зададим теперь отображение f : N × N → A \times \mathbb \to A> формулой f(n,m) = anm. Тогда отображение f сюръективно. Действительно, если a — любой элемент множества А, то a принадлежит некоторому слагаемому An и потому совпадает с каким-ни6удь членом проследовательиости (*) : a = anm. В таком случае пара натуральных чисел (n,m) будет проо6разом элемента a относительно отображения f . Итак, А есть образ счётного множества N × N <\displaystyle \mathbb \times \mathbb > при отображении f. Поэтому А конечно или счётно.

Примеры представления в форме последовательности некоторых объединений:

Определение 2. Действительное число x называется алгебраическим, если является корнем многочлена с целыми коэффициентами.

Пример. Всякое рациональное число r = p q >> является алгебраическим, так как является корнем многочлена q ⋅ x − p .

Теорема 9 . Множество алгебраических чисел счётно.

Доказательство

Сопоставляя многочлену a 0 + a 1 ⋅ x + . . . + a n ⋅ x n +a_\cdot x+. +a_\cdot x^> с целыми коэффициентами элемент (a0, a1, …, an) декартова произведения Z n + 1 ^> , получим биекцию между множеством всех многочленов An степени не выше n и декартовым произведением Z n + 1 ^> . Отсюда в силу счётности множества Z n + 1 ^> следует счётность множества An. Так как множество всех многочленов с целыми коэффициентами представляется в виде A = ∪ n ∈ N A n >A_> , то по теореме 8 множество A счётно. Учитывая, что многочлен степени n имеет не более n корней, получаем, что множество алгебраических чисел представляется в виде счётного объединения конечных множеств и, следовательно, по теореме 8 конечно или счётно. Причём конечность невозможна, так как уже множество рациональных чисел, являющееся подмножеством множества алгебраических чисел, бесконечно.

Теорема 10 . Если множество B бесконечно, а множество А конечно или счётно, то A ∪ B ∼ B .

Доказательство

Согласно теореме 3 множество B содержит счётное подмножество С. Множество A ∖ B как часть конечного или счётного множества A само конечно или счётно. Поэтому по теореме 8 множество C ∪ ( A ∖ B ) счётно. Нетрудно проверить (и это предлагается проделать самостоятельно) справедливость следующих равенств:

Замечание. Из теоремы 10 следует, что всякое бесконечное множество содержит эквивалентное ему собственное подмножество. Конечное множество таким свойством не обладает. Поэтому свойство множества иметь эквивалентную ему правильную часть можно принять за определение бесконечного множества.

Упражнения [ править ]

  1. Докажите, что множество точек плоскости с рациональными координатами счётно.
  2. Докажите, что множество интервалов с рациональными концами счётно.
  3. Пусть A — множество таких вещественных чисел, расстояние между любыми двумя из которых больше 1. Докажите, что множество A конечно или счётно.
  4. Докажите, что множество точек разрыва монотонной функции, определённой на всей числовой прямой, конечно или счётно.
  5. Докажите, что всякое множество попарно не пересекающихся кругов на плоскости конечно или счётно.
  6. Пусть A — множество таких точек плоскости, расстояние между любыми двумя из которых больше фиксированного положительного числа a. Докажите, что множество A конечно или счётно.
  7. Покажите, что множество конечных подмножеств множества N > (натурального ряда) счётно.
  8. Докажите, что множество таких треугольников на плоскости, координаты вершин которых рациональны, счётно.
  9. Докажите, что множество таких многоугольников на плоскости, координаты вершин которых рациональны, счётно.
  10. Будет ли счётным множество таких многочленов, коэффициентами которых служат алгебраические числа?
  11. Установите биекцию между [0,1] и (0,1).
  12. Установите биекцию между (0,2) и ( 0.1 ) ∪ ( 1 , 2 ) .
  13. Установите биекцию между внутренностью единичного круга на плоскости и его внешностью.
  14. Установите биекцию между внешностью единичного круга и плоскостью.

Научный форум dxdy

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

На страницу 1 , 2 След.

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

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

$ \begin</p>
<p> (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 $» /></p>
<p>Итак, в этом массиве первый элемент первой строки равен 1, а вторые элементы перечислены в порядке величины суммы их числителя и знаменателя. Аналогично, по мере продвижения вниз в первом столбце первые элементы перечисляются в соответствии с величиной суммы их числителя и знаменателя. Итак, перемещаясь по любой строке, мы бы нашли вторые элементы пар, перечисленных в порядке их числителя и знаменателя, и, опускаясь в любом столбце, мы бы нашли то же самое с первыми элементами. из пар. Таким образом, все пары могут быть перечислены таким образом.</p>
<p>Теперь мы бы начали считать следующим образом:</p>
<p>Разделите первую пару первой диагональной линией (от верхнего правого угла к нижнему левому), назовите ее 1. Во второй диагональной линии будут подсчитаны элементы <img decoding=и '/2,1)$, и, таким образом, мы будем подсчитывать каждый элемент.

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

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

Заслуженный участник

Последний раз редактировалось Andrey A 21.08.2023, 10:06, всего редактировалось 2 раз(а).

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

$N_i$

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

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

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

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

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

Заслуженный участник

Последний раз редактировалось Andrey A 21.08.2023, 10:20, всего редактировалось 1 раз.

Knight2023
Да ладно, не парьтесь ) Посмотрите еще Ряд Фарея.
Re: Докажите, что множество пар рациональных чисел счетно.
21.08.2023, 10:33

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

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

Заслуженный участник

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

$\gcd ().$

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

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

Заслуженный участник

Knight2023 в сообщении #1606006 писал(а):
Вот как я это пытался

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

Re: Докажите, что множество пар рациональных чисел счетно.
21.08.2023, 12:01
Andrey A в сообщении #1606026 писал(а):
Интересно как

' \to 1$

Биекция между положительными рациональными и натуральными числами:

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

$r=p_1^<a_1>p_2^\ldots p_k^$» />, где <img decoding=— простые, $a$— целые ненулевые числа. Если $a_i$— отрицательное, то соответствующее простое — в знаменателе дроби.

Простые оставляем так, как есть, а для показателей — если $a_i$— положительное, меняем на https://dxdy-03.korotkov.co.uk/f/e/b/0/eb0392c1f164da0d661003d143bb5d5782.pnga_i-1$, а если отрицательное — на $(-2a_i)$

$\dfrac 2 9=2^1 \cdot 3^<-2></p>
<p>Напр. \to 2^1 \cdot 3^4$» /></p>
<p>Тоесть, числу <img decoding=

Обратная задача — по номеру отпеделить число: Факторизация, если степень простого — четная, то делим да 2 и пишем в знаменателе, если нечетная — добавляем '$, делим на https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png$

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

Научный форум dxdy

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

На страницу 1 , 2 След.

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

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

$ \begin</p>
<p> (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 $» /></p>
<p>Итак, в этом массиве первый элемент первой строки равен 1, а вторые элементы перечислены в порядке величины суммы их числителя и знаменателя. Аналогично, по мере продвижения вниз в первом столбце первые элементы перечисляются в соответствии с величиной суммы их числителя и знаменателя. Итак, перемещаясь по любой строке, мы бы нашли вторые элементы пар, перечисленных в порядке их числителя и знаменателя, и, опускаясь в любом столбце, мы бы нашли то же самое с первыми элементами. из пар. Таким образом, все пары могут быть перечислены таким образом.</p>
<p>Теперь мы бы начали считать следующим образом:</p>
<p>Разделите первую пару первой диагональной линией (от верхнего правого угла к нижнему левому), назовите ее 1. Во второй диагональной линии будут подсчитаны элементы <img decoding=и '/2,1)$, и, таким образом, мы будем подсчитывать каждый элемент.

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

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

Заслуженный участник

Последний раз редактировалось Andrey A 21.08.2023, 10:06, всего редактировалось 2 раз(а).

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

$N_i$

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

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

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

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

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

Заслуженный участник

Последний раз редактировалось Andrey A 21.08.2023, 10:20, всего редактировалось 1 раз.

Knight2023
Да ладно, не парьтесь ) Посмотрите еще Ряд Фарея.
Re: Докажите, что множество пар рациональных чисел счетно.
21.08.2023, 10:33

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

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

Заслуженный участник

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

$\gcd ().$

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

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

Заслуженный участник

Knight2023 в сообщении #1606006 писал(а):
Вот как я это пытался

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

Re: Докажите, что множество пар рациональных чисел счетно.
21.08.2023, 12:01
Andrey A в сообщении #1606026 писал(а):
Интересно как

' \to 1$

Биекция между положительными рациональными и натуральными числами:

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

$r=p_1^<a_1>p_2^\ldots p_k^$» />, где <img decoding=— простые, $a$— целые ненулевые числа. Если $a_i$— отрицательное, то соответствующее простое — в знаменателе дроби.

Простые оставляем так, как есть, а для показателей — если $a_i$— положительное, меняем на https://dxdy-03.korotkov.co.uk/f/e/b/0/eb0392c1f164da0d661003d143bb5d5782.pnga_i-1$, а если отрицательное — на $(-2a_i)$

$\dfrac 2 9=2^1 \cdot 3^<-2></p>
<p>Напр. \to 2^1 \cdot 3^4$» /></p>
<p>Тоесть, числу <img decoding=

Обратная задача — по номеру отпеделить число: Факторизация, если степень простого — четная, то делим да 2 и пишем в знаменателе, если нечетная — добавляем '$, делим на https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png$

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *