Теорема Гёделя о неполноте

[iifat]

Sender в сообщении #1170822 писал(а):

А как мы узнаем, можно ли доказать данное утверждение в данной теории?

Ну мало ли. Например, помедитируем, да докажем. Или способом Гёделя — помнится, он доказал, что если мы докажем утверждение, то докажем и его отрицание (и наоборот).

ArshakA в сообщении #1170818 писал(а):

До каждого утверждения истинность которого мы хотим установить мы дойдём за конечное число шагов

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

[Sender]

iifat в сообщении #1170871 писал(а):

Ну мало ли. Например, помедитируем, да докажем. Или способом Гёделя — помнится, он доказал, что если мы докажем утверждение, то докажем и его отрицание (и наоборот).

Боюсь, этот метод может дать осечку на недоказуемых утверждениях.

[mihaild]

iifat в сообщении #1170871 писал(а):

бесконечное раздувание ничего не доказывает — предел последовательности теорий не определён.

Да ладно вам. У нас возрастающая последовательность теорий, предел естественно определить как объединение.
И если вместо выбора утверждений "как попало", их заранее вполне упорядочить и брать минимальное независимое - то получится ровно доказательство теоремы Линденбаума.
Проблема именно в том, как проверить доказуемость.

[iifat]

Sender в сообщении #1170881 писал(а):

этот метод может дать осечку

Может, разумеется. Но ведь нам предлагают не доказательство, а идею.

mihaild в сообщении #1170884 писал(а):

У нас возрастающая последовательность теорий

Ну, не факт. Если мы берём одно из недоказуемых аксиомой, меняется последовательность — что-то становится доказуемым, что-то вообще опровергаемым.

[mihaild]

iifat в сообщении #1170887 писал(а):

Может, разумеется. Но ведь нам предлагают не доказательство, а идею.

Для $PA$ множество доказуемых (и соответственно опровержимых) утверждений перечислимо, но не разрешимо. Т.е. алгоритма, который берет утверждение, и говорит, доказуемо ли оно - нет (но есть алгоритм, который берет утверждение, и если оно доказуемо, говорит что оно доказуемо, а если нет - то не отвечает).

iifat в сообщении #1170887 писал(а):

Ну, не факт. Если мы берём одно из недоказуемых аксиомой, меняется последовательность — что-то становится доказуемым, что-то вообще опровергаемым.

Ладно, давайте я напишу построже (хотя кажется сказанное ранее формализуется однозначно).
Мы берем и нумеруем все формулы нашей сигнатуры (будем считать ее не более чем счетной): $\varphi_1, \varphi_2, \ldots$. Строим последовательность теорий $T_i$.
$T_0$ - это наша начальная теория, считаем, что непротиворечивая.
$T_{i + 1} = T_i$, если в $T_i \vdash \varphi_1$ или $T_i \vdash \neq \varphi_i$, иначе $T_{i + 1} = T_i \cup \{\varphi_i\}$. В этом случае $T = \bigcup\limits_{i=0}^\infty T_i$ - полная непротиворечивая теория.

[ArshakA]

mihaild в сообщении #1170891 писал(а):

Мы берем и нумеруем все формулы нашей сигнатуры (будем считать ее не более чем счетной): $\varphi_1, \varphi_2, \ldots$. Строим последовательность теорий $T_i$.
$T_0$ - это наша начальная теория, считаем, что непротиворечивая.
$T_{i + 1} = T_i$, если в $T_i \vdash \varphi_1$ или $T_i \vdash \neq \varphi_i$, иначе $T_{i + 1} = T_i \cup \{\varphi_i\}$. В этом случае $T = \bigcup\limits_{i=0}^\infty T_i$ - полная непротиворечивая теория.

Спасибо) Я боялся накосячить в синтаксисе. Данная формализация совершенно согласуется с моими построениями. (Один момент:Теории это что множества аксиом?)

mihaild в сообщении #1170891 писал(а):

Мы берем и нумеруем все формулы нашей сигнатуры (будем считать ее не более чем счетной)

Почему будем считать, разве в формальных системах это не так?

[mihaild]

ArshakA в сообщении #1171024 писал(а):

момент:Теории это что множества аксиом?

Да, это определение теории.

ArshakA в сообщении #1171024 писал(а):

Почему будем считать, разве в формальных системах это не так?

Я не знаю, что понимается тут под "формальными системами". В, например, исчислении предикатов есть понятие сигнатуры. И никто не требует, чтобы она была конечной. Например, с помощью рассмотрения сигнатур произвольной мощности доказывается теорема о повышении мощности.

[knizhnik]

mihaild в сообщении #1170891 писал(а):

$T_{i + 1} = T_i$, если в $T_i \vdash \varphi_1$ или $T_i \vdash \neq \varphi_i$, иначе

Мое мнение здесь вряд ли что-то значит, но все же... Как вы осуществите проверку $T_i \vdash \varphi_i$ или $T_i \vdash \neg \varphi_i$ ? Некоторые арифметические проблемы до сих пор не решены.
Явно построить то, что вы предлагаете построить, невозможно. Даже неясно, как сделать первый шаг.

-- 22.11.2016, 17:07 --

Значит речь о полноте теории, которую нельзя ни предъявить, ни описать разумными средствами.

[ArshakA]

mihaild в сообщении #1171026 писал(а):

Да, это определение теории.

Спасибо)

mihaild в сообщении #1171026 писал(а):

Я не знаю, что понимается тут под "формальными системами".

https://ru.wikipedia.org/wiki/%D0%A4%D0 ... 0%BC%D0%B0

knizhnik в сообщении #1171029 писал(а):

Значит речь о полноте теории, которую нельзя ни предъявить, ни описать разумными средствами.

Мне кажется вы не правы
Это конечно ошибка:

ArshakA в сообщении #1170814 писал(а):

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

Именно из-за проблемы с выяснением доказуемости некоторого утверждения в рамках некоторой теории (о чём мне уже многократно заметили другие участника форума ). Но почему возможность эффективного построения рассматриваемой теории так необходима для её существования?

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

[Someone]

ArshakA в сообщении #1171048 писал(а):

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

Для существования — нет. А вот для теорем Гёделя — да.

[ArshakA]

Someone

(Оффтоп)

Имеет ли какой-то вес утверждение многократно упомянутое на разных страницах википедии? Можно ли вообще доверять ей в математических вопросах?

[Anton_Peplov]

(Про Википедию)

ArshakA в сообщении #1171100 писал(а):

Имеет ли какой-то вес утверждение многократно упомянутое на разных страницах википедии? Можно ли вообще доверять ей в математических вопросах?

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

[ArshakA]

(Оффтоп)

Anton_Peplov
Спасибо большое Куча противоречий исчезла разом

Anton_Peplov в сообщении #1171105 писал(а):

рекомендую начать с книги Клини. Математическая логика.

Я помню я читаю . Но пока не далеко ушёл, времени нет. ВУЗ . А сейчас и сессия скоро.
Пока не прочёл видимо ещё не раз буду обжигаться, но не думать не могу, извините

Someone в сообщении #1171053 писал(а):

ArshakA в сообщении #1171048 писал(а):

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

Для существования — нет. А вот для теорем Гёделя — да.

Больше вопросов нет