Обсуждение:Теоремы Гёделя о неполноте

Untitled

То есть континуум-гипотезу и аксиому выбора можно без нарушения непротиворечивости добавить даже к аксиоматикам, содержащим отрицания континуум-гипотезы и аксиомы выбора? Красота! :)

Нет, нельзя, поскольку в аксиоматике, содержащей отрицание континуум-гипотезы, ложность континуум-гипотезы доказывается элементарно. А речь шла о тех формулах, которые нельзя в данной конкретной аксиоматике ни доказать, ни опровергнуть.Termar 08:11, 14 сентября 2005 (UTC)

Не о математике тут должна идти речь, а о ZF - и то в предположении её изначальной непротиворечивости, каковая (в отличие от формальной арифметики) отнюдь пока не доказана!

Да и вообще не очень ясно, зачем к тексту об арифметической теореме приплетена континуум-гипотеза.

Гастрит

Поправил это утверждение в статье на корректное. halyavin 15:29, 8 сентября 2005 (UTC)

Увы, нет. Цитата: Примерами таких утверждений для теории множеств с аксиоматикой Цермело-Френкеля (ZF) могут служить континуум-гипотеза и аксиома выбора. Но ведь эта фраза автоматически означает, что ZF непротиворечива! Кто это доказал? Когда? Где?

И наконец: теорема Гёделя утверждает общий факт: в любом достаточно "жирном" непротиворечивом логическом исчислении найдётся замкнутая формула, невыводимая вместе со своим отрицанием. Почему же в качестве иллюстрации к этой теореме приводится ссылка на то, что в некотором конкретном исчислении невыводима (причём это ещё бабушка надвое сказала - непротиворечивость ZF не доказана!) конкретная формула?! Да добавить эту формулу к числу аксиом - и всего делов! С тем же успехом можно ссылаться на невыводимость пятого постулата в абсолютной геометрии (каковая была обнаружена задолго до теоремы Гёделя и уж точно не имеет к ней ни малейшего касательства).

Гастрит 11:25, 9 сентября 2005 (UTC)

Возможно я ошибаюсь, но непротиворечивость ZF не может быть доказана (да и на основе чего ее доказывать, на основе ZF?), а потому принимается как данное (иначе вообще нельзя ничего вывести).На счет того, имеют ли подобные примеры отношение к теореме Геделя — сложный вопрос. Может стоит создать отдельную статью "Не доказуемые утверждения" с подобными примерами? (кого-нибудь с каферды логики бы сюда...) halyavin 13:52, 9 сентября 2005 (UTC)

Простите, глубокоуважаемый представитель кафедры дискретной математики (не ошибся? ;)), но это нисколько не влияет на то обстоятельство, что в случае противоречивости ZF и континуум-гипотеза, и аксиома выбора, и вообще всё, что душе угодно, выводятся в ZF. Поэтому в утверждениях, аналогичных обсуждаемому, предположение о непротиворечивости ZF всегда следует специально оговаривать. Тем более, если текст пишется для неспециалистов - нечего устраивать фальшивый парад благополучия! Это раз.

Затем: уж Вам-то, насколько я понимаю, должно быть известно, что ZF - это самое обычное исчисление, не лучше и не хуже других, и вопрос о непротиворечивости ZF - это просто-напросто вопрос о том, выводится ли в оном исчислении некое конкретное слово (стандартное противоречие). Для рассмотрения этого вопроса никакая апелляция к теоретико-множественным представлениям не требуется (как, собственно, она не требуется в любом имеющем реальное содержание математическом вопросе). Кстати, утверждение, будто ZF (или NBG, или NF, или другая аналогичная чертовщина) есть основа всей математики - это вообще полная чушь: окажись любая из этих аксиоматик противоречивой, ЭВМ работать не перестанут, и $2\times 2$ не превратится в 5.

Теперь про отношение континуум-гипотезы к теореме Гёделя. Вероятно (если уж народ так желает упомянуть в связи с этой теоремой непришейкобылехвостную ZF), следовало бы сказать нечто в таком духе: "если ZF непротиворечива, то применительно к ней - а также к любому расширяющему её непротиворечивому исчислению - обязательно должны найтись формулы, невыводимые вместе со своими отрицаниями. В частности, для ZF таковыми (в случае предположения о непротиворечивости) являются континуум-гипотеза etc.". Гастрит 15:21, 9 сентября 2005 (UTC)

Вроде бы математику можно строить так: ZF(C) -> натуральные числа (в частности аксиоматика Пеано) -> понятие языка и исчисления (слово это множество букв, у предиката натуральное число аргументов). Поэтому цикл неизбежно получается. Другое дело, что можно начинать с разных мест (т.е. в качестве основы можно брать натуральные числа или понятие языка и исчисления) и если начинать с другого места, то непротиворечивость ZF может стать доказуемой. (могу все-таки ошибаться: дискра - не логика ;) )

Последняя фраза, действительно, корректнее. Без доказательства больше сказать не о чем ;). Или, действительно, лучше все такие примеры в отдельную статью вынести... halyavin 13:02, 11 сентября 2005 (UTC)

Непонимаю, что в математике, точной науке, в определении (!) значит "достаточно богатой". Сам вообще не разбираюсь в теме, так что поверьте - это "достаточно" сильно запутывает. См. английский вариант: "For any consistent formal theory that proves basic arithmetical truths..." — AL

А если применить оную теорему к ней самой? Не получится ли, что она пилит сук, на котором сидит? То есть, почему-то себя любимую применяемая логика считает абсолютно истинной, эдакий Господь Бог, отделяющей агнцев от козлищ! Быть может проблема не в теории, обвиняемой в неполноте, а в теории, выдвигающей таковое заключение? Проблема не в объекте измерения, а в инструменте измерения?

Эту теорму нельзя применить к ней самой, так как в ней идет речь о формальных теориях, а не о теорамах.

О новых аксиомах

Вот я как раз неспециалист, и о ZF ничего не знаю. Поэтому я приведу пример попроще.

Пусть есть теория первого порядка. Пусть, для определенности, это будет система с конечным числом аксиом и правилом замены (например, система Гильберта-Аккермана из книги "Основы теоретической логики"). Легко проверить, что формула X (т.е. пропозициональная буква X) в этой теории невыводима, как и ее отрицание. Однако, добавив эту формулу к числу аксиом, мы сразу получим противоречие (применив правило замены).

Наверное, не всякую невыводимую формулу можно добавлять к числу аксиом. Текущая же формулировка ("Например, такое утверждение можно добавить к системе аксиом, оставив её непротиворечивой") требует пересмотра.

Михаил Сабуров 16:09, 18 апреля 2008 (UTC)

Что за бред? Помоему с младших классов известно всем, что если принять что-то за истину, а потом получить противоречие, то значит что исходное предположение не верно, а значит оно опровергается в рамках исходной аксиоматики - метод доказательства от противного был известен ещё грекам. Если предположение действительно нельзя ни доказать, ни опровергнуть то оно никак не может испортить непротиворечивую теорию, а наоборот только усиляет её. 86.110.178.202 18:56, 29 сентября 2008 (UTC)Денис

Надо бы уточнить

Многие не знают, что собственно за доказательство у первой теоремы Гёделя о неполноте. Ход доказательства можно видеть, например, в популярной книжке Р. Пенроуза "Новый ум короля". Оно основано на нумерации формальных записей, в том числе записей, содержащих слово "доказывает" (такая-то запись доказывает то-то). Соответственно, оно дано для алгебры, допускающей высказывания о самой себе. Оно НЕ дано для формальной арифметики Пеано (см. en:Peano axioms#Consistency: «Gödel himself pointed out the possibility of giving a finitistic consistency proof of Peano arithmetic or stronger systems by using finitistic methods that are not formalizable in Peano arithmetic, and in 1958 Gödel published a method for proving the consistency of arithmetic using type theory.»). Оно НЕ дано для какой-либо формальной арифметики конечного порядка. Дано только для такой вот рекурсивной формальной арифметики. Например, у англичан есть вот такая формулировка: «Gödel's incompleteness theorems show that theories capable of expressing their own provability relation and of carrying out a diagonal argument are capable of proving their own consistency only if they are inconsistent.» (en:Consistency proof). Нам надо придумать свою похожую формулировку. Кстати, есть класс алгебр, доказывающих собственную полноту (en:Self-verifying theories). Alone Coder 17:38, 8 января 2009 (UTC)

Недавно, в 1997 г. (Зенкин А. А., ДАН, т. 356), опубликовано доказательство некорректности диагонального метода Кантора, на оснвоании которого доказывались теоремы Гёделя. Возникает потребность в переобосновании этих теорем.

И кто хотя бы из российских логиков признал это доказательсво некорректности?

Снесите эту ремарку, куда нибудь из основной статьи.

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

Рецензент?

я Чечулина сейчас посмотрел, как-то не очень аккуратно, он например запросто раскрывает скобки a={a}={{a}}, то есть одетая или голая девушка ему разницы нет. Или пишет у пустого множества есть свойство, что оно само себе принадлежит ф e ф. В общем не математика. Как и тут, "набросок доказательства" ёмаё. Если что не выводимо по-простому, то есть формула лежит отдельно от остальных, то к ней всё же можно добраться с помощью некоего "логического броска" :) Цирк да и только. NOwiking 03:54, 18 августа 2012 (UTC)

Слово "набросок" мне тоже кажется неудачным. Есть предложения? Например, я подумываю исправить на "схема доказательства". --Kuzmaka 10:09, 19 августа 2012 (UTC)

"достаточно богатой"

Что означает "достаточно богатой" или "достаточно сложной"?

В данном контексте это означает, что средствами формализма можно построить арифметику. DmitryGmyrak 10:59, 14 февраля 2012 (UTC)

Переписать

Первая теорема Гёделя (как, впрочем, скорее всего и вторая) говорит не про логику первого порядка, а вообще про любое исчесление, на которое наложены определённые ограничения. То есть не обязательно в этой логике факты записываются так: $\forall \,x\,\exists \,y\,\,x+y=0$. Они могут быть такие: $srhigner\forall sdgiorfg?jio.,!$. Safinaskar 04:46, 8 июня 2009 (UTC)

Статья неправильная и не надо устраивать войны правок

Господа, давайте не будем свои домыслы вписывать в Вики-статью! Создавайте свои сайты и там пишите всё, что вашей душе угодно. А в Вики-статью надо вписывать только то, что общепризнанно, даже, если вам это непонятно. Например, если вам лично непонятно, что означает "истинно" и одновременно "недоказуемо", то это не повод для того, чтобы править статью. Вот, например, цитата из книги Успенского "Теорема Гёделя о неполноте": при определённых условиях в языке существует недоказуемое истинное утверждения. Обратите внимание на слово "истинное" и на то, что автор является доктором физмат наук с 64-го года, учеником Колмогорова. Поэтому, очень большая просьба, если вы сами не являетесь таким же солидным учёным и при этом не понимаете данного предложения, то просто поверьте профессионалу! На этом я считаю, что предмет для войны правок исчерпан: правило об отсутствии оригинальных исследований в Вики весьма чёткое, а приведённая мною цитата так же весьма чёткая. Если есть желание разобраться, то можете обратиться к книге или к обсуждению, но статью оставьте такой, какой я её сейчас сделаю! Dims 08:34, 14 июля 2009 (UTC)

Хорошо, пусть это правильно. Может, тогда поясните это слово в тексте? А то статья от его употребления, мне кажется, становится менее понятной. --infovarius 19:09, 14 июля 2009 (UTC)

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

А простая возможность добавления новых аксиом в теорию (как это было представлено до моих правок) ничего особенного собой не представляет.

Допустим, мы рассматриваем людей. Бац -- добавили аксиому, что все являются женщинами -- и всё, просто сузили область рассмотрения и оставили в ней только женщин. То же самое относится к пятому постулату Евклида -- это просто новая аксиома, сужающая область рассмотрения. Теория с 5-м постулатом -- это геометрия плоского пространства, теория с постулатом Лобачевского -- это геометрия пространства постоянной отрицательной кривизны, а теория без пятого постулата -- это геометрия в пространстве произвольной кривизны. То есть, 5-й постулат просто сужает предмет рассмотрения до пространств с определённой кривизной. Иными словами, невозможность доказать 5-й постулат иллюстрирует совсем не то, о чём говорит теорема Гёделя.

Собственно говоря, мои правки очевидны даже из самой данной статьи. Смотрите: вторая теорема говорит, что примером невыводимого утверждения является утверждение о непротиворечивости данной теории. Но это же не значит, что непротиворечивость произвольна! Допустим, арифметика непротиворечива. По 2-й теореме это невыводимо. Но это же не значит, что мы можем произвольно добавить аксиому, что арифметика противоречива! Dims 08:41, 16 июля 2009 (UTC)

А почему "арифметика непротиворечива" - это истина? Может, это ложь, но так же недоказуемая? infovarius 21:48, 16 июля 2009 (UTC)

Может, и ложь, совершенно верно. В этом и заключается суть теорем о неполноте: вы не можете знать, противоречива ваша система, или нет, и вы точно знаете, что есть истины, которые ваша система не покрывает. То есть, эти теоремы обескураживающие, они говорят, что невыполнима одна из самых претенциозных задач Гилберта! Dims 12:34, 17 июля 2009 (UTC)

"Истины"! блин! Так у Вас истина=утверждение, а я-то грешным образом полагал, что истина=правда! infovarius 23:26, 17 июля 2009 (UTC)

Нет, "истина" -- это правда. А "утверждение" -- это формула, которая может быть истинной или ложной. Например, "Волга впадает в Чёрное море" -- это утверждение, ложное. Dims 08:16, 18 июля 2009 (UTC)

Тогда "арифметика непротиворечива" по-вашему не может быть добавлена к аксиомам, ибо это не истина, а недоказуемое утверждение. И вообще, недоказуемая истина - это плеоназм, противоречие, вот против чего я борюсь. Недоказуемым может быть только утверждение. infovarius 03:55, 19 июля 2009 (UTC)

Но в статье нет словосочетания "истина", там есть "истинная формула" и "истинное утверждение". Утверждение может быть: истинным+недоказуемым, истинным+доказуемым, ложным+недоказуемым, ложным+доказуемым (имеется в виду, конечно, доказуемость отрицания рассматриваемого утверждения), и, наконец, независимым. Dims 06:28, 19 июля 2009 (UTC)

Обсуждение на Астрофоруме: http://www.astronomy.ru/forum/index.php/topic,58629.0.html Dims 06:31, 19 июля 2009 (UTC)

сколько можно обсуждать НЕУДОВЛЕТВОРИТЕЛЬНУЮ (куцую) формулировку,

и делать из неё далеко идущие выводы?

83.167.112.63 19:32, 29 сентября 2009 (UTC)

"Вторая теорема Гёделя" vs "Second incompleteness theorem"

В примечании „В англоязычной математической литературе называется «второй теоремой Гёделя о неполноте» (англ. Gödel's second incompleteness theorem); в русскоязычной литературе называется просто «второй теоремой Гёделя»“ содержится неточность. Английское "incompleteness theorem" означает "теорема, имеющая отношение к неполноте", а русское "теорема о неполноте" означает "теорема, объектом которой является неполнота". Поэтому убираю примечание, вводящее путаницу. Подробности об иноязычных названиях можно узнать по интервики.--Kuzmaka 21:14, 5 января 2010 (UTC)

• Во-первых, как человек, проживший в англоязычных странах более 15 лет, говорю вам, что не вижу существенной разницы между фразами «теорема о неполноте» и "incompleteness theorem". Во-вторых, термин «вторая теорема Гёделя о неполноте» встречается в интернете и в научных работах, и хотя он не очень распространен, его имеет смысл упомянуть хотя бы в примечании. В-третьих, считать, что читатели обязаны читать интервики значит не уважать свой языковой раздел и своих читателей. В-четвертых, английский язык является основным языком международной науки в целом и логики в частности, поэтому упоминание английской терминологии (если она заметно отличается от русской) несомненно имеет смысл. В-пятых, не исключено, что без этого примечания упоминание о второй теореме какой-нибудь участник удалит либо из первого абзаца, либо вообще из статьи. По этим причинам отменяю вашу правку и возвращаю примечание. — Tetromino 22:11, 5 января 2010 (UTC)

Как минимум стоит убрать ваш перевод, противоречащий АИ. Оставляю примечание, но без перевода.--Kuzmaka 01:58, 6 января 2010 (UTC)

Каким АИ противоречит дословный перевод слов "incompleteness theorem" как «теорема о неполноте»? Я с вами согласен, что в АИ теорему называют второй теоремой Гёделя — но это только показывает, что устоявшимся русским термином является «вторая теорема Гёделя» и не имеет никакого отношения к точности перевода английского термина. Если бы перевод английского термина совпадал с термином в русскоязычных АИ, то обсуждаемое примечание изначально было бы ненужно. — Tetromino 03:09, 6 января 2010 (UTC)

„Дословный перевод слов "incompleteness theorem" как «теорема о неполноте»“. Это не так. Дословный перевод фраз incompleteness theorem и theorem about incompleteness не совпадает. Ср.: main theorem и theorem about the main (или theorem on the main), arithmetic theorem и theorem about arithmetic. Incompleteness theorem можно дословно перевести как теорема неполноты или неполнотная теорема, что по-русски выглядит неуклюже. Поэтому и нужны АИ, подтверждающие ваш вариант перевода.--Kuzmaka 10:13, 6 января 2010 (UTC)

Фраза "theorem about the main", ровно как и "theorem on the main", грамматически неправильна и не используется. Тот факт, что вы предложили как пример конструкцию "about N" где N никак не может быть noun phrase-ом заставляет меня усомниться в вашем понимании английского языка. Английские конструкции "N theorem" и "theorem on N" (где N — noun phrase, описывающее тему теоремы) значат одно и то же, переводятся одинаково и отличаются только тем, что "theorem on N" можно использовать как описание теоремы (а не только как название). Типичный пример: Dirichlet's approximation theorem = Dirichlet's theorem on Diophantine approximation. Перевод "N theorem" как "теорема о N" используется всюду. Немного примеров: en:Chinese remainder theorem = китайская теорема об остатках; en:edge-of-the-wedge theorem = теорема Боголюбова «об острие клина»; en:Brouwer fixed point theorem = Теорема Брауэра о неподвижной точке; en:Hilbert's basis theorem = Теорема Гильберта о базисе; Cauchy's mean value theorem = Теорема Коши о среднем значении; en:Lagrange's four-square theorem = Теорема Лагранжа о сумме четырёх квадратов. Продолжить? — Tetromino 15:20, 6 января 2010 (UTC)

Просто предоставьте надежный источник, где second incompleteness theorem переводится как вторая теорема о неполноте, и вопрос будет решен.--Kuzmaka 15:25, 6 января 2010 (UTC)

Например, чл.-корр. РАН Лев Дмитриевич Беклемишев в «Введении в математическую логику» называет «второй теоремой Гёделя о неполноте» именно ту теорему, которую англичане и американцы называют "second incompleteness theorem" и которую в русскоязычной литературе обычно называют второй теоремой Гёделя. По pdf-файлам Беклимешева учатся студенты МГУ. Источник достаточно надежный? — Tetromino 15:39, 6 января 2010 (UTC)

Хороший источник, но это всего лишь неопубликованный конспект лекций, а значит без внешней корректуры/рецензии. Нужно что-то более весомое.--Kuzmaka 16:05, 6 января 2010 (UTC)

У меня нет доступа к русскоязычной университетской библиотеке, поэтому могу только привести отрывки, которые нашел через books.google.ru. На четвертой странице результатов: Толковый словарь по вычислительным системам‎ - Page 205: «Вторая теорема о неполноте связана с программой Гильберта в области …» На пятой странице результатов: Доклады Академии наук СССР, Volume 262‎ - Page 799 (1982): «В силу второй теоремы Гёделя о неполноте каждое доказатель-». На шестой странице результатов: Известия Академии наук СССР, Volume 50‎ - Page 1140 (1986): «… строится при помощи второй теоремы Гёделя о неполноте арифметики …». — Tetromino 16:38, 6 января 2010 (UTC)

Поскольку нашлись русскоязычные, но не переводные, источники, которые упоминают "вторую теорему Гёделя о неполноте", предлагаю такую редакцию примечания, наиболее точно отражающую информацию, которую можно получить из АИ:

Иногда упоминается как вторая теорема Гёделя "о доказательствах непротиворечивости" (ссылка на источник), "о неполноте" (ссылка на источник), "о неполноте арифметики" (ссылка на источник).

Думаю, этого будет вполне достаточно.--Kuzmaka 12:03, 7 января 2010 (UTC)

Разумно. — Tetromino 14:31, 7 января 2010 (UTC)

Ещё раз про "истинность"

Существование просто недоказуемых формул НЕ ЯВЛЯЕТСЯ УТВЕРЖДЕНИЕМ теоремы Гёделя. Пример просто недоказуемой формулы -- это пятый постулат Евклида. Вы где-нибудь читали (в авторитетных источниках), что пятый постулат Евклида -- это пример неполноты геометрии? Нет. А знаете, почему? Потому что этот постулат НЕ ЯВЛЯЕТСЯ ТАКИМ ПРИМЕРОМ. СУТЬЮ теоремы Гёделя является существование в системе ОДНОВРЕМЕННО истинных и недоказуемых формул! Это очень важно! Есть формулы, которые истинные, но это нельзя установить за конечное время (только за бесконечное). Примером такой формулы может служить утверждение о НЕ существовании числа с какими-либо свойствами. Такое утверждение может быть истинным (числа нет), но проверить это может быть можно только перебрав весь бесконечный массив чисел. Dims 08:22, 24 апреля 2011 (UTC)

Существование просто недоказуемых формул НЕ ЯВЛЯЕТСЯ УТВЕРЖДЕНИЕМ теоремы Гёделя. А что является? Приведите формулировку теоремы из авторитетного источника, которая согласуется с Вашим утверждением. --Kuzmaka 09:23, 24 апреля 2011 (UTC)

Вот ссылка: https://docs.google.com/drawings/d/1_24Af1rvO-KGuZgBzmkGYsdRZUqTKSOr59dL7bV1Ooc/edit?hl=ru . Утверждением теоремы является наличие формулы, которая обладает двумя свойствам. Она (1) недоказуема и (2) истинна. Наличие просто недоказуемых утверждений является банальностью. Например, пятый постулат Евклида -- недоказуем. Но мы можем добавить в систему аксиом либо его, либо его отрицание, либо вообще его не добавлять. Получатся просто разные геометрии, только и всего. Более того, независимость, а, значит, и недоказуемость пятого постулата ДОКАЗАНА в 19 м веке. В то время как в теореме Гёделя говорится о том, что недоказуемость той формулы сама по себе тоже недоказуема! Dims 10:20, 24 апреля 2011 (UTC)

Мне затруднительно обнаружить формулировку теоремы по ссылке, которую Вы привели. Вы не могли бы дословно процитировать утверждение теоремы из источника? --Kuzmaka 11:14, 24 апреля 2011 (UTC)

Теорема записана математическими значками двумя страницами ранее. Если Вы пытаетесь представить, что там написано что-то другое, то я привожу ссылку и на этот отрывок: https://docs.google.com/drawings/d/1qzR9WsaV_bpqo6OMZd0oFumfexua1uTGOL6IcVeeQnE/edit?hl=ru. Утверждение про истинность обведено красным квадратиком. Dims 11:41, 24 апреля 2011 (UTC)

Да, действительно, в этом издании сформулировано так. Это отличается и от того, что писали Вы, поскольку содержит полностью утверждение о неразрешимости, и от того, что приводится в других изданиях (Мендельсон, более ранний Клини, собственно Гёдель). Почему Вы считаете необходимым ввести дополнительно упоминание об истинности? На мой взгляд, формулировка во введении от этого только потеряет ясность, станет перегруженной. --Kuzmaka 13:54, 24 апреля 2011 (UTC)

Упоминание об "истинности" - это совершенно необходимый элемент теоремы Гёделя, можно сказать, ее суть, и ни в коем случае не надо его исключать "для ясности". DmitryGmyrak 12:10, 14 февраля 2012 (UTC)

Приведите авторитетный источник, подтверждающий Ваше мнение. --Kuzmaka 12:25, 16 февраля 2012 (UTC)

Д.Гильберт П.Бернайс Основания математики. Теория доказательств. // Москва "Наука" 1982 стр. 341

Теорема. Для любого непротиворечивого дедуктивного формализма F, удовлетворяющего условиям а1) и б1), можно указать такую одноместную рекурсивную функцию f, что формула f(x) = 0 невыводима в F, хотя она и является верифицируемой, так что для каждой цифры n в F выводимо равенство: f(n)=0 Эту теорему, которую Гёдель получил указанным здесь способом, мы будем называть первой теоремой Гёделя о неполноте. В гёделевской формулировке фигурирует не сама эта теорема, а некоторое извлекаемое из нее следствие, которое говорит о существовании таких арифметических предложений, которые в рассматриваемом формализме F являются формально неразрешимыми. При этом под формально неразрешимым в F предложением понимается такое предложение, которое изображается в F некоторой формулой без свободных переменных, причем ни сама эта формула, ни ее отрицание невыводимы в F).

В.А. Успенский Теорема Гёделя о неполноте. (Популярные лекции по математике) // Москва "Наука" 1982 стр. 7 Формулировка теоремы о неполноте, которую мы будем уточнять и доказывать, такова: при определенных условиях в языке существует недоказуемое истинное утверждение. DmitryGmyrak 22:09, 16 февраля 2012 (UTC)

Существование неразрешимых формул не составляет еще утверждение теоремы Гёделя, но лишь является некоторым из нее следствием. Обыкновенная неразрешимость - для большинства формализмов это тривиальное свойство, тогда как теорема Гёделя утверждает нечто более сильное. Желательно вернуть правильную формулировку DmitryGmyrak 22:18, 16 февраля 2012 (UTC)

///Существование просто недоказуемых формул НЕ ЯВЛЯЕТСЯ УТВЕРЖДЕНИЕМ теоремы Гёделя. А что является?/// Является именно утверждение о существовании истинных недоказуемых формул. В терминологии Д.Гильберта - верифицируемых (см. выше)DmitryGmyrak 22:26, 16 февраля 2012 (UTC)

Текущая же формулировка:

существует невыводимая и неопровержимая формула.

вообще тривиальна до безобразия и не выражает даже того (более слабого) утверждения, которое пытается выразить. Например, формула x=1 в арифметике невыводима, также как и неопровержима. Чтобы формулировка имела содержательный смысл надо говорить о замкнутых формулах (без свободных переменных). Впрочем, эти технические уточнения будут излишни, если сразу привести полную формулировку, где речь идет об истинных формулах 12:51, 17 февраля 2012 (UTC)

В первой цитате (Гильберт, Бернайс) истинность не фигурирует. Одного Успенского мало против Гёделя, Мендельсона, того же приведённого Вами Гильберта и Бернайса.

С поправкой о замкнутости формулы согласен. Возможно, стоит заменить "формула" на "предложение" или уточнить каким-либо другим способом. --Kuzmaka 14:02, 22 февраля 2012 (UTC)

Уточнение: Из цитаты "верифицируемой, так что для каждой цифры n в F выводимо равенство: f(n)=0" следует, что верифицируемая не значит истинная, а значит, что выводима каждая формула из ряда f(1)=0, f(2)=0, .... --Kuzmaka 14:05, 22 февраля 2012 (UTC)

В терминологии Гильберта "верифицируемость" - это и есть истинность. Если для всякой цифры n выводимо f(n) - это и значит, что f(x) - истинно, при любом разумном понимании "истинности". Понятие истинности неформализуемо в полном объеме (что понимает Гильберт), но это не мешает делать некоторые о нем утверждения (как теорема Геделя). DmitryGmyrak 20:48, 29 февраля 2012 (UTC)

Позитивизм

Плашка «Позитивизм» выглядит не очень лепо в этой статье. С таким же успехом можно на каждую статью по математической логике её ставить. --Kuzmaka 10:46, 3 июля 2012 (UTC)

Применение к доказательству несуществования Бога в природе

А разве природа - формальная система? По моим представлениям, максимум, что мы можем сказать, что мы не можем помыслить существование Бога. 81.1.142.4 09:56, 8 ноября 2012 (UTC) Иван

Теорема Левенгейма — Сколема

Теорема Левенгейма — Сколема должна быть как-то очень сильно упомянута как здесь, так и в статье аксиома. Ибо:

Теорема Гёделя о неполноте свидетельствует о том, что любая система аксиом не позволяет доказать (или опровергнуть) все теоремы той области математики, для описания которой данная система аксиом предназначена. Теорема Левенгейма — Сколема утверждает, что любая система аксиом допускает намного больше существенно различных интерпретаций, чем предполагалось при ее создании. Аксиомы не устанавливают пределов для интерпретаций, или моделей. Следовательно, математическую реальность невозможно однозначно включить в аксиоматические системы.

Одна из причин появления «побочных» интерпретаций состоит в том, что в каждой аксиоматической системе имеются неопределяемые понятия. Ранее считалось, что аксиомы неявно «определяют» эти понятия. В действительности же одних аксиом недостаточно. Следовательно, неопределяемые понятия могут трансформироваться каким-то заранее непредсказуемым образом.

Теорема Левенгейма — Сколема не менее удивительна, чем теорема Гёделя о неполноте. Она нанесла еще один удар по аксиоматическому методу, который с начала XX в. и вплоть до недавнего времени считался единственно разумным подходом и который поныне используется логицистами, формалистами и представителями теоретико-множественного направления.

Теорему Левенгейма — Сколема, однако, нельзя считать полностью неожиданной. Действительно, теорема Гёделя о неполноте утверждает, что каждая аксиоматическая система неполна. Существуют неразрешимые утверждения. Пусть p — одно из таких утверждений. Ни p, ни его отрицание — утверждение «не p» — не вытекает из аксиом. Следовательно, мы могли бы исходить из более широкой системы аксиом, включив в нее либо исходную систему аксиом и p, либо исходную систему аксиом и «не p». Эти две системы аксиом существенно различны, поскольку их интерпретации не могут быть изоморфными. Иначе говоря, из неполноты следует некатегоричность. Но теорема Левенгейма — Сколема содержит гораздо более сильное и радикальное отрицание категоричности. Она утверждает, что и без введения какой-либо дополнительной аксиомы существуют принципиально различные (неизоморфные) интерпретации, или модели. Разумеется, аксиоматическая система непременно должна быть неполной, ибо в противном случае неизоморфные интерпретации были бы невозможны.Морис Клaйн "Математика. Утрата определенности." Глава XII "Бедствия"

--Nashev 15:10, 29 апреля 2013 (UTC)

• Ну тут можно к очень многим утверждениям прикопаться. "Любая система аксиом не может доказать все утверждения той области математики, для которой она предназначалась" — нет. Аксиомы исчисления высказываний доказывают любое утверждение теории булевых функций. Тут надо уточнять. "Теорема Лёвенгельма-Скулема докащывает, что есть больше интерпретаций, чем мы предполагали", а если мы изначально в счётной модели? Или тут имеется в виду теорема о повышении мощности? Ну и в конце совсем странная вещь, что если бы система была полной, то неизоморфные интерпретации были бы возможны. ... Возьмите классическое доказательство существования нестандартных моделей арифметики и примените его к любой полной непротиворичевой теории в арифметическом языке. Неожиданно увидите, что оно прекрасно работает и для полных теорий. В общем написано тут всё не очень хорошо, ощущение, что автор сам досконально не разбирался в предмете обсуждения. Ну либо это просто устаревший взгляд. Не считаю, что по этому источнику имеет смысл делать правки в статье. Arami Mira (обс.) 10:53, 20 апреля 2024 (UTC)

В статье по адресу https://snob.ru/profile/25137/blog/102090 приводится вот такое очень неплохое описание:

взял некоторую формальную систему математических постулатов (аксиом), и пронумеровал (каталогизировал) все-все-все следствия, которые можно сделать из нее логическим путем. А потом воспользовался «диагональным методом» и доказал, что какого-то утверждения (истинного, заметьте, утверждения!) в этом списке точно не будет. Его можно потом приписать к списку аксиом, опять выполнить всю работу... но опять что-то окажется упущенным. И так до бесконечности

--Nashev 21:43, 13 декабря 2015 (UTC)

Теорема Гёделя о неполноте в формальной логике

Было бы интересно коснуться теоремы Гёделя в ракурсе формальной логики. Поскольку с точки зрения логики теорема Гёделя обладает спорным условием. Если в системе S (претендующей на полноту) не доказывается (не выводится) ложная формула - эту систему нельзя называть неполной. Гёдель иллюстрирует свою теорему на примере натуральных чисел в арифметике и показывает ряд натуральных чисел, для которых выполнимо "А(0), А(1), А(2), … A(N)". С логической точки зрения возникает вопрос: как в системе S может быть выполнима формула "∃x ¬A(x)", если выполним весь ряд формул "А(0), А(1), А(2), … A(N)"? Иными словами, если условие А свойственно всем натуральным числам без исключения, откуда вообще появляется некое "¬A(x)"? При условии выполнимости "А(0), А(1), А(2), … A(N)" формула "∃x ¬A(x)" представляет собой пустое множество, или другими словами, формулу, для которой не существует модели.

Гёдель был не только великим математиком, но и, вероятно, очень остроумным человеком. В логике широко известно его правило модальной логики "A→□A", которое можно прочесть так: "Если имеет место событие "А", но оно имеет место по необходимости". Учитывая, что в модальной логике существует правило первого рода (прямое правило) "□A→A" ("Если событие "А" имеет место по необходимости, но оно имеет место и без необходимости"), Гёдель своим правилом поставил под сомнение целесообразность (как практическую, так и теоретическую) использования знака необходимости "□" вообще. Дым222 (обс.) 13:21, 8 апреля 2018 (UTC)

• Если под "выполнимостью" подразумевать выполнимость в стандартной модели, то такого быть действительно не может. Но теорема Гёделя говорит, что даже если формула "∃x ¬A(x)" невыполнима , все равно не существует доказательства того, что "¬∃x ¬A(x)".
  Модальные логики бывают разными, вы видимо имеете в виду en:Provability logic. Там правило "A→□A", говорит, что если А выводимо, то выводимо и "□A". Из этого действительно следует, что A выводима тогда и только тогда, когда "□A" выводима. Но это не значит, что это то же самое. Вы не можете доказать импликацию "A => □A".
  — Алексей Копылов 17:19, 8 апреля 2018 (UTC)

Спасибо! Теперь многое стало ясно. А почему нельзя доказать импликацию "A⊃□A"? 1. + A 2. □A из 1 по правилу Гёделя 3. A⊃□A из 1 и 2 по правилу дедукции. Извините меня за назойливость и непрофессионализм (я не математик, и теорема Гёделя меня интересует только касательно формальной логики). Разве исчисления в логики предикатов не позволяют доказать невыводимость "∃x¬A(x)"? Означает ли это что логика предикатов как система полна? Дым222 (обс.) 20:06, 8 апреля 2018 (UTC)

• Правило о дедукции не выполняется для логики доказательств (:en:Provability logic). — Алексей Копылов 20:18, 8 апреля 2018 (UTC)

Исчисление высказываний является непротиворечивой, полной, разрешимой теорией (Википедия, . https://ru.wikipedia.org/wiki/Формальная_система) Теоре́ма Гёделя о полноте́ исчисле́ния предика́тов является одной из фундаментальных теорем математической логики: она устанавливает однозначную связь между логической истинностью высказывания и его выводимостью в логике первого порядка. (https://ru.wikipedia.org/wiki/Теорема_Гёделя_о_полноте) Дым222 (обс.) 12:16, 9 апреля 2018 (UTC)