Проблема неполноты арифметики

[migmit]

ewert в сообщении #505984 писал(а):

migmit в сообщении #505941 писал(а):

метатеорем — больше.

А что они дадут для сельского хозяйства?...

Так мы про математику или про сельское хозяйство?
"Я ей про высший матерьял - она мне про соседа".

[epros]

Nobody85 в сообщении #505893 писал(а):

Является ли неполнота арифметики существенной математической проблемой, или это проблема, скорее, философии науки?

Трудно сказать, является ли проблемой математики или философии то, что математикам приходится отличать "истинность" от "доказуемости" - ибо в силу закона исключённого третьего любое утверждение либо истинно, либо ложно, а в силу теоремы о неполноте про "доказуемость или опровержимость" сказать того же нельзя.

Mega Sirius12 в сообщении #506013 писал(а):

и че-возьмем арифметику бесконечномерного порядка и докажет в ней все утверждения

Теорема о неполноте утверждает, что ЛЮБАЯ непротиворечивая теория, которая умеет разлагать натуральные числа на простые сомножители, является неполной.

-- Пн ноя 21, 2011 14:04:04 --

P.S. таким образом, арифметика второго порядка тоже неполна, хотя теорему Гудстейна она и доказывает.

[Portnov]

epros в сообщении #506115 писал(а):

ибо в силу закона исключённого третьего…

Ну, как мы знаем, (многие) современные логики этот закон не признают, так что всё ОК ;)

[Someone]

Portnov в сообщении #506134 писал(а):

так что всё ОК

Что "всё"?

[Portnov]

Ну, понятие истинности, таким образом, получается вполне сопоставимым с понятием доказуемости: неверно ни то, что «любое высказывание либо истино, либо нет», ни то, что «любое высказывание либо доказуемо, либо нет» :)

[epros]

Portnov в сообщении #506151 писал(а):

... ни то, что «любое высказывание либо доказуемо, либо нет»

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

[Nobody85]

Да что мы всё о неполноте да о неполноте! Давайте и о непротиворечивости поговорим :) И вообще, насколько важно найти решение второй проблемы Гильберта (непротиворечивость формальной арифметики)?

[epros]

Nobody85 в сообщении #506162 писал(а):

Да что мы всё о неполноте да о неполноте!

Вроде Вы начали?

Nobody85 в сообщении #506162 писал(а):

Давайте и о непротиворечивости поговорим :) И вообще, насколько важно найти решение второй проблемы Гильберта (непротиворечивость формальной арифметики)?

Непротиворечивость арифметики первого порядка вроде доказывается арифметикой второго порядка. Такое "решение проблемы" Вас устроит? Разумеется, если противоречива сама арифметика второго порядка, то грош цена такому доказательству.

[Nobody85]

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

[Someone]

Настолько, насколько вообще можно считать относительное доказательство непротиворечивости решением проблемы. Фактически, проблема переносится на другую теорию.

[Nobody85]

А какие могут быть способы обеднения арифметики так, чтобы она стала полной, и при этом всё равно была достаточно богатой для практических приложений? Можно, конечно, выкинуть операцию умножения или сделать множество натуральных чисел конечным, но математики от такой арифметики вряд ли будут в восторге:)

[Portnov]

Ну, если, для разнообразия, взять опыт у computer scientists-ов, то нужно такие (полные и/или непротиворечивые) теории применять «по месту» (как применяются упомянутые выше языки TotalFP). Т.е. вот в определённом месте нам нужна полнота — берём полную теорию (жертвуя в этом месте тем, что не обязательно — например, то же умножение не нужно, если теорема у нас про сложение). А всё остальное делать в обыкновенной теории.

[epros]

Nobody85 в сообщении #506394 писал(а):

А какие могут быть способы обеднения арифметики так, чтобы она стала полной, и при этом всё равно была достаточно богатой для практических приложений? Можно, конечно, выкинуть операцию умножения или сделать множество натуральных чисел конечным, но математики от такой арифметики вряд ли будут в восторге:)

Что значит "достаточно богатой для практических приложений"? Арифметика Пресбургера является полной (и даже - алгоритмически разрешимой). Она достаточно богата для практических приложений (с учётом того, что, например, общая формула умножения в ней невыразима)?

Вообще, зачем Вам полнота теории? Она всего лишь означает, что язык теории достаточно беден - на нём нельзя сформулировать ничего такого, что неразрешимо в данной аксиоматике. Или Вы надеетесь построить "теорию всего", которая знает ответы на все вопросы? По-моему, нормальная теория и не должна знать ответы на какие-то вопросы - на те, что вне сферы её компетенции.

[Nobody85]

Объясните, пожалуйста, что такое арифметика второго (и вообще, n-ного) порядка? Это связано с логикой второго и высших порядков?
P.S. Извините за невежество

[epros]

Nobody85 в сообщении #506587 писал(а):

Объясните, пожалуйста, что такое арифметика второго (и вообще, n-ного) порядка? Это связано с логикой второго и высших порядков?

Да, связано. Арифметика Пеано первого порядка (потому что есть и другие арифметики первого порядка) - это наиболее полная арифметика натуральных чисел, записанная в языке исчисления предикатов первого порядка. Арифметика второго порядка потребовалась потому, что в языке первого порядка не нашлось адекватной формулировки для аксиомы индукции. Сам Пеано, после того, как определил натуральные числа как последователи единицы, сформулировал аксиому индукции так: "Других натуральных чисел нет". Аксиома индукции в языке исчисления предикатов второго порядка формализуется так: "Любое множество, содержащее нуль и все его последователи, содержит все натуральные числа". Увы, в языке исчисления предикатов первого порядка допускается квантификация только по объектам теории, но не по множествам объектов. Поэтому в арифметике первого порядка аксиома индукции была заменена схемой аксиом: Для каждой формулы арифметики есть аксиома, что "если формула верна для нуля и всех его последователей, то она верна для любого натурального числа".

К сожалению, схема индукции первого порядка - это не то же самое, что аксиома индукции второго порядка.