![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЭдвард Нельсон, профессор Принстонского университета, объявил, что он доказал противоречивость арифметики Пеано (PA) (Update: если страница не открывается, то вот кэш-версия). Он выложил эскиз своего доказательства; полное и строгое доказательство он все еще пишет, и собирается выкладывать его по частям вместе с формальной проверкой с помощью программы, которую он сам написал.
Нельсон - не сумасброд, а настоящий математик. Его доказательство в принципе несложно, и опирается не недавно найденное новое доказательство второй теоремы Геделя о неполноте (той, которая утверждает, что достаточно сложная система аксиом не может доказать свою непротиворечивость, если она непротиворечива).
Я достаточно помню в этой области, чтобы понять его основные идеи, но недостаточно, чтобы строго их проверить. Мне кажется очень вероятным, что где-то у него есть ошибка. Думаю, в ближайшие пару дней это станет ясно.
P.S. Можно помечтать о том, что будет, если ошибки нет. Конечно, это тогда автоматически самый знаменитый и важный результат в логике за последние сто лет, и немедленный кризис в основаниях математики. Если PA противоречива, то и теория множеств, на которую опирается вся современная математика, тоже противоречива. Будет кризис в основаниях математики, похожий на тот, что случился с открытием парадокса Расселла. Нужно будет заменить теорию множеств на такую, которая все еще достаточно мощна, чтобы поддерживать современную математику, но не доказывает полную неограниченную индукцию в арифметике. Не факт, что это будет просто сделать. "Обычные" математики, не связанные с логикой, конечно, особенно волноваться не будут, как не волновались они и 100 лет назад. Но все равно, если это верно, то гигантской важности результат.
P.P.S. Обсуждение в блоге Джона Баэза.
Нельсон - не сумасброд, а настоящий математик. Его доказательство в принципе несложно, и опирается не недавно найденное новое доказательство второй теоремы Геделя о неполноте (той, которая утверждает, что достаточно сложная система аксиом не может доказать свою непротиворечивость, если она непротиворечива).
Я достаточно помню в этой области, чтобы понять его основные идеи, но недостаточно, чтобы строго их проверить. Мне кажется очень вероятным, что где-то у него есть ошибка. Думаю, в ближайшие пару дней это станет ясно.
P.S. Можно помечтать о том, что будет, если ошибки нет. Конечно, это тогда автоматически самый знаменитый и важный результат в логике за последние сто лет, и немедленный кризис в основаниях математики. Если PA противоречива, то и теория множеств, на которую опирается вся современная математика, тоже противоречива. Будет кризис в основаниях математики, похожий на тот, что случился с открытием парадокса Расселла. Нужно будет заменить теорию множеств на такую, которая все еще достаточно мощна, чтобы поддерживать современную математику, но не доказывает полную неограниченную индукцию в арифметике. Не факт, что это будет просто сделать. "Обычные" математики, не связанные с логикой, конечно, особенно волноваться не будут, как не волновались они и 100 лет назад. Но все равно, если это верно, то гигантской важности результат.
P.P.S. Обсуждение в блоге Джона Баэза.
no subject
Date: 2011-09-30 05:36 am (UTC)Что вы хотели сказать? Что парадокс брадобрея - эквивалент парадокса Рассела? Не верю, вы же математик. Общее у них только self-reference. Никаких противоречий в теории множеств парадокс брадобрея не затрагивает. Чисто семантический парадокс, противоречие в определении действий брадобрея.
no subject
Date: 2011-09-30 10:09 am (UTC)рождение предиката
Date: 2011-10-01 06:44 pm (UTC)Тут что-то может зависеть от формы представления самой "истории", но если брать ту версию, где брадобрею было дано задание, то рассуждать можно так. Если не было уточнения, к какому времени следует побрить, то "неоднозначность" получается в любом случае -- даже если исключить бритьё его самого. С какого момента наступает ответственность за "непобритие" того, кого следовало побрить? То есть подразумевается задание некоторого "часа X". В уточнённой форме получается, что брить следует тех и только тех, кто не побрился до "часа X". Также удобно добавить ограничение, что до этого времени никого брить нельзя. Тогда брадобрей спокойно бреет себя после "часа X", ничего не нарушая.
Понятно, что это объяснение не имеет отношения к проблемам логики как таковой, но оно показывает, что не так легко получить парадокс из этой "модельной" ситуации. Ведь дело не в том, чтобы просто написать предикат, где P(c,y) <-> (\forall y)P(y,y). Такая формула даёт противоречивые следствия очевидным образом, а "интрига" вся в том, чтобы в какой-то "реальной" или "интересной" ситуации предикат с таким свойством вообще возник.
Есть ещё версия, когда брадобрей повесил объявление. Но она тоже немного "хромает", потому что там не вполне ясно, что он имел в виду. "Бреется сам" -- это какой смысл имеет? Что вообще делал так хотя бы раз, или всегда так делает? Явно не хватает квантора. Далее, там понятно, что речь может идти только о каком-то "контингенте". Ведь тех, кого уже нет на свете, и кто носил бороду, он брить явно не может. То есть тут нужна куча уточнений. Не говоря о том, что повесить можно любое объявление -- например, такое, где написано заведомо ложное высказывание.
Re: рождение предиката
Date: 2011-10-01 08:47 pm (UTC)испарение смысла
Date: 2011-10-02 05:51 am (UTC)Re: испарение смысла
Date: 2011-10-02 04:16 pm (UTC)брадобрей не пропадет
Date: 2011-10-01 09:36 pm (UTC)Вообще-то примерно так же можно решать и парадокс Рассела, но там это не так очевидно.
завиральная идея
Date: 2011-10-02 05:58 am (UTC)Наверное, в каких-то задачах бывают трудности, связанные со скрытой "омонимией", когда одним именем называются разные вещи. Но здесь я этого и близко не наблюдаю. Вот идёт "физический" процесс бритья. Кто-то при этом держит бритву (это x), и чью-то бороду при этом бреют (это y). Такое явление мы записываем в виде атомарной формулы P(x,y). В соответствии с правилами логики предикатов, P(x,x) также есть формула. При этом она имеет простой "физический" смысл.
Чтобы вообще исключить возможность "придирок", можно вместо "бреется сам", создающего видимость нового (одноместного) предиката, говорит "бреет сам себя". Но все понимают, что это одно и то же по смыслу.
Re: завиральная идея
Date: 2011-10-02 07:30 am (UTC)По существу Вы утверждаете, что должность директора фирмы (скажем) и сам директор, которой человек, - это одно и то же. Ведь Вы не различаете того брадобрея (как профессиональную функцию, как "должность"), который бреет клиентов, и того брадобрея-человека, который бреется сам, как обычный мужчина.
Или если перевести это на тот язык, на котором, Вы написали предыдущий коммент - бритие у брадобрея описываетсЯ некой атомарной формулы P(x,y), где х - тот, кто бреет, а у - кого бреют, но
1) согласно условиям задачи только один атом может занимать место х. Брадобрей в городе только один
2) брадобрей (как человек) не может раздвоиться и занимать одновременно место профессионала-"брадобрея" и место клиента, то есть не может одновременно и сидеть в креслле, и стоять рядом.
Откуда следует что на P(x,y) наложено ограничение - не допускается P(х,х), на конкретной области аргументов города N.
Таково условие задачи.
Но для само-брития такого ограничения естественно нет, и там будет другая формула - S(x) (или S(x,x), если Вам так больше нравится :)
Короче говоря, брадобрей-человек брет себя сам и не бреется (в принципе не может бриться) у брадобрея-профи. Где тут парадокс-то? Нет никакого противоречия.
Как бы парадоксальность возникает из-за ошибки в формализации, когда всё описывают одной формулой и забывают при этом про ограничения, наложенные условием задачи.
Re: рождение предиката
Date: 2011-10-01 11:29 pm (UTC)Вы очень хорошо проиллюстрировали роль неясности *определения* брадобрея в парадоксе. Парадокс возникает, если мы принимаем определение "брадобрей - это тот, кто бреет тех, кто не бреет себя сам" за корректное. Та мысль, что любой грамматически корректный текст (с грамматической структурой определения) действительно имеет смысл для меня выглядит мистикой на уровне "Bible codes". Определение брадобрея, приведенное мной выше, смысла не имеет, и Вы хорошо проиллюстрировали то, как далеко оно от корректного определения.
Ничто не запрещает нам в процессе формализации этого определения на эвристическом уровне отождествить брадобрея с множеством тех людей, которых он бреет. Тогда мы получим парадокс Рассела.
Если, наоборот, начать с парадокса Рассела, то мы увидим, что он основан на мистической вере в то, что любое грамматически корректное утверждение в формальном языке что-то определяет. Сходная вера распространена в теретической физике: если мы написали формулу со знаком интеграла, то этот интеграл имеет смысл и числовое значение (если это определенный интеграл). Математики давно поняли, что это не так. Физики могут позволить себе эту мистику только потому, что у них есть эксперимент, на основании которого бессмысленные формулы отбрасываются. А в математики экспериментов такого сорта нет и невозможны - нельзя поставить эксперимент, в котором участвуют не то что бесконечные, но и просто очень большие множества или числа.
Определение множества, данное Кантором, было дано не в формальной системе, а на обычном немецком языке. И в нем есть важные, но неформализуемые условия - например, элементы множеств должны быть "четко различимыми объектами нашего сознания" (цитирую по памяти). Парадокс Рассела показывает, что его определение не удовлетворяет условиям Кантора. Так что парадокс Рассела - это противоречие в формальной системе Фреге, а не в теории множеств Кантора (кажется, он и был исходно опубликован как результат о системе Фреге). Математики легко соглашаются с тем, что грамматическая корректность текста на обычном языке еще не означает, что он имеет смысл (опредляет какой-то объект). Почему-то, когда речь заходит о формальных системах, это понимание часто исчезает.
Дальше пошел сплошной пиар. Рассел, как известно, был умелый политический деятель. Довольно загадочным, почему математики и до сих пор иногда возваращаются к этой провокации. Рассел не сделал в математике ничего (просто совсем ничего, а не на каком-то уровне). Откуда у него такой авторитет? Скажем, Брауэр был первоклассным математиков, Эррет Бишоп - очень хорошим, но их теории (интуиционизм и конструктивный анализ Бишопа), основанные на содержательных соображениях (в отличие от тривиальности Рассела), знакомы только тем, кто ими профессионально занимается (интуиционизм Брауэра вообще выжил только в виде его формальной версии, в то время как формализация совершенно чужда идеологии Брауэра).
Может, все дело в том, что про брадобреев, парадокс Рассела, наименьшее неинтересное число и т.п. легко писать в популярных книжках для школьников или широкой публики, а конструктивный анализ Бишопа вряд ли можно воспринять, не зная обычного.
конфликт истолкований
Date: 2011-10-02 06:35 am (UTC)Понятие "бреет" можно определить так, когда сам брадобрей решает, кого брить, а кого нет, и далее это декларирует. Наподобие того, как если бы было сказано "я брею только женатых". Тогда не возникает сомнений ни в осмысленности понятия, ни в истинности заявления, так как предполагается, что своему принципу он далее будет следовать. Но здесь есть другой аспект, который всё "портит": когда мы начинаем далее сравнивать ситуацию с тем, что происходит "на самом деле", то слово "бреет" начинает использоваться уже в другом смысле, который вдобавок следует уточнить. То ли бреет хотя бы раз, то ли бреет всегда, то ли бреет до "часа X", то ли ещё что-то. И в этом случае происходит уже нарушение "закона тождества" в логике: одно имя используется в пределах того же рассуждения для обозначения разных "сущностей".
Но здесь как бы всё ясно, а вот с парадоксом Рассела получается интереснее. Меня всегда (ещё с детских времён) "смущала" одна вещь. А именно, на основании возникновения этого парадокса из аксиоматики исключили "очевидный" для меня "принцип свёртывания". Ведь если в моём распоряжении есть достаточно ясное "свойство", то что мне мешает отобрать из какой-то совокупности предметов в точности то, что обладает этим свойством? И этим принципом совершенно не хотелось "жертвовать", ибо он "очевиден"!
То есть получается так, что у нас в распоряжении имеется некий "оракул", и есть также "сканер" по всем элементам множества. Действуя при помощи этих двух средств, мы получаем то, что хотим. Поэтому в данном случае нет сомнений в "корректности". Как нет их в случае аксиомы выбора: там помимо "сканера" есть ещё "недетерминисткая" процедура извлечения элемента из непустого множества. И на этом основании мы аксиому выбора тоже считаем "верной" при выбранной "содержательной" трактовке.
Свойство множества быть своим собственным элементом тоже считается "ясным", так как "оракул", который "знает всё", либо демонстрирует, что в x присутствует элемент x, либо "перебирает" все элементы из x и показывает, что ни один из них не совпадает с x. На уровне таких "процедур" всё как бы "чисто", и тогда те возражения, о которых Вы говорите, становятся учтёнными. При этом всё хорошо и с "базовыми" принципами, провозглашёнными Кантором. То есть тут всё хорошо отличимо друг от друга (есть другой "оракул", который по двум множествам x и y определяет, равны ли они).
И на таком пути разрешение парадокса Рассела оказывается совершенно не тем, какое предлагается в "популярной" или "околоматематической" литературе. Я когда-то описывал подробно, где тут "зарыта собака", и почему противоречие не возникает, если подходить именно этим способом. Сохраняя в силе те "очевидные" принципы, которые соответствуют нашей интуиции.
Я могу либо дать ссылку на уже написанный текст, либо написать у себя в журнале всё заново.
Что касается "научных" заслуг Рассела, то обычно считается, что это "теория типов". Если говорить о каких-то открытых Расселом новых математических фактах, то ясно, что ни один из них не "конкурирует" с теоремой Брауэра о неподвижной точке. Здесь можно даже сказать, что Рассел занимался не столько математикой, сколько её "основаниями". То есть это как бы другая область. И тут немалую роль сыграл "позитивизм" Рассела, вместе с крайней "узостью" его философских взглядов, налагающих очень сильные ограничения на методологию.
Ну, а тиражи популярных изданий тут сами за себя говорят, так что не удивительно! О "бишопах" скорее можно прочитать в книгах об истории, или о шахматах! :)
Re: конфликт истолкований
Date: 2011-10-02 08:11 am (UTC)А пока я могу только сказать, что свойство "х является элементом х" я лично не ощущаю как четко определенное. Уже идея множества, состоящего из других множеств, представляет небольшие психологические трудности. Теория множеств пошла по пути неограниченного (вверх!) рассмотрения ...множеств множеств множеств - слово можно повторять трансфинитное число раз - влево! Двигаться обратном направлении, рассматривая сущности, которым бы подошло обозначение {{{... ...}}} с бесконечным числом скобок внутрь, крайне неестественно. Такая сущность должна была быть (единственным) элементом самой себя. Мы не занимаемся квантовой теорией поля, написанная формула еще ничего не значит. Я думаю, что Кантор не имел в виду таких сущностей. И математики с удовольствием приняли аксиому фундирования и тут же о ней забыли. Но ведь никто не запрещает нам просто добавить такую сущность к системе. Никто не сомневается в том, что можно добавлять пра-элементы, почему не добавить и такой?
Даже если мы рассматриваем только кумулятивную иерархию множеств (из аксиом Цермело-Френкеля все равно нельзя вывести существования множеств, не входящих в нее), у нас остается еще множество всех множеств. Меня бы это больше беспокоило, тут трудности появляются при свертывании по свойству a=a, которое уж совсем невинно. Моя интерпретация этого парадокса состоит в том, что если разрешить такое свертывание, то понятие множества становится неопределенным. В частности, мы получаем нечто принадлежащее самому себе.
Разговоры о множестве всех множеств опираются на ту же самую мистическую идею о том, что все грамматические корректные фразы что-то определяют. У меня бы и без противоречия с теоремой Кантора возникало бы чувство непонимания, о чем же идет речь.
Суммируя, мне кажется, что математики ничего, кроме кумулятивной иерархии и вообразить себе четко не могут. Аксиомы Цермело-Френкеля описывают некие "очевидно" допустимые методы построения множеств, но вполне могут появиться и другие. Упустил же Цермело аксиому Френкеля. И применялась она вроде бы только один раз. На практике же всем, кроме специалистов по теории множеств, достаточно нескольких первых этажей иерархии (натуральные числа при этом не определяются по фон Нейману - это не более чем красивый - очень красивый - трюк, а являются пра-элементами).
sets and languages
Date: 2011-10-02 11:27 am (UTC)http://falcao.livejournal.com/200177.html?thread=8186097#t8186097
Это коммент из двух частей, но там фактически нужна только вторая, а от первой части достаточно взять лишь три последних абзаца.
Прокомментировать можно там же, если будет желание.
Отмечу здесь ещё такую вещь, что вопрос о том, надо ли брать нефундированные множества, или не надо, а также нужны ли "пра-элементы", я оставляю как бы "за скобками". То есть при любом "окончательном" решении того, что всё-таки следует считать "множествами", получается та картина, которую я описывал.
Лично моё мнение по самому этому вопросу вот какое: я думаю, что "теорий множеств" в определённом смысле столько же, сколько и алгоритмических языков. Вряд ли обоснованной будет попытка придумать "самый лучший" или "самый правильный" AL. Где-то будет одни преимущества, а где-то другие. Верной также будет та точка зрения, что "по сути" все алгоритмические языки представляют собой "одно и то же", что есть фактически "тезис Чёрча". Но это значит лишь то, что разницу можно при желании игнорировать. А сама по себе она всё равно есть, и одноленточная машина Тьюринга вряд ли "поймёт" язык c++.