GotAI.NET - Форум - Искусственный интеллект

Все темы | Новая тема

Стр.1 (6)

След. > >>

Поиск:

Автор

Тема: Счетность вещественных чисел

kcrotor
Сообщений: 402

Счетность вещественных чисел

Добавлено: 19 авг 10 20:22

Обсуждение родилось тут и чтобы не засорять ту ветку открыл новую тему.
Я конечно не согласен с наивным предложение НьюПоиска касательно "отбрасывания запятой", как с доказательством счетности, однако мне кажется счетность вещественных чисел наглядно доказывается парадоксом Ришара:

Цитата:

С помощью некоторых фраз русского языка могут быть охарактеризованы те или иные вещественные числа. Например, фраза «отношение длины окружности к длине её диаметра» характеризует число π, а фраза «две целых и три десятых» характеризует число 2,3. Все фразы русского языка можно перенумеровать определенным способом, например упорядочим фразы по алфавиту как в словаре, тогда каждая фраза получит тот номер, на каком месте она находится. Теперь можно в этой нумерации фраз опустить все те, которые не характеризуют какое-нибудь вещественное число. Число, которое получает при такой нумерации номер n, назовем n-м числом Ришара.

В википедии приводится опровержение этого парадокса:

Цитата:

Рассмотрим такую фразу: «Вещественное число, у которого n-й десятичный знак равен 1, если у n-го числа Ришара n-й десятичный знак не равен 1, и n-й десятичный знак равен 2, если у n-го числа Ришара n-й десятичный знак равен 1». Эта фраза определяет некоторое число Ришара, допустим, k-е; однако, согласно определению, оно отличается от k-го числа Ришара в k-м десятичном знаке. Таким образом, пришли к противоречию.

Которое якобы доказывает что существует число не занумерованное при помощи правила Ришара. Но в этом доказательстве содержится явная ошибка: Наличие алгоритма построения числа еще не свидетельствует о существовании этого числа. Для того чтобы убедится в том что задаваемое алгоритмом число действительно существует нужно убедится что все шаги этого алгоритма выполнимы. Докажем что приведенный алгоритм содержит невыполнимый шаг:
Рассмотрим такую фразу: «Вещественное число, у которого n-й десятичный знак равен 1, если у n-го числа Ришара n-й десятичный знак не равен 1, и n-й десятичный знак равен 2, если у n-го числа Ришара n-й десятичный знак равен 1». Эта фраза имеет некоторый порядковый номер, допустим он равен k При попытке построить число в соответствии с этой фразой мы неизбежно сталкнемся с невыполнимой операцией: сделать так, чтобы в k-ом десятичном знаке стояля цифра отличная от себя самой. Поскольку такой цифры не существует то выполнить этот шаг алгоритма невозможно, а значит НЕ СУЩЕСТВУЕТ предложенного вещественного числа, т.е. числа выбивающегося из нумерации Ришара.

Аналогичная ошибка содержатся и в доказательстве несчетности вещественных чисел, приведенном в википедии:

Цитата:

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

Пусть все числа указанного промежутка уже занумерованы некоторым образом. Тогда их можно выписать в следующем виде:
$x_1 = 0,a_{11}a_{12} \cdots a_{1m} \cdots$
$x_2 = 0,a_{21}a_{22} \cdots a_{2m} \cdots$
$\cdots$
$x_k = 0,a_{k1}a_{k2} \cdots a_{km} \cdots$
$\cdots$

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

Далее предлагается рассмотреть следующее число:
$x = 0, d_1 d_2 \cdots d_m \cdots$

Пусть каждая цифра $d_i$ этого числа удовлетворяет следующим трём свойствам:
$d_i \neq 0$
$d_i \neq 9$
$d_i \neq a_{ii}$

Такое число действительно существует на указанном промежутке, так как оно является вещественным, не совпадает ни с нулём, ни с единицей, а десятичных цифр достаточно, чтобы третье свойство выполнялось. Кроме этого, $x$ интересно тем фактом, что оно не совпадает ни с одним из чисел $x_j$ , выписанных выше, ведь иначе $j$ -я цифра числа $x$ совпала бы с $j$ -ой цифрой числа $x_j$ . Пришли к противоречию, заключающемуся в том, что как бы числа рассматриваемого промежутка ни были занумерованы, всё равно найдётся число из этого же промежутка, которому не присвоен номер.

Вывод что "Такое число действительно существует на указанном промежутке, так как оно является вещественным, не совпадает ни с нулём, ни с единицей, а десятичных цифр достаточно, чтобы третье свойство выполнялось" Ошибочен, поскольку один из его десятичных знаков должен быть не равен сам себе, а цифры не равной самой себе не существует, а значит десятичных цифр НЕдостаточно, чтобы третье свойство выполнялось.

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

Форум: Проблемы искусственного интеллекта