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

Алгебра и логика, 1972, том 11, номер 3, страницы 243–256 (Mi al1338)

Эта публикация цитируется в 2 статьях

О дискретных классах рекурсивно перечислимых множеств

В. В. Вьюгин


Аннотация: Как известно, понятие дискретного семейства множеств предполагает наличие некоторого, класса конечных множеств, определенным образом связанного с исходным семейством. Если этот класс предположить строго вычислимым, получим определение эффективно дискретного семейства (финитно разделяющегося по А. И. Мальцеву). Назовем семейство слабо эффективно дискретным, если указанный класс конечных множеств вычислим. В заметке доказывается, что всякий вычислимый слабо эффективно дискретный класс имеет позитивную нумерацию, строится пример вычислимого дискретного, но не слабо эффективно дискретного класса, обладающего позитивной нумерацией. В заключение доказывается, что минимальная нумерация бесконечного дискретного семейства перечислимых множеств эквивалентна нумерации, в которой каждое конечное множество имеет конечное множество номеров.

УДК: 517.11:518.5

Поступило: 17.02.1972



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


© МИАН, 2025