теоремы Гёделя о полноте и неполноте

[MaxOpSu]

Прошу, разъясните для меня, гумманитария, в чем суть и научная значимость этих теорий. Речь о теоремах Гёделя о полноте и, соответственно, неполноте.

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

Заранее спасибо)

[meduza]

Советую почитать "Гёдель. Эшер. Бах" Хофштадтера.

Если по-простому, то теорема Гёделя о неполноте говорит, что в любой теории есть аксиомы, недоказуемые в рамках этой теории. Это очевидно: любая теория в своем корне будет иметь одну или несколько аксиом.

[venco]

meduza в сообщении #246253 писал(а):

Советую почитать "Гёдель. Эшер. Бах" Хофштадтера.

Если по-простому, то теорема Гёделя о неполноте говорит, что в любой теории есть аксиомы, недоказуемые в рамках этой теории. Это очевидно: любая теория в своем корне будет иметь одну или несколько аксиом.

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

[rishelie]

Если уж быть более точным, то в любой аксиоматической теории, в которую можно погрузить арифметику, можно сформулировать утверждение, которое невозможно доказать средствами данной теории.

Только я вот не очень себе представляю, как можно гуманитарию это объяснить, да еще ссылаясь на профессиональные математические книги.
Ну, можете Коэна почитать, например. А вообще есть гугл.

[Xaositect]

Для любой эффективно аксиоматизируемой непротиворечивой теории, являющейся расширением арифметики Робинсона, существует недоказуемое в этой теории утверждение.

meduza в сообщении #246253 писал(а):

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

-Вот это бред.

А Хофштатера действительно можно почитать, достаточно понятно ИМХО.

[MaxOpSu]

Спасибо за подсказки. ГЭБ уже скачал и по всей видимости, это то, что нужно. Вот на такую конкретную помощь я и расчитывал, когда обращался к людям понимающим, а не к безымянному гуглу)

Что насчет текста? Существует ли текст самого Гёделя в котором он излагает существо своих теорем? Странно, если такого текста нет. Если кто-нибудь знает где его можно достать в инете - очень прошу - дайте ссылку. Пусть даже на языке оригинала.

И еще остался вопрос, связанный с научной значимостью этих теорем. Тут, правда, я чувствую, что должен немного раскрыть причины своего интереса в обсуждаемом предмете. Я студент, специальность философия, и в рамках курса философии науки мне выпала задача раскрыть, когда придет срок, перед аудиторией суть этих теорем. Естественно, в аудитории математиков не предполагается.

Все еще расчитываю на ваши разъяснения по своим вопросам. Если я обратился не по адресу, так и скажите)

[migmit]

Цитата:

Существует ли текст самого Гёделя в котором он излагает существо своих теорем?

Разумеется, существует текст Гёделя, в котором он излагает свои теоремы. Я несколько не врубаюсь в термин "существо".

Цитата:

Если кто-нибудь знает где его можно достать в инете - очень прошу - дайте ссылку. Пусть даже на языке оригинала.

Зачем вам? В классических областях математики оригинальные статьи, как правило, читать бессмысленно - они обычно написаны не вполне внятно. Лишь через некоторое время появляется удобная терминология, важное отделяется от шелухи, и пишутся легко читаемые работы. Вопрос "что же сказал основоположник" в математике абсолютно никакого значения не имеет.

Цитата:

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

Я притворюсь, что не заметил этого. Для многих математиков нет существа более ненавистного, нежели философ, специализирующийся в философии науки. Особенно для тех, у которых в памяти ещё живо получение высшего образования и/или сдача кандминимума.

[delphiec]

Мы учили две теоремы Геделя о неполноте:
Всё это относится к аппарату математической логики и к аскиоматическому методу, которые в том числе изучается программистами и математиками по мат.логике.

Теории первого порядка, для знакомых с мат.логикой легко объяснить, это исчисление предикатов с введёнными кванторами всеобщности и существования, функторами и т.д. Вообщем это "круче" чем исчисление высказываний. Или "новее" обычной бытовой логики, начиная с Аристотеля.

Первая теорема относится к теориям первого порядка, к которым можно отнести арифметику. В теории 1-го порядка существует такая истинная логическая формула F, что ни F, ни не(F) не являются выводимыми в этой теории.

Вторая гласит при тех же условиях, что истинную формулу F, которая утверждает непротиворечивость, нельзя вывести в нашей теории 1-го порядка (в т.ч. арифметика). Собственно это и есть "сущность".

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

Возможно это примерно, также как "где-то" нельзя самого себя вытащить за волосы, например из озера.

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

С открытием Геделя связана жизненная драмма, например для Гильберта. Подробнее можно ознакомиться в книге Констанс Рид "Гильберт", где всё описано "популярным" языком и жизненно.

[Xaositect]

MaxOpSu в сообщении #246278 писал(а):

Что насчет текста? Существует ли текст самого Гёделя в котором он излагает существо своих теорем? Странно, если такого текста нет. Если кто-нибудь знает где его можно достать в инете - очень прошу - дайте ссылку. Пусть даже на языке оригинала.

Перевод оригинала статьи о неполноте системы Principia Mathematica на английский: http://www.research.ibm.com/people/h/hi ... goedel.pdf

-- Чт сен 24, 2009 23:27:15 --

Насчет теоремы о полноте:
Теорема о полноте говорит, что если формула логически следует из теории (т.е. в любой модели теории это утверждение истинно), то эта формула доказуема в этой теории.

[Виктор Викторов]

Вот Вам хорошая лекция Сосинского по Вашей теме.
http://www.mathnet.ru/php/presentation. ... sentid=105
Хорошо бы ещё послушать лекции Успенского. Но сначала именно Сосинского.

[Профессор Снэйп]

rishelie в сообщении #246266 писал(а):

Если уж быть более точным, то в любой аксиоматической теории, в которую можно погрузить арифметику, можно сформулировать утверждение, которое невозможно доказать средствами данной теории.

Не в любой, а в любой перечислимой. Зато арифметику можно погружать слабую, без аксиомы (схемы аксиом) индукции

[rishelie]

Боюсь, наш филозофус не выдержит конкретики:)

[MaxOpSu]

Большое человеческое спасибо всем, кто постарался помочь мне и ссылками и подсказками. Вы мне очень помогли!


Особое и отдельное спасибо тем, кто высказал свое никому(кроме них самих любимых, конечно) не нужное мнение по вопросу, который никто не задавал. Например, насколько мне нужно то, что я просил. Повторяю: никто не спрашивал вашего драгоценного мнения.

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

Желаю здравствовать)

[filippovski]

1. Краткая история появления Первой и Второй теорем К.Гёделя о неполноте может быть вкратце изложена.
Первый раз на неразрешимые высказывания Гёдель указал уже в своей докторской диссертации, написанной им в 1929 г. под руководством Г.Гана и посвящённой доказательству полноты узкого исчисления предикатов. Формулировка и доказательства теорем появились летом 1930. Первый раз публичное изложение ограничительных результатов состоялось в Кёнигсберге осенью того же года на Второй конференции эпистемологии точных наук (5-7 сентября 1930). На этой конференции, --- в самый последний её день, --- состоялся круглый стол по основаниям математики, на котором присутствовали Д.Гильберт, Дж. фон Нейман, Р.Карнап, Фр. Вайсман и проч. Сюда же был приглашён Гёдель. В конце обсуждения Гёдель сделал краткое сообщение о своей первой теореме о неполноте. В Кёнигсберге у Гёделя ещё не было второй теоремы. Однако состоявшаяся в дальнейшем личная встреча с фон Нейманом подтолкнула Гёделя к открытию второй теоремы о неполноте. 23 октября 1930 Г.Ган представил результаты Гёделя на заседании Венской Академии Наук, после чего в венском журнале Anzeiger der Akademia der Wissenschaften in Wien, Mathematischnaturwissenschaftliche Klasse, № 19 за 1930 г. были опубликованы тезисы под заглавием "Некоторые метаматематические результаты о непротиворечивости и полноте".

Цитата:

Gödel K. Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit. In: Anzeiger der Akademia der Wissenschaften in Wien, Mathematischnaturwissenschaftliche Klasse, № 19, 1930. P. 214-215; English translation: Gödel K. Some metamathematical results on completeness and consistency. In: Frege and Gödel: Two Fundamental Texts in Mathematical Logic. Cambridge, Massachusetts, 1970. P. 86-87

Полный текст статьи Гёделя "О формально неразрешимых предложениях Principia Mathematica и родственных систем I"

Цитата:

Gödel K. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter System I. In: Monatshefte für Mathematik und Physik, 38. P. 173-198; English translation: Gödel K. On formally undecidable propositions of Principia Mathematica and related systems I. In: Frege and Gödel: Two Fundamental Texts in Mathematical Logic. Cambridge, Massachusetts, 1970. P. 87-108.

был представлен редактору лейпцигского журнала "Monatshefte für Mathematik und Physik" 17 ноября 1930. Статья была напечатана в 1931 г. на 173-198-й страницах 1-й тетради 38-го тома Monatshefte.

2. Подлинные формулировки теорем (в нумерации статьи (1931) Первая теорема имеет номер VI, а Вторая --- XI):

Первая теорема о неполноте. Для каждого ω-непротиворечивого рекурсивного класса формул k существуют рекурсивные знаки классов r, такие, что ни х Gen r, ни Neg(х Gen r) не принадлежит Flg(k) (где х суть свободная переменная r).

Вторая теорема о неполноте. Пусть k – любой рекурсивный непротиворечивый класс формул; тогда формула, утверждающая, что k является непротиворечивым классом, не является k-доказуемой; в частности, непротиворечивость системы P не является доказуемой в P, если P является непротиворечивой (в противоположном случае, конечно, каждое высказывание доказуемо [в P]).

3. Ссылка на оригинальную статью Гёделя (1931) в английском переводе:
http://books.google.ru/books?id=qW8x7sQ4JXgC&pg=PA4&dq=On+formally+undecidable+propositions&ei=qie9SrefLZ6KzASqtZnUDw#v=onepage&q=On%20formally%20undecidable%20propositions&f=false

4. Ссылка на мою статью о теоремах Гёделя (2009):
http://scipeople.ru/uploads/materials/4339/%D0%A4%D0%B8%D0%BB%D0%B8%D0%BF%D0%BF%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%9B%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9%20%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%20%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%20%D0%9A.%D0%93%D1%91%D0%B4%D0%B5%D0%BB%D1%8F%20%D0%BE%20%D0%BD%D0%B5%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B5.pdf

С уважением, Виталий Филипповский

[MaxOpSu]

Огромное спасибо, Виталий, и за ссылки, и за пояснения!