Полнота теорий высших порядков

[enko]

Имеет ли место полнота теорий высших порядков в отличии от неполноты теории первого порядка (т.Гёделя)

[AGu]

В определенном смысле -- да, имеет. Например, арифметика Пеано второго порядка полна: в ней доказуемы те и только те предложения второго порядка, которые истинны в $\mathbb N$. В этом смысле аналога теоремы Гёделя для теорий второго порядка нет.

Источник: Дж. Булос, Р. Джеффри. Вычислимость и логика. М: Мир, 1994. (Параграф 18.)

[enko]

А формула, утверждающая непротиворечивость теории второго порядка, является выводимой в ней? (аналог второй т.Гёделя).

Я еще не совсем понял чем отличается теория первого порядка, о второго и высших. Вообще насколько применимы эти теории к реальном моделям познания и к обоснованию математики, в частности.

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

AGu писал(а):

В определенном смысле -- да, имеет. Например, арифметика Пеано второго порядка полна: в ней доказуемы те и только те предложения второго порядка, которые истинны в $\mathbb N$. В этом смысле аналога теоремы Гёделя для теорий второго порядка нет.

Источник: Дж. Булос, Р. Джеффри. Вычислимость и логика. М: Мир, 1994. (Параграф 18.)

???

Что-то Вы не так поняли, похоже.

Если фиксировано конечное число схем правил вывода и перечислимое множество аксиом, то множество выводимых предложений теории получается рекурсивно перечислимым. А множество истинных предложений арифметики не то что не перечислимо, а вообще не является арифметическим. Так что не может тут быть никакой "полноты".

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

[enko]

Цитата:

Надо заметить, что топикстартер, по ходу, нифига не шарит в теме

да это так - я только начал изучение этой темы.

Цитата:

Полных теорий первого порядка полно,

Это я знаю.

Цитата:

и к теореме Гёделя вопрос в той постановке, в какой он был задан, никакого отношения не имеет.

Я же спросил верны ли теоремы Гёделя для теорий второго и высших порядков. Что здесь не так?

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

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

Пока я понял так:

Задается алфавит Б и в множестве слов -- Б* алфавита выделяется подмножество "истин" -- T.

Далее в множестве Д* слов алфавита Д задается подмножество D элементы которого наз. "доказательствами"; также на множестве М содержащимся в Д* задается вычислимая функция f:М-->Б* которая имеет область значений f(M) в Б*.

Тройку (Д,D,f) наз. дедуктикой над Б.

Дедуктика (Д,D,f) называется полной относительно (Б,T) если f(D) содержит T.

Дедуктика (Д,D,f) называется непротиворечивой относительно (Б,T) если f(D) содержится в T.

Первая теорема Гёделя о неполноте в этих терминах формулируется сл.образом:
Существует такая фундаментальная пара (Б,Т), такая что не существует дедуктики над Б полной и непротиворечивой.

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

enko писал(а):

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

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

Это неверно. Контрпример --- элементарная теория арифметики, то есть множество всех предложений, истинных на натуральных числах.

Вы в своей формулировке упустили одно очень важное условие на теорию

[маткиб]

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

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

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

маткиб писал(а):

...из аксиом Пеано (второго порядка) выводятся те и только те формулы первого порядка, которые истинны в стандартной модели арифметики.

Это неверно!!!

[маткиб]

Профессор Снэйп в сообщении #155026 писал(а):

...из аксиом Пеано (второго порядка) выводятся те и только те формулы первого порядка, которые истинны в стандартной модели арифметики.



Это неверно!!!

маткиб в сообщении #154936 писал(а):

При этом под выводимостью тупо понимается логическое следование из аксиом.

А что тут не так?

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

маткиб писал(а):

А что тут не так?

А то, что не все формулы первого порядка, истинные в стандартной модели арифметики, выводятся из аксиом Пеано второго порядка.

[маткиб]

Профессор Снэйп в сообщении #155235 писал(а):

А то, что не все формулы первого порядка, истинные в стандартной модели арифметики, выводятся из аксиом Пеано второго порядка.

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

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

маткиб писал(а):

Профессор Снэйп в сообщении #155235 писал(а):

А то, что не все формулы первого порядка, истинные в стандартной модели арифметики, выводятся из аксиом Пеано второго порядка.

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

Под "выводимостью", равно как и под "логическим следованием", обычно понимают нечто другое. То, на что Вы указали, обычно называют "семантической выводимостью" или "семантическим следованием".

[AGu]

Профессор Снэйп писал(а):

AGu писал(а):

В определенном смысле -- да, имеет. Например, арифметика Пеано второго порядка полна: в ней доказуемы те и только те предложения второго порядка, которые истинны в $\mathbb N$. В этом смысле аналога теоремы Гёделя для теорий второго порядка нет.
Источник: Дж. Булос, Р. Джеффри. Вычислимость и логика. М: Мир, 1994. (Параграф 18.)

???
Что-то Вы не так поняли, похоже.

Да, я спутал "семантическую выводимость" с "доказуемостью". Виноват. (Слишком прочно во мне засела их эквивалентность, справедливая для первого порядка.)