Теорема Гёделя. Почти строгое доказательство!

Как же хочется поскорее разобрать основную идею доказательства... Но сначала нам предстоит понять что общего между высказываниями, числами и формальными системами, а также зачем одно переводить в другое! (пожалуйста, не спрашивайте когда будет следующая часть)
Книга Ньюмена и Нагеля: www.amazon.com/G%C3%B6dels-Pr...
Книга Мендельсона: www.routledge.com/Introductio...
ссылка про формальные системы: cs.lmu.edu/~ray/notes/formals...
Таймкоды:
00:00 Мы начинаем!
2:28 Предисловие (изоморфизм и структуры)
7:13 Языки и формальные системы
11:13 Кодирование и типы высказываний
15:16 Противоречия, полнота и выводимость
19:21 Арифметика и теория множеств
26:47 Формальные системы с арифметикой
31:58 Логические пояснения
33:48 Высказывания и числа
43:25 Метаматематика и доказательства
53:58 План доказательства
57:01 Поясняем шаги!
1:09:13 Финальные выводы
#Гедель #логика #парадокс

[@mr.nobody5037]

Теперь не пошутить насчет того когда видео про Гёделя (

[@mechtar92]

У группы Tool тоже вышел новый альбом (

[@user-ix8kx1wb3w]

Жду дебатов Вассермана и Савватеева Один с помощью теоремы Гёделя доказывает, что бога нет, второй что есть

[@PanzerschrekCN]

Существование Бога - то самое противоречивое утверждение в рамках формальной системы, в которой рассуждают Вассерман и Савватеев.

[@xpenxpen5814]

Вас создали ваши родители. Родители боги и они существуют. Что тут доказывать то?

[@Stroporez]

У Вассермана ина это времени нет, он занят выполнением политического заказа Собянина.

[@xpenxpen5814]

Ваши создатели боги. Вас создали ваши родители. Ваши родители боги.

[@denozavr8121]

я: ОГО Даниил в начале ролика: ОГО

[@dmitryostapets3392]

Воу! Ого!

[@trupak85]

ЛОЛ. Я думал что все эти разговоры про видео о теореме Гёделя на протяжении многих многих месяцев это местный мем. А оно оказывается на самом деле есть.

[@stereoDoza]

Когда шутка зашла слишком далеко.

[@nikopst3592]

Оно вышло... Оно живое!

[@Yakimov_proguns]

Кто-то не захотел потерять 10000 рэ... 🙂

[@GhostRider5555555]

+Respect 10,000 Rubs

[@user-ml6xu7hq7n]

Ура это свершилось!

[@user-ub7sc8hu4f]

Вот что 10 тыщ животворящих делают!

[@mhacker84]

Это столько задонатили на ролик?

[@Incipit_Vita_Nova]

Наконец-то теорема Гёгеля.

[@yuriionov4786]

Щастье наступило?

[@Incipit_Vita_Nova]

@@yuriionov4786 Нет, вот ещё бы аллергия прошла... Тогда бы наступило.

[@archetypeteam2818]

Прекрасное пончо, прекрасный Даня и неможетбыть Гёдель))) наверняка столь же прекрасен) а то и поболее)))

[@luckabuse]

Лооол. Взятое ничто есть Бытие. {0} Но диалектики нет :-) А потом ещё ничто {0} и получили дурную бесконечность N. Которую сняли взяв как множество. То есть это упражнение он проделывает диалектически. А всё остальное нет, все его операции откуда берутся из воздуха? А потом удивляется парадоксам.

[@luckabuse]

@@user-oe4zt9ng4t это всё что вы смогли сказать.

[@mr.ki11myselF]

Буду теперь эту дату как второй день рождения отмечать)

[@vladimirpogrebnyak936]

Даниил, десять лайков! Рассказываете про математику, а слушаается как будто триллер)

[@anspoetic]

Добрый день. Возник такой вопрос: 1. Гедель конструирует формулу, которая является примером такой формулы, которая предъявляет неполноту арифметики (формула G). Данная формула саморекурсивна: сама утверждает о собственной недоказуемости. Такой формулой Гедель показал, что в математике возможны утверждения, которые будучи истинными, не могут быть доказаны (это и есть неполнота). 2. Вопрос: я предполагаю, что таким свойством (быть истинными но не доказуемыми) в рамках арифметики могут быть только саморекурсивные утверждения. Так ли это? И еще один момент: я не понимаю операции, когда конкретное натуральное число в один момент используется как код формулы, а в другой - как просто натуральное число. Смотрел лекцию Сосинского, но тоже как-то не понял этого хода: почему так можно делать, как определить, является ли данное натуральное число просто числом или же оно - номер геделевской формулы.

[@cyrillbears2266]

Неужели!? Ролик про Гёделя?! Это случилось!? На деле я в душе не инбу кто такой Гёдель и почему его теорема важнее, разоблачение Шевцова на 3 часа, но я так много про этот ролик слышал, что решил написать комментарий исключительно для продвижения канала.

[@user-wj5yc2md6r]

Спасибо, мы с подругой по переписке из другого города вместе смотрели это каждый у себя. После просмотра наш диалог заметно оживился!

[@elenakaspy8488]

Спасибо! Потрясающее видио. Необыкновенно поддерживает любопытство!

[@NewDeal1917]

Не за что, вам спасибо за внимание!

[@user-bp8vg9pr3z]

Сделай коммент по видео с закрепом с ошибкамии в видео. Так сразу понятно где и какие ошибки. А если нет всё равно пиши *Это комментарий, если ошибки есть - они будут здесь". Это очень полезная привычка.

[@dmitryostapets3392]

Там сейчас модно редактором на ютубе вырезать и вставить нужный фрагмент

[@user-bp8vg9pr3z]

@@dmitryostapets3392 этим мало кто занимается и там много ограничений. А в комменте можно что угодно написать и сразу видны ошибки или их отсутствие.

[@ulovil]

Спасибо, интересно.

[@dravendominos273]

Кайф, настало время посмотреть первое видео

[@reisedurchdiemathe]

Отличная подача материала! Но есть одно небольшое замечание: в 14:51 сказано, что теорема - это выводимая в рамках формальной системы истинная формула. Это не так. Во-первых, формальная система сама по себе ничего не умеет выводить. Для этого ей как минимум нужно исчисление предикатов и правило modus ponens. Во-вторых, если система аксиом противоречива, то в ней теоремой будет любая формула, в том числе тождественно ложная, поскольку из противоречия выводимо все что угодно. На самом деле, понятие истинности жестко привязано к модели. Одна и та же формула может быть как истинной, так и ложной в зависимости от ее интерпретации в модели (например, пятый постула Евклида на плоскости и в модели Клейна). Так что теорема - это просто формула, выводимая из заданного аксиоматического базиса. В связке с моделью верно следующее: если формула выводима, то она истинна в модели, интерпретирующей данную аксиоматику (теорема о корректности ИП). - Подробнее можно посмотреть ролик на канале Савватеева в моем исполнении: kzbin.info/www/bejne/gZnEip2IZ9h2e7s

[@NewDeal1917]

большое спасибо за ваши комментарии! я ни в коем случае не являюсь специалистом или даже продвинутым любителем в матлогике, так что не могу страховаться от некорректных утверждений. надеюсь в следующем году сделать небольшой плейлист по теории доказательств с прицелом на то, чтобы рассказать как можно удобно доказывать всякие штуки на языке Lean, облегчая себе процесс освоения базовых понятий. было бы очень круто по возможности с вами консультироваться и что-то уточнять.

[@reisedurchdiemathe]

@@NewDeal1917 можно пообщаться, почему бы и да. сайт и мыло я указывал в свойствах своего канала. но я тоже не оракул и на все вопросы ответить не смогу) оракулом в матлогике я бы назвал академика Беклемишева)

[@user-zh8dd6co2y]

Пожалуйста поправьте меня, если не вполне строго выражаюсь, но ведь исчисление предикатов это тоже формальная система? Немного занимался когда-то программированием на Прологе, что-то еще, оказывается, помню. Всплыло, когда просматривал видео.

[@reisedurchdiemathe]

@@user-zh8dd6co2y исчисление предикатов - это формальная система + аксиомы исчисления предикатов) просто формальная система - это по сути язык, т.е. набор базовых значков и правил построения выражений. без аксиом она не имеет истинностно-ложного смысла. регулярные выражения - тоже формальная система. а вот разговорный язык - нет, т.к. в нем нет детерминированных правил построения выражений (т.е. по произвольному набору букв машина не всегда может распознать, является ли этот набор правильно построенным словом языка)

[@user-zh8dd6co2y]

@@reisedurchdiemathe Спасибо за уточнение.

[@reisedurchdiemathe]

Да, и, кстати, 27:00 - в элементарной геометрии невозможно интерпретировать арифметику Пеано, т.к. единица и ноль не определимы в э.г. (иначе бы они сохранялись при автоморфизмах). Да и полнота геометрии на это также указывает.

[@NewDeal1917]

но ведь с аксиоматикой Гильберта это уже работает?

[@reisedurchdiemathe]

@@NewDeal1917 с Гильбертом все не очень здорово, т.к. он включил в свою систему аксиому из логики второго порядка (аксиома о полноте). Поэтому лучше брать аксиоматику Тарского. Но и без этого понятно, что раз геометрия полна, т арифметику в ней невозможно интерпретировать, иначе получим противоречие с первой т.Гёделя о неполноте. То же самое относится к теории вещественно замкнутых полей характеристики 0 (по сути матанализ, только без подмножеств - окрестностей и прочего). Вообще логика второго порядка - читай наличие переменных, пробегающих подмножества (или предикаты логики первого порядка), а это гораздо более сильные теории. Немного истории на эту тему я рассказывал в первом ролике про теорему Гудстейна на канале Савватеева.

[@NewDeal1917]

интересно, спасибо! постараюсь глянуть видео

[@user-yz3vx1ke6t]

Просто большое спасибо

[@alcedob.5850]

Я за каналом не слишком плотно слежу и это видео не ждал. Но как же я ему рад!

[@yuriionov4786]

Почему?

[@alcedob.5850]

@@yuriionov4786 тема непонятная, но очень интересная

[@PanzerschrekCN]

20:58 - тут уже я начал немного ехать, хотел было сказать, что единица - это Целковый, Чекушка...

[@vladimirostrouhiy4836]

23:55 Умножение производно от деления?

[@NewDeal1917]

должно быть "от сложения", спасибо!

[@MikhailGoncharov-tl4cr]

я прослушивал на максимальной скорости воспроизведения на 28 минуте чуть не умер. А там материал для размышлений великолепный, виртуозно поданный. Обязательно досмотрю до конца чуть позже

[@PanzerschrekCN]

22:48 не совсем понял, почему сложение - объединение непересекающихся множеств. А что, если множества пересекаются?

[@arabusov]

Число элементов объединения меньше или равно сумме чисел элементов объединяемых по отдельности

[@user-wq3ps3bv7l]

потому что там натуральное число определяется как счет единиц (элементов) от 0 до A и счет от 0 до B и этот процесс не дискретный тогда мы можем задать операцию сложения как счет от 0 до A+B и в этом смысле A и B не пересекаются как не пересекается 2 пальца и 4 пальца когда ты пытаешься посчитать их вместе то есть сложить

[@user-ml6xu7hq7n]

На третьи сутки я досмотрел до конца!

[@user-tr2nd7yx9y]

Это успех! Я уже 14 сутки смотрю, и еще до конца не добрался.

[@fedorfeoctisov2025]

Было сложно, но я законспектировал.

[@Legat89]

О-о-о! Свершилось!

[@whhll1478]

26:20 после этой фразы я и задумался, потому что это есть причина, по которой я смотрю это видео

[@iakoviaroslavich2185]

охерасе!

[@user-ud1xt7os2g]

👍👍👍👍👍👍👍

[@leot9969]

kzbin.info/www/bejne/bGrSpIWEna2cq5o Справа внизу не `n \/ {n}` должно быть?

[@PanzerschrekCN]

Жду больше второго ролика о последствиях теоремы Гёделя. Мне, как практику, это более интересно. И чую я, что последствия не сильно страшные и в большинстве случаев их можно игнорировать.

[@NewDeal1917]

для всяких расчётов и прочих вещей об этом можно даже не задумываться

[@user-vy4iy7xr9z]

Есть лекция Алексея Брониславовича Сосинского по данной теме, прочитанная им на летней мат.школе в Дубне в 2001г kzbin.info/www/bejne/ioS4fH99osZmY8U (про лектора см. википедию) Насчёт последствий : академик В.И. Арнольд мог бы и не согласиться… ;))

[@NewDeal1917]

у него ещё есть для Полит.ру выступление схожее

[@user-vy4iy7xr9z]

@@NewDeal1917 все же Сосинский - внук того самого Чернова и как бы ученик сестры академика Келдыша - это, однако… История! Хотя Ваш подход в части того, что Сосинский не уточнял - вполне его дополняет. Обозначения чуть отличны, но это мелочи.:)) Удачи.

[@dravendominos273]

1:06:53 - не интуитивно! Стулья должны быть подписаны как "полнота" и "непротиворечивость"!

[@PanzerschrekCN]

С операцией следующего элемента для множеств не понял. Как так выходит, что пустое множество объединяется с множеством множеств множеств и т. д. Это ведь разные типы.

[@NewDeal1917]

Мы просто добавляем в набор пустое множество как ещё один элемент, это аналог добавления единицы для натуральных чисел.

[@Berseny]

В принципе понятно, но я так и не осознал, откуда мы взяли, что утверждение G верно, но невыводимо средствами системы PA... Блин, надо будет еще раз пересмотреть. Товарищам огроменное спасибо за титаническую работу, ломающую мозг, как сухую тростинку. =)

[@NewDeal1917]

Потому что если мы допускаем, что G выводимо, то приходим к тому, что одновременно выводимо и его отрицание, а значит, система PA, в которой это возможно, является противоречивой.

[@Berseny]

@@NewDeal1917 Ну вот! Я же говорил, надо еще разик проштудировать. Это мы допускаем, а затем доказательство противоречивости. А я не уяснил, возможно мы доказали прежде возможность невыводимого G. Я отвлекся. =) Как говорил Дракс в "Стражах Галактики": -- Мы вас спасли! -- Мы уже договорились, что взорвать нас вместе с целым кораблем это не спасение! -- Я отвлёкся =)) (Люблю этот детский фильм) И вообще, может быть, это допущение надо доказывать? Ну ладно, вот посмотрю еще разик, может быть, прояснится в голове. =) Блин, в своем комменте запутался. =) Ну ок, исправил

[@Berseny]

@@NewDeal1917 Я просто один момент не догоняю, истинное утверждение, невыводимое для данной системы PA, является аксиоматичным для этой системы? Или просто так, вбоквел? =)

[@NewDeal1917]

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

[@Berseny]

@@NewDeal1917 Именно! Я и пытаюсь понять, что это за истинные утверждения такие, невыводимые в рамках самой системы. Мне это немного неочевидно. С доказательствами противоречивости и неполноты я вроде как разобрался. Благо, простые числа хорошо понимаю, я с ними в юности баловался, таблицы составлял. От нефиг делать... =) Короче, не буду докучать Вам глупыми комментами, а лучше пересмотрю видос. =)

[@eatmore6464]

Круть, больше часа

[@user-ob8xr3se6i]

Одно из тех видео, первый просмотр которого говорит о целесообразности второго просмотра.

[@user-ob8xr3se6i]

@@LasLexus ващет я имею в виду, что материал густ на информацию - где-то известную ранее, а где-то нужную для усвоения с первого просмотра идёт только закрепление и уточнение уже известного ) а со второго надо конспектировать

[@user-wq3ps3bv7l]

как эта буржуазная ересь стыкуется с диалектическим материализмом?

[@stereoDoza]

Эх, дружок. Ты даже не понял, что прямым.

[@Mulinby]

...под номером - кэ ))) 47:52

[@dravendominos273]

Аналогии с языками программирования - вещь. Реально, в миллиард раз проще понимать через опыт программирования. Спасибо! Небольшое критическое замечание: Пожалуйста, постарайтесь не делать утверждения, которые проиллюстрируете только потом, повторившись. Кажется, что что-то упустил по незнанию. Например, как на 20:05. В остальном - зачёт, надеюсь видео по математике ещё будут!

[@NewDeal1917]

спасибо! ближайшие видео, связанные с математикой, будут в плейлисте о производственной функции.

[@mojaghed]

@@NewDeal1917 ██ Нельзя ли для роликов с математикой сделать отдельный плейлист? Пусть там будет мало роликов, но это избавит от необходимости подбирать ключевые слова, чтоб хоть что-то найти. Или тут кроме 2 роликов про теорему Гёделя про математику так ничего и не вышло?

[@vitaliyrealkeks]

Не прошло и года!

[@fklopster]

По таймкодам так и не понял, где начинается сама теорема и постановка задачи? Где её формулировка?

[@NewDeal1917]

начиная с 54-й минуты, резюме формулировок с 1:09:24

[@ulovil]

До практических следствий из теоремы дело не дошло, так понимаю?

[@NewDeal1917]

пока слегка не до этого, но там не то чтобы есть практические следствия, если мы не интересуемся аспектами матлогики

[@user-uo3wb2mh9k]

Есть ли какой-то более-менее простой конкретный пример теоремы, которая верна но не может быть выведена?

[@NewDeal1917]

континуум-гипотеза

[@JohnSmith-pv7lx]

Теорема Гудстейна в арифметике Пеано.

[@user-uo3wb2mh9k]

@@NewDeal1917 ещё такой вопрос. Ты сказал, что как бы мы не достраивали формальную систему, в ней всегда будут невыводимые утверждения. Получается, что для любого невыводимого утверждения мы можем достроить формальную систему, в которой она станет выводимой?

[@NewDeal1917]

Думаю, это лучше спрашивать у господина Казимирова, который по соседству отписался, я настолько в предмете не разбираюсь и боюсь ляпнуть глупость

[@user-xl1ql1uj4n]

Что поел, что радио послушал.

[@consequenceable]

хардкорррррррр

[@PanzerschrekCN]

33:03, то ли ошибка, то ли неточность. A или B = не ( не А и не Б ).

[@NewDeal1917]

а в чём неточность? отрицание меняет конъюнкцию на дизъюнкцию и наоборот

[@PanzerschrekCN]

@@NewDeal1917 Нужно отрицание отрицания, как в формуле выше. Ну или на том месте имелась в виду эквивалентность формулы с одним отрицанием. Короче, не очень чётко вышло.

[@NewDeal1917]

ну я это просто проговорил словами, что мы отрицаем дизъюнкцию. мы сначала там подробные примеры с таблицами истинности вставляли, потом решили вырезать, чтобы не перегружать.

[@user-yt7zo3rf6d]

наверное все таки микрофона получше не хватает. а картинка хороша

[@user-wq3ps3bv7l]

предположу что 99% аудитории просело уже на определении изоморфизма, можно было взять хотя бы геометрическое определение или топологическое, или хотя бы из теории графов что является наиболее прозрачным, а так отсекать 99 человек из ста первым тейком, это как то работа ради работы, типо "я записываю видео для себя, по тому что мне это нравится"

[@NewDeal1917]

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

[@ViniTOO34]

Попадает ли логика предикатов под теорему Гёделя?

[@timothytiberius487]

Нет

[@ViniTOO34]

@@timothytiberius487 спасибо.

[@ViniTOO34]

@@timothytiberius487 но разве ЛПП не является формальной системой? Есть ли в ЛПП натуральные числа и арифметика?

[@timothytiberius487]

@@ViniTOO34, да, является, но она не содержит арифметику Пеано. Есть теорема согласно которой ЛП 1 порядка непротиворечива и полна. Теорема Гёделя касается тех формальных систем которые содержат арифметику Пеано.

[@NewDeal1917]

в том смысле, в котором "формальная система" определяется в видео, не является, т.к. не содержит никаких аксиом и правил вывода, это просто инструмент описания

[@user-if4vj8ol3r]

Перевёл свой QR-код в десятичную систему и получил число, соответствующее высказыванию: " Дата твоей..( подробности в профиле)🚩

[@MrMizzantrop]

Этого просто не может быть!

[@user-ml6xu7hq7n]

Но ведь не для всех высказываний истинность проверяется внешним контекстом. Есть ложные высказывания которые противоречат аксиомам. В чем я не прав?)

[@NewDeal1917]

Аксиомам мы истинностный статус присваиваем тоже спонтанно на основании внешнего контекста и своих соображений

[@shawarmastore2548]

Такое чувство будто я что-то понял и в тоже время ничего

[@nadezhdaposlednaya6526]

Йа мозг сломало ...

[@Stret173]

ГОМОМОРФНО, ОДНАКО!

[@user-lk9kj2ow5b]

33:36 тут опечатка. Автор говорит "дизъюнкция", а в формуле стоит знак конъюнкции. Автор, извинись или на тебя нисподвергнется гнев жителей Атырау, иншалла.

[@NewDeal1917]

верно! при этом, по-хорошему, должна даже строгая дизъюнкция быть, которая опять расписывается через конъюнкцию

[@Rimm1984]

у тебя тоже есть дятел сосед?