Isomorphism Types of Rogers Semilattices in the Analytical Hierarchy

2023

Полный текст Открытый доступ: Green Метаданные (CSL-JSON)
DOI 10.1142/9789811278631_0004
Достоверность данных 70 средняя
Как считается эта оценка

Складывается из проверяемых признаков самой записи: есть ли у статьи DOI, сколько независимых источников подтвердили её данные, заполнены ли обязательные поля и насколько свежо последнее подтверждение. Снижают оценку расхождения между источниками и отсутствие идентификатора. Значение от 80 означает, что запись опубликована без дополнительной проверки; от 60 до 79 — что она опубликована с пониженной достоверностью и ручная проверка желательна. Запись, выверенную редактором вручную, пересчёт не опускает ниже 90. Это оценка наших данных о статье, а не оценка самой статьи.

Аннотация

A numbering of a countable family $S$ is a surjective map from the set of natural numbers $ω$ onto $S$. A numbering $ν$ is reducible to a numbering $μ$ if there is an effective procedure which given a $ν$-index of an object from $S$, computes a $μ$-index for the same object. The reducibility between numberings gives rise to a class of upper semilattices, which are usually called Rogers semilattices. The paper studies Rogers semilattices for families $S \subset P(ω)$ belonging to various levels of the analytical hierarchy. We prove that for any non-zero natural numbers $m\neq n$, any non-trivial Rogers semilattice of a $Π^1_m$-computable family cannot be isomorphic to a Rogers semilattice of a $Π^1_n$-computable family. One of the key ingredients of the proof is an application of the result by Downey and Knight on degree spectra of linear orders.