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

[ewert]

dima90 в сообщении #1100277 писал(а):

Только там еще не будет счетного числа сократимых дробей.

я ничего не понял; но уж что точно -- так это что множество сократимых дробей уж точно счётно.

А зачем счётно -- я не в курсе.

[dima90]

Из той системы нужно выкинуть сократимые дроби, и да, их счетное кол-во -- я так и сказал.

[Anton_Peplov]

dima90
Зачем выкидывать-то? Вы, простите за вульгарность, помните, что такое объединение множеств? Чему равно, скажем, объединение множеств $\{1, 2\}$, $\{2, 3\}$ и $\{3, 4\}$?

[svv]

Мартин Гарднер, Математические новеллы.

Цитата:

Другой, несколько неожиданный метод упорядочения и счета положительных рациональных чисел был предложен американским логиком Чарлзом С. Пирсом. Возьмем две дроби — $0/1$ и $1/0$ (вторая дробь не имеет смысла, но для наших целей это обстоятельство несущественно). Образуем новую дробь, числитель которой равен сумме числителей, а знаменатель — сумме знаменателей двух исходных дробей, и поместим ее между ними: $0/1, 1/1, 1/0$. Проделав только что выполненные операции над каждой парой дробей, стоящих рядом, получим

$$\frac 01\;\frac 12\;\frac 11\;\frac 21\;\frac 10$$

В свою очередь эти пять дробей превращаются в девять дробей

$$\frac 01\;\frac 13\;\frac 12\;\frac 23\;\frac 11\;\frac 32\;\frac 21\;\frac 31\;\frac 10$$

и т.д.
В получающейся бесконечной последовательности каждое рациональное число будет встречаться один и только один раз, причем в несократимом виде. Метод Пирса делает излишним вычеркивание таких дробей, как, например, $10/20$, эквивалентных более простым дробям, также представляющим рациональные числа. При использовании метода Пирса сократимые дроби не появляются. При использовании же других методов упорядочения рациональных чисел исключение дробей, числитель и знаменатель которых содержат общие множители, просто необходимо, иначе одно и то же рациональное число будет сосчитано несколько раз. В методе Пирса происходит постепенное, шаг за шагом, «замазывание щелей» в ряду рациональных чисел, а дроби можно нумеровать в порядке их появления.

Конечно, выделенное (мной) утверждение требует доказательства.

[dima90]

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

$A_1 = \mathbb{Z}$, $A_2 = \mathbb{Z}/2$, $A_3 = \mathbb{Z}/3$..., где под $\mathbb{Z}/n$ понимается множество всех дробей с целым числителем и знаменателем $n$.

Вы не забывайте, что вы написали: среди всех дробей встречаются сократимые.

(Оффтоп)

За вульгарность, конечно, не прощаю.

[Anton_Peplov]

svv в сообщении #1100293 писал(а):

Мартин Гарднер, Математические новеллы.

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

-- 18.02.2016, 00:15 --

dima90 в сообщении #1100295 писал(а):

Вы не забывайте, что вы написали: среди всех дробей встречаются сократимые.

Я прекрасно помню, что я написал, спасибо.
Да, среди всех дробей встречаются сократимые. И что? Ну встретится нам число $1$ как $\frac{1}{1}$, $\frac{2}{2}$, $\frac{3}{3}$... В каждом из множеств $A_i$ оно встретится ровно один раз. И что, мощность $\cup A_i$ от этого как-то изменится?

[arseniiv]

Нумеруя пары $(m,n)$, мы доказываем, что $\mathbb Q$ не более чем счётно. Теперь осталось показать, что оно бесконечно, и дело в шляпе.

[Anton_Peplov]

А бесконечность его доказывается тем, что у него есть бесконечное подмножество $\{\frac{1}{n}\}$.
Но если говорить о моем посте, я вообще не предлагаю ничего нумеровать. Я просто говорю, что $\mathbb{Q}$ - объединение счетной системы счетных множеств и потому счетно. Пусть бы эти множества хоть совпадали между собой.

[dima90]

Anton_Peplov
А к чему вопрос? Ответ: нет.
Кто-то утверждал обратное?

[Anton_Peplov]

dima90 в сообщении #1100304 писал(а):

Кто-то утверждал обратное?

Вы. Вы утверждали, что для доказательства счетности $\cup A_i$ нужно сначала выкинуть сократимые дроби.

[arseniiv]

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

Я просто говорю, что $\mathbb{Q}$ - объединение счетной системы счетных множеств и потому счетно. Пусть бы эти множества хоть совпадали между собой.

Не спорю.

[Dan B-Yallay]

(Оффтоп)

dima90 в сообщении #1100304 писал(а):

А к чему вопрос? Ответ: нет.
Кто-то утверждал обратное?

У Вас время в обратную сторону идёт?

[dima90]

Да не для док-ва их выкинуть нужно, а для отсутствия повторения элементов.

[sergei1961]

Про метод как бы Пирса, который здесь упоминали. Гарднер был не в курсе. Всё это давно известно и изучено вдоль и поперёк. Метод сложения дробей "как у двоешников", числитель с числителем и знаменатель со знаменателем даёт величину, которая называется медиантой двух дробей. Сама числовая последовательность и метод её построения: ряд Фарея, дроби Фарея, метод Фарея. Где только не применяется, начиная с теории чисел...Например, дроби Фарея связаны с цепными дробями. Все нужные теоремы там давно доказаны, в том числе и та, что заметаются все рациональные числа.

[whitefox]

Rusit8800 в сообщении #1099999 писал(а):

По определению множество $F$ счетно, если $F\sim\mathbb{N}$, то есть $f : F \Rightarrow \mathbb{N}$

Разумеется, если $F\sim\mathbb{N}$, то существует $f : F \rightarrow \mathbb{N},$ только такое $f$ не будет нумерацией. А сюръекция $g:\mathbb{N}\rightarrow F$ будет. Также нумерацией множества $F$ будет произвольное отображение из $\mathbb{N}$ на $F,$ то есть отображение некоторого подмножества $\mathbb{N}$ на $F.$

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

Важен ведь только факт наличия алгоритма нумерации.

Достаточно только факта наличия нумерации, не обязательно вычислимой.