Franzn then moves on to discuss various attempts to apply Gdel’s theorem outside mathematics.
It has been claimed that the incompleteness theorem demonstrates the incompleteness of the
Bible, the U.S. Constitution, and Ayn Rand’s philosophy of objectivism. He points out that such
suggestions ignore the essential condition that the system must be capable of formalizing a certain
amount of arithmetic. None of thementioned “systems” have anything to do with arithmetic. Even
worse, they are nothing like a formal system: they do not have an exactly specified formal language,
a set of axioms, or rules of inference. Therefore, Gdel’s theorem simply is not applicable in such
contexts.
Тут некая банальность. Естественно not applicable.
Ну да, он, вроде, и говорит в том смысле что нельзя теорему Гёделя применять ко всему на свете. Т.е., теория должна быть строго формализована, содержать в себе формальную арифметику, и т.д. Есть же, например, известная теорема Тарского о разрешимости формальной геометрии, так что не обязательно всякая сложная теория должна быть не полной.
Тут еще есть такой моментик, что (imho) целью математики (да, наверное, и других наук) не является проверка истинности/ложности всех возможных утверждений. А является ею выяснение истинности/ложности всех интересных утверждений
А построить высказывание Гёделя, которое было бы еще и интересным, не так-то просто. Вроде, у Пенроуза (Новый ум короля) где-то в начале таковое приведено (там что-то про какие-то очень быстро растущие последовательности), но и то там все делается какой-то трансфинитной индукцией что-ли...
Спасибо за наводку. Почитал про Тарского с удовольствием. Кстати, детишек своих он назвал Ина и Ян. Видимо, под влиянием восточной философии.
Теорема Тарского о невыразимости истины
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Теорема Тарского о невыразимости истины - теорема, доказанная Альфредом Тарским в 1936 году, важный ограничивающий результат в математической логике, основаниях математики и формальной семантике. Теорема гласит, что понятие арифметической истины не может быть выражено средствами арифметики. Теорема Тарского применима к любой достаточно сильной формальной системе.
Доказательство теоремы Тарского опирается на гёделевскую нумерацию.
Вот интересно, формальная геометрия не попадает под определение достаточно сильной формальной системы, или здесь что-то другое?
Вот интересно, формальная геометрия не попадает под определение достаточно сильной формальной системы, или здесь что-то другое?
Не подпадает, потому что она не содержит формальную арифметику.
Я этот пример привел в том смысле, что кроме общего негативного результата (обе теоремы Гёделя), есть еще и позитивные результаты о разрешимых теориях. Еще есть теорема того же Гёделя о полноте исчисления предикатов. Может, еще есть какие-нибудь хорошие примеры (не помню уже, я последний курс по матлогике слушал 15 лет назад...
Не подпадает, потому что она не содержит формальную арифметику.
Было бы очень интересно понять откуда берётся, в чем точно состоит источник неполноты арифметики? Известно например, что аддитивния арифметика Прессбургера (без операции умножения *, лишь со сложением +) полна, неужели случайность распределения простых чисел надавила на качели?
построить высказывание Гёделя, которое было бы еще и интересным, не так-то просто.
Есть уже несколько таковых, комбинаторного характера; первое из них получено Парисом-Харрингтоном, о недоказуемости в арифметике Пеано т.н. обобщённой теоремы Рамсея.
Есть уже несколько таковых, комбинаторного характера; первое из них получено Пэрисом-Хэрингтоном, о недоказуемости в арифметике Пеано т.н. обобщённой теоремы Рамсея.
ну да, но в более сильных теориях (в данном случае, насколько я понимаю, в арифметике второго порядка, en.wikipedia.org/wiki/Second-order_arithmetic) это можно доказать. Конечно, и там имеются Гёделевы высказывания, и может даже интересные, но это уже такие дебри, в которые вряд ли кому-нибудь (кроме матёрых матлогиков) особо интересно лазить...
Ну, честно говоря, про теорему Тарского о невыразимости истины я мало что сказать могу
Вот теорему Тарского о разрешимости формальной геометрии пришлось учить к экзамену, но давно это было...
Впрочем, если там говорится об арифметической истине, то, видимо, имеется в виду что эта достаточно сильная формальная система должна включать в себя арифметику?..
Крыс написал(а):
Вот интересно, формальная геометрия не попадает под определение достаточно сильной формальной системы, или здесь что-то другое?
Не подпадает, потому что она не содержит формальную арифметику.
Я этот пример привел в том смысле, что кроме общего негативного результата (обе теоремы Гёделя), есть еще и позитивные результаты о разрешимых теориях. Еще есть теорема того же Гёделя о полноте исчисления предикатов. Может, еще есть какие-нибудь хорошие примеры
Грубо говоря, теория K является достаточно сильной, если понятия натурального числа, 0, 1, сложения и умножения можно определить в K таким образом, чтобы аксиомы формальной арифметики оказывались выводимыми в K
Там же очень интересный пример ( я раньше не знал
)
После того, как Юрий Матиясевич доказал диофантовость любого эффективно перечислимого множества, и были найдены примеры универсальных диофантовых уравнений, появилась возможность сформулировать теорему о неполноте в полиномиальной (или диофантовой) форме[7][8][9]:
Для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение
( + 2z b5)2 + (u + t l)2 + (y + m e)2 + (n q16)2 +
((g + eq3 + lq5 + (2(e z)(1 + g)4 + b5 + b5q4)q4)(n2 n) +
(q3 bl + l + q3 + (b5 2)q5)(n2 1) r)2 +
(p 2ws2r2n2)2 + (p2k2 k2 + 1 2)2 +
(4(c ksn2)2 + k2)2 + (r + 1 + hp h k)2 +
(a (wn2 + 1)rsn2)2 + (2r + 1 + c)2 +
(bw + ca 2c + 4 5 d)2 +
((a2 1)c2 + 1 d2)2 + ((a2 1)i2c4 + 1 f2)2 +
(((a + f2(d2 a))2 1)(2r + 1 + jc)2 + 1 (d + of)2)2 +
(((z + u + y)2 + u)2 + y K)2 = 0
не имеет решений в неотрицательных целых числах, но этот факт не может быть доказан в теории T. Более того, для каждой непротиворечивой теории множество значений параметра K, обладающих таким свойством, бесконечно и алгоритмически неперечислимо.
Грубо говоря, теория K является достаточно сильной, если понятия натурального числа, 0, 1, сложения и умножения можно определить в K таким образом, чтобы аксиомы формальной арифметики оказывались выводимыми в K
Ага! Все-таки арифметическое присутствие в теории содержится во фразе достаточно сильной.
М-да. Специалист - это, как минимум, владение терминологией. Особенно это заметно на ветке про волновой геном.
Не зря открыл я эту тему, пора углубиться в более нетривиальные аспекты теоремы Гёделя
То, что нельзя конечным образом аксиоматизировать арифметику (Гёдель) само по себе удивительно. Вроде читал, что есть и другие математические области/структуры, которым конечное число аксиом не хвататет, хотя не знаю о таких конкретно. Не думаю, что, скажем, теория множетсв останется неполной, если выключить арифметику
. Григорий вроде объяснял мне почему арифметика содержится в теории множеств, но я остался неуверенным. Почем теории множеств арифметика, неужели объединение и Декартово произведение дизъюнктных (непересекающихся) множеств достаточно, дабы заполучить арифметику сложения с умножением? А где дистрибутивный закон (а+b)c = ac + bc?
Во всяком случае я не знаю про другую теорию, кроме арифметики, где можно построить по желанию недоказуемые утверждения со смыслом Я недоказуемо типа Гёделя. Удивительно, что истинность или очевидность Гёделевых предложений не вызывает сомнений, а их отрицания, в отличие, выглядят абсурдными, неверными, несмотря на одинаковую непротиворечивость. Совсем по другому обстоят дела в теории множеств, где истинность недоказуемой континуум-гипотезы далеко не очевидна и приходится наравне рассматривать версии с её отрицанием. Думаю, что несчётность тут играет роковую роль и, как следствие, интуиция истины перестаёт быть гидом. Никто не сомневается, что в пределах счётых натуральных чисел гипотезы Римана или Голдьбаха (любое четное больше 2 есть сумма двух простых), или простых-близнецов должны имеют однозначное (хоть пока и неизвестное нам) решение если не в арифметике первого порядка (могут оказаться недоказуемыми по Гёделю), то в теории вещественных чисел, теории множеств и т.д.
Во всяком случае я не знаю про другую теорию, кроме арифметики, где можно построить по желанию недоказуемые утверждения со смыслом Я недоказуемо типа Гёделя.
Теория без арифметики будет видимо теорией без всяких метрик, а значит теорией нефизичной.
Мне так представляется.
На всякий случай даю ссылку на недавнее популярное (и углубленное одновременно) изложение и обсуждение теоремы Геделя в ЖЖ (на текущий момент из 6 глав): fregimus.livejournal.com/tag/aiГедель
На всякий случай даю ссылку на недавнее популярное (и углубленное одновременно) изложение и обсуждение теоремы Геделя в ЖЖ (на текущий момент из 6 глав): Гедель
Интересно, что даже теория действительных чисел не попадает под понятие фундаментальной арифметики, хотя натуральные числа и являются подмножеством действительных. В теории действительных чисел нельзя говорить о натуральных — внутри теории они никак не выделяются, «ничем не отличаются» от других, нецелых чисел. Поэтому даже такой «близкой» теоретической системе, как действительная математика, теорема Геделя не запрещает быть одновременно полной и непротиворечивой. Она и в самом деле одновременно и полна, и непротиворечива.
А вот о более «сложных» теориях ТГНП как раз не утверждают ничего! Уравнения физики, в частности, опираются не на арифметику, а на вещественные и комплексные числа, к основополагающим теориям которых ТГНП неприменимы в принципе.
Меня удивила данная концепция. Я не задумывался об этом.
Текст аксиом Пеано, как он приведен в оригинальном издании Пеано.
«1 есть натуральное число»;
«следующее за натуральным числом есть натуральное число»;
«1 не следует ни за каким натуральным числом»;
«всякое натуральное число следует только за одним натуральным числом»;
Аксиома полной индукции.
а значит вроде бы неприменима к действительным числам.
Надо будет подумать о действительных числах
Играет ли роль несчетность?
Однако с физической точки зрения это не должно иметь значения
Теория без арифметики будет видимо теорией без всяких метрик, а значит теорией нефизичной.
Я скорее неправ насчёт ненадобности арифметики в теории множеств
. Припомнил, что в своё время читал статью корифея Saharon Shelah-а об арифметике мощностей множеств и как получить всё бОльшие мощности. Вряд ли Шелах мог обойтись без элементарной арифметики конечных множеств (натуральных чисел). В конце концов арифметики мощностей не хватает, дабы подниматься все выше и выше по лестнице и тащим в поддержку аксиомы т.н. больших кардиналов.
Если учитывать то, что множество натуральных чисел равномощно множеству рациональных, то вообще следует ожидать справедливости теоремы Геделя для них, хотя я вот так и не могу найти солидного источника, доказывающего это
И кто-то должен был бы заниматься это проблемой для действительных чисел....
Ну что за страсть говорить о том, чего не понимаешь и о чём ничего не знаешь?! Ну что означает вот это: следует ожидать справедливости теоремы Гёделя для рациональных чисел? И о какой проблеме для действительных чисел идёт речь?
Вместо того, чтобы отправляться от реальной проблемы или предметной области - люди(в данном случае Владимирович, некоторые товарищи - например РАР - ничем другим ине занимаются) исходят из слов, смысла которых они не знают, и начинают мыслить
Или, что означает вот этот бред: Интересно, что даже теория действительных чисел не попадает под понятие фундаментальной арифметики, хотя натуральные числа и являются подмножеством действительных. В теории действительных чисел нельзя говорить о натуральных — внутри теории они никак не выделяются, «ничем не отличаются» от других, нецелых чисел. Поэтому даже такой «близкой» теоретической системе, как действительная математика, теорема Геделя не запрещает быть одновременно полной и непротиворечивой. Она и в самом деле одновременно и полна, и непротиворечива.
А вот о более «сложных» теориях ТГНП как раз не утверждают ничего! Уравнения физики, в частности, опираются не на арифметику, а на вещественные и комплексные числа, к основополагающим теориям которых ТГНП неприменимы в принципе.
Ведь это в полном смысле слова бессмысленный набор слов. Нет, этот бред цитируется, обсуждается ... Нет слов кроме матерных.
Ну что означает вот это: следует ожидать справедливости теоремы Гёделя для рациональных чисел? И о какой проблеме для действительных чисел идёт речь?
Григорий, насколько мне известно, теорема Геделя доказана для определенного класса формальных систем, включающих аксиоматику натуральных чисел.
Эта аксиоматика неприменима к действительным числам.
Например неприменима аксиома Пеано «1 не следует ни за каким натуральным числом»;
Отсюда я поинтересовался, существенен ли данный факт для справедливости теоремы Геделя для формальной системы типа аксиом поля действительных чисел. Звиняйте, если чего забыл в формулировку добавить.
Да это понятно. Непонятно другое - что Вам непонятно - ведь ясно, что натуральные числа - подмножество действительных(хотя этому идиоту, которого вы цитируете, это почему-то неясно), т е теория действитетельных чисел включает арифметику, и следовательно, теорема Гёделя утверждает, что в ней также есть утверждения, которые и их отрицание - недоказуемы - в частности тот же Гёделевский пример. Есть и более интересные - например, гипотеза континуума.
По существу же и у Вас и у того товарища в голове безнадёжная путаница по данному вопросу. Вы путаете формальную теорию - т е, идеально говоря, всё множество выводимых из аксиом теории следствий с реальной - т е комплексом проблем, задач, обьектов, которыми теория интересуется. Т е теория чисел не есть часть теории действительных чисел , ТФДП или ТФКП - те интересуются другими задачами и обьектами - но формально свойства целых или алгебраичеких чисел вполне себе часть тех теорий.
Да это понятно. Непонятно другое - что Вам непонятно - ведь ясно, что натуральные числа - подмножество действительных(хотя этому идиоту, которого вы цитируете, это почему-то неясно), т е теория действитетельных чисел включает арифметику, и следовательно, теорема Гёделя утверждает, что в ней также есть утверждения, которые и их отрицание - недоказуемы - в частности тот же Гёделевский пример.
Видите ли, Григорий, я указал выше, что я не задумывался над этим. И концепция, кою Вы соизволили бредом обругать, меня также удивила. Но, не имея в себе такого количества знаний, коими владеете Вы, я постеснялся дать свое категорическое осуждение этого
Сомнение же мое вызвал тот факт, что некоторые теоремы справедливые для множества натуральных чисел, перестают быть таковыми, ежели речь заходит о множестве чисел действительных. Например теория диофантовых уравнений принципиальна только для чисел натуральных. Нет?
Именно поэтому я и засомневался, строго ли распространять конкретную теорему на систему, в которой отсутствует по крайней мере одна аксиома натуральных чисел.
Поймите же, всё что Вы говорите - просто бессмысленно. Теория диофантовых уравнений вполне имеет себе смысл в рамках теории действительных чисел - просто теория действительных чисел интересуется другими вопросами. Точно так же как деятели, собравсшиеся на давосский форум нисколько не интересуются вопросом, какова будет Ваша или моя пенсия - но этот вопрос осмыслен и даже очень интересен для Вас(о Вашей) или меня(моей). Тчно так же натуральные числа и все их свойства вполне себе включаются в аксиоматику действительных - но теория действительных чисел интересуется другими задачами.