RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1975, том 14, номер 5, страницы 523–532 (Mi al1486)

Двухэлементное отделимое нумерованное множество $\gamma$ с неразрешимой проблемой $P(\gamma,\gamma)$

С. Д. Денисов


Аннотация: В заметке строится рекурсивно перечислимое множество $A\subset N$, $A\neq N$, такое, что в классе $\{B/\overline{\overline{A}\times\overline{B}}\leqslant_{m}A\}$ нет элемента, наибольшего относительно $m$-сводимости (теорема $1$). Как следствие получается теорема $2$: существует вычислимая нумерация $\mu$ семейства $\{\varnothing,\{0\}\}=S$ такая, что для нумерованного множества $\gamma=\langle S,\mu\rangle$ неразрешима проблема $P(\gamma,\gamma)$.

УДК: 517.11:518.5

Поступило: 30.07.1975



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


© МИАН, 2024