Перечислимое множество
Материал из Википедии — свободной encyclopedia
Перечисли́мое мно́жество (эффекти́вно перечислимое, рекурси́вно перечислимое, полуразреши́мое множество[1]) — множество конструктивных объектов (например, натуральных чисел), все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называется корекурсивно перечислимым[2]. Всякое перечислимое множество является арифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню арифметической иерархии[англ.], а корекурсивно перечислимые — уровню
Всякое разрешимое множество является перечислимым.[источник не указан 1349 дней] Перечислимое множество является разрешимым тогда и только тогда, когда его дополнение также перечислимо. Другими словами, множество является разрешимым в том и только том случае, когда оно и перечислимо, и корекурсивно перечислимо. Подмножество перечислимого множества может не быть перечислимым (и даже может не быть арифметическим).
Совокупность всех перечислимых подмножеств является счётным множеством, а совокупность всех неперечислимых подмножеств — несчётным.