valjok
Удален
|
    
Каким же образом доказывается теорема Геделя о неполноте формальных систем? Идея доказательства заключается в том, чтобы построить пример формулы, которая была бы недоказуема и, вместе с тем, содержательно истинна. Таковой являлась бы формула, содержательный смысл которой заключается в том, что она утверждает свою собственную недоказуемость, т.е. невыводимость из аксиом рассматриваемой формальной системы.
Далее идёт построение этой формулы. Но мне кажется, что возникает противоречие: формула верна и ложна одновременно, значит - исчисление протеворечиво. Может быть просто математика "неправильная"? Прочтя вот это внешняя ссылка удалена , я так и не понял, может ли человек решить неразрешимую задачу?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 8 июля 2005 23:11 | IP
|
|
valjok
Удален
|
В догонку, вопрос по дискретке.
В отличае от арифметики, более простая аксиоматическая теория, логика предикатов - свободна от противоречий. То есть согласно теореме о полноте Гейгеля - она полна и непротивотечива. Читаю дальше, подходим к теории алгоритмов, "не найдётся алгоритма, который для произвольной формулы убеждался бы в её истинности или ложности", (с) Чёрч 1936 г. Но позвольте, в полной теории, можно доказать все истенные и ложные утверждения (замкнутые формулы)! Это связано как-то с тем, что исчисление предикатов первого порядка является неразрешимой элементарной теорией для матструктуры М в отличае от булевой алгебры? Совсем запутался.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 9 июля 2005 0:40 | IP
|
|
SCERB
Удален
|
Насколько я помню, теорема Геделя о неполноте говорит что формальная арифметика (система аксиом и правил вывода. индукция, кажется, допускается инфинитная, но точно помню, что не допускается трансфинитная) неполная теория, то есть, существуют формулы о которых формальная арифметика не может сказать, истинны они или ложны.
Насколько помню, если к правилам вывода добавить трансфинитную индукцию, то такая формальная система станет полной (это уже не теорема Геделя, а кого то из математиков, имя которого, увы, сейчас припомнить не могу).
Теорема Геделя показывает ограниченность применения аксиоматизаций в математике.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 9 июля 2005 15:22 | IP
|
|
Unnamed
Новичок
|
valjok
Далее идёт построение этой формулы. Но мне кажется, что возникает противоречие: формула верна и ложна одновременно, значит - исчисление протеворечиво.
Такого противоречия, вроде-то там нет. Но вот такой подход мне действительно не нравится. Мне кажется, что утверждения (высказывания (мы будем рассматривать только абсолютные)), замкнутые (рекурсивно) сами на себе – на собственной верности (верностью будем называть качество высказывания быть истинным или ложным), на самом деле существовать не могут – т.е. такие фразы – это никакие не высказывания вовсе. Допущение подобных высказываний, на мой взгляд, приводит примерно к таким же плачевным результатам, как допущение вольных обращений со множествами в наивной теории множеств.
Для того, чтобы опознать такое псевдовысказывание, полезно бывает раскрыть то, что я называю контекстом высказывания (который обычно кроется как бы в свёрнутом виде, а потому часто ускользает из виду в силу того, что не босается в глаза).
Рассмотрим примеры (некоторые из них есть в ссылке). Для равнозначных высказываний будем использовать знак “<=>”.
1) Высказывание A1: «Данное высказывание ложно» <=> «Высказывание A1 ложно» <=> (раскрываем контекст) «Является ложью высказывание о том, что A1» <=> (раскрываем A1) «Является ложью высказывание о том, что «Является ложью высказывание о том, что «...»»» (бесконечная рекурсия).
Как видно, данное псевдовысказывание лишено смысла, т.к. бесконечно ссылается на само себя. Хотя, на первый взгляд, может показаться, что оно является-таки нормальным высказыванием (если смотреть на неприведённое высказывание, где бессмысленность ещё неочевидна), только вот определить его истинность не представляется возможным: если оно истинно, то получается, что оно ложно, и наоборот.
2) Высказывание A2: «Я не верю в истинность этого высказывания» <=> «Я не верю в то, что A2» <=> (раскрываем A2) «Я не верю в то, что «Я не верю в то, что «...»»» (бесконечаная рекурсия).
Опять же налицо отсутствие осмысленности у A2. И в то же время, можно попробовать придать ему некий смысл. Тогда снова получится белиберда (что неудивительно, т.к. смысла у него всё-таки нет). Если я верю в истинность A2, то я верю, в то, что не верю в истинность A2. Если же я не верю в истинность A2, то A2, очевидно, истинно, т.е. я должен в A2 поверить. В приведённой ссылке упоминался какой-то бред о раздвоении «Я», но иначе как бредом я это назвать не могу (в целом материал мне понравился, к тому же я читал раньше «Тени разума» Пенроуза, но вот там, где автор пишет про субъекта (3-я страница почти целиком), – бред ещё тот – если интересно, могу в форуме «Свободное общение» высказать свою критику). Хотя бы потому, что я могу сформулировать подобные псевдовысказывания так, что никакие раздвоения и т.п. не помогут (например: «Никаким макаром я не верю в A2 – т.е. ни я сам и никакое моё «раздвоенное Я» не может поверить в A2!»).
3) Высказывание A3: «Никто и ничто не может достоверно установить истинность данного высказывания» <=> «Никто и ничто не может достоверно установить истинность того, что A3» <=> (раскрываем A3) «Никто и ничто не может достоверно установить истинность того, что «Никто и ничто не может достоверно установить истинность того, что «...»»» (бесконечная рекурсия).
Снова бессмыслица. А теперь представим, что смысл всё-таки есть (в очередной раз забудем про то, что мы вывели, и посмотрим на изначальную формулировку). Можно сказать, что истинность или ложность любого высказывания устанавливает Реальность. Но, помимо Реальности, есть также другие объекты (Реальность – это как бы некий фундаментальный объект, устанавливающий правильность всех высказываний), которые могут достоверно устанавливать верность какой-то группы высказываний. Данное высказывание утверждает, что ни Реальность, ни какой-либо другой устанавливающий правильность высказываний объект не сможет достоверно установить истинность этого высказывания.
Рассмотрим два случая:
1) если A3 истинно, то Реальность уже устанавливает, что A3 истинно, но само A3 это запрещает (поскольку запрещает установление истинности кем-либо и чем-либо);
2) если A3 ложно, то, согласно A3, кто-то или что-то обязательно должно достоверно установить его истинность, что невозможно, т.к. A3 всё-таки ложно.
В обоих случаях противоречие. А вот стоит нам только убрать из рассматриваемых объектов Реальность (полагать, что «никто и ничто» в A3 – это любой объект, отличный от Реальности), как первый случай уже проходит. И теперь все эти остальные (кроме Реальности) объекты можно на здоровье обзывать «дураками». А можно выкинуть ещё побольше объектов – дабы «дураков» и «знатоков» было столько, сколько нам нужно. Вот и будем мы рассматривать формулы, утверждающие собственную недоказуемость – в рамках той системы, которую мы намереваемся обозвать тупой, разумеется. Но не является ли допущение формул с подобным содержательным смыслом ошибочным?
(Сообщение отредактировал Unnamed 15 июля 2005 17:40)
|
Всего сообщений: 44 | Присоединился: март 2005 | Отправлено: 15 июля 2005 17:32 | IP
|
|
Guest
Новичок
|
Мда...
Почитал внешняя ссылка удалена
Выходит, что там в рамках данной формальной теории доказали недоказуемую формулу. Не бред ли это?
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 15 июля 2005 17:51 | IP
|
|
Indigo
Удален
|
Цитата: Guest написал 15 июля 2005 16:51
Не бред ли это?
Еще хуже! Это - философия... 
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 15 июля 2005 18:16 | IP
|
|
SCERB
Удален
|
Господа, при построении невыводимой в формальной арифметике (аксиомы и правила вывода) формулы Гедель использовал идею парадокса лжеца.
А именно:на Крите все жители лжецы. Критянин Вася говорит "я лжец". Так как Вася критянин, то он действительно лжец. Но так как он лжец и говорит, что он лжец, то получается, что он говорит правду.
Насколько мне известно, теорема Геделя принята многими математиками, в том числе и Давидом Гильбертом.
Это важная и интересная теорема, которую надо знать, понимать, но никак не паниковать, что в математике что-то нехорошо.
Если и выявятся противоречия, проколы, не переживайте, все будет хорошо, найдется кому латать дыры.
Свою силу и истинность математика подтверждает практикой.
Если бы расчеты были неверными, то компьютеры не работали бы, самолеты и космические корабли не летали бы, а балерины не танцевали бы на радость зрителям.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 16 июля 2005 16:00 | IP
|
|
SCERB
Удален
|
" Прочтя вот это внешняя ссылка удалена , я так и не понял, может ли человек решить неразрешимую задачу?"
Что значит неразрешимую задачу?
Для первоклассника квадратное уравнение неразрешимая задача.
Если же понимать под неразрешимой задачей, например, постулат Евклида о параллельных прямых, то нельзя.
Если Вы добавите в систему аксиом Евклида его 5-й постулат, то получите геометрию Евклида, если добавите аксиому о параллельных в форме Лобачевского (некоторое отрицание 5-го постулата Евклида), то получите геометрию Лобачевского (гиперболическую геометрию).
(Сообщение отредактировал SCERB 16 июля 2005 15:19)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 16 июля 2005 16:17 | IP
|
|
valjok
Удален
|
Рассмотрим примеры (некоторые из них есть в ссылке). Для равнозначных высказываний будем использовать знак “<=>”.
1) Высказывание A1: «Данное высказывание ложно» <=> «Высказывание A1 ложно» <=> (раскрываем контекст) «Является ложью высказывание о том, что A1» <=> (раскрываем A1) «Является ложью высказывание о том, что «Является ложью высказывание о том, что «...»»» (бесконечная рекурсия).
Как видно, данное псевдовысказывание лишено смысла, т.к. бесконечно ссылается на само себя. Хотя, на первый взгляд, может показаться, что оно является-таки нормальным высказыванием.
Всё так, только похоже, что без рекурсий в математике неьзя, например супремум:
По мнению Рассела, все парадоксы возникают из-за одной логической ошибки, названной им принципом порочного круга. Этот принцип можно сформулировать так: «Если для того, чтобы определить множество, необходимо использовать все множество, такое определение не имеет смысла». Пуанкаре предложил для этого специальный термин «непредикативное определение». Как бороться с непредикативными определениями, было непонятно. С одной стороны, такие определения могут приводить к парадоксам, но, с другой стороны, как переформулировать определения, чтобы они не были непредикативными?
В качестве непредикативного определения можно привести определение наименьшей верхней границы. Рассмотрим множество всех x, таких, что 3<x<5. Верхними границами называются числа, превосходящие все числа данного множества. Среди них существует наименьшая – это число 5. Таким образом, наименьшая верхняя граница определена через класс верхних границ, содержащий ее саму, но сформулировать его иначе не удавалось.
Взято с внешняя ссылка удалена
Цитата: Indigo написал 15 июля 2005 20:16
Цитата: Guest написал 15 июля 2005 16:51
Не бред ли это?
Еще хуже! Это - философия...
Доказывали-то математики, Гёдель /= Гегель. Хотелось бы пояснений на вторую часть вопроса о невозможности доказать тождественную истинность любой формулы исчисления предикатов, к философии он пока не имеет отношения. Почему Гёдель говорит - можно, Чёрч - нельзя?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 16 июля 2005 16:59 | IP
|
|
valjok
Удален
|
Но так как он лжец и говорит, что он лжец, то получается, что он говорит правду.
Значит, в действительности он лжёт и поэтому говорит не правду. Вот от непонимания и паника. Как можно при доказательстве играть на парадоксах? Уж очень хочется знать, лжёт он или нет на самом деле, каким экспериментом это можно проверить? Существование всемогущего бога можно опровергнуть таким парадоксом, а с Ивановым как быть, который и в самом деле может доказать, что доказать не может?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 16 июля 2005 17:15 | IP
|
|
|
Форум
теорема Геделя о неполноте
