Семинар Добрушинской математической лаборатории ИППИ РАН
19 сентября, вторник, 16:00, ауд. 615 (очно и без трансляции).
В. Кановей, В. Любецкий: Решение проблемы (1948 год) А. Тарского
Аннотация.
Будет изложено полученное докладчиками (2022 год) решение старой
проблемы Тарского о минимальной сложности описания множества D
вещественных чисел, которое состоит из чисел, определяемых формулами
сложности не больше n – любого натурального числа. Тарский доказал: D
описывается формулой сложности n+1 и эта оценка не улучшаема в одной
из моделей. Он поставил вопрос: всегда ли оценка не улучшаема или
существует модель, в которой оценка улучшаема хотя бы до n. Нами
построена модель, в которой оценка улучшаема до 1, т.е. D описывается
формулой сложности 1. Сложность формулы понимается как наибольший тип
переменной в ней. Более того, для любого разрешимого множества U
натуральных чисел нами построена модель, в которой для n из U
множество D описывается формулой сложности не больше n, а для любого n
не из U, наоборот, описание D формулой сложности n+1 не улучшаемо.
| 13.09.2023 | Комеч Сергей Александрович |