Помогите разобраться (несчетность по Кантору)

- Archer - · 22/09/13 2

Начнем с общеизвестного факта:

Теорема Кантора

Чтобы показать несчётность всего множества вещественных чисел, достаточно показать несчётность интервала $(0.1)$ .

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

$\eqno [1.1]$

$x_1 = 0. a_{1,1} a_{1,2} \ldots a_{1,m} \ldots$
$x_2 = 0. a_{2,1} a_{2,2} \ldots a_{2,m} \ldots$
$\ldots$
$x_k = 0. a_{k,1} a_{k,2} \ldots a_{k,m} \ldots$
$\ldots$

Здесь $a_{t,s}$ – $s$ -я цифра $t$ -го числа. Очевидно, что все числа указанного вида действительно принадлежат рассматриваемому промежутку, если только в каждом числе не все цифры сразу являются нулями или девятками.

Рассмотрим теперь следующее число:

$\eqno [1.2]$

$x=0. d_1 d_2 \ldots d_m \ldots$

Пусть каждая цифра $d_s$ этого числа удовлетворяет следующим трём свойствам:

$\eqno [1.3]$

$d_s \neq 0$
$d_s \neq 9$
$d_s \neq a_{s,s}$

Такое число действительно существует на указанном промежутке, так как оно является вещественным, не совпадает ни с нулем, ни с единицей, а десятичных цифр достаточно, чтобы третье свойство выполнялось. Кроме этого, равенство $[1.2]$ интересно тем фактом, что число $x$ не совпадает ни с одним из чисел $x_t$ в $[1.1]$ , ведь иначе $t$ -я цифра числа $x$ совпала бы с $t$ -й цифрой числа $x_t$ . Пришли к противоречию, заключенному в том, что как бы числа рассматриваемого промежутка ни были занумерованы, всё равно найдется число из этого же промежутка, которому не присвоен номер. Таким образом, множество вещественных чисел на $(0.1)$ несчетно.

Мне не очень очевидна логическая безупречность данной теоремы и вот почему.

Рассмотрим следующую конструкцию ( $1 \leqslant i \leqslant b^j-1, \quad j \geqslant 1, \quad b \geqslant 2$ – основание заданной системы счисления):

$\eqno [2.1]$

$f_i = \begin{cases} x_{i,j} = x_{i,j-1}+\frac {a_{i,j}}{b^j}\\ f_{i-1} \end{cases}$

с начальными условиями

$x_{i,0} = 0$
$f_1 = x_{1,j}$

которая в развернутом виде выглядит так

$\eqno [2.2]$

$x_{1,j} = \frac {a_{1,1}} {b}+\frac {a_{1,2}} {b^2}+ \ldots+\frac {a_{1,j}} {b^j}$
$x_{2,j} = \frac {a_{2,1}} {b}+\frac {a_{2,2}} {b^2}+ \ldots+\frac {a_{2,j}} {b^j}$
$\ldots$
$x_{j,j} = \frac {a_{j,1}} {b}+\frac {a_{j,2}} {b^2}+ \ldots+\frac {a_{j,j}} {b^j}$
$\ldots$
$x_{b^j-1,j} = \frac {a_{b^j-1,1}} {b}+\frac {a_{b^j-1,2}} {b^2}+ \ldots+\frac {a_{b^j-1,j}} {b^j}$

Здесь все $a_{i,j}$ – цифры $i$ -того числа, записанного с помощью $j$ цифр в $b$ -ичной системе счисления. $a_{i,j}$ находятся по формуле:

$a_{i,j-k} = \left[ \frac {i} {b^k} \right] \bmod {b}$

где $[\ldots]$ – функция «целая часть», $0 \leqslant k \leqslant j-1$ .

С помощью рекуррентности $[2.1]$ при неограниченном росте $j$ легко получать сколь угодно точное приближение множества вещественных чисел рациональными числами $[2.2]$ в интервале $(0,1]$ .

Зафиксируем $j$ и возьмем, как и в $[1.2]$ , число

$x = 0. d_1 d_2 \ldots d_j$

где $d_s$ удовлетворяют свойствам $[1.3]$ с той лишь разницей, что основание десятичной системы счисления здесь заменено на $b$ . По тем же соображениям, что и раньше, число $x$ отличается от чисел $x_{1,j}, \ldots ,x_{j,j}$ , но оно будет каким-то из чисел $x_{j+1,j}, \ldots, x_{b^j-1,j}$ , потому что они не содержат диагональных элементов $a_{s,s}$ , а в списке $[2.2]$ присутствуют всевозможные наборы из $j$ цифр $b$ различных видов (размещения с повторениями), за исключением нуля.

Раскрывая неограниченно рекуррентность $[2.1]$ (без числа $x_{b^j-1,j}$ , равного в пределе $1$ ), что соответствует $j \to \infty$ , получим множество всех вещественных чисел на промежутке $(0,1)$ , которое, как и в случае конечного $j$ , будет счетным, поскольку число $[1.2]$ с условиями $[1.3]$ никогда не сможет быть построено:

Действительно, каждая цифра $d_s$ числа $[1.2]$ отличается от $s$ -й цифры числа $x_{s,s}$ , но при этом самих чисел в списке $b^s-2$ , поэтому при рассмотрении цифры $d_{b^s-2}$ числа $x$ из $[1.2]$ , отличающейся от $b^s-2$ -й цифры числа $x_{b^s-2,b^s-2}$ , мы будем иметь дело уже со списком из $b^{b^s-2}-2$ чисел (список по условию неограниченно растет). И так далее.

Пожалуйста, укажите ошибку в данном рассуждении, ведь оно противоречит теореме Кантора.

gris · 13/08/08 14495

Заранее извиняюсь, что не успел внимательно вчитаться в Ваш текст, но Ваша идея заранее страдает неким изъяном. Кантор придумал некоторый механизм, который при десятичной системе доказывает невозможность исчерпывающей нумерации действительных чисел. Вы же рассматриваете некоторые усложнения, при которых механизм Кантора уже не работает. Возможно, что Вы ошиблись, и в Ваших выкладках есть ошибка, а возможно, что они безупречны. Но это совершенно неважно, ибо они ничего не доказывают и ничему не противоречат. Мощность множества действительных чисел не зависит от способа их представления. Поэтому достаточно продемонстрировать действенность метода для одной системы счисления. Хотя в множестве всех представлений в счётном множестве систем счисления он может и не работать.

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

Null · 12/08/10 1677

- Archer - в сообщении #767307 писал(а):

Раскрывая неограниченно рекуррентность $[2.1]$ (без числа $x_{b^j-1,j}$ , равного в пределе $1$ ), что соответствует $j \to \infty$ , получим множество всех вещественных чисел на промежутке $(0,1)$ , которое, как и в случае конечного $j$ , будет счетным, поскольку число $[1.2]$ с условиями $[1.3]$ никогда не сможет быть построено:

К сожалению при предельном переходе мы теряем нумерацию всех чисел.

Xaositect · 06/10/08 6422

- Archer - в сообщении #767307 писал(а):

Раскрывая неограниченно рекуррентность $[2.1]$ (без числа $x_{b^j-1,j}$ , равного в пределе $1$ ), что соответствует $j \to \infty$ , получим множество всех вещественных чисел на промежутке $(0,1)$ , которое, как и в случае конечного $j$ , будет счетным, поскольку число $[1.2]$ с условиями $[1.3]$ никогда не сможет быть построено

Нельзя просто так взять и перейти к пределу $j\to \infty$ .

Мы знаем, что такое предел числовой последовательности и предел функции. Что такое предел последовательности пронумерованных множеств действительных чисел разной длины, мы пока не знаем. Попробуйте аккуратно дать определение такого предела и тогда можно уже будет сказать, что сломалось. Без такого определения это просто рукомашество.

Deggial · 20/11/12 5728

i	Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»

Someone · 23/07/05 17976 Москва

- Archer - в сообщении #767307 писал(а):

Раскрывая неограниченно рекуррентность $[2.1]$ (без числа $x_{b^j-1,j}$ , равного в пределе $1$ ), что соответствует $j \to \infty$ , получим множество всех вещественных чисел на промежутке $(0,1)$

Это неверно. Получится множество всех чисел, которые имеют конечную запись в виде $b$ -ичной дроби. Эти числа называются $b$ -ично рациональными, и они не исчерпывают даже всех рациональных чисел. Например, число $\frac b{b^2-1}=0{,}(10)_b$ никогда не появится в вашем списке. Если Вы не согласны, укажите, под каким номером оно будет там присутствовать.

- Archer - · 22/09/13 2

gris в сообщении #767310 писал(а):

Заранее извиняюсь, что не успел внимательно вчитаться в Ваш текст, но Ваша идея заранее страдает неким изъяном. Кантор придумал некоторый механизм, который при десятичной системе доказывает невозможность исчерпывающей нумерации действительных чисел. Вы же рассматриваете некоторые усложнения, при которых механизм Кантора уже не работает. Возможно, что Вы ошиблись, и в Ваших выкладках есть ошибка, а возможно, что они безупречны. Но это совершенно неважно, ибо они ничего не доказывают и ничему не противоречат. Мощность множества действительных чисел не зависит от способа их представления. Поэтому достаточно продемонстрировать действенность метода для одной системы счисления. Хотя в множестве всех представлений в счётном множестве систем счисления он может и не работать.

Насчет противоречия. Думаю, что лучше прояснить в чем суть на более простом примере.

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

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

$\eqno [1.1]$

$x_1 = \ldots a_{1,m} \ldots a_{1,2} a_{1,1}$
$x_2 = \ldots a_{2,m} \ldots a_{2,2} a_{2,1}$
$\ldots$
$x_k = \ldots a_{k,m} \ldots a_{k,2} a_{k,1}$
$\ldots$

( $a_{t,s}$ – $s$ -я цифра $t$ -го числа)

Например, таким

$x_1 = \ldots 001 \leftrightarrow 1$
$x_2 = \ldots 002 \leftrightarrow 2$
$x_3 = \ldots 003 \leftrightarrow 3$
$\ldots$
$x_{10} = \ldots 010 \leftrightarrow 10$
$x_{11} = \ldots 011 \leftrightarrow 11$
$\ldots$

Здесь $\leftrightarrow$ означает взаимно однозначное соответствие.

Рассмотрим теперь следующее число:

$\eqno [1.2]$

$x= \ldots d_m \ldots d_2 d_1$

Пусть каждая цифра $d_s$ этого числа удовлетворяет следующему свойству:

$d_s \neq a_{s,s}$

Такое число, очевидно, натуральное. Но с другой стороны, равенство $[1.2]$ интересно тем фактом, что число $x$ не совпадает ни с одним из чисел $x_t$ в $[1.1]$ , ведь иначе $t$ -я цифра числа $x$ совпала бы с $t$ -й цифрой числа $x_t$ . Значит, число $[1.2]$ представляет собой пример натурального числа, отсутствующего в списке $[1.1]$ , который по предположению содержит все множество натуральных чисел.

Видно, что "доказательство" диагональным методом Кантора "несчетности" натуральных чисел полностью противоречит хорошо известному факту счетности множества натуральных чисел.

Someone в сообщении #767379 писал(а):

- Archer - в сообщении #767307 писал(а):

Раскрывая неограниченно рекуррентность $[2.1]$ (без числа $x_{b^j-1,j}$ , равного в пределе $1$ ), что соответствует $j \to \infty$ , получим множество всех вещественных чисел на промежутке $(0,1)$

Это неверно. Получится множество всех чисел, которые имеют конечную запись в виде $b$ -ичной дроби. Эти числа называются $b$ -ично рациональными, и они не исчерпывают даже всех рациональных чисел. Например, число $\frac b{b^2-1}=0{,}(10)_b$ никогда не появится в вашем списке. Если Вы не согласны, укажите, под каким номером оно будет там присутствовать.

Число будет под номером $(10)_b$

Nemiroff · 20/07/09 4026 МФТИ ФУПМ