Лемма Линденбаума и неполнота арифметики

[valdemir]

Здравствуйте, Коллеги!

Помогите понять, за счёт чего вместе могут существовать следующие утверждения. (Формулировки взяты из Мендельсон "Введение в мат логику")

1) Если теория К первого порядка непротиворечива, то существует непротиворечивое полное её расширение. (стр.73, лемма Линденбаума)
2) Формальная арифметика (система аксиом S1-S9, стр 115-116) является теорией первого порядка
3) Если теория S непротиворечива, то в ней существует неразрешимое предложение этой теории (стр. 161, теорема Гёделя в форме Россера)

На первый взгляд я наблюдаю противоречие: по лемме Линдбаума арифметику можно сделать полной, а по теореме Гёделя нельзя.

Со своей невысокой колокольни вижу только такое объяснение, что "расширить" арифметику до "полного" состояния в принципе можно, но только ценой добавления бесконечного числа аксиом, причём так, что теория перестанет быть эффективно аксиоматизированной. Но сам несколько туманно понимаю это объяснение и не знаю, правильное ли оно.

Прошу разъяснить этот вопрос с одной стороны в строгих терминах, с другой стороны максимально доступно. Спасибо!

[arseniiv]

Ссылка на лемму Линденбаума не сходится.

valdemir в сообщении #1140366 писал(а):

На первый взгляд я наблюдаю противоречие: по лемме Линдбаума арифметику можно сделать полной, а по теореме Гёделя нельзя.

(Раз уж вы неявно предположили, что все упоминающиеся теории непротиворечивы, продолжим это предположение на весь этот пост.) (Первая) теорема Гёделя не говорит, что $S$ нельзя сделать полной. Она говорит, что $S$ неполна и не говорит (в формулировке с указанной страницы) ничего о теориях, включающих $S$ и что-нибудь ещё. Действительно, можно просто взять аксиомами сразу все формулы, истинные в стандартной модели арифметики, и это будет полная и непротиворечивая теория, включающая $S$ (говорят, в теории моделей это вообще полезная вещь — теория любой выбранной алгебраической системы — в данном случае системы $(\mathbb N,0,',+,\cdot,=)$). И теорема Гёделя ничего против не имеет, потому что к такой теории неприменима даже в более общей формулировке ниже по тексту (а в формулировке, упомянутой ровно в том месте, она применима только к $S$).

valdemir в сообщении #1140366 писал(а):

Со своей невысокой колокольни вижу только такое объяснение, что "расширить" арифметику до "полного" состояния в принципе можно, но только ценой добавления бесконечного числа аксиом, причём так, что теория перестанет быть эффективно аксиоматизированной.

Ну, это действительно написано дальше по тексту после приведения более общей формулировки теоремы. Но вообще это не относится к опровержению мнимомго противоречия в 1—3.

[valdemir]

Спасибо! А почему теорема Гёделя (в самой широкой формулировке) не применима к упомянутому Вами случаю "взять аксиомами сразу все формулы, истинные в стандартной модели арифметики, и это будет полная и непротиворечивая теория, включающая $S$"? Из-за неэффективной (нерекурсивной) аксиоматизированности?

[arseniiv]

Следствие 3.34 не оставляет места для сомнений. Непротиворечивость есть по определению, расширением $S$ теория являеся. Остаётся рекурсивная аксиоматизируемость — ей придётся уступить.