Теорема Кантора о несчётности континуума

Автор темы name 
ОбъявленияПоследний пост
ОбъявлениеАктуарий в PPF Life Insurance (Junior)25.03.2021 21:35
ОбъявлениеПреподаватель из Тайваня выкладывает на Pornhub лекции по математике и их смотрят тысячи людей27.09.2021 00:12
ОбъявлениеГранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2022/202314.10.2021 12:28
07.06.2003 04:16
name
Теорема Кантора о несчётности континуума
Речь идёт о статье
А.А. Зенкин "Принцип разделения времени..."
Доклады Академии Наук, 1997, том 356, № 6, с. 733-735

Его комментарий собственной статьи под названием
"Научная контрреволюция в математике" есть на этом сервере:
http://www.mmonline.ru/articles.php3?topic=1,19&mid=1863

В этих статьях, насколько я понял, утверждается,
что обычное доказательство
этой теоремы Кантора (от противного) неверно
и достраивается до "парадокса лжеца".

Есть ли кто-нибудь, кто полностью разобрался
в рассуждениях Зенкина (особенно в ДАН) и может кое-что объяснить?

08.06.2003 16:21
lms
Так...
А возьмется ли Зендин, например, утверждать, что проблема остановки алгоритмически разрешима?
09.06.2003 01:28
name
Кстати, а что это за проблема остановки?
Кстати, а что это за проблема остановки? (я в мат. логике полный профан; насчёт теоремы Кантора интересуюсь потому, что доказательства такого типа в функциональном анализе сплошь и рядом)
09.06.2003 09:43
А при чем тут проблема остановки?
К ней что, несчетность континуума сводится? Если да, то как?

09.06.2003 15:25
Кранов
Нашелся в интернете английский перевод статьи Зенкина в ДАН
Вот, нашелся в интернете английский перевод статьи Зенкина в ДАН:
http://www.com2com.ru/alexzen/papers/dan4-e.doc
Чего стоит, например, такое утверждение:
Цитата

POSTULATE 2. If, within the framework of some (not necessarily formal) system of reasonings U, there is such a formula A that
either U |- A \implies \not A or U |- \not A \implies A is provable,
then U |- (A \implies \not A)&(\not A \implies A) is provable ; <...>.
То есть, если утверждение A ложно в (не)формальной системе U, то
система U противоречива.

Кажется, это какая-то путаница из конструктивной и неконструктивной
логики, не имеющая непосредственного отношения к основаниям математики.

09.06.2003 17:22
Игорь Абрамов
Проблема остановки
Кажется это так:

Останавливается ли данная машина Тьюринга на всех
входных данных, иди, хотя бы для некоторых, зацикливается.

Эта задача алгоритмически неразрешима (если я не переврал
условия)

09.06.2003 17:35
Верно
Или: останавливается ли хоть на каком-то входе, останваливается на собственной записи (проблема самоприменимости), останавливается на каком-то фиксированном входе (пустом, например) и т.п.
Все это примеры алгоритмически неразрешимых проблем. Соответствующие множества номеров будут перечислимыми (поскольку работу всех машин можно моделировать параллельно), но не разрешимыми, более того, это в некотором смысле максимально сложные из перечислимых множеств -- они будут m-полны в этом классе.
09.06.2003 17:47
name
Спасибо за пояснение
Теперь вспомнил, что-то такое было на дискретной математике.
Правда, непонятно, как это связано
с доказательством Кантора и со статьёй Зенкина.
09.06.2003 17:53
name
конструктивная логика?
Правильно ли я понял, что согласно Зенкину,
мы не имеет права в рассуждениях
переходить от предложения
"существует такая функция f, что ..."
к предложению
"пусть f - такая функция" ?
09.06.2003 20:24
lms
счетность
// Правда, непонятно, как это связано
с доказательством Кантора и со статьёй Зенкина.//
Ну там тоже диагональный процесс использовался (который подвергается сомнению).
На самом деле мне финальный вывод понравился:
The sole reason for the appearance of this new paradox in the Cantor set theory is the "declaration" (for it is impossible to prove it) that the infinite listing (1) is actual.
где (1) - это вот что:
Assume that {assumption ьA:} the set O is countable. Then a listing of all xнX exists. Assume that
x1 , x2 , x3 , . . . xn , . . . (1)
is a listing of all real numbers from X.
Наличие такого листинга действительно не доказано - потому что оно и является определением счетного множества.
Насколько можно предположить из текста, авотр имеет другую концепцию счетного множества, примернот акого сорта: множество действительных чисел (т.е. бесконечных последовательностей цифр) называется счетным, если для любого n ("момента времени") множество отрезанных от них начальных отрезков длины n - счетно.
Соответственно, так же решилась бы и проблема остановки: проблема "остановится ли данная программа НЕ ПОЗЖЕ ШАГА n" для любого n разрешима, а вечность нас не интересует.
Таким образом, спор с Кантором если и получается, то об определениях.
10.06.2003 02:46
name
счётность; Кантор и Эвклид
Итак, множество бесконечных последовательностей цифр назовём "счётным" если для любого n множество отрезанных от них начальных отрезков длины n - счётно (*).

Наверное, введённое таким образом понятие
"счётности при любом конечном урезании"
очень интересно, особенно в логике, вычислениях и т.п.,
но оно само опирается на обычное понятие счётности,
поэтому вряд ли может его заменить.
Или в месте (*) имеется в виду "конечно" ?

> Assume that {assumption not A:} the set O is countable. Then a listing of all x in X exists. Assume that
x1 , x2 , x3 , . . . xn , . . . (1)
is a listing of all real numbers from X.

Странно... Видимо, в переводе на English опечатка.
Вместо O и o (с двумя точками) в русском оригинале
стоят X и x, как и должно быть по смыслу.

> Наличие такого листинга действительно не доказано - потому что оно и является определением счетного множества.

Не понял: мы ж предположили, что X счётно,
т.е. пересчёт множества X существует
(пересчёт=нумерация=listing = биекция N на X);
вот мы этот пересчёт берём и пользуемся
(строим число, которое не входит в этот пересчёт).

Вообще, мне кажется, что доказательство Кантора очень похоже на доказательство Эвклида (того факта, что простых чисел бесконечно много).

Так же от противного предполагаем, что P (множество простых чисел)конечно, нумеруем элементы P: p_1,...,p_n
и находим простое число p, которое не входит в эту нумерацию.

Правда, в случае доказательства Эвклида
нумерация конечная (биекция множества {1,...,n} на P),
а в случае Кантора - бесконечная (биекция N на X),
но разве это важно?
"Существование", "наличие", "актуальность" - в чём разница?
Существует биекция - значит можно брать и пользоваться.
10.06.2003 09:48
Не совсем
Цитата

name писал(а) :
Правильно ли я понял, что согласно Зенкину,
Не могу ответить на этот вопрос, поскольку этих работ не читал. Сам термин "конструктивная логика" точным не является, поскольку под него попадает довольно много весьма различных направлений: от интуиционизма до конструктивизма Маркова.

Цитата

мы не имеет права в рассуждениях
переходить от предложения
"существует такая функция f, что ..."
к предложению
"пусть f - такая функция" ?
Ну это вряд ли -- ни в каком разумном смысле такой переход неконструктивным считаться не может. Скорее имеется в виду невыводимость, например, в интуиционистском исчислении предикатов эквивалентностей вида \lnot \forall = \exists \lnot.
10.06.2003 16:38
name
А что тогда значит "объявление актуальным" ?
Maxim A. Babenko> Ну это вряд ли -- ни в каком разумном смысле такой переход неконструктивным считаться не может.

Спасибо за ответ. Это утешает.
Вот два кусочка из обсуждаемой статьи А.А. Зенкина,
которые дали мне повод к такому пониманию.

В начале статьи приведено доказательство Кантора:

> Теорема Кантора. Множество X несчётно.
Доказательство. Допустим, что множество X счётно.
Тогда существует пересчёт всех x \in X. Пусть
x_1, x_2, ... , x_n, ... (1)
есть некоторый пересчёт всех действительных чисел из X.
...

Далее в статье выводится некоторый парадокс вида
(B \to \lnot B) and (\lnot B \to B).
В конце статьи написано, что

> Единственной причиной появления этого нового парадокса канторовской теории множеств является "объявление" (ибо доказать это невозможно) беконечного пересчёта (1) актуальным.
10.06.2003 19:16
Актуальная бесконечность
Цитата

> Единственной причиной появления этого нового парадокса канторовской теории множеств является "объявление" (ибо доказать это невозможно) беконечного пересчёта (1) актуальным.

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

12.06.2003 16:11
name
что можно почитать по логике?
Спасибо за объяснение.
Теперь стало кое-что понятно, но не совсем.
Видимо, нужно почитать серьёзную литературу.
Что Вы посоветуете?
12.06.2003 23:26
lms
конструктивизм
Так ведь Зенкин не причисляет себя к адептам какой-то из неклассических логик (интуиционизм, конструктивизм ...)
Наоборот, вроде как заявка была на искоренение причин, вызвавших их появление. Странно это...
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

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