Трансфинитные развертки арифметических формул
Г. Е. Минц
Аннотация:
Рассматривается трансфинитная итерация вынесения вперед классического существования
$\rceil\forall x\rceil$ (обозначаемого через
$\underset{\dot{}}\exists x$) в виде конструктивной осуществимости
$(\underset{\dot{}}\exists x)$ по схеме:
$$
\underset{\dot{}}\exists x Ax\leftrightarrow\exists y(\underset{\dot{}}\exists x Ax\underset{\dot{}}\vee Ay).
$$
Эта идея была высказана Н. А. Шаниным, который использовал ее для определения мажорант арифметических формул. Для любой отрицательной формулы
$F$ развертка
$F_\alpha$ (трансфинитного) ранга
$\alpha$ определяется как результат
$\alpha$-кратного вынесения кванторов
$\exists$,
$\forall$ по описанной выше схеме и сохранения в конце только бескванторных дизъюнктивных членов. Доказано, что конструктивная истинность
$F_\alpha$ эквивалентна существованию рекурсивного бесконечного вывода формулы
$F$ (по классическим правилам) высоты
$\alpha$. Это позволяет доказать, что
$F_\alpha$ является дизъюнктивной интерпретацией классической арифметики.
Указана модефикация разверток
$F_\alpha$, эквивалентная мажорантам по Н. А. Шанину. Библ. – 8 назв.
УДК:
51.01:164