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

Question

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

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

0

23.10.2024

10 ответов

33 просмотра

Alexander Chichigin

Стикер

0

6 месяцев назад

пільнуй сабаку Автор вопроса

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

0

6 месяцев назад

Alexander Chichigin

пільнуй сабаку
да, но если я хочу аксиоматически описать какие-то...

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

0

6 месяцев назад

Rust Skye

йо привет! если я правильно понял вопрос, то вроде нет (для модальных логик по крайней мере). часто отсутствие финитной и рекурсивной аксиоматизаций показывается редукцией от сигма^1_1 проблемы типа тайлинга с особой тайл, которая появляется бесконечно много в первом ряду. если в языке L1 мы делаем такую редукцию, т.е. находим формулу которая сатисфайбл ифф можно покрыть пространство с данными тайлами, то в более экспрессивном языке L2 будет эквивалентная формула

0

6 месяцев назад

пільнуй сабаку Автор вопроса

Rust Skye
йо привет! если я правильно понял вопрос, то вроде...

спасибо! А можешь мб назвать какую-нибудь статью, где это доказательство через редукцию к сигма^1_1 проделано? Хочу в детали вчитаться, был бы очень благодарен)

0

6 месяцев назад

Rust Skye

пільнуй сабаку
спасибо! А можешь мб назвать какую-нибудь статью, ...

ты как с эпистемной логикой? есть моя статья, я могу там в деталях подсказать

0

6 месяцев назад

пільнуй сабаку Автор вопроса

Rust Skye
ты как с эпистемной логикой? есть моя статья, я мо...

Самое то

0

6 месяцев назад