о Гёделе и Изабелле, take 1
Sep. 2nd, 2002 12:46 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНашлась потерянная было запись о формализации док-ва Гёделя, поэтому кидаю её сюда под элжекат для тех, кому интересно.
subject: формализация V=L и консистенстности аксиомы выбора
(контекст: математика, теория множеств, аксиома выбора)
Немного контекста. В 1940-м году Гёдель доказал, что аксиома выбора (и обобщённая гипотеза континуума вместе с ней) консистентны с остальными аксиомами теории множеств, т.е. что невозможно при помощи остальных аксиом их опровергнуть (при условии, что остальные аксиомы непротиворечивы сами по себе). Это, во-первых, окончательно укрепило статус аксиомы выбора в глазах математиков; во-вторых, результат Гёделя вместе с доказательством Коэна 20 лет спустя (Коэн показал, что эти утверждения из остальных аксиом невозможно доказать) доказывают независимость аксиомы выбора от остальных аксиом -- первое и самое важное нетривиальное доказательство неполноты мощной формальной системы (в данном случае теории множеств без аксиомы выбора), не опирающееся на теоремы Гёделя о неполноте.
(иными словами, из знаменитых теорем Гёделя о неполноте мы знаем, что любая достаточно мощная формальная система -- в том числе теория множеств -- неполна, т.е. существуют утверждения, к-е она не может ни доказать, ни опровергнуть. Но конкретное такое утверждение, формулируемое в процессе док-ва неполноты, независимого математического интереса не представляет. Пример интересного такого утверждения - пятый постулат Евклида, независимый от остальных аксиом геометрии; но аксиомы геометрии намного слабее, чем аксиомы арифметики или теории множеств. Аксиома выбора -- пример такого интересного утверждения, независимого от теории множеств.)
Доказательство Гёделя основывалось на построении специального рода модели теории множеств, под названием конструктивная вселенная (её обычно обозначают буквой L, в отличие от "всей вселенной" вообще, обозначаемой буквой V). В конструктивной вселенной аксиому выбора можно доказать; затем можно показать, что любое док-во противоречия в L влечёт за собой док-во противоречия в обычной теории множеств. Поэтому если бы аксиому выбора можно было опровергнуть при помощи других аксиом, то такое опровержение существовало бы и "внутри" L, и тогда вместе с док-вом аксиомы выбора "внутри" L явило бы собой противоречие, к-е можно было бы вытащить "наружу" в V, и доказать, что остальные аксиомы теории множеств сами по себе противоречивы.
Larry Paulson (Кембридж) недавно закончил формализацию доказательства Гёделя в компьютерной системе Isabelle, существующей для строгой формализации и формальной верификации математических доказательств. Это интересный результат. Формальная верификация математических доказательств -- весьма сложное дело; простой и очевидно истинный для человека-математика шаг в математическом доказательстве может потребовать перевода в сотни и тысячи маленьких формальных шажков для того, чтобы компьютер мог потвердить его формальную строгость и истинность. По этой причине не так уж и много нетривиальных математических теорем (даже в очень слабом для профессионального математика смысле слова "нетривиальный") были формально верифицированы. Вот краткое описание того, что сделал Полсон; а этот файл (>200 страниц, автоматически сгенерированный) содержит нужные формальные определения и доказательства - его любопытно полистать в качестве примера длинного нетривиального формального доказательства.
Я хотел также разобраться в системе Isabelle, но быстро понял, что мне не хватает как адекватного знания лямбда-исчисления (lambda calculus), так и знания языка ML, на котором она написана. Особенно λ-calculus давно уже пора было как следует изучить.
subject: формализация V=L и консистенстности аксиомы выбора
(контекст: математика, теория множеств, аксиома выбора)
Немного контекста. В 1940-м году Гёдель доказал, что аксиома выбора (и обобщённая гипотеза континуума вместе с ней) консистентны с остальными аксиомами теории множеств, т.е. что невозможно при помощи остальных аксиом их опровергнуть (при условии, что остальные аксиомы непротиворечивы сами по себе). Это, во-первых, окончательно укрепило статус аксиомы выбора в глазах математиков; во-вторых, результат Гёделя вместе с доказательством Коэна 20 лет спустя (Коэн показал, что эти утверждения из остальных аксиом невозможно доказать) доказывают независимость аксиомы выбора от остальных аксиом -- первое и самое важное нетривиальное доказательство неполноты мощной формальной системы (в данном случае теории множеств без аксиомы выбора), не опирающееся на теоремы Гёделя о неполноте.
(иными словами, из знаменитых теорем Гёделя о неполноте мы знаем, что любая достаточно мощная формальная система -- в том числе теория множеств -- неполна, т.е. существуют утверждения, к-е она не может ни доказать, ни опровергнуть. Но конкретное такое утверждение, формулируемое в процессе док-ва неполноты, независимого математического интереса не представляет. Пример интересного такого утверждения - пятый постулат Евклида, независимый от остальных аксиом геометрии; но аксиомы геометрии намного слабее, чем аксиомы арифметики или теории множеств. Аксиома выбора -- пример такого интересного утверждения, независимого от теории множеств.)
Доказательство Гёделя основывалось на построении специального рода модели теории множеств, под названием конструктивная вселенная (её обычно обозначают буквой L, в отличие от "всей вселенной" вообще, обозначаемой буквой V). В конструктивной вселенной аксиому выбора можно доказать; затем можно показать, что любое док-во противоречия в L влечёт за собой док-во противоречия в обычной теории множеств. Поэтому если бы аксиому выбора можно было опровергнуть при помощи других аксиом, то такое опровержение существовало бы и "внутри" L, и тогда вместе с док-вом аксиомы выбора "внутри" L явило бы собой противоречие, к-е можно было бы вытащить "наружу" в V, и доказать, что остальные аксиомы теории множеств сами по себе противоречивы.
Larry Paulson (Кембридж) недавно закончил формализацию доказательства Гёделя в компьютерной системе Isabelle, существующей для строгой формализации и формальной верификации математических доказательств. Это интересный результат. Формальная верификация математических доказательств -- весьма сложное дело; простой и очевидно истинный для человека-математика шаг в математическом доказательстве может потребовать перевода в сотни и тысячи маленьких формальных шажков для того, чтобы компьютер мог потвердить его формальную строгость и истинность. По этой причине не так уж и много нетривиальных математических теорем (даже в очень слабом для профессионального математика смысле слова "нетривиальный") были формально верифицированы. Вот краткое описание того, что сделал Полсон; а этот файл (>200 страниц, автоматически сгенерированный) содержит нужные формальные определения и доказательства - его любопытно полистать в качестве примера длинного нетривиального формального доказательства.
Я хотел также разобраться в системе Isabelle, но быстро понял, что мне не хватает как адекватного знания лямбда-исчисления (lambda calculus), так и знания языка ML, на котором она написана. Особенно λ-calculus давно уже пора было как следует изучить.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Ну, почему интереса не представляет?
Date: 2002-09-02 05:35 am (UTC)Пример:
A1 = 2 в степени (2 в степени (2 в степени 2)).
Берем A1, вычитаем из него единицу и представляем в виде степеней двойки; затем все двойки заменяем тройками. Полученное число называем A2, причем очевидно, что A2 > A1 .
Вычитаем из A2 единицу, раскладываем на степени тройки и заменяем все тройки четверками. И так далее.
Оказывается, эта последовательность, вначале круто возрастающая, в конце концов становится убывающей и при некоем N приходит к AN = 1.
Это утверждение доказуемо при помощи теории ординалов (путем замены двойки/тройки/и так далее на ω, и используя теорему об убывающей последовательности ординалов). При помощи же собственно арифметики оно недоказуемо (что, в свою очередь, можно доказать :) ).
Re: Ну, почему интереса не представляет?
Date: 2002-09-02 05:52 am (UTC)Да, можно. Вот ещё один пример.
Но все эти примеры появились уже после док-в Гёделя и Коэна -- а именно,в конце 70-х, после фундаментальных исследований Париса и Харрингтона в этой области. Док-ва Гёделя и Коэна в сумме дали первый нетривиальный приме математически интересного утверждения.
Спасибо
Date: 2002-09-02 06:13 am (UTC)Хотел написать, что она эквивалентна задаче о последовательности, но тут же вспомнил слова мэтра Рона Ахарони: "все правильные теоремы эквивалентны друг другу".
Re: Ну, почему интереса не представляет?
Date: 2002-09-02 10:42 am (UTC)Re: Ну, почему интереса не представляет?
Date: 2002-09-02 10:48 am (UTC)Re: Ну, почему интереса не представляет?
Date: 2002-09-02 10:56 am (UTC)Re: Ну, почему интереса не представляет?
Date: 2002-09-02 10:50 am (UTC)Неа;)
Date: 2002-09-02 11:39 am (UTC)Можно любое число подобного рода.
Т.е. спасибо за уточнение условия!