RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ЛОМИ, 1974, том 40, страницы 101–109 (Mi znsl2685)

Гейтинговское исчисление предикатов с эпсилон-символом

Г. Е. Минц


Аннотация: Известно, что добавление к гейтинговскому исчислению предикатов $\varepsilon$-символа с $\varepsilon$-аксиомам $A[t]\to A[\varepsilon x A]$ дает неконсервативное расширение. Например, становится выводимой формула
$$ \exists x(\rceil P_x\to\rceil Pb\&\rceil Pa). $$
Консервативное расширение получается, если рассматривать $\varepsilon$-символ по аналогии с $\iota$-символом: для любого вхождения символа $\varepsilon x A[x,\alpha_1,\dots,\alpha_n]$ в некоторую секвенцию из данного вывода в антецедент этой секвенции должна входить формула $\forall\alpha_1\dots\forall\alpha_n\exists x A$. Для получающейся системы $HPC^{\varepsilon}$ доказывается устранимость сечения. Указывается, что доказательство допускает обобщение на $HPC$ с разрешимым равенством, на гейтинговскую арифметику со свободными функциональными переменными и принципом выбора:
$$ \Gamma\to\forall x\exists y A;\quad\forall x A_y[f(x)],\quad\Gamma\to C\vdash\Gamma\to C. $$
Распространение на гейтинговскую арифметику со связанными переменными более высоких типов и соответствующими принципами выбора требует привлечения новых идей.

УДК: 51.01



Реферативные базы данных:


© МИАН, 2024