О теореме Кантора и её опровержении

Автор темы egor 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий и рекламы в форуме26.03.2008 03:07
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеВычисление параметров смешанной модели15.11.2017 16:57
19.03.2004 01:35
egor
О теореме Кантора и её опровержении
Я уже когда-то поднимал эту тему, но не имел хорошей ссылки, чтобы каждый желающий смог без труда посмотреть, о чём идёт речь.

Только что я набрёл на хороший электронный вариант статьи
А. А. Зенкина "Ошибка Георга Кантора"
http://www.com2com.ru/alexzen/papers/vf1/vf-rus.html
В этой статье говорится о каком-то логическом недостатке (ошибке?) в
доказательстве теоремы Кантора о несчётности множества двоичных последовательностей.

Мне непонятно, как из не-B в первый раз выводится B,
то есть как сразу после формулы (1.1) получено следующее утверждение:

"Очевидно, что теперь новый счетно-бесконечный пересчет (1.1) будет содержать все действительные числа множества X , т.е.
{ B:} для любого z, если z in X, то z in (1.1)."

Очень бы хотелось понять, как сделан такой вывод.
19.03.2004 13:24
А нечего, IMHO, понимать
потому что бред написан. Никоим образом B не следует из не-B. Да и вообще, мы *уже* предположили, что нумерация содержит *все* действительные числа, а оказалось обратное. Все, \qed. Попытки починить нумерацию добавлением в неё новых чисел - чистой воды схоластика и чушь. Этак можно поспорить и с Евклидовским доказательством бесконечности кол-ва простых чисел.
20.03.2004 01:54
egor
может, какая-нибудь другая логика?
Ваша позиция, в том числе апелляция к доказательству Евклида, почти дословно совпадает с моим (дилетантским) мнением по этому поводу. Проблема в том, как наше мнение разрушить ;)

Дело в том, что чуть более формальная и не такая откровенная версия обсуждаемой статьи опубликована в Докладах РАН (1997, том 356, No. 6, 733-735).
Трудно поверить, что академик, рекомедовавший эту статью,
не обратил внимание на то, что заметил даже я.
Может, он заглянул куда-то глубже?

Мне, как профану в логике, кажутся странными и некоторые выводы в книге Смаллиана (Smullyan) "Как же называется эта книга?" (пункт 250. Принцип пьяницы).
см. http://golovolomka.hobby.ru/books/smullian/name/14.shtml,
а также в книге Кэрролла "История с узелками" (парикмахеры Аллен, Браун и Карр).

Может, дело в том, что мы привыкли к слишком свободной логике (принятой большинством математиков), в то время как автор статьи рассуждает в какой-то другой (например, аристотелевой) логике?

Интересно было бы узнать отзыв конструктивистов об этой статье.
20.03.2004 07:14
Игорь Абрамов
конечно
Собственно ошибки Зенкина начинаются по крайней мере на строчку
раньше. Из того, что мы не умеем явно предъявить еще одно число,
коме диагонального, вовсе не следует, что таких чисел нет.
А дальше начинается полный беспредел ...
В общем, г-н Зенкин зачет бы у меня не получил :)
21.03.2004 23:07
Ссылка
Егор, загляните сюда:
http://www.mmonline.ru/forum/read.php?f=7&i=10798&t=10798#reply_10798



Редактировалось 1 раз(а). Последний 16.07.2008 16:30.
22.03.2004 12:52
Мнение конструктивиста
Цитата

Игорь Абрамов писал(а) :
Собственно ошибки Зенкина начинаются по крайней мере на строчку
раньше. Из того, что мы не умеем явно предъявить еще одно число,
коме диагонального, вовсе не следует, что таких чисел нет.
А дальше начинается полный беспредел ...
В общем, г-н Зенкин зачет бы у меня не получил :)

У меня, кстати, тоже :) Проблема "теоремы" Кантора состоит отнюдь не в применении диагональной процедуры (которая сама по себе безобидна, как слеза младенца), а в априорном допущении о существовании множества вещественных чисел и в принятии "теоремы" Кантора-Бернштейна.

В защиту диагональной процедуры. Рассмотрим в качестве _конструктивных_ вещественных чисел записи алгорифмов, строящих регулярно сходящиеся последовательности рациональных чисел (т.е. таких, что \(\forall n,m>N |A(n)-A(m)|<2^{-N}\) ). Так вот теоремка, притом вполне конструктивная:

ТЕОРЕМА. Осуществим алгорифм B со следующим свойством. Пусть алгорифм C таков, что для любого натурального числа n слово C(n) есть конструктивное вещественное число. Тогда алгорифм B может быть применён к записи алгорифма C, и результат такого применения есть конструктивное вещественное число, не равное никакому из чисел вида C(n).

Если мне не изменяет склероз, теорема сия приводится в "Лекциях по конструктивному математическому анализу" Б.А.Кушнера. Легко видеть, что это --- полнейший конструктивный аналог "теоремы" о несчётности континуума. Алгорифм B --- это как раз диагональная процедура :) Правда, при этом не здоровится уже упомянутой "теореме" Кантора-Бернштейна, на которую Зенкин, вроде, не грешит. Что, впрочем, лишний раз свидетельствует об уровне его горе-критики.

С уважением,
Гастрит

22.03.2004 13:39
Игорь Абрамов
тут я с Вами спорить не буду.
Непонятно все-таки, что там Зенкин напечатал в Докладах ?
Если примерно тоже самое, то это ой. Пропал дом :(
(это я про издание).

По конструктивным диагоналям:
Универсальная функция для всех вычислимых функций понятие
конструктивное ? Вроде так. (Каждой программе для машины
Тьюринга можно поставить в соответствие номер, и наоборот).

Гм. А главная универсальная функция ?
22.03.2004 14:16
Дома вообще несовершенны :(
Цитата

Игорь Абрамов писал(а) :
Непонятно все-таки, что там Зенкин напечатал в Докладах ?
Если примерно тоже самое, то это ой. Пропал дом :(
(это я про издание).

По поводу ДАН'а вопрос интересный. В библиотеку мне идти "по Зенкина", конечно же, лень (впрочем, может, и соберусь как-нибудь :) ). Однако тот факт, что представлена статья 83-летним человеком, умершим через год после публикации, наводит на мысли.

Цитата

По конструктивным диагоналям:
Универсальная функция для всех вычислимых функций понятие
конструктивное ? Вроде так. (Каждой программе для машины
Тьюринга можно поставить в соответствие номер, и наоборот).

Гм. А главная универсальная функция ?

Честное слово, ничего не понял. Универсальный алгорифм, положим, действительно существует. И что Вы с ним намерены делать?

С уважением,
Гастрит

22.03.2004 15:53
Да нет.
Нормальная эта логика, к которой мы привыкли. Всякие забавные парадоксы Б.Рассела и т.д. её отнюдь не опровергают. Автор не аппеллирует к высоким соображениям многозначной логики и т.п. - автор просто гонит.
Вот и конструктивисты то же самое говорят.
И ещё! Как человек, публиковавшийся в ДАН (хотя и не по математике), доложу Вам (только не говорите никому!), что академик, представивший статью, запросто мог не обратить внимание и на худшие вещи. Он мог вообще не читать статью.
22.03.2004 16:54
Игорь Абрамов
да уж
Цитата

Гастрит писал(а) :
Цитата

По конструктивным диагоналям:
Универсальная функция для всех вычислимых функций понятие
конструктивное ? Вроде так. (Каждой программе для машины
Тьюринга можно поставить в соответствие номер, и наоборот).

Гм. А главная универсальная функция ?

Честное слово, ничего не понял. Универсальный алгорифм, положим, действительно существует. И что Вы с ним намерены делать?

С уважением,
Гастрит


Я просто пытаюсь оценить, что из того, что я читаю студентам
по теории вычислимости уцелеет при приходе к власти
конструктивистов :).

А про универсальные алгоритмы я спрашивал вот это:
Есть ли такой универсальный алгоритм A(n,x), к которому можно
свести любой другой универсальный алгоритм B(n,x), т.е.
для любого B найдется вычислимая f, такая, что B(n,x)=A(f(n),x)

Я тут подумал, вроде все получается.

Тогда и результат типа теоремы Успенского-Райса тоже
получается. (Там, правда, в обычном рассуждении
выбираются произвольные представители класса и его
дополнения, но, пожалуй, с этим можно справиться)
22.03.2004 17:19
Вроде бы всё путём
Цитата

Игорь Абрамов писал(а) :
А про универсальные алгоритмы я спрашивал вот это:
Есть ли такой универсальный алгоритм A(n,x), к которому можно
свести любой другой универсальный алгоритм B(n,x), т.е.
для любого B найдется вычислимая f, такая, что B(n,x)=A(f(n),x)

Я тут подумал, вроде все получается.

Тогда и результат типа теоремы Успенского-Райса тоже
получается. (Там, правда, в обычном рассуждении
выбираются произвольные представители класса и его
дополнения, но, пожалуй, с этим можно справиться)

Мне почему-то кажется, что все известные универсальные алгорифмы годятся на роль A(n,x), и положение изменится лишь тогда, когда будет опровергнут тезис Чёрча :) Например, пусть A --- универсальная рекурсивная функция. Тогда, по теореме о сводимости машин Тьюринга к рекурсивным функциям, мы заведомо представим универсальную машину Тьюринга в виде A(f(n),x), где f - ЧРФ, перерабатывающая номер машины Тьюринга в номер эквивалентной ЧРФ. Та же картина будет с другими известными уточнениями понятия алгорифма.

Или я чего-то не понял?

С уважением,
Гастрит

22.03.2004 21:55
egor
всем спасибо за комментарии
Видимо, по этому поводу можно больше не волноваться.
Кстати, насколько я понял из комментария ИСН, в рассматриваемой статье принимается в качестве очевидного тезис о том, что если задана последовательность бинарных последовательностей, то отличную от них последовательность можно построить лишь одним образом. На самом же деле, можно, например, применить диагональный процесс к нечётным цифрам, а чётные выбирать по собственному усмотрению.

Впрочем, теперь это уже не важно. Просто мне почему-то вспомнилось одно "доказательство" теоремы Ферма, в котором автор полагал, что любая пифагорова тройка имеет вид (3k,4k,5k).
16.07.2008 14:33
С котлетами ясно, а как же мухи ?
Каждое действительное число интервала (0,1) можно представить в виде СЧЕТНО бесконечной последовательности чисел после запятой:

0,х1х2х3…

Теорема Кантора о несчетности множества действительных чисел говорит о том, что поставив каждой такой бесконечной записи действительного числа в соответствие натуральное число (т.е. ПРОИЗВОЛЬНО пронумеровав данный список), скажем, так (1):

1) 0,х1х2х3…,
2) 0,y1y2y3…
3) 0,z1z2z3…


ДМК (диагональным методом Кантора) можно получить новое действительное число не вошедшее в список (1), например: 0,x1y2z3…
Тем самым Кантор доказывает несчетность множества действительных чисел интервала (0,1), т.к. исходного числа в списке не было и оно, соответственно, не было пронумеровано, ему не соответствует ни одно натуральное число.

Однако, попробуем поставить все то же множество действительных чисел в соответствие не всему множеству натуральных чисел, а любому его собственному бесконечному подмножеству, скажем пронумеровав действительные числа только нечетными числами, так (2):

1) 0,х1х2х3…,
3) 0,y1y2y3…
5) 0,z1z2z3…


Теперь тем же ДМК получаем не вошедшее в список (2) действительное число : 0,x1y2z3…
Является ли это доказательством несчетности множества действительных чисел ?
Очевидно нет, т.к., не смотря на то, что мы использовали бесконечное множество натуральных чисел для нумерации, мы все же использовали не все из них, и у нас осталось еще бесконечное множество (четных) натуральных чисел для нумерации оставшихся, не вошедших в список (1) действительных чисел.

Однако, если теперь мы построим новый список с включением четных натуральных чисел, которыми пронумеруем не вошедшие в список (2) действительные числа (3):

1) 0,x1x2x3…
2) 0,x1y2z3…
3) 0,y1y2y3…
4) 0,x2y2z3
5) 0,z1z2z3


Опять применяем ДМК и получаем новое не вошедшее в этот список действительное число. Можно ли теперь сделать вывод о несчетности множества действительных чисел и считать теорему Кантора доказанной ?

Тут, у любого здравомыслящего человека (в отличие, как я вижу от предыдущих комментаторов) возникают обоснованные сомнения.
Позвольте, получается в первом случае, в списке(1), содержалось на бесконечное множество действительных чисел меньше чем в списке (3). Откуда они там могли взяться, если в случае (1), перед предъявлением нового действительного числа (например: 0,x1z2y3…), утверждалось, что ВСЕ натуральные числа израсходованы ? Если они все были израсходованы как же удалось впихнуть в тот же список (1,2,3…) еще какие-то действительные числа, например это же число: 0,x1z2y3… которого там (1) раньше не было ???

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

Например, можно разбить множество натуральных чисел на непересекающиеся бесконечные подмножества, скажем:
1) простых чисел;
2) факториалов простых чисел;
3) квадратов четных чисел;
4) корней уравнения x=y^2+56, не содержащихся в списках (1,2,3);
5) корней уравнения x=y^3+17, не содержащихся в списках (1,2,3,4);
… и т.д. и т.п.

Каждое из таких подмножеств будет содержать бесконечное число элементов – натуральных чисел.
Задача сводится лишь к тому, чтобы обнаружить на натуральном ряду бесконечное множество свойств и отношений, которое можно использовать для формирования непересекающихся бесконечных подмножеств.

Если таковых действительно бесконечное множество, в чем лично я нисколько не сомневаюсь, и в каждом будут содержаться бесконечное множество натуральных чисел, не содержащихся в других подмножествах, то, чтобы доказать несчетность множества действительных чисел теоремы Кантора с ее использованием не произвольного, а очень даже специфического отображения действительных чисел на натуральные (а именно: 1,2,3…), будет явно маловато. Нужно либо пытаться опровергнуть, что множество натуральных чисел нельзя разбить на бесконечное множество непересекающихся бесконечных подмножеств или, осуществив это и составив такой действительно произвольный список, пронумеровать им действительные числа, после чего, следуя Кантору, предъявить действительное число, которое в него не вошло.

P.S.: Если же говорить вообще о существовании несчетных множеств, то они несомненно есть по теореме Кантора, в которой утверждается, что множество всех подмножеств обладает большей мощностью, чем исходное множество. Опровергнуть ее действительно нельзя, пока принимается аксиома рефлексивности. В этом случае, даже действительно произвольная нумерация не спасет от необходимости индексации всеми натуральными числами сначала самих себя, а это оставит незанумерованными еще бесконечное несчетное множество подмножеств. Мощность этого бесконечного множества действительно будет превосходить мощность бесконечного счетного множества непересекающихся бесконечных подмножеств множества натуральных чисел. Но вот вопрос о его эквивалентности множеству действительных чисел остается открытым, пока не состоится доказательство в вышеописанном смысле.



Редактировалось 1 раз(а). Последний 16.07.2008 14:38.
16.07.2008 16:25
К чему это всё?
rrr, зачем обсуждать, что какое-то рассуждение не является доказательством теоремы, если известно рассуждение, которое таковым является?

С тем же успехом можно обсуждать доказательство бесконечности множества натуральных чисел (пусть $x_1, x_2,\ldots, x_n$ - все натуральные числа, тогда натуральное число $x_1+x_2+\ldots+x_n$ заведомо в этом списке не упомянуто) - и обнаружить, что на самом деле можно занумеровать сколь угодно много натуральных чисел, итп, и думать, что это может значить для здравомыслящего человека.

Цитата
rrr
Если же говорить вообще о существовании несчетных множеств, то они несомненно есть по теореме Кантора, в которой утверждается, что множество всех подмножеств обладает большей мощностью, чем исходное множество. Опровергнуть ее действительно нельзя, пока принимается аксиома рефлексивности.
Кстати, эта теорема Кантора доказывается точно так же, как и обсуждаемая.



Редактировалось 1 раз(а). Последний 16.07.2008 16:27.
03.11.2018 05:58
О теореме Кантора и её опровержении.
Когда я впервые увидел диагональное доказательство Кантора, у меня возникла уверенность, что здесь ошибка. Ведь элементов на диагонали исчезающе малое количество по сравнению с остальными. С другой стороны, прошло более ста лет, как оно (доказательство) предъявлено. Но сначала довольно долго было не до того, и лишь через немалое время мне удалось найти опровержение. Как раз А.А. Зенкин и подстегнул поиски. Вот посмотрите здесь: http://eugen1937.ucoz.net/Hilbert_rus.html Опровержение континуум-гипотезы устраняет препятствие к воссоединению математиков.



Редактировалось 2 раз(а). Последний 03.11.2018 06:50.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти