Аннотация:
Будет продолжено обсуждение вычислительных аспектов кванторных обогащений логики $L^K_{prob}$. Точнее, речь пойдёт о получении верхних оценок для соответствующих проблем общезначимости. Будет показано, что в каждом из рассматриваемых случаев (нижние) оценки из предыдущего доклада являются точными. Для этого будут доказаны полезные аналоги теоремы Лëвенгейма–Скулема (о понижении мощности) и построены подходящие трансляции в языки арифметики второго и третьего порядков. Следует отметить, что при удалении кванторов по вещественным числам будет происходить существенное падение степени неразрешимости.
|
